c++ - 缓存友好性 std::list 与 std::vector

Question

随着 CPU 缓存越来越好，std::vector 通常优于 std::list，即使在测试 std::列表。出于这个原因，即使在我需要在容器中间删除/插入的情况下，我通常也会选择 std::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(最大化速度)编译。

第一个，RandomAccessDeletion()，生成一个随机索引并将该索引删除 10.000 次。我的假设是正确的， vector 确实比列表快很多:

Random access deletion...

Starting vector measurement...

Took 240299 μs

Starting list measurement...

Took 1368205 μs

vector 比列表快 5.6 倍。尽管我们需要在每次删除时移动 vector 中的元素，但我们很可能要感谢我们的缓存霸主，因为它的影响小于列表的查找时间，正如我们在基准测试中看到的那样。

---

然后我添加了另一个测试，在 TraversedDeletion() 中可以看到。它不使用随机位置来删除，而是在容器中间选择一个索引并将其用作基本迭代器，然后遍历容器以删除 10.000 次。

我的假设是该列表的性能仅略胜于 vector 或与 vector 一样快。

相同执行的结果:

Traversed deletion...

Starting vector measurement....

Took 195477 μs

Starting list measurement...

Took 581 μs

哇。该列表的速度大约是 336 倍。这与我的预期相差甚远。因此，在列表中出现一些缓存未命中似乎根本不重要，因为缩短列表的查找时间会更重要。

---

因此，对于角落/异常案例的性能，或者我的测试用例在某些方面存在缺陷，该列表显然仍然具有非常强大的地位？

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

有没有办法我可以更改 TraversedDeletion() 中的 vector 访问和删除，使其至少比列表更具竞争力？

---

回应@BoPersson 的评论:

vec.erase(it, it+10000) would perform a lot better than doing 10000 separate deletes.

变化:

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

收件人:

vec.erase(itr, itr + 10000);

给我:

Starting vector measurement...

Took 19 μs

这已经是一个重大的改进了。

Answer 1

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

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