Кампанія Facebook аб адкрыцці зыходных тэкстаў рэалізацыі хэш-табліц , аптымізаванай для эфектыўнага спажывання памяці. F14 выкарыстоўваецца ў інфраструктуры Facebook у якасці замены большасці тыпаў хэш-табліц і дазваляе зменшыць спажыванне памяці без страты прадукцыйнасці. F14 прыкметна пераўзыходзіць па прадукцыйнасці хэш-табліцы google::sparse_hash_map, дагэтуль якія лічыліся найболей эфектыўнымі па спажыванні памяці. Код праекту напісаны на мове C++ і ўключаны ў склад бібліятэкі .
F14 ставіцца да алгарытмаў з сістэмай дазволу калізій на аснове падвойнага хэшавання з 14 (У адным вочку хэш-табліцы захоўваецца ланцужок з 14 слотаў, а інтэрвал паміж вочкамі вылічаецца пры дапамозе дапаможнай хэш-функцыі). Для паскарэння аперацый фільтрацыі вочак у рэалізацыі выкарыстоўваюцца вектарныя інструкцыі SSE2 для сістэм x86_64 і NEON для Aarch64, якія дазваляюць распаралеліць выкананне аперацый выбару слотаў з ланцужкамі ключоў і адсяванні ключоў усярэдзіне ланцужка. За раз апрацоўваюцца блокі ў 14 слотаў, што з'яўляецца аптымальным балансам паміж эфектыўнасцю выкарыстання працэсарнага кэша і лікам калізій.
Асаблівасцю F14 з'яўляецца магчымасці выбару розных стратэгій захоўвання дадзеных:
- F14NodeMap - спажывае менш за ўсё памяці для ключоў вялікага і сярэдняга памеру. Забяспечвае ўскоснае захаванне элементаў з выклікам пры кожнай устаўцы функцыі malloc;
- F14ValueMap - забяспечвае мінімальнае спажыванне памяці для невялікіх ключоў. Элементы захоўваюцца ў саміх вочках (inline). Для сярэдніх і вялікіх ключоў падобных падыход прыводзіць да прыкметных накладных выдаткаў памяці;
- F14VectorMap - працуе хутчэй для вялікіх табліц і складаных ключоў, але павольней для простых ключоў і невялікіх табліц. Элементы пакуюцца ў бесперапынна які запаўняецца масіве і адрасуюцца 32-разрадным індэксным паказальнікам;
- F14FastMap - камбінаваная стратэгія. Калі ключ менш 24 байтаў, то выбіраецца F14ValueMap, а калі больш - F14VectorMap.
Крыніца: opennet.ru