XXHash เป็นอัลกอริทึมแฮชที่รวดเร็วมากการประมวลผลที่ขีด จำกัด ความเร็ว RAM รหัสเป็นแบบพกพาสูงและผลิตแฮชที่เหมือนกันในทุกแพลตฟอร์ม (endian น้อย / ใหญ่) ห้องสมุดมีอัลกอริทึมต่อไปนี้:
v0.8.0 ): สร้างแฮช 64 หรือ 128 บิตโดยใช้คณิตศาสตร์เวกเตอร์ ตัวแปร 128 บิตเรียกว่า XXH128ตัวแปรทั้งหมดประสบความสำเร็จในการทำชุดทดสอบ Smhasher ซึ่งประเมินคุณภาพของฟังก์ชั่นแฮช (การชนการกระจายและการสุ่ม) การทดสอบเพิ่มเติมซึ่งประเมินความเร็วและคุณสมบัติการชนกันอย่างละเอียดยิ่งขึ้นของแฮช 64 บิตก็มีให้เช่นกัน
| สาขา | สถานะ |
|---|---|
| ปล่อย | ![]() |
| คนกิน | ![]() |
ระบบอ้างอิงมาตรฐานใช้ CPU Intel I7-9700K และเรียกใช้ Ubuntu X64 20.04 โปรแกรมเกณฑ์มาตรฐานโอเพ่นซอร์สถูกรวบรวมด้วย clang V10.0 โดยใช้ Flag -O3
| ชื่อแฮช | ความกว้าง | แบนด์วิดท์ (GB/S) | ความเร็วข้อมูลขนาดเล็ก | คุณภาพ | การแสดงความคิดเห็น |
|---|---|---|---|---|---|
| XXH3 (SSE2) | 64 | 31.5 gb/s | 133.1 | 10 | |
| XXH128 (SSE2) | 128 | 29.6 gb/s | 118.1 | 10 | |
| Ram Sequential Read | N/A | 28.0 gb/s | N/A | N/A | สำหรับการอ้างอิง |
| City64 | 64 | 22.0 gb/s | 76.6 | 10 | |
| t1ha2 | 64 | 22.0 gb/s | 99.0 | 9 | การชนที่แย่ลงเล็กน้อย |
| เมือง 128 | 128 | 21.7 gb/s | 57.7 | 10 | |
| xxh64 | 64 | 19.4 gb/s | 71.0 | 10 | |
| spookyhash | 64 | 19.3 gb/s | 53.2 | 10 | |
| แม่ | 64 | 18.0 gb/s | 67.0 | 9 | การชนที่แย่ลงเล็กน้อย |
| xxh32 | 32 | 9.7 gb/s | 71.9 | 10 | |
| City32 | 32 | 9.1 gb/s | 66.0 | 10 | |
| เสียงพึมพำ 3 | 32 | 3.9 gb/s | 56.1 | 10 | |
| การผสม | 64 | 3.0 gb/s | 43.2 | 10 | |
| FNV64 | 64 | 1.2 gb/s | 62.7 | 5 | คุณสมบัติหิมะถล่มไม่ดี |
| เบลค 2 | 256 | 1.1 gb/s | 5.1 | 10 | เกี่ยวกับการเข้ารหัสลับ |
| sha1 | 160 | 0.8 gb/s | 5.6 | 10 | การเข้ารหัส แต่เสีย |
| MD5 | 128 | 0.6 gb/s | 7.8 | 10 | การเข้ารหัส แต่เสีย |
หมายเหตุ 1: ความเร็วข้อมูลขนาดเล็กเป็นการประเมิน คร่าวๆ ของประสิทธิภาพของอัลกอริทึมในข้อมูลขนาดเล็ก สำหรับการวิเคราะห์โดยละเอียดเพิ่มเติมโปรดดูย่อหน้าถัดไป
หมายเหตุ 2: อัลกอริทึมบางอย่างมีคุณสมบัติ เร็วกว่าความเร็ว RAM ในกรณีนี้พวกเขาสามารถเข้าถึงศักยภาพความเร็วสูงสุดของพวกเขาเมื่ออินพุตอยู่ในแคช CPU (L3 หรือดีกว่า) แล้ว มิฉะนั้นพวกเขาจะสูงสุดในขีด จำกัด ความเร็ว RAM
ประสิทธิภาพของข้อมูลขนาดใหญ่เป็นเพียงส่วนหนึ่งของภาพ การแฮชยังมีประโยชน์มากในการก่อสร้างเช่นตารางแฮชและตัวกรองบาน ในกรณีการใช้งานเหล่านี้บ่อยครั้งที่จะแฮชข้อมูลขนาดเล็กจำนวนมาก (เริ่มต้นที่ไม่กี่ไบต์) ประสิทธิภาพของอัลกอริทึมอาจแตกต่างกันมากสำหรับสถานการณ์ดังกล่าวเนื่องจากส่วนต่าง ๆ ของอัลกอริทึมเช่นการเริ่มต้นหรือการสรุปกลายเป็นค่าใช้จ่ายคงที่ ผลกระทบของการคาดการณ์ผิดของสาขาก็กลายเป็นปัจจุบันมากขึ้น
XXH3 ได้รับการออกแบบมาเพื่อประสิทธิภาพที่ยอดเยี่ยมทั้งอินพุตทั้งยาวและขนาดเล็กซึ่งสามารถสังเกตได้ในกราฟต่อไปนี้:

