boost :: flat_map и его производительность по сравнению с map и unordered_map

В программировании общеизвестно, что расположение памяти значительно улучшает производительность из-за попаданий в кеш. Недавно я узнал, boost::flat_mapкакая реализация карты является векторной. Кажется, он не так популярен, как ваш типичный map/ unordered_mapпоэтому мне не удалось найти никаких сравнений производительности. Как он сравнивается и каковы наилучшие варианты использования?

Спасибо!

Совсем недавно я провел тест на различных структурах данных в своей компании, поэтому считаю, что мне нужно сказать пару слов. Очень сложно что-то правильно измерить.

Сравнительный анализ

В Интернете мы редко находим (если вообще когда-либо) хорошо спроектированный тест. До сегодняшнего дня я находил только тесты, которые проводились журналистским путем (довольно быстро и скрывая десятки переменных).

1) Необходимо учитывать нагрев кеша

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

По правде говоря, в реальном мире это не имеет особого смысла, потому что ваш кеш не будет теплым, и ваша операция, скорее всего, будет вызвана только один раз. Поэтому вам нужно выполнить тест с использованием RDTSC и время, которое вызывает их только один раз. Intel подготовила документ, описывающий, как использовать RDTSC (используя инструкцию cpuid для очистки конвейера и вызывая ее как минимум 3 раза в начале программы для ее стабилизации).

2) Измерение точности RDTSC

Еще рекомендую сделать так:

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

Это измеритель несоответствия, и он будет принимать минимум всех измеренных значений, чтобы время от времени не получалось -10 ** 18 (64-битные первые отрицательные значения).

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

3) параметры

Последняя проблема заключается в том, что люди обычно проверяют слишком мало вариантов сценария. На производительность контейнера влияют:

1. Распределитель
2. размер вложенного типа
3. стоимость реализации операции копирования, операции присваивания, операции перемещения, операции построения вложенного типа.
4. количество элементов в контейнере (размер задачи)
5. тип имеет тривиальные 3.-операции
6. тип - POD

Пункт 1 важен, потому что контейнеры действительно выделяют время от времени, и очень важно, выделяют ли они с помощью CRT "новый" или какую-то определенную пользователем операцию, такую ​​как выделение пула, список фрилансеров или другое ...

( для людей, интересующихся частью 1, присоединяйтесь к таинственной теме на gamedev о влиянии системного распределителя на производительность )

Пункт 2 заключается в том, что некоторые контейнеры (например, A) будут терять время на копирование материала, и чем больше тип, тем больше накладные расходы. Проблема в том, что при сравнении с другим контейнером B, A может победить B для небольших типов и проиграть для более крупных типов.

Пункт 3 такой же, как пункт 2, за исключением того, что он умножает стоимость на некоторый весовой коэффициент.

Пункт 4 - это вопрос большого O, смешанного с проблемами кеша. Некоторые контейнеры с плохой сложностью могут значительно превосходить контейнеры с низкой сложностью для небольшого количества типов (например, mapvs. vector, потому что их расположение кеша хорошее, но mapфрагментирует память). А затем в какой-то момент они проиграют, потому что ограниченный общий размер начинает «просачиваться» в основную память и вызывать промахи в кэше, плюс тот факт, что может начаться ощущаться асимптотическая сложность.

Пункт 5 касается того, что компиляторы могут исключать пустые или тривиальные вещи во время компиляции. Это может значительно оптимизировать некоторые операции, поскольку контейнеры являются шаблонными, поэтому каждый тип будет иметь свой собственный профиль производительности.

Пункт 6, как и пункт 5, POD могут извлечь выгоду из того факта, что построение копирования - это просто memcpy, и некоторые контейнеры могут иметь конкретную реализацию для этих случаев с использованием частичных специализаций шаблонов или SFINAE для выбора алгоритмов в соответствии с чертами T.

О плоской карте

Очевидно, плоская карта представляет собой отсортированную векторную оболочку, такую ​​как Loki AssocVector, но с некоторыми дополнительными модернизациями, поставляемыми с C ++ 11, использующими семантику перемещения для ускорения вставки и удаления отдельных элементов.

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

Вы думали, что, может быть, вам нужен flat_unorderedmap? что могло бы быть чем- google::sparse_mapто вроде этого - хеш-картой открытого адреса.

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

