Facebook otwiera implementację tablic skrótów F14

Firma z Facebooka ogłosił na temat implementacji tabel skrótów typu open source F14, zoptymalizowany pod kątem efektywnego wykorzystania pamięci. Klawisz F14 jest używany w infrastrukturze Facebooka jako zamiennik większości typów tabel skrótów i może zmniejszyć zużycie pamięci bez utraty wydajności. F14 zauważalnie przewyższa tabele mieszające google::sparse_hash_map, które do tej pory uznawane były za najbardziej wydajne pod względem zużycia pamięci. Kod projektu napisany jest w języku C++ i znajduje się w bibliotece Szaleństwo.

F14 odnosi się do algorytmów z systemem rozwiązywania kolizji opartym na podwójnym mieszaniu z 14 sekwencje próbek (łańcuch 14 szczelin jest przechowywany w jednej komórce tabeli mieszającej, a odstęp między komórkami jest obliczany za pomocą pomocniczej funkcji mieszającej). Aby przyspieszyć operacje filtrowania komórek, w implementacji zastosowano instrukcje wektorowe SSE2 dla systemów x86_64 oraz NEON dla Aarch64, które pozwalają na równoległe wykonywanie operacji wyboru slotów z breloczkami i wyodrębniania kluczy w obrębie łańcucha. Jednorazowo przetwarzane są bloki po 14 slotów, co stanowi optymalny balans pomiędzy efektywnością wykorzystania pamięci podręcznej procesora, a ilością kolizji.

Cechą szczególną F14 jest możliwość wyboru różnych strategii przechowywania danych:

• F14NodeMap - zużywa najmniej pamięci dla dużych i średnich kluczy. Zapewnia, że ​​elementy są przechowywane pośrednio z wywołaniem malloc przy każdym wstawieniu;
• F14ValueMap - zapewnia minimalne zużycie pamięci dla małych kluczy. Elementy są przechowywane w samych komórkach (inline). W przypadku średnich i dużych kluczy takie podejście prowadzi do zauważalnego obciążenia pamięci;
• F14VectorMap - działa szybciej w przypadku dużych tabel i złożonych kluczy, ale wolniej w przypadku prostych kluczy i małych tabel. Elementy są pakowane w stale wypełnianą tablicę i adresowane przez 32-bitowy wskaźnik indeksu;
• F14FastMap to strategia łączona. Jeśli klucz ma mniej niż 24 bajty, wybierana jest F14ValueMap, a jeśli jest większa, wybierana jest F14VectorMap.

Źródło: opennet.ru