สำหรับการวิเคราะห์โดยละเอียดเพิ่มเติมกรุณาเยี่ยมชม wiki: https://github.com/cyan4973/xxhash/wiki/performance-comparison#benchmarks-concentrating-on-small-data-
ความเร็วไม่ใช่คุณสมบัติเดียวที่สำคัญ ค่าแฮชที่ผลิตจะต้องเคารพการกระจายตัวที่ยอดเยี่ยมและคุณสมบัติการสุ่มเพื่อให้ส่วนย่อยใด ๆ ของมันสามารถนำมาใช้เพื่อกระจายตารางหรือดัชนีสูงสุดรวมถึงลดปริมาณการชนในระดับทฤษฎีขั้นต่ำตามความขัดแย้งวันเกิด
xxHash ได้รับการทดสอบกับชุดทดสอบ Smhasher ที่ยอดเยี่ยมของ Austin Appleby และผ่านการทดสอบทั้งหมดเพื่อให้มั่นใจว่าระดับคุณภาพที่สมเหตุสมผล นอกจากนี้ยังผ่านการทดสอบเพิ่มเติมจาก Smhasher ที่ใหม่กว่าซึ่งมีสถานการณ์และเงื่อนไขเพิ่มเติม
ในที่สุด XXHASH ให้ผู้ทดสอบการชนจำนวนมากของตัวเองสามารถสร้างและเปรียบเทียบแฮชหลายพันล้านเพื่อทดสอบขีด จำกัด ของอัลกอริทึมแฮช 64 บิต ด้านหน้านี้ XXHash มีผลลัพธ์ที่ดีสอดคล้องกับความขัดแย้งวันเกิด การวิเคราะห์รายละเอียดเพิ่มเติมมีการบันทึกไว้ในวิกิ
มาโครต่อไปนี้สามารถตั้งค่าได้ตามเวลาการรวบรวมเพื่อปรับเปลี่ยนพฤติกรรมของ libxxhash โดยทั่วไปจะถูกปิดใช้งานโดยค่าเริ่มต้น
XXH_INLINE_ALL : ทำฟังก์ชั่นทั้งหมด inline การใช้งานจะรวมอยู่ใน xxhash.h โดยตรง ฟังก์ชั่นการ inlining เป็นประโยชน์ต่อความเร็วโดยเฉพาะอย่างยิ่งสำหรับปุ่มขนาดเล็ก มัน มีประสิทธิภาพอย่างมาก เมื่อความยาวของคีย์แสดงเป็น ค่าคงที่เวลารวบรวม โดยมีการปรับปรุงประสิทธิภาพที่สังเกตได้ในช่วง +200% ดูบทความนี้สำหรับรายละเอียดXXH_PRIVATE_API : ผลลัพธ์เดียวกันกับ XXH_INLINE_ALL ยังคงมีให้สำหรับการสนับสนุนมรดก ชื่อเน้นว่าชื่อสัญลักษณ์ XXH_* จะไม่ถูกส่งออกXXH_STATIC_LINKING_ONLY : ให้การเข้าถึงการประกาศสถานะภายในซึ่งจำเป็นสำหรับการจัดสรรแบบคงที่ เข้ากันไม่ได้กับการเชื่อมโยงแบบไดนามิกเนื่องจากความเสี่ยงของการเปลี่ยนแปลง ABIXXH_NAMESPACE : คำนำหน้าสัญลักษณ์ทั้งหมดที่มีค่าของ XXH_NAMESPACE แมโครนี้สามารถใช้ชุดอักขระที่รวบรวมได้เท่านั้น มีประโยชน์ในการหลีกเลี่ยงการชนกันของการตั้งชื่อสัญลักษณ์ในกรณีที่มีการรวมซอร์สโค้ดของ XXHash หลายรายการ แอปพลิเคชันไคลเอนต์ยังคงใช้ชื่อฟังก์ชั่นปกติเนื่องจากสัญลักษณ์จะถูกแปลโดยอัตโนมัติผ่าน xxhash.hXXH_FORCE_ALIGN_CHECK : ใช้เส้นทางการอ่านโดยตรงที่เร็วขึ้นเมื่อมีการจัดแนวอินพุต ตัวเลือกนี้อาจส่งผลให้มีการปรับปรุงประสิทธิภาพอย่างมากต่อสถาปัตยกรรมที่ไม่สามารถโหลดหน่วยความจำจากที่อยู่ที่ไม่ได้จัดตำแหน่งเมื่ออินพุตไปยังแฮชเกิดขึ้นเพื่อจัดตำแหน่งตามขอบเขต 32 หรือ 64 บิต มันเป็นอันตราย (เล็กน้อย) บนแพลตฟอร์มที่มีประสิทธิภาพการเข้าถึงหน่วยความจำที่ไม่ได้จัดตำแหน่งที่ดี (คำสั่งเดียวกันสำหรับการเข้าถึงทั้งแบบจัดตำแหน่งและไม่สอดคล้อง) ตัวเลือกนี้ถูกปิดใช้งานโดยอัตโนมัติใน x86 , x64 และ aarch64 และเปิดใช้งานบนแพลตฟอร์มอื่น ๆ ทั้งหมดXXH_FORCE_MEMORY_ACCESS : วิธีเริ่มต้น 0 ใช้สัญกรณ์พกพา memcpy() วิธีการที่ 1 ใช้แอตทริบิวต์ packed เฉพาะ GCC ซึ่งสามารถให้ประสิทธิภาพที่ดีขึ้นสำหรับเป้าหมายบางอย่าง วิธีที่ 2 บังคับให้อ่านแบบไม่สอดคล้องกันซึ่งไม่สอดคล้องกับมาตรฐาน แต่บางครั้งอาจเป็นวิธีเดียวที่จะแยกประสิทธิภาพการอ่านได้ดีขึ้น วิธีที่ 3 ใช้การดำเนินการ byteshift ซึ่งดีที่สุดสำหรับคอมไพเลอร์เก่าซึ่งไม่ได้อินไลน์ memcpy() หรือระบบใหญ่-เอดินโดยไม่ต้องใช้คำสั่ง byteswapXXH_CPU_LITTLE_ENDIAN : โดยค่าเริ่มต้น Endianness จะถูกกำหนดโดยการทดสอบรันไทม์ที่ได้รับการแก้ไขในเวลาคอมไพล์ หากด้วยเหตุผลบางอย่างคอมไพเลอร์ไม่สามารถทำให้การทดสอบรันไทม์ง่ายขึ้นก็อาจทำให้ประสิทธิภาพมีประสิทธิภาพ เป็นไปได้ที่จะข้ามการตรวจจับอัตโนมัติและเพียงระบุว่าสถาปัตยกรรมนั้นมีน้อยที่สุดโดยการตั้งค่าแมโครนี้เป็น 1 การตั้งค่าเป็น 0 รัฐใหญ่XXH_ENABLE_AUTOVECTORIZE : Auto-Vectorization อาจถูกเรียกใช้สำหรับ XXH32 และ XXH64 ขึ้นอยู่กับความสามารถของเวกเตอร์ CPU และเวอร์ชันคอมไพเลอร์ หมายเหตุ: Auto-Vectorization มีแนวโน้มที่จะถูกกระตุ้นได้ง่ายขึ้นด้วย clang ดังล่าสุด สำหรับ XXH32, SSE4.1 หรือเทียบเท่า (นีออน) ก็เพียงพอแล้วในขณะที่ XXH64 ต้องการ AVX512 น่าเสียดายที่การฉีดยาอัตโนมัติโดยทั่วไปจะเป็นอันตรายต่อประสิทธิภาพของ XXH ด้วยเหตุนี้ซอร์สโค้ด XXHASH จึงพยายามป้องกันการใช้ Vectorization อัตโนมัติโดยค่าเริ่มต้น ที่ถูกกล่าวว่าระบบพัฒนาขึ้นและข้อสรุปนี้ไม่ได้เกิดขึ้น ตัวอย่างเช่นมีรายงานว่าซีพียู ZEN4 ล่าสุดมีแนวโน้มที่จะปรับปรุงประสิทธิภาพด้วยการทำให้เป็นเวกเตอร์ ดังนั้นหากคุณต้องการหรือต้องการทดสอบรหัสเวกเตอร์คุณสามารถเปิดใช้งานการตั้งค่าสถานะนี้: มันจะลบรหัสป้องกันที่ไม่มีการใช้ยาออกไปทำให้มีแนวโน้มมากขึ้นสำหรับ XXH32 และ XXH64 ที่จะถูกนำไปใช้อัตโนมัติXXH32_ENDJMP : สลับขั้นตอนการสรุปหลายสาขาของ XXH32 ด้วยการกระโดดครั้งเดียว นี่เป็นสิ่งที่ไม่พึงปรารถนาสำหรับประสิทธิภาพโดยเฉพาะอย่างยิ่งเมื่อแฮทช์อินพุตที่มีขนาดสุ่ม แต่ขึ้นอยู่กับสถาปัตยกรรมและคอมไพเลอร์ที่แน่นอนการกระโดดอาจให้ประสิทธิภาพที่ดีขึ้นเล็กน้อยสำหรับอินพุตขนาดเล็ก ปิดใช้งานโดยค่าเริ่มต้นXXH_IMPORT : MSVC เฉพาะ: ควรกำหนดไว้สำหรับการเชื่อมโยงแบบไดนามิกเท่านั้นเนื่องจากป้องกันข้อผิดพลาดการเชื่อมโยงXXH_NO_STDLIB : ปิดการใช้งานการเรียกใช้ฟังก์ชั่น <stdlib.h> โดยเฉพาะอย่างยิ่ง malloc() และ free() libxxhash 's XXH*_createState() จะล้มเหลวและส่งคืน NULL เสมอ แต่แฮชชอตเดียว (เช่น XXH32() ) หรือสตรีมมิ่งโดยใช้สถานะที่ได้รับการจัดสรรแบบคงที่ยังคงทำงานตามที่คาดไว้ การสร้างธงนี้มีประโยชน์สำหรับสภาพแวดล้อมที่ฝังตัวโดยไม่ต้องจัดสรรแบบไดนามิกXXH_DEBUGLEVEL : เมื่อตั้งค่าเป็นค่าใด ๆ > = 1, เปิดใช้งานคำสั่ง assert() สิ่งนี้ (เล็กน้อย) การดำเนินการช้าลง แต่อาจช่วยค้นหาข้อบกพร่องในระหว่างการดีบัก XXH_NO_XXH3 : ลบสัญลักษณ์ที่เกี่ยวข้องกับ XXH3 (ทั้ง 64 และ 128 บิต) จากไบนารีที่สร้างขึ้น XXH3 เป็นผู้สนับสนุนที่ใหญ่ที่สุดในขนาด libxxhash ดังนั้นจึงมีประโยชน์ในการลดขนาดไบนารีสำหรับแอปพลิเคชันที่ไม่ได้ใช้ XXH3XXH_NO_LONG_LONG : ลบการรวบรวมอัลกอริทึมที่อาศัย long long 64 บิตซึ่งรวมถึง XXH3 และ XXH64 จะรวบรวม XXH32 เท่านั้น มีประโยชน์สำหรับเป้าหมาย (สถาปัตยกรรมและคอมไพเลอร์) โดยไม่ต้องรองรับ 64 บิตXXH_NO_STREAM : ปิดใช้งานสตรีมมิ่ง API จำกัด ไลบรารีให้เป็นตัวแปรนัดเดียวเท่านั้นXXH_NO_INLINE_HINTS : โดยค่าเริ่มต้น XXHASH ใช้ __attribute__((always_inline)) และ __forceinline เพื่อปรับปรุงประสิทธิภาพด้วยราคารหัส การกำหนดแมโครนี้เป็น 1 จะทำเครื่องหมายฟังก์ชั่นภายในทั้งหมดเป็น static ที่ช่วยให้คอมไพเลอร์ตัดสินใจว่าจะอินไลน์ฟังก์ชั่นหรือไม่ สิ่งนี้มีประโยชน์มากเมื่อปรับให้เหมาะสมสำหรับขนาดไบนารีที่เล็กที่สุดและถูกกำหนดโดยอัตโนมัติเมื่อรวบรวมด้วย -O0 , -Os , -Oz หรือ -fno-inline บน GCC และ Clang สิ่งนี้อาจเพิ่มประสิทธิภาพขึ้นอยู่กับคอมไพเลอร์และสถาปัตยกรรมXXH_SIZE_OPT : 0 : ค่าเริ่มต้นเพิ่มประสิทธิภาพสำหรับความเร็ว 1 : ค่าเริ่มต้นสำหรับ -Os และ -Oz : ปิดใช้งานแฮ็คความเร็วสำหรับการเพิ่มประสิทธิภาพขนาด 2 : ทำให้โค้ดมีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้ประสิทธิภาพอาจร้องไห้ XXH_VECTOR : เลือกชุดคำสั่งเวกเตอร์ด้วยตนเอง (ค่าเริ่มต้น: เลือกอัตโนมัติในเวลารวบรวม) ชุดคำสั่งที่มีอยู่คือ XXH_SCALAR , XXH_SSE2 , XXH_AVX2 , XXH_AVX512 , XXH_NEON และ XXH_VSX คอมไพเลอร์อาจต้องใช้แฟล็กเพิ่มเติมเพื่อให้แน่ใจว่าการสนับสนุนที่เหมาะสม (ตัวอย่างเช่น gcc บน X86_64 ต้องการ -mavx2 สำหรับ AVX2 หรือ -mavx512f สำหรับ AVX512 )XXH_PREFETCH_DIST : เลือกระยะการดึงข้อมูลล่วงหน้า สำหรับการปรับตัวใกล้กับโลหะเข้ากับแพลตฟอร์มฮาร์ดแวร์ที่เฉพาะเจาะจง xxh3 เท่านั้นXXH_NO_PREFETCH : ปิดการใช้งาน prefetching แพลตฟอร์มหรือสถานการณ์บางอย่างอาจทำงานได้ดีขึ้นโดยไม่ต้องทำการดึงข้อมูลล่วงหน้า xxh3 เท่านั้น เมื่อรวบรวมอินเทอร์เฟซบรรทัดคำสั่ง xxhsum โดยใช้ make ตัวแปรสภาพแวดล้อมต่อไปนี้สามารถตั้งค่าได้:
DISPATCH=1 : ใช้ xxh_x86dispatch.c เพื่อเลือกโดยอัตโนมัติระหว่างชุดคำสั่ง scalar , sse2 , avx2 หรือ avx512 ที่รันไทม์ ขึ้นอยู่กับโฮสต์ท้องถิ่น ตัวเลือกนี้ใช้ได้เฉพาะสำหรับระบบ x86 / x64XXH_1ST_SPEED_TARGET : เลือกเป้าหมายความเร็วเริ่มต้นที่แสดงใน MB/S สำหรับการทดสอบความเร็วแรกในโหมดมาตรฐาน เกณฑ์มาตรฐานจะปรับเป้าหมายในการทำซ้ำครั้งต่อไป แต่การทดสอบครั้งแรกจะทำ "สุ่มสี่สุ่มห้า" โดยกำหนดเป้าหมายความเร็วนี้ ปัจจุบันตั้งค่าอนุรักษ์ไว้ที่ 10 MB/s เพื่อรองรับแพลตฟอร์มที่ช้ามาก (จำลอง)NODE_JS=1 : เมื่อรวบรวม xxhsum สำหรับ node.js ด้วย emscripten สิ่งนี้จะเชื่อมโยงไลบรารี NODERAWFS สำหรับการเข้าถึงระบบไฟล์ที่ไม่ จำกัด และ patches isatty เพื่อให้ยูทิลิตี้บรรทัดคำสั่งตรวจจับเทอร์มินัลอย่างถูกต้อง สิ่งนี้ทำให้ไบนารีจำเพาะต่อ Node.jsคุณสามารถดาวน์โหลดและติดตั้ง XXHASH โดยใช้ VCPKG Perdency Manager:
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash
พอร์ต XXHASH ใน VCPKG ได้รับการปรับปรุงโดยสมาชิกในทีม Microsoft และผู้มีส่วนร่วมในชุมชน หากเวอร์ชันล้าสมัยโปรดสร้างปัญหาหรือดึงคำขอบนที่เก็บ VCPKG
ตัวอย่างที่ง่ายที่สุดเรียกตัวแปร XXHash 64 บิตเป็นฟังก์ชั่นหนึ่งนัดที่สร้างค่าแฮชจากบัฟเฟอร์เดียวและเรียกใช้จากโปรแกรม C/C ++:
#include "xxhash.h"
(...)
XXH64_hash_t hash = XXH64 ( buffer , size , seed );
}ตัวแปรสตรีมมิ่งมีส่วนร่วมมากขึ้น แต่ทำให้สามารถให้ข้อมูลเพิ่มขึ้น:
#include "stdlib.h" /* abort() */
#include "xxhash.h"
XXH64_hash_t calcul_hash_streaming ( FileHandler fh )
{
/* create a hash state */
XXH64_state_t * const state = XXH64_createState ();
if ( state == NULL ) abort ();
size_t const bufferSize = SOME_SIZE ;
void * const buffer = malloc ( bufferSize );
if ( buffer == NULL ) abort ();
/* Initialize state with selected seed */
XXH64_hash_t const seed = 0 ; /* or any other value */
if ( XXH64_reset ( state , seed ) == XXH_ERROR ) abort ();
/* Feed the state with input data, any size, any number of times */
(...)
while ( /* some data left */ ) {
size_t const length = get_more_data ( buffer , bufferSize , fh );
if ( XXH64_update ( state , buffer , length ) == XXH_ERROR ) abort ();
(...)
}
(...)
/* Produce the final hash value */
XXH64_hash_t const hash = XXH64_digest ( state );
/* State could be re-used; but in this example, it is simply freed */
free ( buffer );
XXH64_freeState ( state );
return hash ;
} ไฟล์ไลบรารี xxhash.c และ xxhash.h ได้รับใบอนุญาต BSD ยูทิลิตี้ xxhsum ได้รับใบอนุญาต GPL
นอกเหนือจากรุ่นอ้างอิง C แล้ว XXHASH ยังมีให้บริการจากภาษาการเขียนโปรแกรมที่แตกต่างกันมากมายด้วยผู้สนับสนุนที่ยอดเยี่ยม พวกเขาอยู่ที่นี่
การแจกแจงจำนวนมากรวมตัวจัดการแพ็คเกจซึ่งช่วยให้การติดตั้ง XXHASH ง่ายขึ้นเนื่องจากทั้งไลบรารี libxxhash และอินเตอร์เฟสบรรทัดคำสั่ง xxhsum
xxhsum -c และการสนับสนุนที่ยอดเยี่ยมในช่วง XXH ต้น ๆXXH64 เวอร์ชันแรกXXH3 และ XXH128