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

Но std::unordered_mapкажется невероятно медленным... Так что это наш микро -тест (для параллельной карты, мы создали новый поток, чтобы убедиться, что блокировка не оптимизируется, и обратите внимание, что я никогда не вставляю 0, потому что я также тестирую с google::dense_hash_map, для которого требуется нулевое значение):

boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits::min(), std::numeric_limits::max());
std::vector vec(SIZE);
for (int i = 0; i < SIZE; ++i) {
    uint64_t val = 0;
    while (val == 0) {
        val = dist(rng);
    }
    vec[i] = val;
}
std::unordered_map map;
auto begin = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
    map[vec[i]] = 0.0;
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast(end - begin);
std::cout << "inserts: " << elapsed.count() << std::endl;
std::random_shuffle(vec.begin(), vec.end());
begin = std::chrono::high_resolution_clock::now();
long double val;
for (int i = 0; i < SIZE; ++i) {
    val = map[vec[i]];
}
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;

(РЕДАКТИРОВАТЬ :весь исходный код можно найти здесь:http://pastebin.com/vPqf7eya)

Результат для std::unordered_mapравен:

inserts: 35126
get    : 2959

Дляgoogle::dense_map:

inserts: 3653
get    : 816

Для нашей поддерживаемой вручную параллельной карты (, которая выполняет блокировку, хотя эталонный тест является однопоточным -, но в отдельном потоке порождения):

inserts: 5213
get    : 2594

Если я скомпилирую тестовую программу без поддержки pthread и запущу все в основном потоке, я получу следующие результаты для нашей параллельной карты, поддерживаемой вручную:

inserts: 4441
get    : 1180

Я компилирую с помощью следующей команды:

g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc

Так что особенно вставки на std::unordered_mapкажутся чрезвычайно дорогими -35 секунд против 3 -5 секунд для других карт. Кроме того, время поиска кажется довольно высоким.

Мой вопрос :почему это? Я прочитал еще один вопрос о stackoverflow, где кто-то спрашивает, почему std::tr1::unordered_mapмедленнее, чем его собственная реализация. Там ответ с наивысшим рейтингом гласит, что std::tr1::unordered_mapнеобходимо реализовать более сложный интерфейс. Но я не вижу этого аргумента :мы используем подход ведра в нашей параллельной _карте, std::unordered_mapтоже использует подход ведра -(google::dense_hash_mapне работает, но чем std::unordered_mapдолжен быть по крайней мере таким же быстрым, как наша безопасная версия параллелизма с ручной поддержкой -? ).Кроме того, я не вижу в интерфейсе ничего, что заставляло бы функцию, из-за которой хэш-карта работала плохо...

Итак, мой вопрос :, правда ли, что std::unordered_mapкажется очень медленным? Если нет :, что не так? Если да :, в чем причина этого.

И мой главный вопрос :, почему вставка значения в std::unordered_mapтакая ужасно дорогая (, даже если мы резервируем достаточно места в начале, она не работает намного лучше -, так что перефразирование, похоже, не проблема )?

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

Прежде всего :да, представленный тест не безупречен -это потому, что мы много с ним играли, и это просто хак (например, uint64дистрибутив для генерации целых чисел на практике не будет хорошая идея, исключать 0 из цикла довольно глупо и т. д... ).

На данный момент в большинстве комментариев объясняется, что я могу сделать неупорядоченную карту _быстрее, предварительно выделив для нее достаточно места. В нашем приложении это просто невозможно :мы разрабатываем систему управления базами данных и нуждаемся в хеш-карте для хранения некоторых данных во время транзакции (, например информации о блокировке ). Таким образом, эта карта может быть любой: от 1 (пользователя, который просто делает одну вставку и фиксирует )до миллиардов записей (, если происходит полное сканирование таблицы ). Здесь просто невозможно предварительно выделить достаточно места (и просто выделить много вначале будет потреблять слишком много памяти ).

Кроме того, я извиняюсь, что не сформулировал свой вопрос достаточно ясно :Я не очень заинтересован в быстром создании неупорядоченной _карты (с использованием плотной хеш-карты Google, которая отлично работает для нас ), я просто не Я действительно не понимаю, откуда берутся эти огромные различия в производительности. Это не может быть просто предварительное распределение (даже при достаточном количестве предварительно выделенной памяти, плотная карта на порядок быстрее, чем неупорядоченная карта _,наша параллельная карта, поддерживаемая вручную, начинается с массива размером 64 -, поэтому он меньше, чем неупорядоченная _карта ).

Так в чем же причина такой плохой работы std::unordered_map? Или другой вопрос :Можно ли написать реализацию интерфейса std::unordered_map, которая соответствует стандарту и (почти )так же быстро, как плотная хеш-карта Google? Или в стандарте есть что-то, что заставляет разработчика выбирать неэффективный способ его реализации?

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

Профилируя, я вижу, что много времени уходит на целочисленные деления. std::unordered_mapиспользует простые числа для размера массива, в то время как другие реализации используют степень двойки. Почему std::unordered_mapиспользует простые -числа? Чтобы работать лучше, если хэш плохой? Для хороших хэшей это не имеет значения.

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

Это номера дляstd::map:

inserts: 16462
get    : 16978

Оооооооо :почему вставки в std::mapбыстрее, чем вставки в std::unordered_map... Я имею в виду WAT? std::mapимеет худшую локализацию (дерево по сравнению с массивом ), нуждается в большем распределении (на вставку по сравнению с повторным хешированием + плюс ~1 на каждое столкновение )и, что наиболее важно, :имеет другая алгоритмическая сложность (O (logn )vs O (1 ))!