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

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

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

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

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 так ужасно дорого (даже если мы зарезервируем достаточно места в начале, он не работает намного лучше - так что перефразирование, кажется, не проблема)?

EDIT:

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

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

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

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

EDIT 2:

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

EDIT 3:

это цифры для std::map:

inserts: 16462
get    : 16978

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