09.10.2011

Обявление: “hashtables”, нова Haskell библиотека за бързо изменими хеш-таблици.

* Source text URL: http://gregorycollins.net/posts/2011/06/11/announcing-hashtables




Много се радвам да обявя днес пускането на пазара на първата версия hashtables – Haskell библиотека за бързо изменими хеш-таблици. Библиотеката hashtables съдържа три различни реализации (implementation) на изменими хеш-таблици в ST монадата, а също клас на типа (type class), абстрахиращ функциите за всяко едно от тях, и набор от обвиващи функции (wrapper functions) за използване на хеш-таблиците в IO монадата.

Какво е включено?
Библиотеката hashtables съдържа реализации на следните структури от данни:

- Data.HashTable.ST.Basic: стандартна хеш-таблица за отворено адресиране, използваща линейно пробване (linear probing) за справяне с колизии. Откъм чиста скорост това трябва да е най-бързата към момента реализация на Haskell хеш-таблица за търсене (lookup) въпреки че тя има по-висок overhead от другите таблици. Както много реализации на хеш-таблици, тя може да претърпи големи забавяния, когато таблицата се увеличава, поради рехеширането на всички елементи в нея.   

- Data.HashTable.ST.Cuckoo: реализация на Cuckoo hashing, въведен от Pagh и Rodler през 2001 г. Cuckoo hashing разполага с търсене O(1) “в най-лошия случай” (worst-case O(1) lookup) и може да достигне висок “фактор на зареждане” (load factor), което означава, че таблицата може да работи задоволително дори при над 90% запълненост. Случайни тестове показват, че тази реализация на Cuckoo hashing е малко по-бърза при вмъкване (insert) и малко по-бавна при търсене (lookup) oт Data.HashTable.ST.Basic, като в същото време е по-ефикасна откъм място с около половин дума за изобразяване на ключова стойност.

- Data.HashTable.ST.Linear: линейна хеш-таблица, която губи известна работоспособност при търсене и вмъкване за сметка на по-висока ефикасност откъм място и много по-малки забавяния при увеличаване на таблицата. Случайни тестове най-често показват, че тази таблица е малко по-бърза от Data.HashTable от базовата Haskell библиотека.  

Защо е бавна Data.HashTable

Хората често отбелязват , че реализацията на хеш-таблици от базовата Haskell библиотека е бавна. В исторически план има няколко причини за това: първо, хората, ползващи Haskell, обикновено предпочитат персистентни (persistent) структури от данни пред ефемерни (ephemeral). Второ, допреди GHC 6.12.2 GHC имаше недопустимо голям overhead при използване на изменими масиви (mutable arrays), поради липса на маркиране на карти (card marking) в колектора за боклуците (garbage collector).

Въпреки това тестове на по-нови версии на GHC показват, че реализацията на хеш-таблици от базовата Haskell библиотека е по-бавна, отколкото би трябвало да бъде. За да обясним това, нека разгледаме дефиницията на типа данни за Data.HashTable:

data HashTable key val = HashTable {
                                     cmp    ::!(key -> key -> Bool),
                                     hash_fn::!(key -> Int32),
                                     tab    ::!(IORef (HT key val))
                                   }

data HT key val
  = HT {
        kcount ::!Int32,              -- Total number of keys.
        bmask  ::!Int32,
        buckets::!(HTArray [(key,val)])
       }

Нека игнорираме засега типа HashTablе, тъй като в същността си той е просто IORef обвивка около HT типа, който съдържа фактическата таблица. Хеш-таблицата от Data.HashTable използва отделно нареждане в списък (chaining), в който ключовете се хешират в блокове (buckets), всеки от които съдържа свързан списък от (ключ, стойност) редове (tuples). За да обясним защо това не е особенно добра стратегия за хеш-таблици в Haskell, нека видим как изглежда разположението на паметта на тази структура от данни по време на работа.

Memory layout of Data.HashTable
Расположение на паметта данни в Data.HashTable

Всяка стрелка в горната схема представлява указател, който при дереференция може (и вероятно го прави) да причини кеш пропуск (cache miss). По време на търсене, всеки път, когато тестираме запис в някой от блоковете според ключа на търсене, предизвикваме зареждането на три кеш реда:
• един самите cons клетки
• един за блока
• един за ключа

Ако един блок средно има b eлементa, успешното търсене предизвиква зареждането средно на 1+ 3b/2 кеш реда: един за дереференция на масива от блокове, за да се придвижи указателя до първата cons клетка, и 3b/2 за намиране на съответния ключ в масива от блокове. Неуспешното търсене е по-лошо – то причинява зареждането на цели 1+ 3b кеш реда – защото трябва да разгледаме всеки ключ в блока. 

ok ok