Мы разрабатываем высокопроизводительное критическое программное обеспечение на 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<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> 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<int, long double> 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<std::chrono::milliseconds>(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<std::chrono::milliseconds>(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;
(EDIT: весь исходный код можно найти здесь: 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
необходимо реализовать более сложный интерфейс. Но я не вижу этого аргумента: мы используем подход ведра в нашей concurrent_map, std::unordered_map
тоже использует подход ведра (google::dense_hash_map
не использует, но чем std::unordered_map
должен быть хотя бы таким же быстрым, как наша защищенная от параллелизма версия?). Кроме того, я не вижу в интерфейсе ничего, что заставляло бы функцию, из-за которой хэш-карта работала плохо...
Итак, мой вопрос: правда ли, что std::unordered_map
кажется очень медленным? Если нет: что не так? Если да: в чем причина этого.
И мой главный вопрос: почему вставка значения в std::unordered_map
так ужасно затратна (даже если мы зарезервируем достаточно места в начале, это не будет работать намного лучше, так что перефразирование, похоже, не проблема)?
РЕДАКТИРОВАТЬ:
Прежде всего: да, представленный тест не безупречен - это потому, что мы много с ним играли, и это просто хак (например, распределение uint64
для генерации целых чисел на практике было бы не очень хорошей идеей, исключите 0 в петля какая-то глупая и т. д.).
На данный момент большинство комментариев объясняют, что я могу сделать unordered_map быстрее, предварительно выделив для него достаточно места. В нашем приложении это просто невозможно: мы разрабатываем систему управления базой данных и нуждаемся в хеш-карте для хранения некоторых данных во время транзакции (например, информации о блокировке). Таким образом, эта карта может быть любой: от 1 (пользователь просто делает одну вставку и фиксирует) до миллиардов записей (если происходит полное сканирование таблицы). Здесь просто невозможно предварительно выделить достаточно места (и просто выделить много в начале будет потреблять слишком много памяти).
Кроме того, я извиняюсь, что не сформулировал свой вопрос достаточно ясно: я не очень заинтересован в том, чтобы сделать unordered_map быстрым (использование плотной хеш-карты Google отлично работает для нас), я просто не очень понимаю, откуда берутся эти огромные различия в производительности. . Это не может быть просто предварительное выделение (даже при наличии достаточного количества предварительно выделенной памяти, плотная карта на порядок быстрее, чем unordered_map, наша параллельная карта, поддерживаемая вручную, начинается с массива размером 64, то есть меньше, чем unordered_map).
Так в чем же причина такой плохой работы 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) против O(1)) !
SIZE
. - person Ylisar   schedule 23.07.2012