c++ - 链表的通用函数 remove() 与成员函数 remove()

Question

我正在阅读 Nicolai M.Josuttis 撰写的“The C++ STL. A Tutorial and References”一书，在专门介绍 STL 算法的一章中，作者陈述如下:如果你调用 remove()列表的元素，算法不知道它正在对列表进行操作，因此会执行它的操作适用于任何容器:通过更改元素的值重新排序元素。例如，如果算法删除第一个元素后，所有后续元素都将分配给它们之前的元素。这行为与列表的主要优点相矛盾:通过插入、移动和删除元素的能力修改链接而不是值。为了避免性能不佳，列表为所有操作算法提供了特殊的成员函数。你应该总是喜欢他们。此外，这些成员函数确实删除了“已删除”的元素，如本例所示:

#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> coll;
// insert elements from 6 to 1 and 1 to 6
for (int i=1; i<=6; ++i) {
coll.push_front(i);
coll.push_back(i);
}
// remove all elements with value 3 (poor performance)
coll.erase (remove(coll.begin(),coll.end(),
3),
coll.end());
// remove all elements with value 4 (good performance)
coll.remove (4);
}

当然，这似乎足以让我进一步考虑，但无论如何，我决定在我的 PC 上查看运行类似代码的结果，尤其是在 MSVC 2013 环境中。这是我即兴创作的代码:

int main()
{
    srand(time(nullptr));
    list<int>my_list1;
    list<int>my_list2;
    int x = 2000 * 2000;

    for (auto i = 0; i < x; ++i)
    {
        auto random = rand() % 10;
        my_list1.push_back(random);
        my_list1.push_front(random);
    }

    list<int>my_list2(my_list1);

    auto started1 = std::chrono::high_resolution_clock::now();
    my_list1.remove(5);
    auto done1 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using member function remove: " << chrono::duration_cast<chrono::milliseconds>(done1 - started1).count();

    cout << endl << endl;

    auto started2 = std::chrono::high_resolution_clock::now();
    my_list2.erase(remove(my_list2.begin(), my_list2.end(),5), my_list2.end());
    auto done2 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using generic algorithm remove: " << chrono::duration_cast<chrono::milliseconds>(done2 - started2).count();

    cout << endl << endl;
}

当看到下面的输出时我很惊讶:

Execution time while using member function remove: 10773

Execution time while using generic algorithm remove: 7459 

您能否解释一下这种矛盾行为的原因是什么？

Answer 1

这是一个缓存问题。大多数性能问题都是缓存问题。我们总是认为算法是首先要看的。但是，如果您故意强制编译器在一次运行中使用来自不同位置的内存，而在下一次运行中使用所有来自下一个位置的内存，您将看到缓存问题。

通过在构建原始列表时注释掉 push_back 或 push_front，我强制编译器创建代码以在 中构建具有连续内存元素的列表my_list1.

my_list2 始终位于连续内存中，因为它是在单个拷贝中分配的。

运行输出:

Execution time while using member function remove: 121

Execution time while using generic algorithm remove: 125


Process finished with exit code 0

这是我的代码，其中一个推送被注释掉了。

#include <list>
#include <algorithm>
#include <chrono>
#include <iostream>

using namespace std;

int main()
{
    srand(time(nullptr));
    list<int>my_list1;
//    list<int>my_list2;
    int x = 2000 * 2000;

    for (auto i = 0; i < x; ++i)
    {
        auto random = rand() % 10;
//        my_list1.push_back(random);  // avoid pushing to front and back to avoid cache misses.
        my_list1.push_front(random);
    }

    list<int>my_list2(my_list1);

    auto started1 = std::chrono::high_resolution_clock::now();
    my_list1.remove(5);
    auto done1 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using member function remove: " << chrono::duration_cast<chrono::milliseconds>(done1 - started1).count();

    cout << endl << endl;

    auto started2 = std::chrono::high_resolution_clock::now();
    my_list2.erase(remove(my_list2.begin(), my_list2.end(),5), my_list2.end());
    auto done2 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using generic algorithm erase: " << chrono::duration_cast<chrono::milliseconds>(done2 - started2).count();

    cout << endl << endl;
}

通过增加元素的数量并颠倒调用顺序以使删除先发生然后删除发生，删除需要更长的时间。同样，这更多的是关于缓存，而不是关于算法或正在完成的工作量。如果您正在运行另一个会弄脏缓存、检查互联网或移动鼠标的程序，则您的 32 KB L1 缓存将被弄脏，并且该运行的性能会下降。