الصفحة الرئيسية>المتعلقة بالبرمجة>كود مصدر C#
تنزيل

xxhash - خوارزمية تجزئة سريعة للغاية

xxhash هي خوارزمية تجزئة سريعة للغاية ، معالجة بحدود سرعة ذاكرة الوصول العشوائي. الكود محمول للغاية ، وينتج تجزئة متطابقة في جميع المنصات (Little / Big Endian). تتضمن المكتبة الخوارزميات التالية:

  • XXH32: يولد تجزئة 32 بت ، باستخدام حساب 32 بت
  • XXH64: يولد تجزئة 64 بت ، باستخدام حساب 64 بت
  • XXH3 (منذ v0.8.0 ): يولد 64 أو 128 بت ، باستخدام حساب ناقل. يسمى المتغير 128 بت XXH128.

جميع المتغيرات إكمال جناح اختبار SMHASHER بنجاح الذي يقيم جودة وظائف التجزئة (التصادم والتشتت والعشوائية). كما يتم توفير اختبارات إضافية ، والتي تقيّم خصائص السرعة والتصادم بشكل أكثر شمولية لتجزئة 64 بت.

فرع حالة
يطلق بناء الحالة
ديف بناء الحالة

المعايير

يستخدم النظام المرجعي المعياري وحدة المعالجة المركزية Intel I7-9700K ، ويقوم بتشغيل Ubuntu X64 20.04. يتم تجميع برنامج Benchmark مفتوح المصدر باستخدام clang V10.0 باستخدام علامة -O3 .

اسم التجزئة عرض النطاق الترددي (GB/S) سرعة البيانات الصغيرة جودة تعليق
XXH3 (SSE2) 64 31.5 جيجابايت/ثانية 133.1 10
XXH128 (SSE2) 128 29.6 جيجابايت/ثانية 118.1 10
القراءة المتسلسلة ذاكرة الوصول العشوائي ن/أ 28.0 جيجابايت/ثانية ن/أ ن/أ للرجوع إليها
City64 64 22.0 جيجابايت/ثانية 76.6 10
T1HA2 64 22.0 جيجابايت/ثانية 99.0 9 تصادم أسوأ بقليل
City128 128 21.7 جيجابايت/ثانية 57.7 10
XXH64 64 19.4 جيجابايت/ثانية 71.0 10
Spookyhash 64 19.3 غيغابايت/ثانية 53.2 10
ماما 64 18.0 جيجابايت/ثانية 67.0 9 تصادم أسوأ بقليل
XXH32 32 9.7 جيجابايت/ثانية 71.9 10
City32 32 9.1 غيغابايت/ثانية 66.0 10
Murmur3 32 3.9 جيجابايت/ثانية 56.1 10
سيفاش 64 3.0 جيجابايت/ثانية 43.2 10
FNV64 64 1.2 جيجابايت/ثانية 62.7 5 خصائص الانهيار الفقيرة
Blake2 256 1.1 غيغابايت/ثانية 5.1 10 التشفير
SHA1 160 0.8 جيجابايت/ثانية 5.6 10 التشفير ولكن مكسورة
MD5 128 0.6 جيجابايت/ثانية 7.8 10 التشفير ولكن مكسورة

ملاحظة 1: سرعة البيانات الصغيرة هي تقييم تقريبي لكفاءة الخوارزمية على البيانات الصغيرة. لمزيد من التحليل التفصيلي ، يرجى الرجوع إلى الفقرة التالية.

ملاحظة 2: تتميز بعض الخوارزميات بشكل أسرع من سرعة ذاكرة الوصول العشوائي . في هذه الحالة ، لا يمكنهم الوصول إلى إمكاناتهم السريعة فقط عندما تكون الإدخال بالفعل في ذاكرة التخزين المؤقت لوحدة المعالجة المركزية (L3 أو أفضل). خلاف ذلك ، فإنهم أقصى حد على حد سرعة ذاكرة الوصول العشوائي.

بيانات صغيرة

الأداء على البيانات الكبيرة هو جزء واحد فقط من الصورة. التجزئة مفيدة للغاية في الإنشاءات مثل جداول التجزئة ومرشحات بلوم. في حالات الاستخدام هذه ، من المتكرر لتجزئة الكثير من البيانات الصغيرة (بدءًا من بايت بضع بايت). يمكن أن يكون أداء الخوارزمية مختلفًا تمامًا عن مثل هذه السيناريوهات ، حيث تصبح أجزاء من الخوارزمية ، مثل التهيئة أو الانتهاء ، تكلفة ثابتة. كما يصبح تأثير سوء التهيج للفرع أكثر حاضرًا.

