Замена 32-разрядного счетчика циклов на 64-разрядный вводит сумасшедшие отклонения производительности

Я искал самый быстрый способ 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 читается из командной строки. После этого мы перебираем буфер и используем развернутую версию x86. popcount свойственный исполнять попконт. Чтобы получить более точный результат, мы делаем поп-счет 10000 раз. Мы измеряем время для попкорна. В верхнем регистре переменная внутреннего цикла unsigned в нижнем регистре переменная внутреннего цикла uint64_t, Я думал, что это не должно иметь никакого значения, но дело обстоит наоборот.

(Абсолютно безумные) результаты

Я скомпилирую его так (версия g++: Ubuntu 4.8.2-19ubuntu1):

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

Вот результаты на моем процессоре Haswell Core i7-4770K @ 3,50 ГГц, работающем test 1 (так 1 МБ случайных данных):

  • без знака 41959360000 0,401554 с 26,113 ГБ / с
  • uint64_t 41959360000 0,759822 с 13,8003 ГБ / с

Как видите, пропускная способность 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 ГБ / с
  • uint64_t 41959360000 0,680954 с, 15,3986 ГБ / с

Так что это почти тот же результат и все еще странный. Но теперь это становится супер странным. Я заменяю размер буфера, который был прочитан из ввода, константой 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 с 15,4906 ГБ / с

Чего ждать? Теперь обе версии опустились до медленного 15 ГБ / с. Таким образом, замена непостоянной константы даже приводит к медленному коду в обоих случаях для Clang!

Я попросил коллегу с процессором Ivy Bridge скомпилировать мой тест. Он получил аналогичные результаты, так что, похоже, это не Haswell. Поскольку два компилятора дают здесь странные результаты, это также не является ошибкой компилятора. У нас здесь нет процессора AMD, поэтому мы могли тестировать только с Intel.

Больше безумия, пожалуйста!

Возьмите первый пример (тот, с atol(argv[1])) и положить static перед переменной, т.е.

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

Вот мои результаты в g++:

  • без знака 41959360000 0,396728 с 26,4306 ГБ / с
  • uint64_t 41959360000 0,509484 с 20,5811 ГБ / с

Ууу, еще одна альтернатива. У нас все еще есть быстрые 26 ГБ / с u32, но нам удалось получить u64 по крайней мере, от 13 ГБ / с до версии 20 ГБ / с! На компьютере моего коллеги, u64 версия стала еще быстрее чем u32 версия, дающая самый быстрый результат из всех. К сожалению, это работает только для g++, clang++ кажется, не заботится о static,

Мой вопрос

Можете ли вы объяснить эти результаты? Особенно:

  • Как может быть такая разница между u32 а также u64?
  • Как замена непостоянного постоянным размером буфера может привести к снижению оптимального кода?
  • Как можно вставить static ключевое слово сделать u64 цикл быстрее? Даже быстрее, чем оригинальный код на компьютере моего коллеги!

Я знаю, что оптимизация - сложная задача, однако я никогда не думал, что такие небольшие изменения могут привести к 100% -ной разнице во времени выполнения и что небольшие факторы, такие как постоянный размер буфера, могут снова полностью смешивать результаты. Конечно, я всегда хочу иметь версию, способную подсчитывать 26 ГБ / с. Единственный надежный способ, который я могу придумать, это скопировать и вставить сборку для этого случая и использовать встроенную сборку. Это единственный способ избавиться от компиляторов, которые, кажется, сходят с ума от небольших изменений. Как вы думаете? Есть ли другой способ надежно получить код с большей производительностью?

Разборка

Вот разборка для различных результатов:

Версия 26 ГБ / с из g++ / u32 / неконстантного размера 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 / неконстантного размера 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 ГБ / с из clang++ / u64 / non-const bufsize:

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 ГБ / с из clang++ / 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 Ключевое слово перед переменной размера! В будущем я всегда буду тестировать различные альтернативы на разных компиляторах, когда пишу действительно сжатые и горячие циклы, которые имеют решающее значение для производительности системы.

Интересно также то, что разница в производительности все еще так велика, хотя я уже развернул цикл четыре раза. Так что даже если вы развернетесь, вы все равно можете столкнуться с серьезными отклонениями производительности. Довольно интересно.

11 ответов

Решение

Culprit: ложная зависимость от данных (а компилятор даже не знает об этом)

На процессорах Sandy/Ivy Bridge и Haswell инструкция:

popcnt  src, dest

по-видимому, имеет ложную зависимость от регистра назначения dest, Даже если инструкция только пишет в нее, инструкция будет ждать до dest готов перед выполнением.

Эта зависимость не только поддерживает 4 popcntс одного цикла итерации. Он может переносить итерации цикла, делая невозможным для процессора распараллеливание различных итераций цикла.

unsigned против uint64_t и другие изменения не влияют напрямую на проблему. Но они влияют на распределитель регистров, который назначает регистры переменным.

В вашем случае скорости являются прямым результатом того, что привязано к (ложной) цепочке зависимостей, в зависимости от того, что решил сделать распределитель регистров.

  • 13 ГБ / с имеет цепочку: popcnt-add-popcnt-popcnt → следующая итерация
  • 15 ГБ / с имеет цепочку: popcnt-add-popcnt-add → следующая итерация
  • 20 ГБ / с имеет цепочку: popcnt-popcnt → следующая итерация
  • 26 ГБ / с имеет цепочку: popcnt-popcnt → следующая итерация

