Facebook şirketi hash tablolarının açık kaynak uygulaması hakkında verimli bellek tüketimi için optimize edilmiştir. F14, Facebook altyapısında çoğu karma tablo türünün yerine kullanılır ve performanstan ödün vermeden bellek tüketimini azaltabilir. F14, şu ana kadar bellek tüketimi açısından en verimli olduğu düşünülen google::sparse_hash_map karma tablolarından belirgin şekilde daha iyi performans gösteriyor. Proje kodu C++ ile yazılmıştır ve kütüphaneye dahil edilmiştir. .
F14, 14 ile çift karmaya dayalı çarpışma çözümleme sistemine sahip algoritmaları ifade eder. (14 yuvalık bir zincir, bir karma tablosu hücresinde saklanır ve hücreler arasındaki aralık, yardımcı bir karma işlevi kullanılarak hesaplanır). Uygulama, hücre filtreleme işlemlerini hızlandırmak amacıyla x2_86 sistemleri için SSE64 vektör talimatlarını ve Aarch64 için NEON'u kullanır; bu, anahtar zincirleriyle yuvaların seçilmesi ve zincir içindeki anahtarların elenmesi için işlemlerin yürütülmesinin paralelleştirilmesine olanak tanır. Bir seferde 14 yuvalık bloklar işlenir; bu, işlemci önbelleğinin kullanım verimliliği ile çarpışma sayısı arasındaki en uygun dengedir.
F14'ün özel bir özelliği, farklı veri depolama stratejilerini seçebilme yeteneğidir:
- F14NodeMap - büyük ve orta boyutlu anahtarlar için en az belleği tüketir. Her eklemede malloc çağrısıyla öğelerin dolaylı olarak saklanmasını sağlar;
- F14ValueMap - küçük tuşlar için minimum bellek tüketimi sağlar. Öğeler hücrelerin kendisinde (satır içi) depolanır. Orta ve büyük tuşlar için bu yaklaşım gözle görülür bellek yüküne yol açar;
- F14VectorMap - büyük tablolar ve karmaşık anahtarlar için daha hızlı çalışır, ancak basit anahtarlar ve küçük tablolar için daha yavaş çalışır. Öğeler sürekli olarak doldurulan bir diziye paketlenir ve 32 bitlik bir dizin işaretçisi tarafından adreslenir;
- F14FastMap birleşik bir stratejidir. Anahtar 24 bayttan küçükse F14ValueMap seçilir, daha fazlaysa F14VectorMap seçilir.
Kaynak: opennet.ru