Facebook e bula ts'ebetsong ea litafole tsa F14 hash

Khampani ea Facebook e phatlalalitse mabapi le ts'ebetsong ea mohloli o bulehileng oa litafole tsa hash F14, e ntlafalitsoeng bakeng sa tšebeliso e nepahetseng ea memori. F14 e sebelisoa metheong ea Facebook e le sebaka sa mefuta e mengata ea litafole tsa hash mme e ka fokotsa ts'ebeliso ea mohopolo ntle le ho tela ts'ebetso. F14 e sebetsa hantle ho feta litafole tsa google::sparse_hash_map, tseo ho fihlela joale li nkuoang li sebetsa hantle haholo mabapi le tšebeliso ea mohopolo. Khoutu ea morero e ngotsoe ho C ++ 'me e kenyelelitsoe laebraring Booatla.

F14 e bua ka li-algorithms tse nang le sistimi ea tharollo ea likhohlano e thehiloeng ho hashing e habeli le 14 tatellano ea lisampole (ketane ea li-slots tse 14 e bolokoa ka seleng e le 'ngoe ea tafole ea hash,' me nako e pakeng tsa lisele e baloa ho sebelisoa ts'ebetso e thusang ea hashi). Ho potlakisa ts'ebetso ea ho sefa lisele, ts'ebetsong e sebelisa litaelo tsa vector SSE2 bakeng sa litsamaiso tsa x86_64 le NEON bakeng sa Aarch64, e lumellang ho tsamaisana le ts'ebetso ea ts'ebetso ea ho khetha li-slots ka liketane tsa bohlokoa le ho hlopha linotlolo ka har'a ketane. Li-block tsa li-slots tse 14 li sebetsoa ka nako e le 'ngoe, e leng tekanyo e nepahetseng lipakeng tsa katleho ea ho sebelisa cache ea processor le palo ea likhohlano.

Karolo e ikhethang ea F14 ke bokhoni ba ho khetha maano a fapaneng a ho boloka data:

• F14NodeMap - e sebelisa mohopolo o fokolang bakeng sa linotlolo tse kholo le tse mahareng. E netefatsa hore likarolo li bolokoa ka mokhoa o sa tobang ka mohala o eang ho malloc ho kenyelletso ka 'ngoe;
• F14ValueMap - e fana ka tšebeliso e fokolang ea mohopolo bakeng sa linotlolo tse nyane. Lintho li bolokiloe liseleng ka botsona (inline). Bakeng sa linotlolo tse mahareng le tse kholo, mokhoa ona o lebisa mohopolong o hlokomelehang;
• F14VectorMap - e sebetsa ka potlako bakeng sa litafole tse kholo le linotlolo tse rarahaneng, empa butle bakeng sa linotlolo tse bonolo le litafole tse nyane. Lielemente li pakiloe ka har'a sehlopha se lulang se le teng 'me se rarolloa ka index ea 32-bit;
• F14FastMap ke leano le kopaneng. Haeba senotlolo se le ka tlase ho li-byte tse 24, ebe ho khethoa F14ValueMap, 'me haeba ho feta, ho khethoa F14VectorMap.

Source: opennet.ru