Разница между 20 ГБ / с и 26 ГБ / с кажется незначительным артефактом косвенной адресации. В любом случае, процессор достигает других узких мест, как только вы достигнете этой скорости.


Чтобы проверить это, я использовал встроенную сборку, чтобы обойти компилятор и получить именно ту сборку, которую я хочу. Я также разделил count переменная, чтобы сломать все другие зависимости, которые могут мешать с тестами.

Вот результаты:

Sandy Bridge Xeon @ 3,5 ГГц: (полный тестовый код находится внизу)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 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 не совсем самая используемая инструкция. Поэтому неудивительно, что крупный компилятор может пропустить что-то подобное. Кроме того, нигде нет документации, в которой упоминается эта проблема. Если Intel не раскроет это, то никто за пределами не узнает, пока кто-то не наткнется на это случайно.

(Обновление: начиная с версии 4.9.2, GCC знает об этой ложной зависимости и генерирует код, чтобы компенсировать ее при включенной оптимизации. Основные компиляторы других поставщиков, включая Clang, MSVC и даже собственный ICC Intel, еще не знают о эта микроархитектурная ошибка и не будет генерировать код, который ее компенсирует.)

Почему у процессора такая ложная зависимость?

Мы можем только строить предположения, но вполне вероятно, что Intel имеет одинаковую обработку для многих инструкций с двумя операндами. Общие инструкции, такие как add, sub возьмите два операнда, оба из которых являются входными данными. Так что Intel, вероятно, засунул 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
Этот тест варьируется количество popcnts, которые находятся в (ложной) цепочке зависимостей.

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 использовать 64-битную uint.

Я немного повозился со сборкой:
Просто возьмите 32-битную версию, замените все 32-битные инструкции / регистры на 64-битную версию во внутреннем цикле popcount программы. Замечание: код так же быстр, как и 32-битная версия!

Это, очевидно, хак, поскольку размер переменной на самом деле не 64-битный, так как другие части программы все еще используют 32-битную версию, но пока внутренний цикл popcount доминирует над производительностью, это хорошее начало,

Затем я скопировал код внутреннего цикла из 32-битной версии программы, взломал его до 64-битного, поиграл с регистрами, чтобы сделать его заменой для внутреннего цикла 64-битной версии. Этот код также работает так же быстро, как и 32-битная версия.

Я пришел к выводу, что это плохое планирование инструкций компилятором, а не фактическое преимущество в скорости / задержке 32-битных инструкций.

(Предостережение: я взломал сборку, мог что-то сломать, не заметив. Я так не думаю.)

Это не ответ, но трудно прочитать, если я добавлю результаты в комментарии.

Я получаю эти результаты с Mac Pro ( Westmere 6-Cores Xeon 3,33 ГГц). Я скомпилировал это с clang -O3 -msse4 -lstdc++ a.cpp -o a (-O2 получить тот же результат).

лязг с 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 заявление в обратном порядке: 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 = количество, rdi = буфер, r13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        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 $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

Я не могу дать авторитетный ответ, но предоставлю обзор вероятной причины. Эта ссылка довольно ясно показывает, что для инструкций в теле вашего цикла существует соотношение 3:1 между задержкой и пропускной способностью. Это также показывает эффекты множественной отправки. Поскольку в современных процессорах x86 есть три типа целых (отдай или возьми), обычно можно отправлять по три инструкции за цикл.

Таким образом, между пиковым конвейером и многократной диспетчеризацией и отказом этих механизмов мы имеем коэффициент производительности в шесть раз. Общеизвестно, что сложность набора команд x86 значительно облегчает возникновение причудливых поломок. У документа выше есть отличный пример:

Производительность Pentium 4 для 64-битных сдвигов вправо очень низкая. 64-разрядное смещение влево, а также все 32-разрядные сдвиги имеют приемлемую производительность. Похоже, что путь данных от старших 32 битов к младшим 32 битам АЛУ не разработан должным образом.

Лично я столкнулся со странным случаем, когда горячая петля работала значительно медленнее на конкретном ядре четырехъядерного чипа (AMD, если я помню). На самом деле мы получили лучшую производительность при расчете сокращения карты, отключив это ядро.

Здесь я думаю, что утверждение для целочисленных единиц: popcntС помощью счетчика 32-битной ширины счетчик циклов и вычисление адреса могут едва работать на полной скорости, но 64-разрядный счетчик вызывает конфликты и задержки конвейера. Поскольку всего около 12 циклов, потенциально 4 цикла с множественной диспетчеризацией, на выполнение тела цикла, один останов может разумно повлиять на время выполнения в 2 раза.

Изменение, вызванное использованием статической переменной, которая, как я предполагаю, просто вызывает незначительное переупорядочение команд, является еще одним свидетельством того, что 32-битный код находится в некоторой переломной точке для разногласий.

Я знаю, что это не строгий анализ, но это правдоподобное объяснение.

Вы пробовали проходить -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

Вы пытались переместить шаг сокращения за пределы цикла? Прямо сейчас у вас есть зависимость от данных, которая действительно не нужна.

Пытаться:

  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];

У вас также происходят странные псевдонимы, и я не уверен, что они соответствуют строгим правилам псевдонимов.

Это не ответ, а отзыв с несколькими компиляторами 2021 года. На Intel CoffeeLake 9900k.

С компилятором Microsoft (VS2019), набор инструментов v142:

       unsigned        209695540000    1.8322 sec      28.6152 GB/s
uint64_t        209695540000    3.08764 sec     16.9802 GB/s

