链表的泛型函数remove()与成员函数remove)

Question

我正在阅读Nicolai m.Josuttis撰写的《C++STL教程和参考文献》一书，作者在专门讨论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);
}

当然，这似乎足以让人信服，但无论如何，我决定在我的电脑上运行类似的代码，特别是在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缓存将被弄脏，并且该运行的性能会下降。