Странный бенчмарк, странные либы (unordered_map vs. GLib hashtable)

[mejedi]

Согласно common knowledge, код на C++ не медленнее кода на Си.

Недавно мне довелось разбираться с результатами странного бенчмарка: вставка 10M элементов в хеш таблицу, std::unordered_map vs. GLib hashtable, функции хеширования идентичные. Код на Си работает 4 секунды, плюсовая версия медленнее почти в два раза. WTF?

Comments

[zeux]

Ну это не "код медленнее" это "библиотека отличается".
А то иначе рекомендую например попробовать ifstream vs FILE* на Windows/OSX...

В glibc таблица простых следует правилу "ресайз примерно в 1.5 раза". Но используется вот так:

if ((hash_table->size >= 3 * hash_table->nnodes && \
hash_table->size > HASH_TABLE_MIN_SIZE) || \
(3 * hash_table->size <= hash_table->nnodes && \
hash_table->size < HASH_TABLE_MAX_SIZE)) \
g_hash_table_resize (hash_table); \

Внутри g_hash_table_resize:
new_size = g_spaced_primes_closest (hash_table->nnodes);
new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);

MIN_SIZE = 11, MAX_SIZE = 13.8M

Т.е. таблица простых используется для поиска нового количества бакетов по формуле "взяли кол-во элементов в хеш таблице, нашли следующее простое в таблице простых и никогда не делаем больше чем 13.8M". Т.к. таблица сделана по правилу "ресайз в 1.5 раза" то получается примерно "в тот момент когда количество элементов в таблице превысит количество бакетов примерно в три раза увеличим количество бакетов так чтобы оно было больше количества элементов примерно в полтора" - я путаю или получается рост от 3 до 4.5 раза в зависимости от того как попадется простое число?

В libstdc++ в таблице простых числа более или менее плотно, однако используется она вот так:

return std::make_pair(true,
_M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1,
__n_bkt * _S_growth_factor)));

_M_next_bkt это вот:

const unsigned long* __next_bkt =
std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
_M_next_resize =
__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
return *__next_bkt;

Значения по-умолчанию такие:
_M_max_load_factor = 1
_S_growth_factor = 2

Получается что когда количество элементов достигает количества бакетов, мы умножаем его на 2 и находим следующее простое - получается рост примерно в 2 раза.

Если я не напутал (этот код я только читал, а не запускал), то разница собственно не в таблице простых а в стратегии роста. Можно попробовать сделать hash.max_load_factor(3) чтобы сделать их поближе - правда рост в libstdc++ будет все равно в два раза.

Еще отмечу что 10M это опасно-близко к 13.8M (это лимит на бакеты, с учетом load factor 3 получается что после 40M элементов glibc таблица перестает расти и можно начать терять скорость на длинных списках), и плюс с фактором 4.5 и вышеописанным критерием можно случайно "удачно" попасть с числами - т.е. чтобы glibc таблица была чуть-чуть до лимита за которым следует ресайз в 4.5 раза.

[mejedi]

Абсолютно согласен, что дело тут в библиотеках. Возможно, моя гипотеза неверна и надо было аккуратно разбираться до конца, с запуском под профайлером и прочей тяжелой артилерией.