Facebook отвори кода за реализацията на хеш таблиците F14

2
659

Facebook обяви, че вече е отворен сорс кода за реализацията на хеш таблиците F14. Таблиците F14 се използват в инфраструктурата на Facebook като замяна на повечето други типове хеш таблици, понеже осезателно намаляват използваната памет без загуба на производителността. F14 значително превъзхожда по производителност хеш таблицата google::sparse_hash_map, каято доскоро се считаше за най-ефективна по отношение на използваната памет. Кодът на проекта е написан на програмния език С++ и е включен в библиотеката Folly.

F14 е от фамилията алгоритми със система за разрешаване на колизиите на базата на двойно хеширане с 14 последователни проби (в една клетка на хеш таблицата се съхранява верига от 14 слота, а дистанциите между клетките се изчисляват с помощта на допълнителна хеш функция). За ускоряване на операциите за филтриране на клетките се използват векторните инструкции SSE2 за x86_64 системите и NEON за Aarch64, които дават възможност за паралелна обработка на операциите за избор на слотове с веригите ключови значения и отсяването на ключовите значения в самата верига. Обработват се по 14 слота наведнъж, което е оптималния баланс между ефективността на използване на процесорния кеш и броя колизии.

Друга особеност на F14 е възможността за избор на различни стратегии за съхраняване на данните:

  • F14NodeMap: най-малко използвана памет за ключове с голям и среден размер
  • F14ValueMap: минимално използване на памет за ключове с малък размер
  • F14VectorMap: най-бърз работа при големи таблици и сложни ключове, но бавна работа при малки таблици и опростени ключове
  • F14FastMap: комбинирана стратегия. Ако ключът е по-малък от 24 байта, избира се F14ValueMap, а ако е по-голям – F14VectorMap

2
ДОБАВИ КОМЕНТАР

avatar
1 Коментари
1 Отговори на коментарите
1 Последователи
 
Коментарът с най-много реакции
Най-горещият коментар
  Абонирай се  
нови стари оценка
Извести ме за
Panko
Panko

нищо не разбрах. hash mash pash. 24,f23, f16,f17

Мангалата
Мангалата

Ми то програмирането и алгоритмите не са за чалгаджии или ритни-топковци.