В этом посте обсуждается эффективность поиска элемента в контейнерах STL C ++ 11 фиксированного размера с небольшим количеством элементов.
Сложность поиска элемента в std::vector
с помощью линейного поиска составляет O (N). Это O (log N) для std::map
и O (1) для std::unordered_map
. Однако обозначение сложности игнорирует постоянные множители. Различные контейнеры имеют разные накладные расходы на обход для поиска элемента. Например, ветвление узла во время обхода дерева в std::set
и сложность хеширования в std::unordered_set
считаются постоянными накладными расходами по сложности. С другой стороны, хотя сложность std::vector
линейна, адреса памяти элементов в std::vector
непрерывны, что означает более быстрый доступ к элементам по порядку.
Поэтому первая идея, которая мне приходит в голову, - это использовать
std::vector
для повышения производительности поиска.
Чтобы доказать это и удовлетворить свое любопытство, я провел несколько экспериментов, чтобы проверить скорость поиска упомянутых контейнеров STL. Обратите внимание, что этот эксперимент не предназначен для получения определенного количества элементов для каждого контейнера с наилучшей производительностью.
Коды можно найти по адресу https://gist.github.com/gx578007/836e3ba0069d1570086b0a4c114dca31
Среда:
- Процессор: Intel (R) Core (TM) i5–3337U CPU @ 1,80 ГГц
- ОС: 64-битная Ubuntu 14.04
- Компилятор: gcc-4.8.4
- Параметры компиляции: -O3 -std = c ++ 11
- Строка кэша: 64 байта Инициализация
Каждый контейнер инициализируется n
элементами следующими способами. Это разовая работа. Процесс поиска элемента будет повторяться десять миллионов раз для инициализированных контейнеров. Функция rand64()
реализована для генерации случайного 64-битного целого числа без знака.
- std :: vector ‹uint64_t›
std::vector<uint64_t> c; for (int i=0; i<n; i++) c.push_back(rand64());
2. std :: set ‹uint64_t›
std::set<uint64_t> c; for (int i=0; i<n; i++) c.insert(rand64());
3. std :: unordered_set ‹uint64_t›
std::unordered_set<uint64_t> c; for (int i=0; i<n; i++) c.insert(rand64());
Найти элементы
Для std::vector
применяется линейный поиск. И std::set
, и std::unordered_set
используют find
для поиска целевого значения. Целевое значение будет назначаться случайным образом на каждой итерации.
- std :: vector ‹uint64_t›
// Linear search. for (int i=0; i<1000000; ++i){ uint64_t target = x; // one of existing numbers for (int k=0; k<c.size(); ++k) if (c[k] == target) break; }
2. std :: set ‹uint64_t›
for (int i=0; i<1000000; ++i){ uint64_t target = x; // one of existing numbers c.find(target); }
3. std :: unordered_set ‹uint64_t›
for (int i=0; i<1000000; ++i){ uint64_t target = x; // one of existing numbers c.find(target); }
Результаты эксперимента
Время выполнения поиска по количеству элементов показано на рис. 1. По оси ординат отложено время выполнения в секундах. По оси абсцисс отложено количество элементов. Можно заметить, что производительность всех трех контейнеров находится в жесткой гонке с n=1
до n=64
. Для n>=64
время выполнения std::vector
линейно увеличивается по мере увеличения n
и std::set
увеличения логарифмически. std::unordered_set
поддерживать почти постоянное время выполнения, когда n
увеличивается.
Чтобы ясно увидеть детальную разницу между n=1
и n=64
, я сужаю диапазон, как показано на рис. 2. Что меня удивляет, так это то, что производительность std::vector
не всегда лучше, чем я думал, когда n
мало. Вместо этого std::unordered_set
в моих экспериментах часто может иметь примерно на 10% быстрее, чем std::vector
forn≥4
. И std::set
всегда худший в этом диапазоне.
Ладно ... так что случилось? Чтобы узнать больше об этом, я использовал инструмент профилирования Linux (perf) для отслеживания промахов в кэше и переходов во время поиска, которые показаны на Рис. 3 и Рис. 4. соответственно.
На рис. 3 показано количество промахов в кэше в логарифмической шкале количества элементов. Для n≥512
количество промахов в кэше std::set
и std::unordered_set
намного больше, чем std::vector
. Для n<=64
разница в количестве промахов в кэше этих трех контейнеров невелика. Похоже, что кеш-память хорошо задействована для всех контейнеров, и я считаю, что это основная причина, по которой std::vector
не смог превзойти два других контейнера в этом диапазоне. То есть непрерывный доступ к памяти std::vector
может не иметь большого преимущества, когда n
мало в этом эксперименте. Однако колебания количества промахов в кэше std::set
и std::unordered_set
можно наблюдать на рис. 3. Число промахов кэша std::vector
более стабильно, чем два других. Например, для n=8
количество промахов в кэше std::unordered_set
внезапно становится больше, чем std::vector
, и соответствующая скорость поиска становится хуже, чем std::vector
.
На рис. 4 он показывает процент пропусков ветвления по отношению к количеству элементов. Можно сказать, что прогнозы ветвлений очень точны (›98%) для обоихstd::vector
и std::unordered_set
. Тем не менее, процент неудачных переходов для std::set
, очевидно, намного выше, чем для двух других. Из-за худшей производительности std::set
при использовании кеша и прогнозировании ветвлений это может объяснить, почему время выполнения std::set
является худшим.
В этом эксперименте результат поиска указывает почти лучший вариант для каждого контейнера. При небольшом размере программы код можно было бы хорошо оптимизировать. И большая часть кешей (кешей данных и кешей инструкций) и аппаратных ресурсов достаточна для поисковых операций. Кроме того, эксперимент проводится с одним потоком, так что штрафы за переключение контекста сводятся к минимуму.
Следовательно, в реальных сложных и больших программах производительность поиска может ухудшиться. Системные факторы, такие как промахи в кэше, могут иметь большее влияние на операции поиска, особенно для std::set
и std::unordered_set
с точки зрения промахов кэша.
В заключение поиска среди нескольких элементов, если поиск является единственной целью или использование памяти вызывает беспокойство, std::vector
по-прежнему остается моим первым приоритетом, потому что преимущества непрерывного доступа к памяти, которые могут уменьшить количество промахов кеша в большинстве случаев. И, безусловно, если элементы будут добавляться или удаляться динамически, std::unordered_set
и std::set
будут более подходящими.