c++ - ما هي أسرع وظيفة التجزئة للمؤشرات؟




performance pointers (4)

الإجابة الصحيحة من وجهة النظر النظرية هي: "استخدام std::hash الذي من المحتمل أن يكون جيدًا ليكون جيدًا كما يحصل ، وإذا كان ذلك غير قابل للتطبيق ، فاستخدم وظيفة تجزئة جيدة بدلاً من واحدة سريعة. وظيفة هاش لا يهم بقدر جودتها " .

الإجابة العملية هي: "استخدام std::hash ، وهو pss-poor ، ولكن مع ذلك أداء جيد بشكل مدهش."

TL، DR
بعد أن أصبحت محل اهتمام ، ركضت حوالي 30 ساعة من المعايير خلال عطلة نهاية الأسبوع. من بين أمور أخرى ، حاولت أن أحصل على حالة متوسطة مقابل أسوأ حالة وحاولت إكراه std::unordered_map في سلوك أسوأ الحالات من خلال إعطائها تلميحات سيئة عمداً على تعدادات الدلو فيما يتعلق بحجم المجموعة المدرج.

قارنت تجزئات سيئة ( std::hash<T*> ) إلى تجزئات الأغراض العامة المعروفة من نوعية جيدة عموما (djb2 ، sdbm) ، فضلا عن اختلافات هذه التي تمثل طول المدخلات قصير جدا ، وإلى تجزئات يعتقد بوضوح أن تستخدم في هاشتل (murmur2 و murmur3) ، وجزء piss-poor التي هي في الواقع أسوأ من لا تجزئة على الإطلاق لأنها رمي بعيدا الكون.
بما أن أقل 2-3 بتات تكون صفرًا دائمًا على المؤشرات بسبب المحاذاة ، فقد رأيت أنه من المفيد اختبار نوبة عمل بسيطة كـ "هاش" ، لذلك سيتم استخدام المعلومات غير الصفرية فقط ، في حالة استخدام المثال على سبيل المثال فقط البتات N الأدنى. تبين أنه من أجل التحولات المعقولة (لقد حاولت أيضا التحولات غير المعقولة!) هذا يؤدي في الواقع بشكل جيد.

الموجودات

بعض النتائج التي توصلت إليها كانت معروفة وغير مفاجئة ، والبعض الآخر مثير للدهشة:

  • من الصعب توقع ما هو التجزئة "الجيدة". كتابة مهام هاش جيدة أمر صعب. ليس من المستغرب ، حقيقة معروفة ، وثبت مرة أخرى.
  • لا يوجد تفرد واحد يتفوق بشكل كبير على كل الآخرين في كل سيناريو. لا يوجد تفرد واحد يتفوق بشكل كبير على جميع الآخرين 80٪ من الوقت. كانت النتيجة الأولى متوقعة ، والثانية هي مفاجئة.
  • من الصعب حقاً الضغط على std::unordered_map بشكل سيئ. حتى عندما تعطى تلميحات سيئة عن عمد إلى جرد التهم التي تجبر على إعادة تجزئته ، فإن الأداء العام ليس أسوأ بكثير. فقط وظائف هاش الأكثر سوءًا التي تتخلص من معظم الإنتروبيا بطريقة سخيفة تقريبًا ، يمكنها التأثير بشكل كبير على الأداء بأكثر من 10 إلى 20٪ (مثل right_shift_12 ، والتي لا تؤدي عمليًا إلا إلى 12 قيمة مميزة right_shift_12 ! ليس من المستغرب أن خريطة تجزئة تدير حوالي 100 مرة أبطأ في هذه الحالة - نحن نقوم بشكل أساسي بالبحث عن الوصول العشوائي في قائمة مرتبطة.).
  • بعض النتائج "المضحكة" هي بالتأكيد بسبب تفاصيل التنفيذ. يستخدم تنفيذي (GCC) عدد دلائل أكبر من 2 ني نيوتن أكبر من 2 ، ويدرج القيم ذات التجزئة الأولية في أول الأمر في قوائم مرتبطة.
  • إن تخصص std::hash<T*> مثير للشفقة الصريحة لدول مجلس التعاون الخليجي ( reinterpret_cast بسيطة). funnily، a functor الذي يعمل الشيء المتماثل بشكل منتظم يؤدي بشكل أسرع في الإدخالات وأبطأ في الوصول العشوائي . والفارق صغير (12 جزءًا من الثانية في اختبار تجريبي من 8 إلى 10 ثوانٍ) ، ولكنه ليس ضجيجًا ، ولكنه موجود بشكل مستمر - ربما يرتبط بإعادة ترتيب التعليمات أو خط الأنابيب. من المذهل كيف أن نفس الشفرة ذاتها (التي هي أيضًا عملية no-op) تؤدي بشكل مختلف بشكل مختلف في سيناريوهين مختلفين.
  • لا تؤدي التجزئات المثيرة للشفقة أداءً أسوأ بكثير من التجزئات أو التجزئات "الجيدة" المصممة بشكل صريح لجداول التجزئة. في الواقع ، نصف الوقت ، هم الأفضل أداء ، أو بين أعلى 3.
  • وظائف هاش "الأفضل" نادرًا ما تؤدي إلى أفضل أداء عام.
  • تجدر الإشارة إلى أن التجزئة التي تم نشرها كإجابات في سؤال SO هذه هي موافق بشكل عام. وهي جيدة في المتوسط ​​، ولكنها لا تفوق على std::hash . عادة سوف تهبط في الأعلى 3-4.
  • التجزئات الفقيرة ضعيفة إلى حد ما على ترتيب الإدراج (يؤدي بشكل أسوأ عند الإدراج العشوائي والبحث العشوائي بعد الإدراج العشوائي) في حين أن التجزئات "الجيدة" أكثر مرونة لتأثير ترتيب الإدراج (اختلاف بسيط أو لا فرق) ، ولكن الأداء العام هو لا يزال أبطأ قليلا.