Критерий повторного хеширования в хэш-карте открытого адреса - это когда емкость превышает размер вектора корзины, умноженный на коэффициент загрузки.

Типичный коэффициент нагрузки 0.8: поэтому вам нужно позаботиться об этом, если вы можете предварительно intended_filling * (1/0.8) + epsilonизменить размер своей хеш-карты перед ее заполнением, всегда предварительно изменяйте размер до: это даст вам гарантию того, что вам никогда не придется ложно перефразировать и повторно копировать все во время заполнения.

Преимущество закрытых карт адресов ( std::unordered..) в том, что вам не нужно заботиться об этих параметрах.

Но boost::flat_mapэто упорядоченный вектор; следовательно, он всегда будет иметь асимптотическую сложность log (N), что хуже, чем хэш-карта открытого адреса (амортизированное постоянное время). Вы тоже должны это учитывать.

Результаты тестов

Это тест с использованием разных карт (с intключом и __int64/ somestructкак значением) и std::vector.

информация о проверенных типах:

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

Вставка

РЕДАКТИРОВАТЬ:

Мои предыдущие результаты включали ошибку: они фактически тестировали упорядоченную вставку, которая показала очень быстрое поведение для плоских карт.
Я оставил эти результаты позже на этой странице, потому что они интересны.
Это правильный тест:

Я проверил реализацию, здесь нет такой вещи, как отложенная сортировка, реализованная в плоских картах. Каждая вставка сортируется на лету, поэтому этот тест демонстрирует асимптотические тенденции:

map: O (N * log (N))
хэш-карты: O (N)
векторные и плоские карты: O (N * N)

Предупреждение : здесь и далее 2 теста для std::mapи оба flat_mapявляются ошибочными и фактически проверяют упорядоченную вставку (против случайной вставки для других контейнеров. Да, это сбивает с толку, извините):

Мы видим, что упорядоченная вставка приводит к обратному выталкиванию и выполняется очень быстро. Однако, судя по результатам моего теста, не нанесенным на диаграмму, я также могу сказать, что это далеко не абсолютная оптимальность для обратной вставки. При 10k элементов достигается идеальная оптимальность обратной вставки для предварительно зарезервированного вектора. Что дает нам 3 миллиона циклов; мы наблюдаем здесь 4.8M для упорядоченной вставки в flat_map(следовательно, 160% от оптимального).

Анализ: помните, что это «случайная вставка» вектора, поэтому огромный 1 миллиард циклов происходит из-за необходимости сдвигать половину (в среднем) данных вверх (один элемент на один элемент) при каждой вставке.

Случайный поиск из 3 элементов (часы перенормированы на 1)

по размеру = 100

по размеру = 10000

Итерация

размер больше 100 (только тип MediumPod)

больше 10000 (только тип MediumPod)

Конечная соль

В конце концов, я хотел вернуться к «Бенчмаркингу §3 Pt1» (системному распределителю). В недавнем эксперименте, который я проводил вокруг производительности разработанной мной хэш-карты открытых адресов , я измерил разрыв в производительности более 3000% между Windows 7 и Windows 8 в некоторых std::unordered_mapслучаях использования ( обсуждаемых здесь ).
Что заставляет меня предупредить читателя о приведенных выше результатах (они были сделаны на Win7): ваш опыт может отличаться.

наилучшие пожелания

Из документации кажется, что это аналог, Loki::AssocVectorкоторым я довольно много пользуюсь. Поскольку он основан на векторе, он имеет характеристики вектора, а именно:

• Итераторы становятся недействительными при sizeвыходе за пределы capacity.
• Когда он выходит за пределы, capacityнеобходимо перераспределять и перемещать объекты, то есть вставка не гарантирует постоянного времени, за исключением особого случая вставки в, endкогдаcapacity > size
• Поиск выполняется быстрее, чем std::mapиз-за расположения кеша, двоичный поиск, который имеет те же характеристики производительности, что и в std::mapпротивном случае
• Использует меньше памяти, потому что это не связанное двоичное дерево
• Он никогда не сжимается, если вы не укажете ему принудительно (поскольку это вызывает перераспределение)

Лучше всего использовать, когда вы знаете количество элементов заранее (чтобы вы могли reserveзаранее) или когда вставка / удаление редко, но поиск выполняется часто. Аннулирование итератора делает его немного громоздким в некоторых случаях использования, поэтому они не взаимозаменяемы с точки зрения корректности программы.