elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Теория на практике или хеш-таблицы часть 4
elizarov

При дизайне алгоритмов и структур данных часто приходится пользоваться анализом асимптотической сложности алгоритмов использую О-нотацию. Редко приходится использовать резальтаты каких-либо численных, а не асимптотических расчетов. Тем удивительней, когда их результаты помогают не только выбрать алгоритм, но и найти ошибки в его реализации, как это произошло после написания предыдущей части рассказа про дизайн быстрых хеш-таблиц.

Ключевой параметр хеш-таблицы это коэффициент её заполнения. Он особенно важен в таблицах с открытой адресаций, которые и являются предметом моего рассмотрения как самые компактные по занимаемой и адресуемой памяти, а значит и самые быстрые. Зная коэффициент заполнения α, можно вычислить ожидаемое число проб которые будет делать алгоритм для успешного поиска элемента.

ожидаемое число проб в зависимости о коэффициента заполнения

По просьбе rp1810 я поменял реализацию FastCache2 (алгоритма с двойным хешированием), чтобы после заполнения данными коэффициент заполнения был близок к тому, на котором тестируется FastCache (алгоритм с линейным исследованием) хотя, как я наглядно покажу в одной из будущих заметок, в разумных пределах это не оказывает существенного эффекта на скорость работы.

Подготавливая таблицу со сравнительными параметрами, которая включает в себя коэффициент заполнения а так же фактическое и теоретическое число проб, я обратил внимание на то, что фактическое число проб сильно отличается от теоретического значения несмотря на перемешивание идентификаторов, призванное сделать их случайными. Так как теоретическое значение рассчитывается в предположении полностью случайных данных, то это признак существенного отличия фактических данных от случайных. После исправления функции перемешивания в тестовом коде всё встало на свои места. Результаты сравнения FastCache и FastCache2 после этих изменений сведены в таблицу ниже:

Реализация Описание α Число проб (время нс)
Исходная последовательность
Число проб (время нс)
Перемешанные идентификаторы
Число проб
Теоретическое
Формула
FastCache один массив, открытая адресация,
линейное исследование, хеш умножением
51% 1.30 (83 ± 1) 1.49 (101 ± 1) 1.52 (1+1/(1-α))/2
FastCache2 один массив, открытая адресация,
двойное хеширование, хеш делением
46% 1.00 (68 ± 1) 1.31 (113 ± 1) 1.34 ln(1/(1-α))/α

Это таблица наглядно демонстрирует, что при исходном распределении запросов, когда наиболее часто запрашиваемые идентификаторы находятся в узком диапазоне, двойное хеширование фактически работает как массив, в подавляющем большинстве случаев находя элемент с первого раза. Более того, умножение на магическое число, используемое в алгоритме FastHash с линейным исследованием в качестве хеш-функции, не обеспечивает идеальное размазывание данных по хеш-таблице случайным образом — получается чуть меньше проб, чем должно быть для полностью случайных данных.

Просмотрев полную таблицу в предыдущей заметке можно найти одну быструю реализацию, для которой перемешивание данных вообще не влияет на производительность. Это HPPC, который использует MurmurHash для очень хорошего, неотличимого от случайного, размазывания данных по хеш-таблице.


  • 1
Надеюсь, ты не за один проход считал число проб и время? :-)

(Теоретическое число проб имеет смысл сравнивать только со средним числом проб при однократном обращении к каждому хранимому элементу :), а вот время - нужно считать проходом по массиву с учетом кратности).

Так что эта, оба числа проб покажи - среднее число проб _при однократном проходе_ и при проходе _с_учетом_кратности_

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


Edited at 2012-05-22 11:41 am (UTC)

А с учетом вероятности, вроде как, получается 1.13 FastCache vs 1.26 FastCache2... Все-таки ресайз FastCache действительно замечателен.

Где-то у тебя ошибка закралась: 1.25 FastCache и 1.21 FastCache2 (это суммарное число проб поделенное на всю последовательность доступа из 10M элементов). Ресайз не оказывает насколько большого значение. Без него (если делать его в другую сторону) взвешеннае на вероятность число проб проседает до 1.35. И это все-равно лучше чем невзвешенное 1.49, ибо в время инициализации после последнего ресайза в кэш добавляются уже только редко используемые элементы.



Развертку по размеру кеша, в который впервые вставлялись элементы - можешь сделать?

У меня получилась примерно такая цифирь:
17 и менее бит - 17% обращений, ~1.01 проб на обращение
18 бит - 16% обращений, ~1.035 проб на обращение
19 бит - 27% обращений, ~1.08 проб на обращение
20 бит - 30% обращений, ~1.2 проб на обращение
21 бит - 10% обращений, ~1.4 проб на обращение
Ну и во всех частях число проб на обращение и проб на элемент - вроде бы должны совпадать (с небольшой погрешностью, в части 21 бит - погрешность чуть больше)
Для FastCache2 - я обсчитался. Там так и должно быть - очень близко к теоретическому значению на 1/3.

Это нормально, что во 2 столбце для FC2 число проб меньше, а время больше ?

Конечно. FC2 использует двойное хеширование и из-за этого проб меньше. Но эти пробы идут в произвольные регионы памяти, которые еще надо загрузить. Это очень долго. В то время как линейное исследование читает адрес следующего объекта для пробы рядом — из уже загруженной в кеш процессора области.

в первом столбце это не заметно.

P.S. И самый главный вопрос - как это завести для конкурентного окружения =)

Чего не заметно?

  • 1
?

Log in

No account? Create an account