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





4 Answers

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

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

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

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

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

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

optimization software

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

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




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

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

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

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

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

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

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




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



Related