Подтвердить что ты не робот

Кэшируемость std:: list vs std::vector

Когда кеширование процессора становится лучше и лучше std::vector обычно превосходит std::list, даже когда дело доходит до тестирования сильных сторон std::list. По этой причине даже в ситуациях, когда мне нужно удалить/вставить в середине контейнера, я обычно выбираю 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 (Maximize speed).

Первый, RandomAccessDeletion(), генерирует случайный индекс и стирает этот индекс 10.000 раз. Мои предположения были правильными, и вектор действительно намного быстрее, чем список:

Удаление случайного доступа...

Начало измерения вектора...

Взял 240299 мкс

Измерение начального списка...

Взял 1368205 мкс

Вектор на 5,6 раза быстрее, чем в списке. Мы можем, скорее всего, поблагодарить наших кэшистов за это преимущество в производительности, хотя нам нужно сдвинуть элементы в векторе при каждом удалении, которое оно влияет, меньше времени поиска списка, как мы можем видеть в тесте.

Итак, я добавил еще один тест, увиденный в TraversedDeletion(). Он не использует рандомизированные позиции для удаления, а скорее выбирает индекс в середине контейнера и использует его как базовый итератор, а затем пересекает контейнер, чтобы стереть 10.000 раз.

Мои предположения состояли в том, что список будет превосходить вектор лишь незначительно или быстро, как вектор.

Результаты для одного и того же выполнения:

Отслеживание удаления...

Начало измерения вектора....

Взял 195477 мкс

Измерение начального списка...

Взял 581 мкс

Wow. Список содержит 336x быстрее. Это действительно далеко от моих ожиданий. Таким образом, наличие нескольких промахов в списке не похоже вообще на то, что сокращение времени поиска для списка весит больше.

Итак, список, по-видимому, по-прежнему имеет очень сильную позицию, когда дело доходит до производительности для угловых/необычных случаев, или мои тестовые примеры некорректны?

Означает ли это, что список в настоящее время является лишь разумным вариантом для большого количества вставок/исключений в середине контейнера при прохождении или есть другие случаи?

Есть ли способ изменить векторный доступ и стирание в TraversedDeletion(), чтобы сделать его по меньшей мере более конкурентным по сравнению с списком?

В ответ на комментарий @BoPersson:

vec.erase(it, it+10000) будет намного лучше, чем 10000 отдельные удаления.

Изменение:

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

To:

vec.erase(itr, itr + 10000);

Дал мне:

Начало измерения вектора...

Взял 19 мкс

Это уже значительное улучшение.

4b9b3361

ОТВЕТЫ

Ответ 1

Длительная продолжительность list в RandomDeletion обусловлена ​​временем, которое требуется для перехода от начала списка к произвольно выбранному элементу, операции O (N).

TraverseDeletion просто увеличивает итератор, операцию O (1).

Ответ 2

В TraversedDeletion вы по существу делаете pop_front, но вместо того, чтобы быть впереди, вы делаете это посередине. Для связанного списка это не проблема. Удаление node является операцией O (1). К сожалению, когда вы делаете это в векторе, это операция O (N), где N - vec.end() - itr. Это связано с тем, что он должен копировать каждый элемент из точки удаления вперед по одному элементу. Поэтому в векторном случае это намного дороже.

С другой стороны, в RandomAccessDeletion вы постоянно меняете точку удаления. Это означает, что у вас есть операция O (N), чтобы пересечь список, чтобы перейти к node для удаления, и O (1), чтобы удалить node против трассировки O (1), чтобы найти элемент и O ( N) для копирования элементов в вектор вперед. Причина в том, что это не то же самое, хотя стоимость перехода от node до node имеет более высокую константу, чем требуется для копирования элементов в векторе.

Ответ 3

"Быстрая" часть о векторе "достигает" элемента, к которому необходимо получить доступ (перемещение). Фактически вы не тратите много вектора на удаление, а получаете доступ только к первому элементу. (Я бы сказал, что adavance-by-one не делает много измерений мудрыми)

Затем удаление занимает довольно много времени (O (n), поэтому при удалении каждого из них он O (n²)) из-за изменения элементов в памяти. Поскольку удаление изменяет память на местах после удалённого элемента, вы также не можете извлечь выгоду из предварительной выборки, которая также является вещью, которая делает вектор таким быстрым.

Я не уверен, насколько удаление также приведет к недействительности кэшей, поскольку память за итератором изменилась, но это также может очень сильно повлиять на производительность.

Ответ 4

В первом тесте список должен был пройти до точки удаления, а затем удалить запись. Время, затраченное на список, состояло в перемещении для каждого удаления.

Во втором тесте список просматривается один раз, а затем повторно удаляется. Время, проведенное, все еще было в обход; удаление было дешевым. За исключением того, что мы не переходим многократно.

Для вектора обход свободен. Удаление требует времени. Случайное удаление элемента занимает меньше времени, чем потребовалось, чтобы список проходил к этому случайному элементу, поэтому вектор выигрывает в первом случае.

Во втором случае вектор выполняет тяжелую работу намного много раз, чем в списке, он тяжело работает.

Но проблема заключается в том, что вы не должны трассировать и удалять из вектора. Это приемлемый способ сделать это для списка.

То, как вы пишете это для вектора, будет std::remove_if, а затем erase. Или просто одно стирание:

  auto index = vec.size() / 2;
  auto itr = vec.begin() + index;
  vec.erase(itr, itr+10000);

Или, чтобы подражать более сложному процессу принятия решений, включающему стирание элементов:

  auto index = vec.size() / 2;
  auto itr = vec.begin() + index;
  int count = 10000;
  auto last = std::remove_if( itr, vec.end(),
    [&count](auto&&){
      if (count <= 0) return false;
      --count;
      return true;
    }
  );
  vec.erase(last, vec.end());

Почти единственный случай, когда list работает быстрее, чем vector, когда вы храните итератор в list, и вы периодически стираете его или рядом с этим итератором, продолжая перемещаться по списку между этими действиями стирания.

Почти каждый другой вариант использования имеет шаблон использования vector, который соответствует или превосходит производительность list в моем опыте.

Код не всегда может быть переведен в строку-лайн, как вы показали.

Каждый раз, когда вы стираете элемент в векторе, он перемещает "хвост" вектора над 1.

Если вы удалите 10000 элементов, он перемещает "хвост" вектора более 10000 за один шаг.

Если вы remove_if, он эффективно удаляет хвост, дает вам "потерянный" остаток, и вы можете удалить отходы из вектора.

Ответ 5

Я хочу, чтобы po указывал на то, что еще не упоминается в этом вопросе:

В std::vector, когда вы удаляете элемент в середине, элементы перемещаются благодаря новой семантике перемещения. Это одна из причин, по которой первый тест принимает эту скорость, потому что вы даже не копируете элементы после удалённого итератора. Вы можете воспроизвести эксперимент с вектором и списком некопируемого типа и посмотреть, как лучше работает производительность списка (в сравнении).