ເຟສບຸກເປີດການປະຕິບັດຕາຕະລາງ F14 hash

ບໍລິສັດເຟສບຸກ ປະ​ກາດ ກ່ຽວກັບການປະຕິບັດແຫຼ່ງເປີດຂອງຕາຕະລາງ hash F14, ເຫມາະສໍາລັບການບໍລິໂພກຄວາມຊົງຈໍາທີ່ມີປະສິດທິພາບ. F14 ຖືກນໍາໃຊ້ໃນໂຄງສ້າງພື້ນຖານຂອງເຟສບຸກເປັນການທົດແທນສໍາລັບປະເພດຂອງຕາຕະລາງ hash ສ່ວນໃຫຍ່ແລະສາມາດຫຼຸດຜ່ອນການບໍລິໂພກຫນ່ວຍຄວາມຈໍາໂດຍບໍ່ມີການເສຍສະລະການປະຕິບັດ. F14 ສັງເກດເຫັນໄດ້ດີກວ່າຕາຕະລາງ hash ຂອງ google::sparse_hash_map, ເຊິ່ງມາຮອດປັດຈຸບັນນີ້ຖືວ່າມີປະສິດທິພາບທີ່ສຸດໃນການບໍລິໂພກຄວາມຊົງຈຳ. ລະຫັດໂຄງການແມ່ນຂຽນໃນ C ++ ແລະຖືກລວມຢູ່ໃນຫ້ອງສະຫມຸດ ໂງ່.

F14 ໝາຍເຖິງສູດການຄິດໄລ່ທີ່ມີລະບົບການແກ້ໄຂການປະທະກັນໂດຍອີງໃສ່ການກົດສອງເທົ່າກັບ 14. ລໍາດັບຂອງຕົວຢ່າງ (ລະບົບຕ່ອງໂສ້ຂອງ 14 ຊ່ອງຖືກເກັບໄວ້ໃນຕາລາງ hash ດຽວ, ແລະໄລຍະຫ່າງລະຫວ່າງເຊລຖືກຄິດໄລ່ໂດຍໃຊ້ຟັງຊັນ hash auxiliary). ເພື່ອເລັ່ງການດໍາເນີນງານການກັ່ນຕອງເຊນ, ການປະຕິບັດການນໍາໃຊ້ຄໍາແນະນໍາ vector SSE2 ສໍາລັບລະບົບ x86_64 ແລະ NEON ສໍາລັບ Aarch64, ເຊິ່ງອະນຸຍາດໃຫ້ຂະຫນານການປະຕິບັດການດໍາເນີນການສໍາລັບການເລືອກສະລັອດຕິງທີ່ມີຕ່ອງໂສ້ທີ່ສໍາຄັນແລະ sifting ອອກຄີພາຍໃນຕ່ອງໂສ້. ຕັນຂອງ 14 ສະລັອດຕິງຖືກປະມວນຜົນໃນເວລາ, ຊຶ່ງເປັນຄວາມສົມດຸນທີ່ດີທີ່ສຸດລະຫວ່າງປະສິດທິພາບຂອງການນໍາໃຊ້ຖານຄວາມຈໍາຂອງໂປເຊດເຊີແລະຈໍານວນຂອງການຂັດກັນ.

ຄຸນນະສົມບັດພິເສດຂອງ F14 ແມ່ນຄວາມສາມາດໃນການເລືອກຍຸດທະສາດການເກັບຮັກສາຂໍ້ມູນທີ່ແຕກຕ່າງກັນ:

• F14NodeMap - ໃຊ້ຫນ່ວຍຄວາມຈໍາຫນ້ອຍທີ່ສຸດສໍາລັບກະແຈຂະຫນາດໃຫຍ່ແລະຂະຫນາດກາງ. ຮັບປະກັນວ່າອົງປະກອບຖືກເກັບໄວ້ໂດຍທາງອ້ອມດ້ວຍການໂທຫາ malloc ໃນແຕ່ລະການແຊກ;
• F14ValueMap - ສະຫນອງການບໍລິໂພກຫນ່ວຍຄວາມຈໍາຫນ້ອຍທີ່ສຸດສໍາລັບກະແຈຂະຫນາດນ້ອຍ. ອົງປະກອບຖືກເກັບໄວ້ໃນເຊລດ້ວຍຕົນເອງ (ໃນແຖວ). ສໍາລັບກະແຈຂະຫນາດກາງແລະຂະຫນາດໃຫຍ່, ວິທີການນີ້ນໍາໄປສູ່ຄວາມຊົງຈໍາ overhead ສັງເກດເຫັນ;
• F14VectorMap - ເຮັດວຽກໄດ້ໄວຂຶ້ນສໍາລັບຕາຕະລາງຂະຫນາດໃຫຍ່ແລະກະແຈທີ່ຊັບຊ້ອນ, ແຕ່ຊ້າກວ່າສໍາລັບຄີງ່າຍດາຍແລະຕາຕະລາງຂະຫນາດນ້ອຍ. ອົງປະກອບຖືກບັນຈຸເຂົ້າໄປໃນອາເຣທີ່ມີປະຊາກອນຢ່າງຕໍ່ເນື່ອງແລະແກ້ໄຂໂດຍຕົວຊີ້ດັດສະນີ 32-bit;
• F14FastMap ແມ່ນຍຸດທະສາດລວມ. ຖ້າລະຫັດແມ່ນຫນ້ອຍກວ່າ 24 bytes, ຫຼັງຈາກນັ້ນເລືອກ F14ValueMap, ແລະຖ້າຫຼາຍ, F14VectorMap ຖືກເລືອກ.

ແຫຼ່ງຂໍ້ມູນ: opennet.ru