1.7 C
София

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

Най-четени

Даниел Десподовhttps://www.kaldata.com/
Ежедневен автор на новини. Увличам се от съвременни технологии, оръжие, информационна безопасност, спорт, наука и концепцията Internet of Things.

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
Абонирай се
Извести ме за
guest
2 Коментара
стари
нови
Отзиви
Всички коментари

Нови ревюта

Ревю на рутера TP-Link Archer C64: клас AC1200 с гигабитови портове

Брандът TP-Link отдавна е добре позната на нашия пазар, което не е изненадващо, тъй като компанията е един от най-големите производители на мрежово оборудване....

Подобни новини