اختبار الإعداد

تم إجراء الاختبار ليس فقط أي قيم محاذاة لـ 4 بايت أو 8 بايت (أو أيا كان) ، ولكن للعناوين الفعلية التي تم الحصول عليها من تخصيص مجموعة كاملة من العناصر الموجودة على كومة الذاكرة المؤقتة ، وتخزين العناوين كما يوفرها المُخصص في std::vector (تم حذف الكائنات ، لم تكن هناك حاجة إليها).
تم إدراج العناوين في std::unordered_map المخصصة حديثًا لكل اختبار بالترتيب المخزن في المتجه ، مرة واحدة في الترتيب الأصلي ("تسلسلي") ومرة ​​واحدة بعد تطبيق std::random_shuffle على المتجه.

تم إجراء الاختبارات لمجموعات من 50000 و 1000000 كائن بحجم 4 و 16 و 64 و 256 و 1024 (النتائج لـ 64 تم حذفها هنا للإيجاز ، كما لو كنت تتوقع في مكان ما في الوسط بين 16 و 256 - StackOverflow يسمح فقط بعرض 30 ألف حرف).
تم تنفيذ جناح اختبار 3 مرات ، والنتائج متفاوتة بنسبة 3 أو 4 ميلي ثانية هنا وهناك ، ولكن متطابقة عموما. النتائج المنشورة هنا هي الجولة الأخيرة.

ترتيب الإدراج في الاختبار "العشوائي" بالإضافة إلى نمط الوصول (في كل اختبار) هو شبه عشوائي ، ولكنه مطابق تمامًا لكل وظيفة هاش في الاختبار التجريبي.

التوقيتات تحت معايير التجزئة هي لجمع 4.000.000.000 قيمة تجزئة في متغير صحيح.

insert العمود هو الوقت بالمللي ثانية لـ 50 تكرارًا لإنشاء std::unordered_map ، وإدراج 50،000 و 1000000 عنصر على التوالي ، وتدمير الخريطة.

access للعمود هو الوقت بالمللي ثانية للقيام بـ 1000000 عملية بحث عن عنصر شبه عشوائي في "المتجه" متبوعًا بالبحث عن هذا العنوان في unordered_map .
يتضمن هذا التوقيت على متوسط ​​misage ذاكرة التخزين المؤقت للوصول إلى عنصر عشوائي في vector ، على الأقل بالنسبة لمجموعة البيانات الكبيرة (مجموعة بيانات صغيرة تتناسب تمامًا مع L2).

جميع الأوقات على 2.66 غيغاهرتز إنتل Core2 ، ويندوز 7 ، مجلس التعاون الخليجي 4.8.1 / MinGW-w64_32. دقة الموقت @ 1ms.

مصدر الرمز

