缓存友好性std :: list vs std :: vector

Question

随着CPU缓存变得越来越好,即使在测试a的优势时也会std::vector表现出色.出于这个原因,即使在我需要删除/插入容器中间的情况下,我通常会选择,但我意识到我从未测试过这个以确保假设是正确的.所以我设置了一些测试代码:std::liststd::liststd::vector

#include <iostream>
#include <chrono>
#include <list>
#include <vector>
#include <random>

void TraversedDeletion()
{
    std::random_device dv;
    std::mt19937 mt{ dv() };
    std::uniform_int_distribution<> dis(0, 100000000);

    std::vector<int> vec;
    for (int i = 0; i < 100000; ++i)
    {
        vec.emplace_back(dis(mt));
    }

    std::list<int> lis;
    for (int i = 0; i < 100000; ++i)
    {
        lis.emplace_back(dis(mt));
    }

    {
        std::cout << "Traversed deletion...\n";
        std::cout << "Starting vector measurement...\n";

        auto now = std::chrono::system_clock::now();
        auto index = vec.size() / 2;
        auto itr = vec.begin() + index;
        for (int i = 0; i < 10000; ++i)
        {
            itr = vec.erase(itr);
        }

        std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " ?s\n";
    }

    {
        std::cout << "Starting list measurement...\n";

        auto now = std::chrono::system_clock::now();
        auto index = lis.size() / 2;
        auto itr = lis.begin();
        std::advance(itr, index);
        for (int i = 0; i < 10000; ++i)
        {
            auto it = itr;
            std::advance(itr, 1);
            lis.erase(it);
        }

        std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " ?s\n";
    }

}

void RandomAccessDeletion()
{
    std::random_device dv;
    std::mt19937 mt{ dv() };
    std::uniform_int_distribution<> dis(0, 100000000);

    std::vector<int> vec;
    for (int i = 0; i < 100000; ++i)
    {
        vec.emplace_back(dis(mt));
    }

    std::list<int> lis;
    for (int i = 0; i < 100000; ++i)
    {
        lis.emplace_back(dis(mt));
    }

    std::cout << "Random access deletion...\n";
    std::cout << "Starting vector measurement...\n";
    std::uniform_int_distribution<> vect_dist(0, vec.size() - 10000);

    auto now = std::chrono::system_clock::now();

    for (int i = 0; i < 10000; ++i)
    {
        auto rand_index = vect_dist(mt);
        auto itr = vec.begin();
        std::advance(itr, rand_index);
        vec.erase(itr);
    }

    std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " ?s\n";

    std::cout << "Starting list measurement...\n";

    now = std::chrono::system_clock::now();

    for (int i = 0; i < 10000; ++i)
    {
        auto rand_index = vect_dist(mt);
        auto itr = lis.begin();
        std::advance(itr, rand_index);
        lis.erase(itr);
    }

    std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " ?s\n";
}

int main()
{
    RandomAccessDeletion();
    TraversedDeletion();
    std::cin.get();
}

---

所有结果都是用/02 (Maximize speed).编译的.

第一个,RandomAccessDeletion()生成一个随机索引并擦除该索引10,000次.我的假设是正确的,矢量确实比列表快得多:

随机访问删除...

开始矢量测量......

花了240299μs

开始列表测量...

花了1368205μs

向量比列表快约5.6倍.我们很可能感谢我们的缓存领域的这种性能优势,即使我们需要在每次删除时移动向量中的元素,它的影响小于列表的查找时间,正如我们在基准测试中看到的那样.

---

那么我又添加了另一个测试,见于TraversedDeletion().它不使用随机位置来删除,而是在容器中间选取一个索引并将其用作基本迭代器,然后遍历容器以擦除10.000次.

我的假设是列表的性能仅略高于矢量或者与向量一样快.

执行相同的结果:

遍历删除...

开始矢量测量....

花了195477μs

开始列表测量...

花了581μs

哇.该列表快了约336倍.这与我的期望相差甚远.因此,在列表中有一些缓存未命中似乎根本不重要,因为减少列表的查找时间会更加重要.

---

因此,对于角落/异常案例的表现,该列表显然仍然具有非常强大的地位,或者我的测试案例在某种程度上存在缺陷？

这是否意味着现在的列表只是在遍历容器中间或在其他情况下在容器中间进行大量插入/删除的合理选项？

有没有办法可以改变向量访问和删除,TraversedDeletion()使其至少比列表更具竞争力？

---

回应@ BoPersson的评论:

vec.erase(it, it+10000) 比执行10000次单独删除要好得多.

更改:

for (int i = 0; i < 10000; ++i)
{
    itr = vec.erase(itr);
}

至:

vec.erase(itr, itr + 10000);

给我:

开始矢量测量......

花了19μs

这已经是一项重大改进.

Answer 1

你本质上TraversedDeletion是在做a pop_front，但你不是在前面，而是在中间做。对于链表来说这不是问题。删除节点是一个 O(1) 操作。不幸的是，当你在向量中执行此操作时，它是 O(N) 操作，其中N是vec.end() - itr。这是因为它必须将每个元素从删除点向前复制一个元素。这就是为什么它在矢量情况下要贵得多。

另一方面，RandomAccessDeletion您不断更改删除点。这意味着您有一个 O(N) 操作来遍历列表以到达要删除的节点，并且有一个 O(1) 操作来删除节点，而 O(1) 遍历来查找元素和一个 O(N) 操作来删除节点。向前复制向量中的元素。但这不一样的原因是从一个节点遍历到另一个节点的成本比复制向量中的元素所需的常数更高。