تم تصميم XXH3 للأداء الممتاز على كل من المدخلات الطويلة والصغيرة ، والتي يمكن ملاحظتها في الرسم البياني التالي:

XXH3 ، الكمون ، الحجم العشوائي

للحصول على تحليل أكثر تفصيلاً ، يرجى زيارة wiki: https://github.com/cyan4973/xxhash/wiki/performance-comparison#benchmarks-concentrating-on-small-data-

جودة

السرعة ليست الخاصية الوحيدة التي تهم. يجب أن تحترم قيم التجزئة المنتجة خصائص التشتت والاحتفال العشوائي ، بحيث يمكن استخدام أي قسم فرعي منه لنشر جدول أو فهرس بشكل أقصى ، وكذلك تقليل كمية التصادم إلى الحد الأدنى من المستوى النظري ، بعد مفارقة عيد الميلاد.

تم اختبار xxHash مع مجموعة اختبار Smhasher الممتازة من أوستن Appleby ، ويجري جميع الاختبارات ، مما يضمن مستويات جودة معقولة. كما أنه يجتاز اختبارات ممتدة من شوكات جديدة من Smhasher ، والتي تتميز سيناريوهات وظروف إضافية.

أخيرًا ، توفر XXHash اختبار تصادمها الضخم ، قادرًا على إنشاء ومقارنة مليارات التجزئة لاختبار حدود خوارزميات التجزئة 64 بت. على هذه الجبهة أيضًا ، يتميز XXHash بنتائج جيدة ، تمشيا مع مفارقة عيد الميلاد. تم توثيق تحليل أكثر تفصيلا في الويكي.

بناء المعدلات

يمكن تعيين وحدات الماكرو التالية في وقت التجميع لتعديل سلوك libxxhash . يتم تعطيلها عمومًا افتراضيًا.

  • XXH_INLINE_ALL : اجعل جميع الوظائف inline ، يتم تضمين التنفيذ مباشرة داخل xxhash.h . وظائف التحديد مفيدة للسرعة ، لا سيما للمفاتيح الصغيرة. يكون ذلك فعالًا للغاية عندما يتم التعبير عن طول المفتاح باعتباره ثابتًا لوقت الترجمة ، مع ملاحظة تحسين الأداء في نطاق +200 ٪. انظر هذا المقال للحصول على التفاصيل.
  • XXH_PRIVATE_API : نفس النتيجة مثل XXH_INLINE_ALL . لا تزال متاحة للدعم القديم. يؤكد الاسم على أنه لن يتم تصدير أسماء الرموز XXH_* .
  • XXH_STATIC_LINKING_ONLY : يتيح الوصول إلى إعلان الحالة الداخلية ، المطلوب للتخصيص الثابت. غير متوافق مع الارتباط الديناميكي ، بسبب مخاطر التغيرات ABI.
  • XXH_NAMESPACE : بادئة جميع الرموز بقيمة XXH_NAMESPACE . يمكن لهذا الماكرو استخدام مجموعة الأحرف القابلة للتجميع فقط. مفيد للتهرب من تصادمات تسمية الرموز ، في حالة شوائب متعددة لرمز المصدر XXHash. لا تزال تطبيقات العميل تستخدم أسماء الوظائف العادية ، حيث يتم ترجمة الرموز تلقائيًا من خلال xxhash.h .
  • XXH_FORCE_ALIGN_CHECK : استخدم مسار قراءة مباشر أسرع عند محاذاة الإدخال. يمكن أن يؤدي هذا الخيار إلى تحسن كبير في الأداء على البنية غير قادرة على تحميل الذاكرة من العناوين غير المحددة عندما يحدث إدخال إلى التجزئة على حدود 32 أو 64 بت. إنه (قليلاً) ضار على النظام الأساسي مع أداء جيد للوصول إلى الذاكرة غير محاذاة (نفس التعليمات لكل من الوصول المحاذاة وغير المحاذاة). يتم تعطيل هذا الخيار تلقائيًا على x86 و x64 و aarch64 ، وتمكينه على جميع الأنظمة الأساسية الأخرى.
  • XXH_FORCE_MEMORY_ACCESS : تستخدم الطريقة الافتراضية 0 ترميز memcpy() محمول. تستخدم الطريقة 1 سمة packed خاصة بـ GCC ، والتي يمكن أن توفر أداء أفضل لبعض الأهداف. القوات 2 القوات غير المحددة ، والتي ليست متوافقة معتاد ، ولكن قد تكون في بعض الأحيان الطريقة الوحيدة لاستخراج أداء أفضل للقراءة. تستخدم الطريقة 3 عملية بتجميع ، والتي هي الأفضل للمترجمين القدامى التي لا تضمن memcpy() أو أنظمة endian الكبيرة دون تعليمات byteswap.
  • XXH_CPU_LITTLE_ENDIAN : افتراضيًا ، يتم تحديد Endianness بواسطة اختبار وقت التشغيل في وقت الترجمة. إذا ، لسبب ما ، لا يمكن للمترجم تبسيط اختبار وقت التشغيل ، فقد يكلف الأداء. من الممكن تخطي الكشف التلقائي وتوضح ببساطة أن الهندسة المعمارية هي القليل من الإنديان من خلال تعيين هذا الماكرو إلى 1. وضعه على 0 حالات كبيرة.
  • XXH_ENABLE_AUTOVECTORIZE : قد يتم تشغيل التخصيص التلقائي لـ XXH32 و XXH64 ، اعتمادًا على إمكانيات متجه وحدة المعالجة المركزية وإصدار المترجم. ملاحظة: يميل التمييز التلقائي إلى أن يتم تشغيله بسهولة أكبر مع الإصدارات الحديثة من clang . بالنسبة لـ XXH32 أو SSE4.1 أو المكافئ (NEON) كافية ، في حين يتطلب XXH64 AVX512. لسوء الحظ ، فإن التهيئة التلقائية تضر بشكل عام بأداء XXH. لهذا السبب ، يحاول رمز مصدر XXHASH منع التخلص التلقائي افتراضيًا. ومع ذلك ، تتطور الأنظمة ، وهذا الاستنتاج ليس وشيكًا. على سبيل المثال ، تم الإبلاغ عن أن وحدات المعالجة المركزية 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 ، لذلك من المفيد تقليل الحجم الثنائي للتطبيقات التي لا تستخدم XXH3 .
  • XXH_NO_LONG_LONG : يزيل تجميع الخوارزميات التي تعتمد على أنواع long long 64 بت تتضمن XXH3 و XXH64 . سيتم تجميع XXH32 فقط. مفيد للأهداف (البنية والمجموعات المترجمة) دون دعم 64 بت.
  • XXH_NO_STREAM : يعطل واجهة برمجة تطبيقات البث ، مما يحد من المكتبة على متغيرات اللقطة الفردية فقط.
  • 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 : يجعل الكود صغيرًا قدر الإمكان ، قد يبكي الأداء