كود المصدر متاح على Ideone ، مرة أخرى بسبب الحد الأقصى لعدد الحروف في Stackoverflow 30k.

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

نتائج الإختبار

Benchmarking hash funcs...
std::hash                 2576      
reinterpret_cast          2561      
djb2                      13970     
djb2_mod                  13969     
sdbm                      10246     
yet_another_lc            13966     
murmur2                   11373     
murmur3                   15129     
simple_xorshift           7829      
double_xorshift           13567     
right_shift_2             5806      
right_shift_3             5866      
right_shift_4             5705      
right_shift_5             5691      
right_shift_8             5795      
right_shift_12            5728      
MyTemplatePointerHash1    5652      
BasileStarynkevitch       4315      

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 421        6988       
reinterpret_cast          408        7083       
djb2                      451        8875       
djb2_mod                  450        8815       
sdbm                      455        8673       
yet_another_lc            443        8292       
murmur2                   478        9006       
murmur3                   490        9213       
simple_xorshift           460        8591       
double_xorshift           477        8839       
right_shift_2             416        7144       
right_shift_3             422        7145       
right_shift_4             414        6811       
right_shift_5             425        8006       
right_shift_8             540        11787      
right_shift_12            1501       49604      
MyTemplatePointerHash1    410        7138       
BasileStarynkevitch       445        8014       

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 443        7570       
reinterpret_cast          436        7658       
djb2                      473        8791       
djb2_mod                  472        8766       
sdbm                      472        8817       
yet_another_lc            458        8419       
murmur2                   479        9005       
murmur3                   491        9205       
simple_xorshift           464        8591       
double_xorshift           476        8821       
right_shift_2             441        7724       
right_shift_3             440        7716       
right_shift_4             450        8061       
right_shift_5             463        8653       
right_shift_8             649        16320      
right_shift_12            3052       114185     
MyTemplatePointerHash1    438        7718       
BasileStarynkevitch       453        8140       

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 8945       32801      
reinterpret_cast          8796       33251      
djb2                      11139      54855      
djb2_mod                  11041      54831      
sdbm                      11459      36849      
yet_another_lc            14258      57350      
murmur2                   16300      39024      
murmur3                   16572      39221      
simple_xorshift           14930      38509      
double_xorshift           16192      38762      
right_shift_2             8843       33325      
right_shift_3             8791       32979      
right_shift_4             8818       32510      
right_shift_5             8775       30436      
right_shift_8             10505      35960      
right_shift_12            30481      91350      
MyTemplatePointerHash1    8800       33287      
BasileStarynkevitch       12885      37829      

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 12183      33424      
reinterpret_cast          12125      34000      
djb2                      22693      51255      
djb2_mod                  22722      51266      
sdbm                      15160      37221      
yet_another_lc            24125      51850      
murmur2                   16273      39020      
murmur3                   16587      39270      
simple_xorshift           16031      38628      
double_xorshift           16233      38757      
right_shift_2             11181      33896      
right_shift_3             10785      33660      
right_shift_4             10615      33204      
right_shift_5             10357      38216      
right_shift_8             15445      100348     
right_shift_12            73773      1044919    
MyTemplatePointerHash1    11091      33883      
BasileStarynkevitch       15701      38092      

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 415        8243       
reinterpret_cast          422        8321       
djb2                      445        8730       
djb2_mod                  449        8696       
sdbm                      460        9439       
yet_another_lc            455        9003       
murmur2                   475        9109       
murmur3                   482        9313       
simple_xorshift           463        8694       
double_xorshift           465        8900       
right_shift_2             416        8402       
right_shift_3             418        8405       
right_shift_4             423        8366       
right_shift_5             421        8347       
right_shift_8             453        9195       
right_shift_12            666        18008      
MyTemplatePointerHash1    433        8191       
BasileStarynkevitch       466        8443       

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 450        8135       
reinterpret_cast          457        8208       
djb2                      470        8736       
djb2_mod                  476        8698       
sdbm                      483        9420       
yet_another_lc            476        8953       
murmur2                   481        9089       
murmur3                   486        9283       
simple_xorshift           466        8663       
double_xorshift           468        8865       
right_shift_2             456        8301       
right_shift_3             456        8302       
right_shift_4             453        8337       
right_shift_5             457        8340       
right_shift_8             505        10379      
right_shift_12            1099       34923      
MyTemplatePointerHash1    464        8226       
BasileStarynkevitch       466        8372       

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 9548       35362      
reinterpret_cast          9635       35869      
djb2                      10668      37339      
djb2_mod                  10763      37311      
sdbm                      11126      37145      
yet_another_lc            11597      39944      
murmur2                   16296      39029      
murmur3                   16432      39280      
simple_xorshift           16066      38645      
double_xorshift           16108      38778      
right_shift_2             8966       35953      
right_shift_3             8916       35949      
right_shift_4             8973       35504      
right_shift_5             8941       34997      
right_shift_8             9356       31233      
right_shift_12            13831      45799      
MyTemplatePointerHash1    8839       31798      
BasileStarynkevitch       15349      38223      

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 14756      36237      
reinterpret_cast          14763      36918      
djb2                      15406      38771      
djb2_mod                  15551      38765      
sdbm                      14886      37078      
yet_another_lc            15700      40290      
murmur2                   16309      39024      
murmur3                   16432      39381      
simple_xorshift           16177      38625      
double_xorshift           16073      38750      
right_shift_2             14732      36961      
right_shift_3             14170      36965      
right_shift_4             13687      37295      
right_shift_5             11978      35135      
right_shift_8             11498      46930      
right_shift_12            25845      268052     
MyTemplatePointerHash1    10150      32046      
BasileStarynkevitch       15981      38143      

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 432        7957       
reinterpret_cast          429        8036       
djb2                      462        8970       
djb2_mod                  453        8884       
sdbm                      460        9110       
yet_another_lc            466        9015       
murmur2                   495        9147       
murmur3                   494        9300       
simple_xorshift           479        8792       
double_xorshift           477        8948       
right_shift_2             430        8120       
right_shift_3             429        8132       
right_shift_4             432        8196       
right_shift_5             437        8324       
right_shift_8             425        8050       
right_shift_12            519        11291      
MyTemplatePointerHash1    425        8069       
BasileStarynkevitch       468        8496       

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 462        7956       
reinterpret_cast          456        8046       
djb2                      490        9002       
djb2_mod                  483        8905       
sdbm                      482        9116       
yet_another_lc            492        8982       
murmur2                   492        9120       
murmur3                   492        9276       
simple_xorshift           477        8761       
double_xorshift           477        8903       
right_shift_2             458        8116       
right_shift_3             459        8124       
right_shift_4             462        8281       
right_shift_5             463        8370       
right_shift_8             458        8069       
right_shift_12            662        16244      
MyTemplatePointerHash1    459        8091       
BasileStarynkevitch       472        8476       

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 9756       34368      
reinterpret_cast          9718       34897      
djb2                      10935      36894      
djb2_mod                  10820      36788      
sdbm                      11084      37857      
yet_another_lc            11125      37996      
murmur2                   16522      39078      
murmur3                   16461      39314      
simple_xorshift           15982      38722      
double_xorshift           16151      38868      
right_shift_2             9611       34997      
right_shift_3             9571       35006      
right_shift_4             9135       34750      
right_shift_5             8978       32878      
right_shift_8             8688       30276      
right_shift_12            10591      35827      
MyTemplatePointerHash1    8721       30265      
BasileStarynkevitch       15524      38315      

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 14169      36078      
reinterpret_cast          14096      36637      
djb2                      15373      37492      
djb2_mod                  15279      37438      
sdbm                      15531      38247      
yet_another_lc            15924      38779      
murmur2                   16524      39109      
murmur3                   16422      39280      
simple_xorshift           16119      38735      
double_xorshift           16136      38875      
right_shift_2             14319      36692      
right_shift_3             14311      36776      
right_shift_4             13932      35682      
right_shift_5             12736      34530      
right_shift_8             9221       30663      
right_shift_12            15506      98465      
MyTemplatePointerHash1    9268       30697      
BasileStarynkevitch       15952      38349      

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 421        7863       
reinterpret_cast          419        7953       
djb2                      457        8983       
djb2_mod                  455        8927       
sdbm                      445        8609       
yet_another_lc            446        8892       
murmur2                   492        9090       
murmur3                   507        9294       
simple_xorshift           467        8687       
double_xorshift           472        8872       
right_shift_2             432        8009       
right_shift_3             432        8014       
right_shift_4             435        7998       
right_shift_5             442        8099       
right_shift_8             432        7914       
right_shift_12            462        8911       
MyTemplatePointerHash1    426        7744       
BasileStarynkevitch       467        8417       

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 452        7948       
reinterpret_cast          456        8018       
djb2                      489        9037       
djb2_mod                  490        8992       
sdbm                      477        8795       
yet_another_lc            491        9179       
murmur2                   502        9078       
murmur3                   507        9273       
simple_xorshift           473        8671       
double_xorshift           480        8873       
right_shift_2             470        8105       
right_shift_3             470        8100       
right_shift_4             476        8333       
right_shift_5             468        8065       
right_shift_8             469        8094       
right_shift_12            524        10216      
MyTemplatePointerHash1    451        7826       
BasileStarynkevitch       472        8419       

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 10910      38432      
reinterpret_cast          10892      38994      
djb2                      10499      38985      
djb2_mod                  10507      38983      
sdbm                      11318      37450      
yet_another_lc            11740      38260      
murmur2                   16960      39544      
murmur3                   16816      39647      
simple_xorshift           16096      39021      
double_xorshift           16419      39183      
right_shift_2             10219      38909      
right_shift_3             10012      39036      
right_shift_4             10642      40284      
right_shift_5             10116      38678      
right_shift_8             9083       32914      
right_shift_12            9376       31586      
MyTemplatePointerHash1    8777       30129      
BasileStarynkevitch       16036      38913      

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 16304      38695      
reinterpret_cast          16241      39641      
djb2                      16377      39533      
djb2_mod                  16428      39526      
sdbm                      15402      37811      
yet_another_lc            16180      38730      
murmur2                   16679      39355      
murmur3                   16792      39586      
simple_xorshift           16196      38965      
double_xorshift           16371      39127      
right_shift_2             16445      39263      
right_shift_3             16598      39421      
right_shift_4             16378      39839      
right_shift_5             15517      38442      
right_shift_8             11589      33547      
right_shift_12            11992      49041      
MyTemplatePointerHash1    9052       30222      
BasileStarynkevitch       16163      38829      

