Я искал самый быстрый способ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 CPU @ 3,50 ГГц, работаетtest 1 (так 1 МБ случайных данных):

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

Как видите, пропускная способностьuint64_t версиятолько половина один изunsigned версия! Кажется, проблема в том, что генерируются разные сборки, но почему? Сначала я подумал об ошибке компилятора, поэтому я попыталсяclang++ (Ubuntuлязг версия 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 / non-const bufsize:

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

13 ГБ / с версия отg ++ / u64 / non-const bufsize:

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

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

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