c++ استبدال متغير عدد الحلقات 32 بت مع 64 بت يقدم انحرافات الأداء المجنونة




performance optimization (7)

كنت أبحث عن أسرع طريقة popcount كبيرة من البيانات. واجهت تأثيرًا غريبًا للغاية : أدى تغيير متغير الحلقة من unsigned إلى uint64_t إلى انخفاض الأداء بنسبة 50٪ على جهاز الكمبيوتر.

المؤشر

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

كما ترى ، نقوم بإنشاء مخزن مؤقت للبيانات العشوائية ، حيث يكون الحجم x ميجابايت حيث تتم قراءة x من سطر الأوامر. بعد ذلك ، نقوم بالتكرار فوق المخزن المؤقت ونستخدم إصدارًا غير popcount x 86 popcount intrinsic لتنفيذ popcount. للحصول على نتيجة أكثر دقة ، سنقوم بتخصيص 10000 مرة. نحن نقيس أوقات الفاكسات. في الحالة العلوية ، يكون متغير الحلقة الداخلية unsigned ، وفي الحالة السفلية ، يكون متغير الحلقة الداخلية uint64_t . اعتقدت أن هذا يجب أن لا فرق ، ولكن العكس هو الحال.

النتائج (مجنون تماما)

أنا تجميع ذلك مثل هذا (نسخة ز + +: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

فيما يلي النتائج الموجودة على المعالج الأساسي الخاص بي Haswell Core i7-4770K CPU @ 3.50 GHz ، وهو test 1 الجاري test 1 (أي 1 ميجابايت من البيانات العشوائية):

  • غير موقعة 41959360000 0.401554 ثانية 26.113 جيجابايت / ثانية
  • uint64_t 41959360000 0.759822 sec 13.8003 GB / s

كما ترون ، فإن الناتج من الإصدار uint64_t هو فقط نصف الإصدار unsigned ! يبدو أن المشكلة هي أنه يتم إنشاء تجميع مختلف ، ولكن لماذا؟ أولاً ، فكرت في خطأ في برنامج التحويل البرمجي ، لذا حاولت استخدام clang++ (إصدار Ubuntu Clang 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

النتيجة: test 1

  • غير موقعة 41959360000 0.398293 ثانية 26.3267 GB / s
  • uint64_t 41959360000 0.680954 sec 15.3986 GB / s

لذا ، فهي تقريباً نفس النتيجة وما زالت غريبة. لكن الآن أصبح الأمر غريبًا جدًا. أقوم باستبدال حجم المخزن المؤقت الذي تمت قراءته من الإدخال باستخدام ثابت 1 ، لذلك أقوم بتغيير:

uint64_t size = atol(argv[1]) << 20;

إلى

uint64_t size = 1 << 20;

وبالتالي ، يعرف المحول البرمجي الآن حجم المخزن المؤقت في وقت التحويل البرمجي. ربما يمكنه إضافة بعض التحسينات! فيما يلي أرقام لـ g++ :

  • غير موقعة 41959360000 0.509156 ثانية 20.5944 جيجابايت / ثانية
  • uint64_t 41959360000 0.508673 ثانية 20.6139 جيجابايت / ثانية

الآن ، كلا الإصدارين بسرعة متساوية. ومع ذلك ، حصلت على unsigned أبطأ ! انخفض من 26 إلى 20 GB/s ، وبالتالي استبدال غير ثابت من قبل قيمة ثابتة تؤدي إلى التقشف . على محمل الجد ، ليس لدي أي فكرة عما يجري هنا! ولكن الآن clang++ مع الإصدار الجديد:

  • غير موقعة 41959360000 0.677009 ثانية 15.4884 جيجابايت / ثانية
  • uint64_t 41959360000 0.676909 sec 15.4906 GB / s

انتظر ماذا؟ الآن ، انخفض كلا الإصدارين إلى بطء عدد 15 جيجابايت / ثانية. وبالتالي ، فإن استبدال قيمة غير ثابتة بقيمة ثابتة يؤدي إلى بطء الرمز في كلتا الحالتين لكلانج!

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

مزيد من الجنون ، من فضلك!

خذ المثال الأول (الذي يحتوي على atol(argv[1]) وضع static قبل المتغير ، أي:

static uint64_t size=atol(argv[1])<<20;

فيما يلي نتائجي في g ++:

  • غير موقعة 41959360000 0.396728 ثانية 26.4306 غيغابايت / ثانية
  • uint64_t 41959360000 0.509484 sec 20.5811 GB / s

نعم ، بديل آخر . لا يزال لدينا بسرعة 26 جيجابايت / ثانية مع u32 ، ولكن تمكنا من الحصول على u64 على الأقل من 13 جيجابايت / ثانية إلى إصدار 20 جيجابايت / ثانية! على جهاز الكمبيوتر الخاص بي الزملاء ، أصبح الإصدار u64 أسرع من الإصدار u32 ، مما أسفر عن أسرع نتيجة للجميع. للأسف ، هذا يعمل فقط ل g++ ، لا يبدو أن رعاية static عن static .

سؤالي

هل يمكنك شرح هذه النتائج؟ خصوصا:

  • كيف يمكن أن يكون هناك فرق بين u32 و u64 ؟
  • كيف يمكن استبدال جهاز ثابت غير ثابت من خلال حجم ثابت لعزلة المخزن المؤقت؟
  • كيف يمكن لإدخال الكلمة الأساسية static جعل حلقة u64 أسرع؟ حتى أسرع من الشفرة الأصلية على جهاز الكمبيوتر الخاص بي في الزميل!

وأنا أعلم أن التحسين هو منطقة صعبة ، ومع ذلك ، لم أكن أعتقد أبدا أن مثل هذه التغييرات الصغيرة يمكن أن تؤدي إلى اختلاف بنسبة 100 ٪ في وقت التنفيذ ، وأن العوامل الصغيرة مثل حجم المخزن المؤقت الثابت يمكن مرة أخرى خلط النتائج تماما. بالطبع ، أرغب دائمًا في الحصول على الإصدار القادر على إصدار الفوتوشوب 26 جيجابايت / ثانية. الطريقة الوحيدة الموثوق بها التي يمكنني التفكير فيها هي نسخة لصق التجميع لهذه الحالة واستخدام التجميع المضمّن. هذه هي الطريقة الوحيدة التي يمكنني بها التخلص من المجمعين الذين يبدو أنهم غاضبون من التغييرات الصغيرة. ما رأيك؟ هل هناك طريقة أخرى للحصول على الكود مع معظم الأداء؟

التفكيك

هنا هو التفكيك للنتائج المختلفة:

26 جيجابايت / ثانية إصدار من g ++ / u32 / non-const bufsize :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

إصدار 13 جيجابايت / ثانية من g ++ / u64 / non-const bufsize :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

إصدار 15 جيجابايت / ثانية من bujs +++ / u64 / non-const :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

إصدار 20 جيجابايت / ثانية من g ++ / u32 و u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

إصدار 15 جيجابايت / ثانية من bang + u32 & u64 / const bufsize :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

ومن المثير للاهتمام أن الإصدار الأسرع (26 جيجابايت / ثانية) هو الأطول أيضاً! يبدو أن الحل الوحيد الذي يستخدم lea . بعض الإصدارات تستخدم jb للقفز ، والبعض الآخر يستخدم jne . ولكن بصرف النظر عن ذلك ، يبدو أن جميع الإصدارات قابلة للمقارنة. لا أرى أين يمكن أن تنشأ فجوة أداء 100٪ ، لكنني لست بارعة في فك التجميع. يبدو أبطأ إصدار (13 جيجابايت / ثانية) حتى قصيرة وجيدة للغاية. يمكن لأي شخص أن يفسر هذا؟

الدروس المستفادة

مهما كانت الإجابة على هذا السؤال ، لقد تعلمت أنه في الحلقات الساخنة حقا كل التفاصيل يمكن أن يهم ، حتى التفاصيل التي لا يبدو أن لديها أي ارتباط إلى رمز الساخن . لم افكر ابدا في نوع ما لاستخدامه لمتغير حلقة ، ولكن كما ترون مثل هذا التغيير الطفيف يمكن أن تحدث فرقا بنسبة 100 ٪ ! حتى نوع تخزين المخزن المؤقت يمكن أن يحدث فرقًا كبيرًا ، كما رأينا مع إدخال الكلمة الرئيسية static أمام متغير الحجم! في المستقبل ، سأقوم باختبار البدائل المختلفة على مختلف المترجمين عند كتابة حلقات ضيقة وساخنة حقاً تكون ضرورية لأداء النظام.

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


TL ؛ DR: استخدم __builtin الجوهرية بدلا من ذلك.

لقد تمكنت من إنشاء gcc 4.8.4 (وحتى 4.7.3 على gcc.godbolt.org) إنشاء رمز الأمثل لهذا باستخدام __builtin_popcountll الذي يستخدم نفس توجيه التجميع ، ولكن ليس لديه هذا الخطأ التبعية الخاطئة.

لست متأكدًا بنسبة 100٪ من شفرة قياس الأداء ، ولكن يبدو أن مخرجات objdump تشارك وجهات نظري. أنا استخدم بعض الحيل الأخرى ( ++i مقابل i++ ) لجعل المجمع unroll حلقة بالنسبة لي دون أي تعليمات movl (سلوك غريب ، يجب أن أقول).

النتائج:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

رمز قياس الأداء:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

خيارات الترجمة:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

نسخة مجلس التعاون الخليجي:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

إصدار Linux kernel:

3.19.0-58-generic

معلومات وحدة المعالجة المركزية:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

المذنب: تبعية بيانات خاطئة (وليس المترجم حتى على علم به)

على Sandy / Ivy Bridge ومعالجات Haswell ، التعليمات:

popcnt  src, dest

يبدو أن لها تبعية كاذبة على الوجهة سجل dest . على الرغم من أن التعليمة تكتب فقط ، dest التعليمات حتى تصبح جاهزة قبل التنفيذ.

هذه التبعية لا تحافظ فقط على s 4 popcnt من تكرار حلقة واحدة. يمكن أن تحمل عبر تكرار التكرار الحلقي مما يجعل من المستحيل على المعالج موازنة تكرارات الحلقة المختلفة.

unsigned uint64_t والقرص الأخرى لا تؤثر بشكل مباشر على المشكلة. لكنها تؤثر على مخصص السجل الذي يعين السجلات للمتغيرات.

في حالتك ، تكون السرعات نتيجة مباشرة لما يتمسكت به سلسلة التبعية (الزائفة) اعتمادًا على ما قرره مسؤول التوزيع.

  • 13 جيجابايت / ثانية لديه سلسلة: popcnt - add - popcnt - popcnt → التالي التكرار
  • 15 GB / s لديه سلسلة: popcnt - add - popcnt - add → next iteration
  • 20 GB / s لديه سلسلة: popcnt - popcnt → التكرار التالي
  • 26 جيجابايت / ثانية لديه سلسلة: popcnt - popcnt → التكرار التالي

يبدو أن الفرق بين 20 جيجابايت / ثانية و 26 جيجابايت / ثانية هو قطعة أثرية ثانوية للعناوين غير المباشرة. في كلتا الحالتين ، يبدأ المعالج بضرب اختناقات أخرى بمجرد الوصول إلى هذه السرعة.

لاختبار ذلك ، استخدمت التجميع المضمّن لتجاوز المحول البرمجي والحصول على التجميع الذي أريده تمامًا. أنا أيضا تقسيم المتغير count لكسر جميع الاعتمادات الأخرى التي قد الفوضى مع المعايير.

وهنا النتائج:

ساندي بريدج زيون @ 3.5 غيغاهرتز: (يمكن العثور على رمز اختبار كامل في الأسفل)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • أوبونتو 12

تسجيلات مختلفة: 18.6195 جيجابايت / ثانية

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

نفس السجل: 8.49272 جيجابايت / ثانية

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

نفس السجل مع سلسلة مكسورة: 17.8869 جيجابايت / ثانية

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

ما الخطأ في المترجم؟

يبدو أن لا GCC ولا Visual Studio على علم بأن popcnt لديه مثل هذه تبعية خاطئة. ومع ذلك ، هذه التبعيات الكاذبة ليست غير شائعة. انها مجرد مسألة ما إذا كان المترجم يدرك ذلك.

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

( التحديث: اعتبارًا من الإصدار 4.9.2 ، يدرك مجلس التعاون الخليجي هذه التبعية الخاطئة ويولد كودًا لتعويضه عند تمكين عمليات التحسين. لم يعد المجمعون الرئيسيون من الموردين الآخرين ، بما في ذلك Clang و MSVC وحتى ICC الخاصة بـ Intel على علم بـ هذا erratum microarch المعمارية ولن ينبعث التعليمات البرمجية التي تعوض عن ذلك.)

لماذا وحدة المعالجة المركزية لديها مثل هذه التبعية الزائفة؟

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

لا تظهر معالجات AMD هذه التبعية الخاطئة.

رمز الاختبار الكامل أدناه كمرجع:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

يمكن العثور على http://pastebin.com/kbzgL8si مثير للاهتمام على حد سواء هنا: http://pastebin.com/kbzgL8si
popcnt هذا benchmark عدد popcnt s الموجودة في سلسلة التبعية (false).

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

لقد قمت بترميز برنامج C مكافئ للتجربة ، ويمكنني أن أؤكد هذا السلوك الغريب. ما هو أكثر من ذلك ، تعتقد gcc أن العدد الصحيح 64 بت (والذي من المحتمل أن يكون size_t أية حال ...) ليكون أفضل ، لأن استخدام uint_fast32_t يؤدي إلى استخدام gcc uint_fast32_t 64 بت.

فعلت القليل من التلويث مع الجمعية:
ما عليك سوى أخذ الإصدار 32 بت ، واستبدال جميع الإرشادات / التسجيلات ذات 32 بتًا بإصدار 64 بت في حلقة popcount-loop الداخلية للبرنامج. ملاحظة: الكود هو بنفس سرعة إصدار 32 بت!

من الواضح أن هذا هو الاختراق ، حيث أن حجم المتغير ليس 64 بت ، حيث أن أجزاء أخرى من البرنامج لا تزال تستخدم الإصدار 32 بت ، ولكن طالما أن حلقة popcount-loop الداخلية تهيمن على الأداء ، فهذه بداية جيدة .

ثم قمت بنسخ رمز الحلقة الداخلية من الإصدار 32 بت من البرنامج ، واخترقناه ليكون 64 بت ، مغشوشًا بالسجلات لجعله بديلاً للحلقة الداخلية لإصدار 64 بت. يعمل هذا الرمز أيضًا بسرعة الإصدار 32 بت.

استنتاجي هو أن هذا هو جدولة تعليمات سيئة من قبل المجمع ، وليس ميزة السرعة / الكمون الفعلي من تعليمات 32 بت.

(Caveat: لقد اخترقت التجمع ، يمكن أن يكون كسر شيء دون أن يلاحظ. لا أعتقد ذلك.)


هل حاولت نقل خطوة التخفيض خارج الحلقة؟ في الوقت الحالي ، لديك تبعية بيانات ليست ضرورية فعلاً.

محاولة:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

لديك أيضًا بعض التعرجات الغريبة التي تحدث ، والتي لست متأكدًا أنها متوافقة مع قواعد التعرّف الصارمة.


هذه ليست إجابة ، ولكن من الصعب أن تقرأ إذا وضعت النتائج في التعليق.

أحصل على هذه النتائج مع ماك برو ( Westmere 6-Cores Xeon 3.33 غيغاهرتز). أنا جمعت ذلك مع clang -O3 -msse4 -lstdc++ a.cpp -oa (-O2 الحصول على نفس النتيجة).

uint64_t size=atol(argv[1])<<20; with uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

رنة مع uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

حاولت أيضًا أن:

  1. عكس ترتيب الاختبار ، والنتيجة هي نفسها لذلك يستبعد عامل ذاكرة التخزين المؤقت.
  2. for (uint64_t i=size/8;i>0;i-=4) for عبارة for في عكس: for (uint64_t i=size/8;i>0;i-=4) . وهذا يعطي نفس النتيجة ويثبت أن التجميع ذكي بدرجة كافية لعدم قسمة الحجم بمقدار 8 كل تكرار (كما هو متوقع).

هنا هو تخميني البرية:

عامل السرعة يأتي في ثلاثة أجزاء:

  • ذاكرة التخزين المؤقت الكود: uint64_t نسخة أكبر حجم الكود ، ولكن هذا ليس له تأثير على بلدي Xeon وحدة المعالجة المركزية. هذا يجعل الإصدار 64 بت أبطأ.

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

  • تنبعث التعليمات فقط في الترجمة فئة 64 بت (أي ، الجلب المسبق). هذا يجعل 64 بت أسرع.

تتطابق العوامل الثلاثة مع النتائج التي تبدو متضاربة ظاهريًا.


لقد حاولت ذلك باستخدام Visual Studio 2013 Express ، باستخدام مؤشر بدلاً من فهرس ، مما أدى إلى تسريع العملية قليلاً. أظن أن هذا بسبب أن العنوان عبارة عن علامة + تسجيل ، بدلاً من إزاحة + تسجيل + (تسجيل << 3). كود C ++.

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

كود التجميع: r10 = bfrptr، r15 = bfrend، rsi = count، rdi = buffer، r13 = k:

[email protected]:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT [email protected]
        npad    4
[email protected]:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT [email protected]
[email protected]:
        dec     r13
        jne     SHORT [email protected]

هل حاولت تمرير -funroll-loops -fprefetch-loop-arrays إلى GCC؟

أتلقى النتائج التالية باستخدام هذه التحسينات الإضافية:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s




compiler-optimization