STL list very bad performance
c++, list, stl
Solution
If you want to check whether a container is nonempty, 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 notes in the comments, C++11 strengthens the requirement on `size` that it really is constant — if you have a compliant compiler/library, you can try enabling the options to compiling for that standard or later)
Problem
It's supposed that "push_back" and "pop_front" methods of a STL list (implemented as a double linked list) should be constant O(1). However we were having cpu issues in an application running on linux and we found that "pop_front" method is incredibly inefficient when using lists. Is this a list implementaion issue or is the expected behaviour? This is the example 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 different number of nodes we get: 5000 nodes: ``` 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 ``` 10000 nodes: ``` 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 ``` 100000 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