Странный бенчмарк, странные либы (unordered_map vs. GLib hashtable)
Согласно 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 целых чисел на моем ноутбуке).
Недавно мне довелось разбираться с результатами странного бенчмарка: вставка 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 целых чисел на моем ноутбуке).