С компилятором Intel 2021:

       unsigned        209695540000    1.70845 sec     30.688 GB/s
uint64_t        209695540000    1.57956 sec     33.1921 GB/s

Согласно ответу Mysticial, компилятор Intel знает о зависимости от ложных данных, но не компилятор Microsoft.

Для компилятора Intel я использовал /QxHost(оптимизация архитектуры ЦП, которая является архитектурой хоста) /Oi(включить встроенные функции) и #include <nmmintrin.h>вместо #include <immintrin.h>.

Полная команда компиляции: /GS /W3 /QxHost /Gy /Zi /O2 /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Qipo /Zc:forScope /Oi /MD /Fa"x64\Release\" /EHsc /nologo /Fo"x64\Release\" //fprofile-instr-use "x64\Release\" /Fp"x64\Release\Benchmark.pch" .

Декомпилированная (по IDA 7.5) сборка от ICC:

      int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v6; // er13
  _BYTE *v8; // rsi
  unsigned int v9; // edi
  unsigned __int64 i; // rbx
  unsigned __int64 v11; // rdi
  int v12; // ebp
  __int64 v13; // r14
  __int64 v14; // rbx
  unsigned int v15; // eax
  unsigned __int64 v16; // rcx
  unsigned int v17; // eax
  unsigned __int64 v18; // rcx
  __int64 v19; // rdx
  unsigned int v20; // eax
  int result; // eax
  std::ostream *v23; // rbx
  char v24; // dl
  std::ostream *v33; // rbx
  std::ostream *v41; // rbx
  __int64 v42; // rdx
  unsigned int v43; // eax
  int v44; // ebp
  __int64 v45; // r14
  __int64 v46; // rbx
  unsigned __int64 v47; // rax
  unsigned __int64 v48; // rax
  std::ostream *v50; // rdi
  char v51; // dl
  std::ostream *v58; // rdi
  std::ostream *v60; // rdi
  __int64 v61; // rdx
  unsigned int v62; // eax

  __asm
  {
    vmovdqa [rsp+98h+var_58], xmm8
    vmovapd [rsp+98h+var_68], xmm7
    vmovapd [rsp+98h+var_78], xmm6
  }
  if ( argc == 2 )
  {
    v6 = atol(argv[1]) << 20;
    _R15 = v6;
    v8 = operator new[](v6);
    if ( v6 )
    {
      v9 = 1;
      for ( i = 0i64; i < v6; i = v9++ )
        v8[i] = rand();
    }
    v11 = (unsigned __int64)v6 >> 3;
    v12 = 0;
    v13 = Xtime_get_ticks_0();
    v14 = 0i64;
    do
    {
      if ( v6 )
      {
        v15 = 4;
        v16 = 0i64;
        do
        {
          v14 += __popcnt(*(_QWORD *)&v8[8 * v16])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 24])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 16])
               + __popcnt(*(_QWORD *)&v8[8 * v15 - 8]);
          v16 = v15;
          v15 += 4;
        }
        while ( v11 > v16 );
        v17 = 4;
        v18 = 0i64;
        do
        {
          v14 += __popcnt(*(_QWORD *)&v8[8 * v18])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 24])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 16])
               + __popcnt(*(_QWORD *)&v8[8 * v17 - 8]);
          v18 = v17;
          v17 += 4;
        }
        while ( v11 > v18 );
      }
      v12 += 2;
    }
    while ( v12 != 10000 );
    _RBP = 100 * (Xtime_get_ticks_0() - v13);
    std::operator___std::char_traits_char___(std::cout, "unsigned\t");
    v23 = (std::ostream *)std::ostream::operator<<(std::cout, v14);
    std::operator___std::char_traits_char____0(v23, v24);
    __asm
    {
      vmovq   xmm0, rbp
      vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000
      vpunpckldq xmm0, xmm0, xmm8
      vmovapd xmm7, cs:__xmm@45300000000000004330000000000000
      vsubpd  xmm0, xmm0, xmm7
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm6, xmm1, xmm0
      vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
    }
    v33 = (std::ostream *)std::ostream::operator<<(v23);
    std::operator___std::char_traits_char___(v33, " sec \t");
    __asm
    {
      vmovq   xmm0, r15
      vpunpckldq xmm0, xmm0, xmm8
      vsubpd  xmm0, xmm0, xmm7
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm0, xmm1, xmm0
      vmulsd  xmm7, xmm0, cs:__real@40c3880000000000
      vdivsd  xmm1, xmm7, xmm6
    }
    v41 = (std::ostream *)std::ostream::operator<<(v33);
    std::operator___std::char_traits_char___(v41, " GB/s");
    LOBYTE(v42) = 10;
    v43 = std::ios::widen((char *)v41 + *(int *)(*(_QWORD *)v41 + 4i64), v42);
    std::ostream::put(v41, v43);
    std::ostream::flush(v41);
    v44 = 0;
    v45 = Xtime_get_ticks_0();
    v46 = 0i64;
    do
    {
      if ( v6 )
      {
        v47 = 0i64;
        do
        {
          v46 += __popcnt(*(_QWORD *)&v8[8 * v47])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 8])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 16])
               + __popcnt(*(_QWORD *)&v8[8 * v47 + 24]);
          v47 += 4i64;
        }
        while ( v47 < v11 );
        v48 = 0i64;
        do
        {
          v46 += __popcnt(*(_QWORD *)&v8[8 * v48])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 8])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 16])
               + __popcnt(*(_QWORD *)&v8[8 * v48 + 24]);
          v48 += 4i64;
        }
        while ( v48 < v11 );
      }
      v44 += 2;
    }
    while ( v44 != 10000 );
    _RBP = 100 * (Xtime_get_ticks_0() - v45);
    std::operator___std::char_traits_char___(std::cout, "uint64_t\t");
    v50 = (std::ostream *)std::ostream::operator<<(std::cout, v46);
    std::operator___std::char_traits_char____0(v50, v51);
    __asm
    {
      vmovq   xmm0, rbp
      vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000
      vsubpd  xmm0, xmm0, cs:__xmm@45300000000000004330000000000000
      vpermilpd xmm1, xmm0, 1
      vaddsd  xmm6, xmm1, xmm0
      vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
    }
    v58 = (std::ostream *)std::ostream::operator<<(v50);
    std::operator___std::char_traits_char___(v58, " sec \t");
    __asm { vdivsd  xmm1, xmm7, xmm6 }
    v60 = (std::ostream *)std::ostream::operator<<(v58);
    std::operator___std::char_traits_char___(v60, " GB/s");
    LOBYTE(v61) = 10;
    v62 = std::ios::widen((char *)v60 + *(int *)(*(_QWORD *)v60 + 4i64), v61);
    std::ostream::put(v60, v62);
    std::ostream::flush(v60);
    free(v8);
    result = 0;
  }
  else
  {
    std::operator___std::char_traits_char___(std::cerr, "usage: array_size in MB");
    LOBYTE(v19) = 10;
    v20 = std::ios::widen((char *)&std::cerr + *((int *)std::cerr + 1), v19);
    std::ostream::put(std::cerr, v20);
    std::ostream::flush(std::cerr);
    result = -1;
  }
  __asm
  {
    vmovaps xmm6, [rsp+98h+var_78]
    vmovaps xmm7, [rsp+98h+var_68]
    vmovaps xmm8, [rsp+98h+var_58]
  }
  return result;
}

