Skip to main content
GameDev.net gamedev.net
🔒 Locked

Linked lists are slow?

Started by nullsquared Jan 20, 2010 at 2:54 PM 11 replies 3.2k views
Original Post
nullsquared
nullsquared
Consider this code: 

#include <iostream>
#include <list>
#include <vector>

int main()
{
    std::list<int> nums;
    for (int i = 0; i < 1000; ++i)
    {
        nums.clear();
        for (int j = 0; j < 5000; ++j)
        {
            nums.push_back(j);
        }
    }
}
Executing it results in a noticeable pause (about 2-3 seconds). Now, replace std::list with std::vector. No other changes. The resulting executable executes and finishes instantly. I noticed this while messing around in school with Code::Blocks and GCC 4.4 on my USB, and I just confirmed it with MSVC 2008 Pro. Call me stupid, but I cannot grasp what is going on here. I thought std::list::push_back was O(1)? In fact, I rolled my own implementation just to be sure: 

// custom test list
namespace detail
{
template <typename T>
class list
{
    private:
        struct node
        {
            T val;
            node(const T &val): val(val), next(NULL) {}
            node *next;
        };
        node *_head, *_tail;

    public:
        list(): _head(NULL), _tail(NULL) {}
        ~list() { clear(); }

        void push_back(const T &val)
        {
            node *n = new node(val);
            if (!_tail)
                _head = _tail = n;
            else
            {
                _tail->next = n;
                _tail = n;
            }
        }

