เฟสบุ๊คของบริษัท ในการใช้งานตารางแฮชโอเพ่นซอร์ส ปรับให้เหมาะสมสำหรับการใช้หน่วยความจำอย่างมีประสิทธิภาพ F14 ใช้ในโครงสร้างพื้นฐานของ Facebook แทนตารางแฮชประเภทส่วนใหญ่ และช่วยให้คุณลดการใช้หน่วยความจำโดยไม่ลดทอนประสิทธิภาพ F14 มีประสิทธิภาพดีกว่าตารางแฮชของ google::sparse_hash_map อย่างเห็นได้ชัด ซึ่งจนถึงขณะนี้ถือว่าหน่วยความจำมีประสิทธิภาพสูงสุด รหัสโครงการเขียนด้วยภาษา C++ และรวมอยู่ในไลบรารี .
F14 หมายถึงอัลกอริทึมที่มีระบบแก้ไขการชนกันโดยยึดตามการแฮชสองครั้งด้วย 14 (เซลล์หนึ่งของตารางแฮชจัดเก็บสายโซ่ 14 ช่อง และช่วงเวลาระหว่างเซลล์จะคำนวณโดยใช้ฟังก์ชันแฮชเสริม) เพื่อเพิ่มความเร็วในการดำเนินการกรองเซลล์ การนำไปใช้งานใช้คำสั่งเวกเตอร์ SSE2 สำหรับระบบ x86_64 และ NEON สำหรับระบบ Aarch64 ซึ่งช่วยให้คุณสามารถขนานการดำเนินการของการเลือกสล็อตกับพวงกุญแจและคีย์การคัดกรองภายในห่วงโซ่ บล็อก 14 สล็อตได้รับการประมวลผลในแต่ละครั้ง ซึ่งเป็นความสมดุลที่เหมาะสมที่สุดระหว่างประสิทธิภาพของการใช้แคชโปรเซสเซอร์และจำนวนการชนกัน
คุณลักษณะของ F14 คือความสามารถในการเลือกกลยุทธ์การจัดเก็บข้อมูลต่างๆ:
- F14NodeMap - ใช้หน่วยความจำน้อยที่สุดสำหรับคีย์ขนาดใหญ่และขนาดกลาง จัดให้มีการจัดเก็บองค์ประกอบทางอ้อมด้วยการเรียกทุกครั้งที่ใส่ฟังก์ชัน malloc
- F14ValueMap - ให้การใช้หน่วยความจำน้อยที่สุดสำหรับคีย์ขนาดเล็ก องค์ประกอบจะถูกเก็บไว้ในเซลล์เอง (อินไลน์) สำหรับคีย์ขนาดกลางและขนาดใหญ่ วิธีการนี้นำไปสู่การโอเวอร์เฮดของหน่วยความจำที่เห็นได้ชัดเจน
- F14VectorMap เร็วกว่าสำหรับตารางขนาดใหญ่และคีย์ที่ซับซ้อน แต่ช้ากว่าสำหรับคีย์ธรรมดาและตารางขนาดเล็ก องค์ประกอบถูกบรรจุลงในอาร์เรย์ที่อยู่ติดกันและระบุด้วยตัวชี้ดัชนี 32 บิต
- F14FastMap เป็นกลยุทธ์แบบผสมผสาน ถ้าคีย์น้อยกว่า 24 ไบต์ F14ValueMap จะถูกเลือก และถ้ามากกว่า จะเลือก F14VectorMap
ที่มา: opennet.ru