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

Facebook компания обявиха относно внедряването на хеш таблици с отворен код F14, оптимизиран за ефективна консумация на памет. 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