Facebook-ը բացում է F14 հեշ աղյուսակների ներդրումը

Facebook ընկերություն հայտարարվեց Հեշ աղյուսակների բաց կոդով ներդրման մասին F14, օպտիմիզացված հիշողության արդյունավետ սպառման համար: F14-ն օգտագործվում է Facebook-ի ենթակառուցվածքում՝ որպես հեշ աղյուսակների շատ տեսակների փոխարինում և կարող է նվազեցնել հիշողության սպառումը, առանց կատարողականության զոհաբերության: F14-ը նկատելիորեն գերազանցում է google::sparse_hash_map հեշ աղյուսակներին, որոնք մինչ այժմ համարվում էին ամենաարդյունավետը հիշողության սպառման առումով: Ծրագրի կոդը գրված է C++-ով և ներառված է գրադարանում Folly.

F14-ը վերաբերում է ալգորիթմներին բախման լուծման համակարգով, որը հիմնված է կրկնակի հեշինգի վրա 14-ով նմուշների հաջորդականությունը (14 սլոտներից բաղկացած շղթան պահվում է հեշ աղյուսակի մեկ բջիջում, և բջիջների միջև ընդմիջումը հաշվարկվում է օժանդակ հեշ ֆունկցիայի միջոցով): Բջիջների ֆիլտրման գործողությունները արագացնելու համար ներդրումն օգտագործում է վեկտորային հրահանգներ SSE2 x86_64 համակարգերի համար և NEON՝ Aarch64-ի համար, որոնք թույլ են տալիս զուգահեռացնել գործողությունների կատարումը՝ առանցքային շղթաներով սլոտներ ընտրելու և շղթայում ստեղները մաղելու համար: Միաժամանակ մշակվում են 14 սլոտների բլոկներ, ինչը օպտիմալ հավասարակշռություն է պրոցեսորի քեշի օգտագործման արդյունավետության և բախումների քանակի միջև:

F14-ի հատուկ առանձնահատկությունը տվյալների պահպանման տարբեր ռազմավարություններ ընտրելու ունակությունն է.

• F14NodeMap - սպառում է ամենաքիչ հիշողությունը մեծ և միջին չափի ստեղների համար: Ապահովում է տարրերի անուղղակի պահեստավորում՝ յուրաքանչյուր ներդիրում malloc ֆունկցիայի կանչով.
• F14ValueMap - ապահովում է հիշողության նվազագույն սպառում փոքր ստեղների համար: Տարրերը պահվում են հենց բջիջներում (inline): Միջին և մեծ ստեղների համար այս մոտեցումը հանգեցնում է նկատելի հիշողության ավելացման.
• F14VectorMap - ավելի արագ է աշխատում մեծ սեղանների և բարդ ստեղների համար, բայց ավելի դանդաղ՝ պարզ ստեղների և փոքր սեղանների համար: Տարրերը փաթեթավորվում են շարունակաբար բնակեցված զանգվածի մեջ և հասցեագրվում են 32-բիթանոց ցուցիչով;
• F14FastMap-ը համակցված ռազմավարություն է: Եթե ​​ստեղնը 24 բայթից պակաս է, ապա ընտրված է F14ValueMap, իսկ եթե ավելին է՝ F14VectorMap:

Source: opennet.ru