Osclaíonn Facebook cur i bhfeidhm táblaí hash F14

Cuideachta Facebook d'fhógair an faoi ​​fhorfheidhmiú foinse oscailte táblaí hash F14, optamaithe le haghaidh tomhaltas cuimhne éifeachtach. Úsáidtear F14 i mbonneagar Facebook mar ionadach don chuid is mó de na táblaí hash agus féadann sé tomhaltas cuimhne a laghdú gan feidhmíocht a íobairt. Is léir go sáraíonn F14 táblaí hash google::sparse_hash_map, a measadh go dtí seo ar na cinn is éifeachtaí ó thaobh tomhaltas cuimhne. Tá cód an tionscadail scríofa i C++ agus tá sé san áireamh sa leabharlann Amaideach.

Tagraíonn F14 d'algartaim le córas réitigh imbhuailte bunaithe ar hashing dúbailte le 14 seichimh samplaí (Stóráiltear slabhra de 14 sliotán i gcill tábla hash amháin, agus ríomhtar an t-eatramh idir cealla ag baint úsáide as feidhm hash cúnta). Chun oibríochtaí scagtha cille a bhrostú, úsáideann an cur i bhfeidhm treoracha veicteoirí SSE2 do chórais x86_64 agus NEON do Aarch64, a cheadaíonn cur i gcrích oibríochtaí chun sliotáin a roghnú le slabhraí tábhachtacha agus eochracha a scagadh amach laistigh den slabhra a chomhthreomharú. Déantar bloic de 14 sliotán a phróiseáil ag an am, agus is é sin an chothromaíocht is fearr idir éifeachtacht úsáid taisce an phróiseálaí agus líon na n-imbhuailtí.

Gné speisialta de F14 is ea an cumas straitéisí stórála sonraí éagsúla a roghnú:

• F14NodeMap - ídíonn an chuimhne is lú d'eochracha móra agus meánmhéide. Cinntíonn sé go ndéantar eilimintí a stóráil go hindíreach le glao go malloc ar gach ionsá;
• F14ValueMap - soláthraíonn sé tomhaltas cuimhne íosta le haghaidh eochracha beaga. Stóráiltear eilimintí sna cealla iad féin (inlíne). I gcás eochracha meánmhéide agus mór, eascraíonn an cur chuige seo chun cinn cuimhne suntasach;
• F14VectorMap - oibríonn sé níos tapúla le haghaidh táblaí móra agus eochracha casta, ach níos moille le haghaidh eochracha simplí agus táblaí beaga. Déantar na heilimintí a phacáil in eagar a bhfuil daonra leanúnach ann agus tugtar treoirphointe 32-giotán orthu;
• Is straitéis chomhcheangailte é F14FastMap. Má tá an eochair níos lú ná 24 bytes, ansin roghnaítear F14ValueMap, agus má tá níos mó, roghnaítear F14VectorMap.

Foinse: oscailtenet.ru