STL列表性能非常糟糕

Question

假设STL列表的"push_back"和"pop_front"方法(实现为双链表)应该是常量O(1).但是我们在linux上运行的应用程序中遇到了cpu问题,我们发现使用列表时"pop_front"方法效率极低.这是列表实现问题还是预期的行为？

这是示例代码:

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;
}

对于不同数量的节点,我们得到:

5000个节点:

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个节点:

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个节点:

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

谢谢!

维森特

Answer 1

如果要检查容器是否!c.empty()为非空,则应使用,而不是c.size() > 0.

这对于特别重要std::list,因为在一些实现中,size是线性时间操作,而不是恒定时间操作.

(尽管正如vsoftco在评论中指出的那样,C++ 11强化了size它实际上是不变的要求- 如果你有一个兼容的编译器/库,你可以尝试启用选项来编译该标准或更高版本)