Фејсбук отвора имплементација на хаш табели F14

Фејсбук компанија објави за имплементација на хаш табели со отворен код 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