Facebook F14 хэш таблицаларын ишке ашырууну ачат

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

Source: opennet.ru