В этом посте обсуждается эффективность поиска элемента в контейнерах 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-битного целого числа без знака.

  1. 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 для поиска целевого значения. Целевое значение будет назначаться случайным образом на каждой итерации.

  1. 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 будут более подходящими.