Facebook компани хэш хүснэгтүүдийн нээлттэй эхийн хэрэгжилтийн талаар , санах ойг үр ашигтай зарцуулахаар оновчтой болгосон. F14 нь Facebook-ийн дэд бүтцэд ихэнх төрлийн хэш хүснэгтийг орлох байдлаар ашиглагддаг бөгөөд гүйцэтгэлийг алдагдуулахгүйгээр санах ойн зарцуулалтыг бууруулж чаддаг. F14 нь google::sparse_hash_map хэш хүснэгтүүдээс илт давуу бөгөөд санах ойн хэрэглээний хувьд хамгийн үр дүнтэй гэж тооцогддог. Төслийн код нь C++ хэл дээр бичигдсэн бөгөөд номын санд багтсан болно .
F14 нь 14-тэй давхар хэш дээр суурилсан мөргөлдөөнийг шийдвэрлэх системтэй алгоритмуудыг хэлнэ. (14 үүрний хэлхээг нэг хэш хүснэгтийн нүдэнд хадгалдаг бөгөөд нүднүүдийн хоорондын зайг туслах хэш функцийг ашиглан тооцоолно). Нүдний шүүлтүүрийн ажиллагааг хурдасгахын тулд уг хэрэгжилт нь x2_86 системд зориулсан SSE64 вектор зааврыг, Aarch64-д зориулсан NEON-ийг ашигладаг бөгөөд энэ нь түлхүүрийн гинж бүхий үүр сонгох, гинж доторх түлхүүрүүдийг шигших үйлдлүүдийн гүйцэтгэлийг зэрэгцүүлэх боломжийг олгодог. 14 слот бүхий блокуудыг нэг дор боловсруулдаг бөгөөд энэ нь процессорын кэшийг ашиглах үр ашиг болон мөргөлдөөний тоо хоорондын оновчтой тэнцвэр юм.
F14-ийн онцлог шинж чанар нь өөр өөр өгөгдөл хадгалах стратегийг сонгох чадвар юм.
- F14NodeMap - том болон дунд хэмжээний товчлууруудад хамгийн бага санах ой зарцуулдаг. Элементүүдийг оруулах бүр дээр malloc руу залгах замаар шууд бусаар хадгалахыг баталгаажуулдаг;
- F14ValueMap - жижиг товчлууруудын санах ойн хамгийн бага зарцуулалтыг хангадаг. Элементүүд нь нүднүүдэд өөрөө хадгалагддаг (дотоод). Дунд болон том түлхүүрүүдийн хувьд энэ арга нь мэдэгдэхүйц санах ойд хүргэдэг;
- F14VectorMap - том хүснэгтүүд болон төвөгтэй товчлууруудад илүү хурдан ажилладаг бол энгийн товчлуурууд болон жижиг хүснэгтүүдэд илүү удаан ажилладаг. Элементүүдийг тасралтгүй дүүргэсэн массив болгон багцалж, 32 битийн индекс заагчаар хаягласан;
- F14FastMap бол хосолсон стратеги юм. Хэрэв түлхүүр 24 байтаас бага бол F14ValueMap, илүү бол F14VectorMap-г сонгоно.
Эх сурвалж: opennet.ru