и разборка основного:

      .text:0140001000    .686p
.text:0140001000    .mmx
.text:0140001000    .model flat
.text:0140001000
.text:0140001000 ; ===========================================================================
.text:0140001000
.text:0140001000 ; Segment type: Pure code
.text:0140001000 ; Segment permissions: Read/Execute
.text:0140001000 _text           segment para public 'CODE' use64
.text:0140001000    assume cs:_text
.text:0140001000    ;org 140001000h
.text:0140001000    assume es:nothing, ss:nothing, ds:_data, fs:nothing, gs:nothing
.text:0140001000
.text:0140001000 ; =============== S U B R O U T I N E =======================================
.text:0140001000
.text:0140001000
.text:0140001000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:0140001000 main            proc near      ; CODE XREF: __scrt_common_main_seh+107↓p
.text:0140001000      ; DATA XREF: .pdata:ExceptionDir↓o
.text:0140001000
.text:0140001000 var_78          = xmmword ptr -78h
.text:0140001000 var_68          = xmmword ptr -68h
.text:0140001000 var_58          = xmmword ptr -58h
.text:0140001000
.text:0140001000    push    r15
.text:0140001002    push    r14
.text:0140001004    push    r13
.text:0140001006    push    r12
.text:0140001008    push    rsi
.text:0140001009    push    rdi
.text:014000100A    push    rbp
.text:014000100B    push    rbx
.text:014000100C    sub     rsp, 58h
.text:0140001010    vmovdqa [rsp+98h+var_58], xmm8
.text:0140001016    vmovapd [rsp+98h+var_68], xmm7
.text:014000101C    vmovapd [rsp+98h+var_78], xmm6
.text:0140001022    cmp     ecx, 2
.text:0140001025    jnz     loc_14000113E
.text:014000102B    mov     rcx, [rdx+8]    ; String
.text:014000102F    call    cs:__imp_atol
.text:0140001035    mov     r13d, eax
.text:0140001038    shl     r13d, 14h
.text:014000103C    movsxd  r15, r13d
.text:014000103F    mov     rcx, r15        ; size
.text:0140001042    call    ??_U@YAPEAX_K@Z ; operator new[](unsigned __int64)
.text:0140001047    mov     rsi, rax
.text:014000104A    test    r15d, r15d
.text:014000104D    jz      short loc_14000106E
.text:014000104F    mov     edi, 1
.text:0140001054    xor     ebx, ebx
.text:0140001056    mov     rbp, cs:__imp_rand
.text:014000105D    nop     dword ptr [rax]
.text:0140001060
.text:0140001060 loc_140001060:    ; CODE XREF: main+6C↓j
.text:0140001060    call    rbp ; __imp_rand
.text:0140001062    mov     [rsi+rbx], al
.text:0140001065    mov     ebx, edi
.text:0140001067    inc     edi
.text:0140001069    cmp     rbx, r15
.text:014000106C    jb      short loc_140001060
.text:014000106E
.text:014000106E loc_14000106E:    ; CODE XREF: main+4D↑j
.text:014000106E    mov     rdi, r15
.text:0140001071    shr     rdi, 3
.text:0140001075    xor     ebp, ebp
.text:0140001077    call    _Xtime_get_ticks_0
.text:014000107C    mov     r14, rax
.text:014000107F    xor     ebx, ebx
.text:0140001081    jmp     short loc_14000109F
.text:0140001081 ; ---------------------------------------------------------------------------
.text:0140001083    align 10h
.text:0140001090
.text:0140001090 loc_140001090:    ; CODE XREF: main+A2↓j
.text:0140001090      ; main+EC↓j ...
.text:0140001090    add     ebp, 2
.text:0140001093    cmp     ebp, 2710h
.text:0140001099    jz      loc_140001184
.text:014000109F
.text:014000109F loc_14000109F:    ; CODE XREF: main+81↑j
.text:014000109F    test    r13d, r13d
.text:01400010A2    jz      short loc_140001090
.text:01400010A4    mov     eax, 4
.text:01400010A9    xor     ecx, ecx
.text:01400010AB    nop     dword ptr [rax+rax+00h]
.text:01400010B0
.text:01400010B0 loc_1400010B0:    ; CODE XREF: main+E7↓j
.text:01400010B0    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:01400010B6    add     rcx, rbx
.text:01400010B9    lea     edx, [rax-3]
.text:01400010BC    popcnt  rdx, qword ptr [rsi+rdx*8]
.text:01400010C2    add     rdx, rcx
.text:01400010C5    lea     ecx, [rax-2]
.text:01400010C8    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:01400010CE    add     rcx, rdx
.text:01400010D1    lea     edx, [rax-1]
.text:01400010D4    xor     ebx, ebx
.text:01400010D6    popcnt  rbx, qword ptr [rsi+rdx*8]
.text:01400010DC    add     rbx, rcx
.text:01400010DF    mov     ecx, eax
.text:01400010E1    add     eax, 4
.text:01400010E4    cmp     rdi, rcx
.text:01400010E7    ja      short loc_1400010B0
.text:01400010E9    test    r13d, r13d
.text:01400010EC    jz      short loc_140001090
.text:01400010EE    mov     eax, 4
.text:01400010F3    xor     ecx, ecx
.text:01400010F5    db      2Eh
.text:01400010F5    nop     word ptr [rax+rax+00000000h]
.text:01400010FF    nop
.text:0140001100
.text:0140001100 loc_140001100:    ; CODE XREF: main+137↓j
.text:0140001100    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:0140001106    add     rcx, rbx
.text:0140001109    lea     edx, [rax-3]
.text:014000110C    popcnt  rdx, qword ptr [rsi+rdx*8]
.text:0140001112    add     rdx, rcx
.text:0140001115    lea     ecx, [rax-2]
.text:0140001118    popcnt  rcx, qword ptr [rsi+rcx*8]
.text:014000111E    add     rcx, rdx
.text:0140001121    lea     edx, [rax-1]
.text:0140001124    xor     ebx, ebx
.text:0140001126    popcnt  rbx, qword ptr [rsi+rdx*8]
.text:014000112C    add     rbx, rcx
.text:014000112F    mov     ecx, eax
.text:0140001131    add     eax, 4
.text:0140001134    cmp     rdi, rcx
.text:0140001137    ja      short loc_140001100
.text:0140001139    jmp     loc_140001090
.text:014000113E ; ---------------------------------------------------------------------------
.text:014000113E
.text:014000113E loc_14000113E:    ; CODE XREF: main+25↑j
.text:014000113E    mov     rsi, cs:__imp_?cerr@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cerr
.text:0140001145    lea     rdx, aUsageArraySize ; "usage: array_size in MB"
.text:014000114C    mov     rcx, rsi        ; std::ostream *
.text:014000114F    call    std__operator___std__char_traits_char___
.text:0140001154    mov     rax, [rsi]
.text:0140001157    movsxd  rcx, dword ptr [rax+4]
.text:014000115B    add     rcx, rsi
.text:014000115E    mov     dl, 0Ah
.text:0140001160    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:0140001166    mov     rcx, rsi
.text:0140001169    mov     edx, eax
.text:014000116B    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:0140001171    mov     rcx, rsi
.text:0140001174    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:014000117A    mov     eax, 0FFFFFFFFh
.text:014000117F    jmp     loc_1400013E2
.text:0140001184 ; ---------------------------------------------------------------------------
.text:0140001184
.text:0140001184 loc_140001184:    ; CODE XREF: main+99↑j
.text:0140001184    call    _Xtime_get_ticks_0
.text:0140001189    sub     rax, r14
.text:014000118C    imul    rbp, rax, 64h ; 'd'
.text:0140001190    mov     r14, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout
.text:0140001197    lea     rdx, aUnsigned  ; "unsigned\t"
.text:014000119E    mov     rcx, r14        ; std::ostream *
.text:01400011A1    call    std__operator___std__char_traits_char___
.text:01400011A6    mov     rcx, r14
.text:01400011A9    mov     rdx, rbx
.text:01400011AC    call    cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64)
.text:01400011B2    mov     rbx, rax
.text:01400011B5    mov     rcx, rax        ; std::ostream *
.text:01400011B8    call    std__operator___std__char_traits_char____0
.text:01400011BD    vmovq   xmm0, rbp
.text:01400011C2    vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000
.text:01400011CA    vpunpckldq xmm0, xmm0, xmm8
.text:01400011CF    vmovapd xmm7, cs:__xmm@45300000000000004330000000000000
.text:01400011D7    vsubpd  xmm0, xmm0, xmm7
.text:01400011DB    vpermilpd xmm1, xmm0, 1
.text:01400011E1    vaddsd  xmm6, xmm1, xmm0
.text:01400011E5    vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
.text:01400011ED    mov     r12, cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@N@Z ; std::ostream::operator<<(double)
.text:01400011F4    mov     rcx, rbx
.text:01400011F7    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:01400011FA    mov     rbx, rax
.text:01400011FD    lea     rdx, aSec       ; " sec \t"
.text:0140001204    mov     rcx, rax        ; std::ostream *
.text:0140001207    call    std__operator___std__char_traits_char___
.text:014000120C    vmovq   xmm0, r15
.text:0140001211    vpunpckldq xmm0, xmm0, xmm8
.text:0140001216    vsubpd  xmm0, xmm0, xmm7
.text:014000121A    vpermilpd xmm1, xmm0, 1
.text:0140001220    vaddsd  xmm0, xmm1, xmm0
.text:0140001224    vmulsd  xmm7, xmm0, cs:__real@40c3880000000000
.text:014000122C    vdivsd  xmm1, xmm7, xmm6
.text:0140001230    mov     rcx, rbx
.text:0140001233    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:0140001236    mov     rbx, rax
.text:0140001239    lea     rdx, aGbS       ; " GB/s"
.text:0140001240    mov     rcx, rax        ; std::ostream *
.text:0140001243    call    std__operator___std__char_traits_char___
.text:0140001248    mov     rax, [rbx]
.text:014000124B    movsxd  rcx, dword ptr [rax+4]
.text:014000124F    add     rcx, rbx
.text:0140001252    mov     dl, 0Ah
.text:0140001254    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:014000125A    mov     rcx, rbx
.text:014000125D    mov     edx, eax
.text:014000125F    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:0140001265    mov     rcx, rbx
.text:0140001268    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:014000126E    xor     ebp, ebp
.text:0140001270    call    _Xtime_get_ticks_0
.text:0140001275    mov     r14, rax
.text:0140001278    xor     ebx, ebx
.text:014000127A    jmp     short loc_14000128F
.text:014000127A ; ---------------------------------------------------------------------------
.text:014000127C    align 20h
.text:0140001280
.text:0140001280 loc_140001280:    ; CODE XREF: main+292↓j
.text:0140001280      ; main+2DB↓j ...
.text:0140001280    add     ebp, 2
.text:0140001283    cmp     ebp, 2710h
.text:0140001289    jz      loc_14000131D
.text:014000128F
.text:014000128F loc_14000128F:    ; CODE XREF: main+27A↑j
.text:014000128F    test    r13d, r13d
.text:0140001292    jz      short loc_140001280
.text:0140001294    xor     eax, eax
.text:0140001296    db      2Eh
.text:0140001296    nop     word ptr [rax+rax+00000000h]
.text:01400012A0
.text:01400012A0 loc_1400012A0:    ; CODE XREF: main+2D6↓j
.text:01400012A0    xor     ecx, ecx
.text:01400012A2    popcnt  rcx, qword ptr [rsi+rax*8]
.text:01400012A8    add     rcx, rbx
.text:01400012AB    xor     edx, edx
.text:01400012AD    popcnt  rdx, qword ptr [rsi+rax*8+8]
.text:01400012B4    add     rdx, rcx
.text:01400012B7    xor     ecx, ecx
.text:01400012B9    popcnt  rcx, qword ptr [rsi+rax*8+10h]
.text:01400012C0    add     rcx, rdx
.text:01400012C3    xor     ebx, ebx
.text:01400012C5    popcnt  rbx, qword ptr [rsi+rax*8+18h]
.text:01400012CC    add     rbx, rcx
.text:01400012CF    add     rax, 4
.text:01400012D3    cmp     rax, rdi
.text:01400012D6    jb      short loc_1400012A0
.text:01400012D8    test    r13d, r13d
.text:01400012DB    jz      short loc_140001280
.text:01400012DD    xor     eax, eax
.text:01400012DF    nop
.text:01400012E0
.text:01400012E0 loc_1400012E0:    ; CODE XREF: main+316↓j
.text:01400012E0    xor     ecx, ecx
.text:01400012E2    popcnt  rcx, qword ptr [rsi+rax*8]
.text:01400012E8    add     rcx, rbx
.text:01400012EB    xor     edx, edx
.text:01400012ED    popcnt  rdx, qword ptr [rsi+rax*8+8]
.text:01400012F4    add     rdx, rcx
.text:01400012F7    xor     ecx, ecx
.text:01400012F9    popcnt  rcx, qword ptr [rsi+rax*8+10h]
.text:0140001300    add     rcx, rdx
.text:0140001303    xor     ebx, ebx
.text:0140001305    popcnt  rbx, qword ptr [rsi+rax*8+18h]
.text:014000130C    add     rbx, rcx
.text:014000130F    add     rax, 4
.text:0140001313    cmp     rax, rdi
.text:0140001316    jb      short loc_1400012E0
.text:0140001318    jmp     loc_140001280
.text:014000131D ; ---------------------------------------------------------------------------
.text:014000131D
.text:014000131D loc_14000131D:    ; CODE XREF: main+289↑j
.text:014000131D    call    _Xtime_get_ticks_0
.text:0140001322    sub     rax, r14
.text:0140001325    imul    rbp, rax, 64h ; 'd'
.text:0140001329    mov     rdi, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout
.text:0140001330    lea     rdx, aUint64T   ; "uint64_t\t"
.text:0140001337    mov     rcx, rdi        ; std::ostream *
.text:014000133A    call    std__operator___std__char_traits_char___
.text:014000133F    mov     rcx, rdi
.text:0140001342    mov     rdx, rbx
.text:0140001345    call    cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64)
.text:014000134B    mov     rdi, rax
.text:014000134E    mov     rcx, rax        ; std::ostream *
.text:0140001351    call    std__operator___std__char_traits_char____0
.text:0140001356    vmovq   xmm0, rbp
.text:014000135B    vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000
.text:0140001363    vsubpd  xmm0, xmm0, cs:__xmm@45300000000000004330000000000000
.text:014000136B    vpermilpd xmm1, xmm0, 1
.text:0140001371    vaddsd  xmm6, xmm1, xmm0
.text:0140001375    vdivsd  xmm1, xmm6, cs:__real@41cdcd6500000000
.text:014000137D    mov     rcx, rdi
.text:0140001380    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:0140001383    mov     rdi, rax
.text:0140001386    lea     rdx, aSec       ; " sec \t"
.text:014000138D    mov     rcx, rax        ; std::ostream *
.text:0140001390    call    std__operator___std__char_traits_char___
.text:0140001395    vdivsd  xmm1, xmm7, xmm6
.text:0140001399    mov     rcx, rdi
.text:014000139C    call    r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double)
.text:014000139F    mov     rdi, rax
.text:01400013A2    lea     rdx, aGbS       ; " GB/s"
.text:01400013A9    mov     rcx, rax        ; std::ostream *
.text:01400013AC    call    std__operator___std__char_traits_char___
.text:01400013B1    mov     rax, [rdi]
.text:01400013B4    movsxd  rcx, dword ptr [rax+4]
.text:01400013B8    add     rcx, rdi
.text:01400013BB    mov     dl, 0Ah
.text:01400013BD    call    cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char)
.text:01400013C3    mov     rcx, rdi
.text:01400013C6    mov     edx, eax
.text:01400013C8    call    cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char)
.text:01400013CE    mov     rcx, rdi
.text:01400013D1    call    cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void)
.text:01400013D7    mov     rcx, rsi        ; Block
.text:01400013DA    call    cs:__imp_free
.text:01400013E0    xor     eax, eax
.text:01400013E2
.text:01400013E2 loc_1400013E2:    ; CODE XREF: main+17F↑j
.text:01400013E2    vmovaps xmm6, [rsp+98h+var_78]
.text:01400013E8    vmovaps xmm7, [rsp+98h+var_68]
.text:01400013EE    vmovaps xmm8, [rsp+98h+var_58]
.text:01400013F4    add     rsp, 58h
.text:01400013F8    pop     rbx
.text:01400013F9    pop     rbp
.text:01400013FA    pop     rdi
.text:01400013FB    pop     rsi
.text:01400013FC    pop     r12
.text:01400013FE    pop     r13
.text:0140001400    pop     r14
.text:0140001402    pop     r15
.text:0140001404    retn
.text:0140001404 main            endp

