Общая функция remove() vs Функция-член remove () для связанного списка

Question

Я читаю книгу "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;
}

Увеличивая количество элементов и меняя порядок вызовов, чтобы сначала было выполнено удаление, а затем - удаление, удаление займет больше времени. Опять же, это больше о кешировании, чем об алгоритме или объеме выполняемой работы. Если вы запускаете другую программу, которая загрязняет кэш, проверяет Интернет или перемещает мышь, ваш кэш L1 объемом 32 КБ будет загрязнен, и производительность для этого запуска снизится.