Универсальная функция remove () против функции-члена remove () для связанного списка

Я читаю книгу «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 Environment. Вот мой импровизированный код:

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 

Не могли бы вы объяснить, в чем может быть причина такого противоречивого поведения?

Производительность, вероятно, не самая подходящая причина в этом сценарии; а) потому что это, вероятно, неправильно и б) потому что производительность std::list в любом случае заведомо низкая (конечно, в зависимости от варианта использования). Что звучит более уместно, так это то, что один подход делает недействительными указатели и ссылки на элементы, которые вы не удаляете, а другой - нет. И в конце концов, такие гарантии обычно являются причиной использования связного списка для начала.

Baum mit Augen 31.10.2018 14:12
int очень маленькие и их легко копировать. Разница между этими двумя методами может быть разной, если копирование значений обходится дороже, чем просто разъединение узлов.
Blastfurnace 31.10.2018 14:21

@Blastfurnace Значения обычно не копируются, а только меняются местами. Обычно это тоже очень дешево. Особенно по сравнению с обходом по списку.

Baum mit Augen 31.10.2018 14:23

Вы измеряли производительность в отладочной или оптимизированной сборке?

Max Langhof 31.10.2018 14:25

@BaummitAugen Я не думаю, что std::remove меняет местами значения (они могут быть перемещены).

Blastfurnace 31.10.2018 14:25

@Blastfurnace Верно, только переезд назначает. Тем не менее, суть остается в силе.

Baum mit Augen 31.10.2018 14:27

@BaummitAugen Функция-член работает быстрее, когда копирование типа стоит дорого: coliru.stacked-crooked.com/a/efcf94fde4887777

Blastfurnace 31.10.2018 14:44

@Blastfurnace Конечно. Как я уже сказал, это дешево на обычно. Если по какой-либо причине у вас есть список этих больших объектов, различные факторы, безусловно, могут стать важными или даже доминирующими в каждом отдельном случае. Обратите внимание, как в исходном примере действительно используется int, и при этом по-прежнему применяется заявленная производительность.

Baum mit Augen 31.10.2018 14:48
0
8
59
1

Ответы 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

Вот мой код с закомментированным одним из push-уведомлений.

#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-килобайтный кэш L1 будет загрязнен, и производительность упадет для этого запуска.

Я просто закомментировал my_list1.push_back(random);. Это не позволяло коду выделять память из разных мест для разных частей списка и увеличивало эффективность кэширования.

Gardener 31.10.2018 14:37

По мере того, как я увеличиваю x, эффективность стирания увеличивается и превосходит удаление, но кеширование по-прежнему имеет большой эффект.

Gardener 31.10.2018 14:40

Умножив x на 8, а затем переключив порядок стирания на первое, а удаление на второе, я получаю время выполнения стирания 617 и удаления 689. Помните, что в оригинале операции удаления были «быстрее». тестовое задание. Однако попыток запустить второй удаляет не было. Если запустить вторую операцию удаления и удалить переднюю и заднюю вставки, удаление будет медленнее.

Gardener 31.10.2018 14:43

Если вы не верите, что это может быть проблема кеширования, вам нужно посмотреть это: Скотт Майерс о кэшировании

Gardener 31.10.2018 14:45

Другие вопросы по теме