Обновление спецификации Coffee Lake : «Выполнение инструкции POPCNT может занять больше времени, чем ожидалось».

TL;DR: использовать __builtin внутренние вместо этого.

Я смог сделать gcc 4.8.4 (и даже 4.7.3 на gcc.godbolt.org) генерируют оптимальный код для этого, используя __builtin_popcountll который использует ту же инструкцию по сборке, но не имеет этой ошибки ложной зависимости.

Я не уверен на 100% в своем коде бенчмаркинга, но objdump Выход, кажется, разделяет мои взгляды. Я использую некоторые другие приемы (++i против i++) сделать цикл развертки компилятором для меня без каких-либо 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:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Версия ядра Linux:

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:

Хорошо, я хочу дать небольшой ответ на один из подвопросов, заданных ОП, которые, кажется, не рассматриваются в существующих вопросах. Предостережение: я не проводил никакого тестирования, генерации или разборки кода, просто хотел поделиться мыслью, которую другие могли бы разъяснить.

Почему static изменить производительность?

Строка, о которой идет речь:uint64_t size = atol(argv[1])<<20;

Короткий ответ

Я бы посмотрел на сборку, созданную для доступа size и посмотрите, есть ли дополнительные шаги по перенаправлению указателя, связанные с нестатической версией.

