STL list is very poor

Question

It was assumed that the push_back and pop_front methods of the STL list (implemented as a double linked list) should be O (1) constant. However, we had processor problems in an application running on Linux, and we found that the pop_front method is incredibly inefficient when using lists. Is this a list implementation problem or is the expected behavior?

This is a sample code:

class A { public: A() { mA = rand(); mB = rand(); mC = rand(); mD = rand(); } u32 mA; u32 mB; u32 mC; u32 mD; }; #define DELTA(t1, t0) ((t1.tv_sec - t0.tv_sec)*1000 + ((t1.tv_usec - t0.tv_usec)/1000)) int main(int argc, char* argv[]) { std::list<A> l; std::queue<A> q; std::deque<A> dq; printf("Creating nodes..."); std::vector<A> v; for (int i = 0; i < 100000; ++i) { A a; v.push_back(a); } printf("OK\n"); timeval t0, t1; printf("std::deque test: push back..."); gettimeofday(&t0, NULL); for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) { dq.push_back(*iter); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), dq.size()); printf("std::deque test: pop front..."); gettimeofday(&t0, NULL); while (dq.size() > 0) { A a = dq.front(); dq.pop_front(); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), dq.size()); printf("std::queue test: push back..."); gettimeofday(&t0, NULL); for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) { q.push(*iter); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), q.size()); printf("std::queue test: pop front..."); gettimeofday(&t0, NULL); while (q.size() > 0) { A a = q.front(); q.pop(); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), q.size()); printf("std::list test: push back..."); gettimeofday(&t0, NULL); for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) { l.push_back(*iter); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), l.size()); printf("std::list test: pop front..."); gettimeofday(&t0, NULL); while (l.size() > 0) { A a = l.front(); l.pop_front(); } gettimeofday(&t1, NULL); printf("Done in %d ms, size = %d\n", DELTA(t1, t0), l.size()); return 0; } 

For a different number of nodes we get:

5000 knots:

 std::deque test: push back...Done in 0 ms, size = 5000 std::deque test: pop front...Done in 0 ms, size = 0 std::queue test: push back...Done in 0 ms, size = 5000 std::queue test: pop front...Done in 0 ms, size = 0 std::list test: push back...Done in 0 ms, size = 5000 std::list test: pop front...Done in 202 ms, size = 0 

10,000 knots:

 std::deque test: push back...Done in 0 ms, size = 10000 std::deque test: pop front...Done in 0 ms, size = 0 std::queue test: push back...Done in 0 ms, size = 10000 std::queue test: pop front...Done in 0 ms, size = 0 std::list test: push back...Done in 1 ms, size = 10000 std::list test: pop front...Done in 279 ms, size = 0 

100,000 nodes:

 std::deque test: push back...Done in 5 ms, size = 100000 std::deque test: pop front...Done in 4 ms, size = 0 std::queue test: push back...Done in 3 ms, size = 100000 std::queue test: pop front...Done in 4 ms, size = 0 std::list test: push back...Done in 12 ms, size = 100000 std::list test: pop front...Done in 31148 ms, size = 0 

Thanks!

Vicente

Answer 1

If you want to check if the container is not empty, you should use !c.empty() , not c.size() > 0 .

This is especially important for std::list , because in some implementations size is a linear time operation, not a constant time operation.

(although, as vsoftco points out in the comments, C ++ 11 reinforces the requirement for size that it really is constant - if you have a compatible compiler / library, you can try turning on the compilation options for this with a standard or later)

Answer 2

So, here is some practical answer: your tests are just wrong.

First of all, your code is badly written in C ++ 03, and it uses the evil C functions inside. you should use a random C ++ 11 generator, chrono functions, and a C ++ 11 style loop cycle. Only then can a C ++ developer really talk about your code.

Secondly, 5000 elements is too small a number to actually conclude anything. try a larger number, like 1'000'000, and do the same test many times inside the loop. only then can you see the difference between the various containers.

Thirdly, I doubt that gettimeofday is actually accurate enough to measure this type of test, you definitely need to use some of the chrono C ++ 11 functions, or at least use the rdtsc command on Linux.

Fourth, you need to isolate your tests. one test test all of your container is installed incorrectly. one test can cause the cache to fill up with hot data, and the test that comes after that just uses that hot data with a false performance boost. use different tests for different containers.

Finally, I agree that, generally speaking, the linked list is not the fastest container ever made. complexity is the kind of leader when it comes to speeding up your code. complexity is the mathematical limit. it does not take into account the real processor architectures and simply assumes that everything is a fundamental step, which is wrong.

In a typical C ++ application, the main two performance factors are:

• Cache (linked list is terrible)
• the number of allocations / deallocations (the linked list is terrible at the same time)

The list is very poor in performance due to these two reasons. you do not spread the data tightly, which leads to numerous cache errors, and also leads to the fact that the application leads to many small memory allocations, one of the weaknesses in C ++.