بناء المعدلات الخاصة بـ XXH3

  • 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 : تعطيل الجذور المسبقة. قد تؤدي بعض المنصات أو المواقف بشكل أفضل دون الإصابة المسبقة. XXH3 فقط.

متغيرات Makefile

عند تجميع واجهة سطر الأوامر xxhsum باستخدام make ، يمكن أيضًا تعيين متغيرات البيئة التالية:

  • DISPATCH=1 : استخدم xxh_x86dispatch.c ، للاختيار تلقائيًا بين تعليمات scalar أو sse2 أو avx2 أو avx512 في وقت التشغيل ، اعتمادًا على المضيف المحلي. هذا الخيار صالح فقط لأنظمة x86 / x64 .
  • XXH_1ST_SPEED_TARGET : حدد هدف السرعة الأولي ، معبر عنه في MB/s ، لاختبار السرعة الأولى في الوضع القياسي. سيقوم المعيار بضبط الهدف بتكرارات لاحقة ، ولكن يتم إجراء الاختبار الأول "عمياء" من خلال استهداف هذه السرعة. تم تعيينه حاليًا على 10 ميجابايت/ثانية ، لدعم منصات بطيئة للغاية (محاكاة).
  • NODE_JS=1 : عند تجميع xxhsum لـ node.js مع emscripten ، يربط هذا مكتبة NODERAWFS للوصول إلى نظام الملفات غير المقيد وتصحيحات isatty لجعل أداة سطر الأوامر الكشف بشكل صحيح. هذا يجعل الثنائي محددًا لـ Node.js.

بناء xxhash - باستخدام VCPKG

يمكنك تنزيل وتثبيت xxhash باستخدام مدير التبعية VCPKG: 

 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 Easy كمكتبة libxxhash وواجهة سطر أوامر xxhsum .

شكر خاص

  • Takayuki Matsuoka ، AKA @T -Mat ، لإنشاء xxhsum -c ودعم كبير خلال إصدارات XXH المبكرة
  • Mathias Westerdahl ، الملقب jcash ، لتقديم الإصدار الأول من XXH64
  • Devin Hussey ، AKA @easyaspi314 ، من أجل تحسينات منخفضة المستوى على XXH3 و XXH128
يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل