Delphi. Що таїть у собі TDictionary


Доброго часу доби.
А чи знаєте ви, що не всі хеш таблиці однаково корисні? Зараз я розповім вам історію, як одна погана хеш таблиця з'їв всю продуктивність, і не скривилася. І як виправлення цієї хеш таблиці прискорило код майже в 10 разів.
Звичайно, згідно теми — у статті мова піде про Delphi, але навіть якщо ви не Delphi розробник, то все одно раджу заглянути під кат, а після прочитання статті у вихідний код хеш-таблиць, які ви використовуєте. А Delphi розробникам я раджу взагалі відмовитися від стандартного TDictionary.


1. Як влаштована хеш таблиця.

Якщо ви відмінно знаєте як влаштована хеш-таблиця, і що таке linear probing — можете сміливо переходити до другої частини.

Будь-яка хеш таблиця всередині — це по суті деякий масив. Елементи такого масиву прийнято називати bucket-ами. І одне з центральних місць в хеш таблиці — це хеш функція. Взагалі хеш-функція — це функція, що відображає одне безліч на інше безліч фіксованого значення. І завдання будь-якої хеш-функції — дати рівномірно розподілений результат на фіксованій множині. Більше про хеш функції можна почитати у вікіпедії, я не буду на цьому зупинятися.
Отже ми підготували масив скажімо 10 bucket-ів. Тепер ми готові складати значення в наш масив. Ми беремо хеш від нашого ключа. Наприклад хеш виявився 32 бітовим цілим числом M. Щоб визначити, в якій bucket ми будемо записувати наше значення — ми беремо залишок від ділення: Index := M mod 10. І кладемо в bucket[Index] := NewKeyValuePair.
Рано чи пізно ми зіткнемося з тим, що в bucket[Index] вже буде лежати якесь значення. І нам треба буде щось з цим робити. Такий випадок називається дозволом колізій (Collision resolution). Існує декілька технік дозволу колізій. Ось основні:

Separate chaining або closed addressing
У найпростішому випадку цей метод є ось що. Кожен bucket — це посилання на голову пов'язаного списку (linked list). Коли виникає колізія — ми просто додаємо в linked list ще один елемент. Щоб наш список не виродився в декілька лінійних linked list-ів вводять таке поняття, як load factor. Тобто коли кількість елементів на один bucket перевищує деяке число (load factor) — створюється новий масив bucket-ів, і всі елементи з старого розпихуються за новим. Процедура називається rehash.
Недоліки цього підходу в тому, що для кожної пари <ключ, значення> ми створюємо об'єкт, який потрібно додати в linked list.
Цей підхід можна поліпшити. Наприклад, якщо замість bucket-ів зберігати пару <ключ, значення> + посилання на голову linked list-а. Встановивши load factor 1 або навіть 0.75 можна практично уникнути створення елементів linked list-а. А bucket-и, які є масив — дуже дружелюбно ложаться на кеш процесора. p.s. На даний момент я вважаю це найкращим способом вирішення колізій.

Open addressing
Для цього методу у нас все bucket-и — це масив <ключ, значення>, і абсолютно всі елементи хеш таблиці зберігаються в bucket-ах. По одному елементу на bucket. Спроба вставити елемент в таку хеш таблицю називається probe. Найбільш відомі такі методи проб: Linear probing, Quadratic probing, Double hashing.
Давайте подивимося як працює Linear probing.
Ось ми потрапили в ситуацію, коли bucket уже зайнятий іншим елементом:

Тоді ми просто додаємо до bucket-у одиницю, і кладемо елемент в сусідній:

Знову потрапили в цей же bucket? Тепер доведеться переступити аж 3 елемента:

А ось зовсім невдало вийшло:

З останнього прикладу добре видно, що для того, щоб цей метод був ефективний — потрібно щоб було багато вільних bucket-ов, а ще дуже важливо, щоб вставлені елементи не кучкувалися в певних ділянках, що накладає високі вимоги на хеш-функцію.
Спроба обійти невдалу хеш-функцію — це Quadratic probing і Double hashing. Суть Quadratic probing в тому, що наступна probe буде через 1, 2, 4, 8 і т. д. елементів. Суть Double hashing в тому, що розмір стрибка для наступної probe вибирається за допомогою хеш-функції. Або відмінною від першої, або тією ж, але хеш береться від індексу bucket в який тільки що намагалися покласти.
Але найголовніше в Open addressing те, що навіть якщо ми 10000 елементів заповнили без єдиної колізії, то додавання 10001-го може призвести до того, що ми переберемо всі 10000 вже знаходяться там елементів. І найстрашніше, що коли ми покладемо цей 10001-ый, щоб потім до нього звернутися — нам знову доведеться перебрати 10000 попередніх.
Є ще одна неприємна річ, яка випливає з усього вищесказаного. Для Open addressing важливий порядок заповнення. Яка б чудова гешфункція не була все може зіпсувати порядок заповнення. Давайте подивимося останній розглянемо останній випадок, нам не пощастило. Всі елементи були заповнені без єдиної колізії, але останній елемент з колізією, яка призвела до перебору купи bucket-ів:

А що якби ми спочатку поклали цей єдиний елемент:

у нас колізія, ми перебрали всього 1 бакет.
А потім поклали б сусіда:

знову перебрали б 1 бакет.
І наступного сусіда:

В сумі додавання призвело б лише до однієї колізії на кожний елемент. І хоча сумарна кількість перебраних bucket-ів при додаванні залишилося колишнім — воно в цілому став більш збалансованим. І тепер при зверненні до будь-якого елементу ми б зробили 2 перевірки у bucket-ах.

2. Що ж не Так у Delphi з Linear probing в TDictionary?

Адже такий «невдалий» порядок з хорошою хешфункцией складно отримати, скажіть ви? І сильно помилитеся.
Для того, щоб отримати всі елементи TDictionary — нам треба пройтися по масиву бакетов, і зібрати елементи у зайнятих клітинках. Головний підступ тут в тому, що послідовність зберігається! Просто створюємо ще один TDictionary, і перекидаємо дані в нього… і отримуємо купу колізій на останніх елементах перед черговим grow.
Найпростіший код, щоб відтворити ситуацію:
Hash1 := TDictionary<Integer, Integer>.Create();
Hash2 := TDictionary<Integer, Integer>.Create();

for i := 0 to 1280000 do // цей TDictionary заповниться дуже швидко
Hash1.Add(i, i);
for i in Hash1.Keys do // а цей - несподівано повільніше, в десятки разів!
Hash2.Add(i, i);

У TDictionary rehash настає тільки тоді, коли вільних клітинок у масиві bucket-ів стає менше 25% (Grow threshold = 75%). Збільшення ємності відбувається завжди у 2 рази. Ось заповнені bucket-и у великому словнику:

спроба додати дані елементи в таблицю меншого розміру можна розглянути так. Розділимо велику таблицю на 2 частини. Перша частина ляже абсолютно ідентично.

Тепер нам треба додати елементи з другої половини (зелененькі).

Бачите як зростає кількість колізій при додаванні другої половини? І якщо до rehash-а ще далеко, а таблиця досить велика — ми можемо отримати колосальний оверхед.
Давайте порахуємо кількість колізій при додаванні нового елемента. Для цього я скопіював собі вихідний код TDictionary, і додав пару коллбек методів, які повертають колізії. Результати вивів на графіки:

Я заповнював хеш таблицю значень, і по мірі заповнення вимірював кількість колізій, кожні нові N значень відображає новий піксель по осі X. Тобто горизонтальна вісь відображає заповнення таблиці, а вертикальна — кількість колізій. Праворуч від кожного графіка значення:
  • Max collision — максимальна кількість колізій в межах одного пікселя по осі X.
  • Items per pixel — кількість елементів, що припадають на один піксель графіка по осі X.
  • Items count — сумарна кількість елементів в хештаблице
  • Filling percentage — відношення к-сті елементів до кількості bucket-ів в таблиці.
Чорна лінія — максимальне число колізій в пікселі. Червона — середнє арифметичне від колізій в пікселі.
На першому графіку при заповненні 48% все добре. Максимум колізій 169. Як тільки ми переступати 50% — починається сама жах. Так при 61% наступає сама жость. Кількість колізій на елемент може досягати 130 тисяч! І так до 75%. Після 75% відбувається grow, і відсоток заповнення зменшується.
Кожна пила з купою колізій — ніщо інше, як те, що я показував на малюнку вище. Закінчується «пила» rehash-му і різким падінням колізій.
Волею випадку ви можете опинитися на вершині такої пилки, і спроба працювати з останніми доданими елементами супроводжуватиметься у вас сильними гальмами.
Як же це виправити? Ну найочевидніший варіант — це grow threshold встановити в 50%. Тобто вільних комірок в хештаблице має бути не менше 50%. Зміна цього порогу дає ось такі графіки:

на тих же обсягах даних. Ціною додаткової пам'яті ми «виграли» собі процесорний час. Проблема тут в тому, що поле GrowThreshold недоступне зовні. Можна постаратися уникнути невдалих послідовностей. Або вручну перемішувати/сортувати дані перед приміщенням в таблицю, що достатньо дорого, або створювати різні таблиці з різними хешфункциями. Багато хеш-функції (такі як Murmur2, BobJenkins hash) дають можливість поставити Seed/InitialValue. Але ці значення навмання підбирати теж не рекомендується. В більшості випадків в якості seed підійде просте число, але все таки краще почитати мануал по конкретній хеш функції.
Ну і нарешті моя порада — не використовуйте Open addressing як універсальний метод для будь хеш таблиці. Я вважаю краще звернути увагу на Separate chaining з бакетами <ключ, зачение>+вказівник на голову linked list-а з load factor-му близько 0.75.

p.s. На пошук даного підводного каменя я витратив кілька днів. Ситуація ускладнювалася тим, що великі обсяги даних отпрофайлить складно + залежність від % заповнення TDictionary призводила до того, що гальма містичним чином періодично зникали. Так що спасибі за увагу, сподіваюся, ви про це не спіткнетеся. ;)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.