Длинный ответ

Поскольку существует только одна копия переменной, была ли она объявлена static или нет, и размер не изменяется, я теоретизирую, что разница - это расположение памяти, используемой для поддержки переменной, и того места, где она используется в коде ниже.

Хорошо, чтобы начать с очевидного, помните, что всем локальным переменным (вместе с параметрами) функции предоставляется место в стеке для использования в качестве хранилища. Теперь, очевидно, кадр стека для main() никогда не очищается и генерируется только один раз. Хорошо, как насчет того, чтобы сделать это static? Что ж, в этом случае компилятор знает, как зарезервировать пространство в глобальном пространстве данных процесса, чтобы его местоположение не могло быть очищено удалением стекового фрейма. Но, тем не менее, у нас есть только одно местоположение, так в чем же разница? Я подозреваю, что это связано с тем, как ссылки на ячейки памяти в стеке ссылаются.

Когда компилятор генерирует таблицу символов, он просто делает запись для метки вместе с соответствующими атрибутами, такими как размер и т. Д. Он знает, что он должен зарезервировать соответствующее пространство в памяти, но на самом деле не выбирает это место, пока несколько позже в процесс после выполнения анализа живучести и, возможно, регистрации распределения. Как тогда компоновщик узнает, какой адрес предоставить машинному коду для кода окончательной сборки? Он либо знает конечное местоположение, либо знает, как добраться до места. Со стеком довольно просто сослаться на один из двух элементов на основе местоположения, указатель на кадр стека и затем смещение в кадре. Это в основном потому, что компоновщик не может знать местоположение стекового фрейма до времени выполнения.