https://code.i-harness.com

الحاويات المستندة إلى جدول التجزئة عبارة عن مجموعة unordered_map سريعة جدًا (على سبيل المثال ، unordered_set ، unordered_set ).

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

تعتبر المؤشرات نوعًا بسيطًا ، وهي في الأساس قيمة 4/8 بايت والتي تحدد كائنًا بشكل فريد. تكمن المشكلة في أن استخدام عنوان نتيجة دالة هاش ليس فعالًا نظرًا لأن عدة LSB تكون صفراً.

مثال:

struct MyVoidPointerHash {
    size_t operator()(const void* val) const {
        return (size_t)val;
    }
};

التنفيذ الأسرع هو فقدان عدد قليل من البتات:

struct MyVoidPointerHash2 {
    size_t operator()(const void* val) const {
        return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
    }
};

وقد أنتج هذا الأخير زيادة في الأداء بنسبة 10-20٪ على تطبيق كبير يستخدم مجموعات وخرائط البعير بعشرات الآلاف من العناصر التي يتم بناؤها وتطهيرها بشكل متكرر.

يمكن للشخص تقديم مخطط أفضل لمؤشرات التجزئة؟

يجب أن تكون الوظيفة كما يلي:

  1. بسرعة! ويجب أن تتماشى جيدًا.
  2. عرض توزيع معقول ، مسموح اصطدامات نادرة.

