Является ли gcc std:: unordered_map медленной? Если да - почему?

Мы разрабатываем высокопроизводительное критическое программное обеспечение на С++. Там нам нужна параллельная карта хэша и реализована одна. Итак, мы написали бенчмарк, чтобы выяснить, насколько медленнее наша сопоставимая хэш-карта сравнивается с 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 должен реализовать более сложный интерфейс. Но я не вижу этого аргумента: мы используем метод bucket в нашем concurrent_map, std::unordered_map также использует метод bucket-подхода (google::dense_hash_map не работает, но std::unordered_map должен быть как минимум так же быстро, как и наша поддержка concurrency -безопасная версия?). Кроме того, я ничего не вижу в интерфейсе, который заставляет функцию, которая делает хэш-карту плохо работать...

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

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

EDIT:

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

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

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

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

ИЗМЕНИТЬ 2:

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

ИЗМЕНИТЬ 3:

Это числа для std::map:

inserts: 16462
get    : 16978

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

Ответы

inserts: 37728
get    : 2985

inserts: 2531
get    : 1565

template <typename TEST>
void time_test (TEST t, const char *m) {
    struct tms start;
    struct tms finish;
    long ticks_per_second;

    times(&start);
    t();
    times(&finish);
    ticks_per_second = sysconf(_SC_CLK_TCK);
    std::cout << "elapsed: "
              << ((finish.tms_utime - start.tms_utime
                   + finish.tms_stime - start.tms_stime)
                  / (1.0 * ticks_per_second))
              << " " << m << std::endl;
}

#define SIZE 10000000
#define DEPTH 3
std::vector<uint64_t> vec(SIZE);
boost::mt19937 rng;
boost::uniform_int<uint64_t> dist(std::numeric_limits<uint64_t>::min(),
                                  std::numeric_limits<uint64_t>::max());
std::unordered_map<int, long double> map(SIZE/DEPTH);

void
test_insert () {
    for (int i = 0; i < SIZE; ++i) {
        map[vec[i]] = 0.0;
    }
}

void
test_get () {
    long double val;
    for (int i = 0; i < SIZE; ++i) {
        val = map[vec[i]];
    }
}

int main () {
    for (int i = 0; i < SIZE; ++i) {
        uint64_t val = 0;
        while (val == 0) {
            val = dist(rng);
        }
        vec[i] = val;
    }
    time_test(test_insert, "inserts");
    std::random_shuffle(vec.begin(), vec.end());
    time_test(test_insert, "get");
}

#ifndef DEPTH
#define DEPTH 10000000
#endif

elapsed: 7.12 inserts, elapsed: 2.32 get, -DDEPTH=10000000
elapsed: 6.99 inserts, elapsed: 2.58 get, -DDEPTH=1000000
elapsed: 8.94 inserts, elapsed: 2.18 get, -DDEPTH=100000
elapsed: 5.23 inserts, elapsed: 2.41 get, -DDEPTH=10000
elapsed: 5.35 inserts, elapsed: 2.55 get, -DDEPTH=1000
elapsed: 6.29 inserts, elapsed: 2.05 get, -DDEPTH=100
elapsed: 6.76 inserts, elapsed: 2.03 get, -DDEPTH=10
elapsed: 2.86 inserts, elapsed: 2.29 get, -DDEPTH=1

inserts: 9280 
get: 3302

inserts: 23946
get: 24824

inserts: 7289
get: 1908

inserts: 19222 
get: 19711