Прежде всего, попытайтесь оценить пиковую производительность - изучите https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf В частности, Приложение С.

В вашем случае это таблица C-10, которая показывает, что инструкция POPCNT имеет задержку = 3 такта и пропускную способность = 1 такт. Пропускная способность показывает вашу максимальную скорость в тактах (умножьте на частоту ядра и 8 байтов в случае popcnt64, чтобы получить максимально возможное значение пропускной способности).

Теперь проверьте, что сделал компилятор, и суммируйте пропускную способность всех других инструкций в цикле. Это даст наилучшую оценку сгенерированного кода.

Наконец, посмотрите на зависимости данных между инструкциями в цикле, так как они будут вызывать большую задержку, а не пропускную способность, поэтому разделите инструкции одной итерации в цепочках потока данных и рассчитайте задержку между ними, а затем наивно извлекайте максимальную из них. это даст приблизительную оценку с учетом зависимостей потока данных.

Однако в вашем случае правильное написание кода устранит все эти сложности. Вместо того, чтобы накапливаться в одной переменной count, просто накапливайте в разные (например, count0, count1, ... count8) и суммируйте их в конце. Или даже создайте массив count [8] и накапливайте его элементы - возможно, он будет даже векторизован, и вы получите намного лучшую пропускную способность.

PS и никогда не запускайте эталонный тест в течение секунды, сначала прогрейте ядро, затем выполните цикл в течение по крайней мере 10 секунд или лучше 100 секунд. в противном случае вы протестируете аппаратное обеспечение управления питанием и реализацию DVFS аппаратно:)