تحديث - نتائج القياس

قمت بتشغيل مجموعتين من الاختبارات ، واحدة لـ int* فئة له حجم 4KB. النتائج مثيرة جدا للاهتمام.

لقد استخدمت std::unordered_set لجميع الاختبارات مع حجم البيانات التي 16MB التي تم تخصيصها في مكالمة واحدة new . تم تشغيل الخوارزمية الأولى مرتين للتأكد من أن مخابئ التخزين سريعة قدر المستطاع وأن وحدة المعالجة المركزية تعمل بأقصى سرعة.

الإعداد: VS2013 (x64) و i7-2600 و Windows 8.1 x64.

  • VS2013 وظيفة التجزئة الافتراضية
  • Hash1: return (size_t)(val);
  • Hash2: return '(size_t)(val) >> 3;
  • Hash3 (BasileStarynkevitch): uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15)); uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15));
  • Hash4 (Roddy): uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16)); uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16));
  • Hash5 (egur):

الشفرة:

template<typename Tval>
struct MyTemplatePointerHash1 {
    size_t operator()(const Tval* val) const {
        static const size_t shift = (size_t)log2(1 + sizeof(Tval));
        return (size_t)(val) >> shift;
    }
};

الاختبار 1 - int* :

  • استغرق الافتراضي VS2013 1292ms
  • Hash1 تولى 742ms
  • استغرق Hash2 343ms
  • استغرق Hash3 1008ms
  • تولى Hash4 629ms
  • استغرق Hash5 350MS

