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




software optimization (8)

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

  • unsigned 41959360000 0,401554 sec 26.113 GB / s
  • uint64_t 41959360000 0,759822 с 13,8003 ГБ / с

Как вы видите, пропускная способность версии uint64_t составляет только половину unsigned версии! Проблема заключается в том, что генерируется другая сборка, но почему? Во-первых, я подумал о ошибке компилятора, поэтому я попробовал clang++ (Ubuntu Clang version 3.4-1ubuntu3):

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

Результат: test 1

  • unsigned 41959360000 0.398293 sec 26.3267 GB / s
  • uint64_t 41959360000 0,680954 sec 15.3986 Гб / с

Таким образом, это почти тот же результат и по-прежнему странный. Но теперь это становится супер странным. Я заменяю размер буфера, который был прочитан с ввода с константой 1 , поэтому я меняю:

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

в

uint64_t size = 1 << 20;

Таким образом, компилятор теперь знает размер буфера во время компиляции. Возможно, он может добавить некоторые оптимизации! Вот цифры для g++ :

  • unsigned 41959360000 0.509156 sec 20.5944 GB / s
  • uint64_t 41959360000 0.508673 sec 20.6139 GB / s

Теперь обе версии одинаково быстры. Тем не менее, unsigned получил еще медленнее ! Он опустился с 26 до 20 GB/s , поэтому замена непостоянного на постоянное значение приведет к деоптимизации . Серьезно, я понятия не имею, что здесь происходит! Но теперь clang++ с новой версией:

  • unsigned 41959360000 0,677009 с 15,4884 ГБ / с
  • uint64_t 41959360000 0,7676909 с 15,4906 ГБ / с

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

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

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

Возьмем первый пример (один с atol(argv[1]) ) и ставим перед переменной переменную, то есть:

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

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

  • unsigned 41959360000 0,396728 sec 26,4306 ГБ / с
  • uint64_t 41959360000 0.509484 сек 20.5811 ГБ / с

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

Мой вопрос

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

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

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

Разборка

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

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

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


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

Пытаться:

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

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


Я пробовал это с помощью 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]

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

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

clang с 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

clang with 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-бит быстрее.

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


Я закодировал эквивалентную программу для экспериментов, и я могу подтвердить это странное поведение. Более того, gcc считает, что 64-битное целое число (вероятно, должно быть, size_t ) будет лучше, так как использование uint_fast32_t заставляет gcc использовать 64-разрядный uint.

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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

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

PPS Я слышал бесконечные дебаты о том, сколько времени должно проводиться в реальном времени. Самые умные люди даже спрашивают, почему 10 секунд не 11 или 12. Я должен признать, что это смешно в теории. На практике вы просто заходите и запускаете столик по сто раз подряд и записываете отклонения. Это IS смешно. Большинство людей меняют исходный код и запускают скамью после этого точно в один голос, чтобы записать новую запись о производительности. Правильно делайте правильно.

Не уверен еще? Просто используйте выше C-версию теста assp1r1n3 ( https://.com/a/37026212/9706746 ) и попробуйте 100 вместо 10000 в цикле повторов.

Мои шоу 7960X, с RETRY = 100:

Количество: 203182300 Истекшее: 0.008385 секунд Скорость: 12.505379 GB / s

Количество: 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 GB / s

Количество: 20318230000 Истек: 0.665337 секунд Скорость: 15.760073 ГБ / с

Количество: 20318230000 Истек: 0.662138 секунд Скорость: 15.836215 ГБ / с

PPPS Наконец, на «принятом ответе» и других mistery ;-)

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

Таким образом, перейдите на сайт 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, являются виновниками, поэтому я следую предложению и создаю пример inm asm, см. Ниже.

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

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

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

Вы пробовали передать -funroll-loops -fprefetch-loop-arrays ?

Я получаю следующие результаты с этими дополнительными оптимизациями:

[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

TL; DR: Вместо этого используйте __builtin intrinsics.

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

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




compiler-optimization