Ua wehe ʻo Facebook i ka hoʻokō ʻana i nā papa hash F14

hui Facebook haʻiʻia ka e pili ana i ka hoʻokō open source o nā papa hash F14, i hoʻopaʻa ʻia no ka hoʻohana pono ʻana i ka hoʻomanaʻo. Hoʻohana ʻia ʻo F14 i ka ʻōnaehana Facebook ma ke ʻano he pani no ka hapa nui o nā papa hash a hiki ke hōʻemi i ka hoʻohana ʻana i ka hoʻomanaʻo me ka ʻole o ka kaumaha ʻana i ka hana. Ua ʻoi aku ka maikaʻi o ka F14 i nā papa hash google::sparse_hash_map, i manaʻo ʻia ʻo ia ka mea ʻoi aku ka maikaʻi o ka hoʻohana ʻana i ka hoʻomanaʻo. Ua kākau ʻia ke code papahana ma C++ a hoʻokomo ʻia i loko o ka waihona Ka lapuwale.

ʻO ka F14 e pili ana i nā algorithms me kahi ʻōnaehana hoʻonā hui ʻana e pili ana i ka hashing pālua me 14 nā kaʻina o nā laʻana (Hoʻopaʻa ʻia kahi kaulahao o 14 mau mākia i loko o hoʻokahi keena papaʻaina hash, a helu ʻia ka wā ma waena o nā cell me ka hoʻohana ʻana i kahi hana hash kōkua). No ka hoʻokō wikiwiki ʻana i nā hana kānana cell, hoʻohana ka hoʻokō ʻana i nā ʻōkuhi vector SSE2 no nā ʻōnaehana x86_64 a me NEON no Aarch64, e ʻae ai i ka hoʻohālikelike ʻana i ka hoʻokō ʻana i nā hana no ke koho ʻana i nā pahu me nā kaulahao kī a me ke kānana ʻana i nā kī i loko o ke kaulahao. Hoʻopili ʻia nā poloka o 14 slots i ka manawa, ʻo ia ke kaulike maikaʻi loa ma waena o ka pono o ka hoʻohana ʻana i ka cache processor a me ka helu o nā hui.

ʻO kahi hiʻohiʻona kūikawā o F14 ka hiki ke koho i nā hoʻolālā mālama ʻikepili like ʻole:

• F14NodeMap - hoʻopau i ka mea hoʻomanaʻo liʻiliʻi no nā kī nui a me waena. E hōʻoia i ka mālama pono ʻole ʻana o nā mea me kahi kelepona i malloc ma kēlā me kēia hoʻokomo;
• F14ValueMap - hāʻawi i ka hoʻohana hoʻomanaʻo liʻiliʻi no nā kī liʻiliʻi. Mālama ʻia nā mea i loko o nā keena ponoʻī (inline). No nā kī liʻiliʻi a nui, alakaʻi kēia ala i ka hoʻomanaʻo ʻike ma luna;
• F14VectorMap - hana wikiwiki no nā papa nui a me nā kī paʻakikī, akā ʻoi aku ka lohi no nā kī maʻalahi a me nā papa liʻiliʻi. Hoʻopili ʻia nā mea i loko o kahi pūʻulu hoʻomau ʻia a kamaʻilio ʻia e kahi kuhikuhi kuhikuhi 32-bit;
• ʻO F14FastMap kahi hoʻolālā hui. Inā emi ke kī ma mua o 24 bytes, koho ʻia ʻo F14ValueMap, a inā ʻoi aku, koho ʻia ʻo F14VectorMap.

Source: opennet.ru