        void clear()
        {
            node *n = _head;
            while (n)
            {
                node *old = n;
                n = n->next;
                delete old;
            }
            _head = _tail = NULL;
        }
};
}
Once again, same slowness... (removing the call to clear() every iteration doesn't change anything at all regarding the speed) I'm a bit baffled. Is it because std::vector::push_back is essentially O(1) if capacity() > size()? Even so, list::push_back is always O(1), it's essentially an allocation and an assignment - is it the memory allocation that is tripping it up?
Crazyfool
Crazyfool
I am not really sure but I think these kinds of tests often dont give clear results as to what is causing the problem [edit: slowness].

I don't use lists that often because they don't provide random access, I much prefer deques.
Rycross
Rycross
Off the top of my head, vector would be more cache-friendly than list, and wouldn't require dynamic allocation of nodes on every push_back (and subsequent de-allocation on clear). For vector, re-allocation of memory is amortized, and the code produced would likely only resize on the outer loop's first pass, meaning 1 <= i < 1000 is going to be a good deal more performant.

Edit: To help ease your confusion, all O(1) tells you is that if you have n items in your list, then it will take roughly the same amount of time to add an item as the case where you have only 1 item in that list. It doesn't tell you how long it takes you to add that one item.
rip-off
rip-off
Dynamic allocation would almost certainly be a culprit. Have you tried using a pooled allocator with std::list<> (I believe boost provides drop-in replacements)?
blog | twitter
KulSeran
KulSeran
nums.clear(); on a list is going to free all the elements in a std::list.
it doesn't clear the elements in a std::vector. Thus, after the first loop, std::vector does not do any memory allocation. std::list still does. That is likely the speedup you are seeing.
owl
owl
Yes. Calling the clear() method on the list 1000 times was the first thing I spoted as a kind of crazy thing to do.
[size="2"]I like the Walrus best.
Bregma
Bregma
Quote:
Original post by nullsquared
Call me stupid, but I cannot grasp what is going on here. I thought std::list::push_back was O(1)?

Indeed, push_back() on both containers is O(1). Where your understanding breaks down is the meaning of O(1). O(1) is not a number. It is a growth characteristic. It does not describe how fast an algorithm is but rather the second-degree characteristic of how much less fast the algorithm becomes as the size of the input grows.

The complexity of std::list is more along the lines of "push_back() is slower than for std::vector over amortized use." That's about as strict as you're going to get.
Stephen M. Webb
Professional Free Software Developer
Zahlman
Zahlman
Quote:
Original post by KulSeran
nums.clear(); on a list is going to free all the elements in a std::list.
it doesn't clear the elements in a std::vector. Thus, after the first loop, std::vector does not do any memory allocation. std::list still does. That is likely the speedup you are seeing.


Nit: std::vector.clear() will call destructors for the cleared elements (which happens to do nothing for primitive types; thus, good implementations will specialize for primitive types to skip this step completely instead of repeatedly calling an empty function), but it won't deallocate memory. Deallocating memory isn't particularly slow, but this also means that on each subsequent iteration of the outer loop, the code with the vector won't have to re-allocate the memory (which is generally pretty slow); it will just reuse its old capacity.
Antheus
Antheus
Vector retains capacity, so it will only need to perform a total of ~6 calls to new/malloc/allocator. All other operations will be sequential single writes (+ update of count), almost entirely via L1 cache.

List needs to perform 1 allocation per element (5 million alloc/deallocs), 3 writes (value, next, tail) and accesses memory non sequentially.

vector usually resizes by doubling the size, so even without clearing, vector will need to be resized some log2(5000000) 22 times. List will always need to allocate 5 million elements.


As a rule of thumb, linked lists are slow if implemented this way. It is often worth considering implementing them in-place:
std::vector< std::pair<T, int> >
, where the int parameter is index of next element. This retains the algorithmic complexity, but considerably reduces overhead. Also notice that vector can be resized without breaking the list. It does however reallocate individual elements. Instead, if pointers to elements are desirable, index can be used. Final benefit of this list is that it allows fast unordered traversal (just iterate over vector).
nullsquared
nullsquared
Ok cool thanks guys, I had a hunch that was the issue but I wasn't quite sure [smile]

BTW,
Quote:
Yes. Calling the clear() method on the list 1000 times was the first thing I spoted as a kind of crazy thing to do.

I actually removed this call and the performance didn't alter much
Quote:
(removing the call to clear() every iteration doesn't change anything at all regarding the speed)
Kylotan
Kylotan
Apart from the memory allocation issue, has anybody considered that the vector version might actually be doing nothing at all? It would be far easier for the compiler to work out that the underlying vector is never accessed than it would to work out that none of the list nodes are being referenced.

After all, if the original poster is compiling without optimisations, it leaves all kind of debugging information in there which can make structures arbitrarily slow. And if he is compiling with optimisations, the compiler can remove anything it considers pointless.

Try adding random numbers to the structure, then iterating over it once and adding them all up, and output that to standard input. That should stop it optimising anything away.
Antheus
Antheus
Quote:
Original post by Kylotan
has anybody considered that the vector version might actually be doing nothing at all?


Yes.

#include <iostream>#include <list>#include <vector>#include <boost/timer.hpp>template <typename T>class list{public:        struct node        {            T val;            node(const T &val): val(val), next(NULL) {}			node() : val(0), next(NULL) {}            node *next;        };        node *_head, *_tail;        list(): _head(NULL), _tail(NULL), prealloc(10000), offset(0) {}        ~list() { clear(); }        void push_back(const T &val)        {			node * n = &prealloc[offset++];			n->val = val;            if (!_tail)                _head = _tail = n;            else            {                _tail->next = n;                _tail = n;            }        }		node * begin() {			return _head;		}        void clear()        {            _head = _tail = NULL;			offset = 0;        }private:	int offset;	std::vector<node> prealloc;};int main(){	srand(1234);    std::list<int> numl;	boost::timer t1;    for (int i = 0; i < 1000; ++i)    {        numl.clear();        for (int j = 0; j < 5000; ++j)        {            numl.push_back(j);        }    }	double t1e = t1.elapsed();	std::list<int>::iterator i = numl.begin();	std::advance(i, rand() % 100);	std::cout << t1e << " " << (*i) << std::endl;	srand(1234);    list<int> numl2;	boost::timer t3;    for (int i = 0; i < 1000; ++i)    {        numl2.clear();        for (int j = 0; j < 5000; ++j)        {            numl2.push_back(j);        }    }	double t3e = t3.elapsed();	list<int>::node * curr = numl2.begin();	int n = rand() % 100;	for (int i = 0; i < n; i++) curr =  curr->next;	std::cout << t3e << " " << curr->val << std::endl;	srand(1234);	std::vector<int> numv;	boost::timer t2;    for (int i = 0; i < 1000; ++i)    {        numv.clear();        for (int j = 0; j < 5000; ++j)        {            numv.push_back(j);        }    }	std::cout << t2.elapsed() << " " << numv[rand() % 100] << std::endl;}


Quote:
0.97 68 // std::list
0.013 68 // custom list with preallocated storage
0.022 68 // std::vector


Ad-hoc allocations for this purpose really do consume a lot of time (that is different from new itself being slow, the generic implementation of new simply isn't suited for this type of task).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.