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