الاختبار 1 - 4K_class* :

  • استغرق الافتراضي VS2013 0.423ms
  • أخذت Hash1 23.889ms
  • استغرق Hash2 6.331ms
  • تولى Hash3 0.366ms
  • تولى Hash4 0.390ms
  • استغرق Hash5 0.290ms

Update2:

الفائز حتى الآن هو وظيفة التجزئة (Hash5) templated. أفضل مستوى أداء للسرعة لأحجام القطع المختلفة.

تحديث 3: إضافة وظيفة التجزئة الافتراضية للخط الأساسي. تبين أنه بعيد عن المثالية.


بعد ترك هذا السؤال يكمن لفترة من الوقت ، سأقوم بنشر أفضل دالة تجزئة لمؤشرات حتى الآن:

template<typename Tval>
struct MyTemplatePointerHash1 {
    size_t operator()(const Tval* val) const {
        static const size_t shift = (size_t)log2(1 + sizeof(Tval));
        return (size_t)(val) >> shift;
    }
};

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


لا يمكن التغلب على الحل الخاص بك في مضمار السباق للأداء (لا من أجل char ، ولا للبنية ذات الحجم 1024) ، ولكن بمعنى الصحة هناك بعض التحسينات:

#include <iostream>
#include <new>
#include <algorithm>
#include <unordered_set>
#include <chrono>

#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <cmath>

namespace
{

template< std::size_t argument, std::size_t base = 2, bool = (argument < base) >
constexpr std::size_t log = 1 + log< argument / base, base >;

template< std::size_t argument, std::size_t base >
constexpr std::size_t log< argument, base, true > = 0;

}

struct pointer_hash
{

    template< typename type >
    constexpr
    std::size_t
    operator () (type * p) const noexcept
    {
        return static_cast< std::size_t >(reinterpret_cast< std::uintptr_t >(p) >> log< std::max(sizeof(type), alignof(type)) >);
    }

};

template< typename type = std::max_align_t, std::size_t i = 0 >
struct alignas(alignof(type) << i) S
{

};

int
main()
{
    constexpr std::size_t _16M = (1 << 24);
    S<> * p = new S<>[_16M]{};
    auto latch = std::chrono::high_resolution_clock::now();
    {
        std::unordered_set< S<> *, pointer_hash > s;
        for (auto * pp = p; pp < p + _16M; ++pp) {
            s.insert(pp);
        }
    }
    std::cout << std::chrono::duration_cast< std::chrono::milliseconds >(std::chrono::high_resolution_clock::now() - latch).count() << "ms" << std::endl;
    delete [] p;
    return EXIT_SUCCESS;
}

ومن الواضح أن الإجابة تعتمد على النظام والمعالج (على وجه الخصوص ، بسبب حجم الصفحة وحجم الكلمة). أنا أقترح

  struct MyVoidPointerHash {
      size_t operator()(const void* val) const {
         uintptr_t ad = (uintptr_t) val;
         return (size_t) ((13*ad) ^ (ad >> 15));
      }
  };

تكمن الفكرة في أن حجم الصفحة غالباً ما يكون في العديد من الأنظمة 4 كيلوبايت (أي 2 12 ) ، لذا فإن التحول الصحيح >>15 سيضع أجزاء عنوان مهمة في الأجزاء السفلى. 13* هو في الغالب للمتعة (ولكن 13 هو رئيس الوزراء) ولتبديل المزيد من البتات. الحصري أو ^ يخلط بت وبسرعة حقا. لذا فإن البتات السفلية للتجزئة هي خليط من العديد من البتات (العالية والمنخفضة) من المؤشر.

أنا لا أدعي بعد أن وضعت الكثير من "العلم" في وظائف هاش هذه. لكنهم غالباً ما يعملون بشكل جيد. YMMV. أود أن أخمن أنه يجب عليك تجنب تفعيل ASLR !







hash