?

Log in

Странный бенчмарк, странные либы (unordered_map vs. GLib hashtable) - A cure for !being an axe-wielding homicidal maniac [entries|archive|friends|userinfo]
A cure for !being an axe-wielding homicidal maniac

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Странный бенчмарк, странные либы (unordered_map vs. GLib hashtable) [дек. 29, 2014|02:42 pm]
A cure for !being an axe-wielding homicidal maniac
Согласно common knowledge, код на C++ не медленнее кода на Си.

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

Во-первых, это сравнение ужа с ежом; как минимум аллокаторы разные. Но это не самое важное.

Во-вторых, алгоритмически, контейнеры устроены одинаково: коллизии отрабатываются списками, количество корзин — простое число. Следующее простое число берется из таблицы (GLib, STL).

Легко видеть, что в таблица простых чисел GLib значительно меньше; перестроение таблицы происходит реже. Общее число обработанных элементов при перестроениях таблицы (всего вставляем N элементов):
N      10000000

GLib   27690445
STL   126439189


Если в STL варианте заранее преаллоцировать все 10M корзин, время выполнения падает до 3.5 секунды, что вполне соотносится с интуицией (при перестроении таблицы на каждый элемент приходится несколько случайных обращений к памяти, память медленная).

Еще интересный takeaway — современные процессоры неплохо предсказывают косвенные переходы, поэтому несмотря на то, что в GLib функция сравнения и функция хеширования вызываются по указателю, на результаты это почти не влияет.

Std::sort все еще быстрее qsort в два раза (при сортировке 10M целых чисел на моем ноутбуке).
СсылкаОтветить

Comments:
[User Picture]From: zeux
2014-12-30 07:28 am
Ну это не "код медленнее" это "библиотека отличается".
А то иначе рекомендую например попробовать 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 раза.
(Ответить) (Thread)
[User Picture]From: mejedi
2014-12-30 08:07 am
Абсолютно согласен, что дело тут в библиотеках. Возможно, моя гипотеза неверна и надо было аккуратно разбираться до конца, с запуском под профайлером и прочей тяжелой артилерией.
(Ответить) (Parent) (Thread)