PPS Я слышал бесконечные споры о том, сколько времени должно действительно пройти тест. Самые умные люди даже спрашивают, почему 10 секунд, а не 11 или 12. Я должен признать, что это забавно в теории. На практике вы просто стоите и запускаете бенчмарк сто раз подряд и записываете отклонения. Это смешно. Большинство людей меняют источник и запускают Bench после этого ровно ОДИН РАЗ, чтобы получить новый рекорд производительности. Делай правильные вещи правильно.

Еще не убежден? Просто используйте вышеупомянутую C-версию теста assp1r1n3 ( /questions/37926904/zamena-32-razryadnogo-schetchika-tsiklov-na-64-razryadnyij-vvodit-sumasshedshie-otkloneniya-proizvoditelnosti/37926910#37926910) и попробуйте 100 вместо 10000 в цикле повтора.

Мой 7960X показывает, с RETRY=100:

Счетчик: 203182300 Прошло: 0.008385 секунд Скорость: 12.505379 ГБ / с

Количество: 203182300 Прошло: 0,011063 секунды Скорость: 9,478225 ГБ / с

Количество: 203182300 Прошло: 0,011188 секунд Скорость: 9,372327 ГБ / с

Счетчик: 203182300 Прошло: 0,010393 с. Скорость: 10,089252 ГБ / с

Количество: 203182300 Прошло: 0,009076 секунд Скорость: 11,553283 ГБ / с

с RETRY=10000:

Счетчик: 20318230000 Прошло: 0,661791 сек. Скорость: 15,844519 ГБ / с

Количество: 20318230000 Прошло: 0,665422 секунд Скорость: 15,758060 ГБ / с

Счетчик: 20318230000 Прошло: 0,660983 секунды. Скорость: 15,863888 ГБ / с.

Счетчик: 20318230000 Прошло: 0,665337 секунд. Скорость: 15,760073 ГБ / с.

Счетчик: 20318230000 Прошло: 0,662138 секунд Скорость: 15,836215 ГБ / с

PPPS Наконец-то о "принятом ответе" и других тайнах;-)

Давайте воспользуемся ответом assp1r1n3 - у него ядро ​​2,5 ГГц. POPCNT имеет 1 тактовый выход, его код использует 64-битное popcnt. Таким образом, для его настройки математика составляет 2,5 ГГц * 1 тактовая частота * 8 байт = 20 ГБ / с. Он видит скорость 25 Гбит / с, возможно, из-за турбонаддува до 3 ГГц.

Таким образом, перейдите на ark.intel.com и найдите i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70-GHz-?q=i7-4870HQ

Это ядро ​​может работать до 3,7 ГГц, а реальная максимальная скорость его оборудования составляет 29,6 ГБ / с. Так где еще 4Гб / с? Возможно, он расходуется на логику цикла и другой окружающий код в каждой итерации.

Где эта ложная зависимость? аппаратное обеспечение работает почти с максимальной скоростью. Может быть, моя математика плохая, иногда это случается:)

PPPPPS Тем не менее, люди, предположившие, что HW errata является виновником, поэтому я следую предложению и создаю пример встроенного asm, см. Ниже

На моем 7960X первая версия (с одним выходом для cnt0) работает со скоростью 11 МБ / с, вторая версия (с выходом для cnt0, cnt1, cnt2 и cnt3) работает со скоростью 33 МБ / с. И можно сказать - вуаля! это выходная зависимость.

Хорошо, возможно, я подчеркнул, что не имеет смысла писать такой код, и это не проблема выходной зависимости, а глупая генерация кода. Мы не тестируем аппаратное обеспечение, мы пишем код для максимальной производительности. Вы можете ожидать, что HW OOO будет переименовывать и скрывать эти "выходные зависимости", но, gash, просто делайте правильные вещи правильно, и вы никогда не столкнетесь с какой-либо тайной.

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}
Другие вопросы по тегам