Mae Facebook yn agor gweithredu tablau stwnsh F14

Cwmni Facebook cyhoeddi am weithredu tablau hash ffynhonnell agored F14, wedi'i optimeiddio ar gyfer defnydd cof effeithlon. Defnyddir F14 yn seilwaith Facebook yn lle'r rhan fwyaf o fathau o dablau hash a gall leihau'r defnydd o gof heb aberthu perfformiad. Mae F14 yn amlwg yn perfformio'n well na thablau stwnsh google::sparse_hash_map, sydd hyd yma wedi'u hystyried fel y rhai mwyaf effeithlon o ran defnydd cof. Mae cod y prosiect wedi'i ysgrifennu yn C++ ac wedi'i gynnwys yn y llyfrgell Ffolineb.

Mae F14 yn cyfeirio at algorithmau gyda system datrys gwrthdrawiadau yn seiliedig ar stwnsio dwbl gyda 14 dilyniannau o samplau (mae cadwyn o 14 slot yn cael ei storio mewn un gell bwrdd hash, a chyfrifir yr egwyl rhwng celloedd gan ddefnyddio swyddogaeth hash ategol). Er mwyn cyflymu gweithrediadau hidlo celloedd, mae'r gweithrediad yn defnyddio cyfarwyddiadau fector SSE2 ar gyfer systemau x86_64 a NEON ar gyfer Aarch64, sy'n caniatáu cyfochri gweithrediadau ar gyfer dewis slotiau gyda chadwyni allweddol a didoli allweddi o fewn y gadwyn. Mae blociau o 14 slot yn cael eu prosesu ar y tro, sef y cydbwysedd gorau posibl rhwng effeithlonrwydd defnyddio storfa'r prosesydd a nifer y gwrthdrawiadau.

Nodwedd arbennig o F14 yw'r gallu i ddewis gwahanol strategaethau storio data:

• F14NodeMap - yn defnyddio'r cof lleiaf ar gyfer allweddi mawr a chanolig. Yn sicrhau bod elfennau'n cael eu storio'n anuniongyrchol gyda galwad i malloc ar bob mewnosodiad;
• F14ValueMap - yn darparu defnydd cof lleiaf posibl ar gyfer allweddi bach. Mae elfennau'n cael eu storio yn y celloedd eu hunain (mewn llinell). Ar gyfer allweddi canolig a mawr, mae'r dull hwn yn arwain at gorbenion cof amlwg;
• F14VectorMap - yn gweithio'n gyflymach ar gyfer tablau mawr ac allweddi cymhleth, ond yn arafach ar gyfer allweddi syml a thablau bach. Mae'r elfennau'n cael eu pacio i mewn i arae sy'n cael ei boblogi'n barhaus ac yn cael sylw gan bwyntydd mynegai 32-did;
• Mae F14FastMap yn strategaeth gyfun. Os yw'r allwedd yn llai na 24 beit, yna dewisir F14ValueMap, ac os yw'n fwy, dewisir F14VectorMap.

Ffynhonnell: opennet.ru