Заміна 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 , щоб виконати 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 CPU @ 3.50 GHz, запуск test 1 (так що 1 випадкові дані MB):

  • unsigned 41959360000 0.401554 sec 26.113 GB / s
  • uint64_t 41959360000 0,759822 сек 13.8003 GB / s

Як ви бачите, пропускна здатність версії uint64_t тільки наполовину - одна з версій unsigned ! Проблема полягає в тому, що генерується інша збірка, але чому? По-перше, я подумав про помилку компілятора, тому я спробував c> (Ubuntu C> версія 3.4-1ubuntu3):

 c> 

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

Отже, це майже той же результат і як і раніше дивний. Але тепер це стає супер дивним. Я заміняю розмір буфера, який був прочитаний з введення з константою 1 , тому я змінюю:

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

до

 uint64_t size = 1 << 20; 

Таким чином, компілятор тепер знає розмір буфера під час компіляції. Можливо, він може додати деякі оптимізації! Ось цифри для g++ :

Тепер обидві версії однаково швидкі. Однак unsigned отримав ще повільніше! Він впав з 26 до 20 GB/s , таким чином, замінивши непостійне на постійне значення, призведе до деоптімізаціі. Серйозно, я поняття не маю, що тут відбувається! Але тепер до c> з новою версією:

Зачекайте, що? Тепер обидві версії впали до повільного числа в 15 біт / с. Таким чином, заміна непостійного на постійне значення навіть призводить до повільного коду в випадках для C>

Я попросив колегу з CPU

1250
01 авг. заданий gexicide 01 Серпня. 2014-08-01 13:33 '14 13:33 2014-08-01 13:33
@ 10 відповідей

Culprit: False Залежність даних (і компілятор навіть не знає про це)

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

 popcnt src, dest 

схоже, має помилкову залежність від регістру призначення dest . Незважаючи на те, що інструкція тільки записує на неї, команда буде чекати, поки dest не буде готова до виконання.

Ця залежність не просто утримує 4 popcnt від однієї ітерації циклу. Він може переносити чергуються ітерації циклу, що унеможливлює паралельне використання процесором різних ітерацій циклу.

unsigned vs. uint64_t і інші твіки не впливають безпосередньо на проблему. Але вони впливають на розподільник регістрів, який присвоює регістри змінним.

У вашому випадку швидкості є прямим результатом того, що застрягло в ланцюжку залежностей (false) в залежності від того, що вирішило зробити розподільник регістрів.

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

Чому у процесора є така помилкова залежність?

Ми можемо тільки здогадуватися, але, швидше за все, у 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
Цей критерій змінює кількість popcnt , які знаходяться в ланцюжку залежностей (false).

 False Chain 0: 41959360000 0.57748 sec 18.1578 GB/s False Chain 1: 41959360000 0.585398 sec 17.9122 GB/s False Chain 2: 41959360000 0.645483 sec 16.2448 GB/s False Chain 3: 41959360000 0.929718 sec 11.2784 GB/s False Chain 4: 41959360000 1.23572 sec 8.48557 GB/s 
1404
02 авг. відповідь дан Mysticial 02 Серпня. 2014-08-02 01:41 '14 в 1:41 2014-08-02 1:41

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

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

Це, очевидно, хак, оскільки розмір змінної насправді не 64-бітний, так як інші частини програми як і раніше використовують 32-бітну версію, але до тих пір, поки внутрішній цикл popcount домінує над продуктивністю, це хороший старт.

Потім я скопіював код внутрішнього циклу з 32-розрядної версії програми, зламав її до 64 біт, перегравши регістри, щоб замінити її внутрішнім циклом 64-бітової версії. Цей код також працює так само швидко, як 32-розрядної версії.

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

(Застереження: я зламав збірку, міг щось зламати, не помітивши. Так думай.)

border=0
49
02 авг. відповідь дан EOF 02 Серпня. 2014-08-02 01:55 '14 о 1:55 2014-08-02 1:55

Це не відповідь, але його важко прочитати, якщо я поставлю результати в коментарі.

Я отримую ці результати за допомогою Mac Pro ( Westmere 6-Cores Xeon 3.33 GHz). Я скомпілював його з c> (-O2 отримати той же результат).

c>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 

c>uint64_t size=1<<20;

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

Я також спробував:

  • Скасуйте порядок тестування, результат буде таким же, щоб виключити фактор кеша.
  • Виконайте оператор for в зворотному порядку: for (uint64_t i=size/8;i>0;i-=4) . Це дає той же результат і доводить, що компілятор досить розумний, щоб не розділити розмір на 8 на кожній ітерації (як і очікувалося).

Ось моє дике припущення:

Коефіцієнт швидкості входить в три частини:

  • кеш коду: uint64_t версія має більший розмір коду, але це не впливає на мій процесор Xeon. Це уповільнює роботу 64-розрядної версії.

  • Використовувані інструкції. Зверніть увагу не тільки на кількість циклів, але і на буфер, з 32-бітовим і 64-розрядних індексом на двох версіях. Доступ до покажчика з 64-бітовим зміщенням запитує виділений 64-бітний регістр і адресацію, в той час як ви можете використовувати негайне для 32-бітного зміщення. Це може зробити 32-розрядну версію швидше.

  • Інструкції видаються тільки в 64-бітної компіляції (тобто попередньої вибірці). Це робить 64-біт швидше.

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

24
01 авг. відповідь дан Non-maskable Interrupt 01 Серпня. 2014-08-01 14:04 '14 о 14:04 2014-08-01 14:04

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

Таким чином, між піковим конвеєром і множинної пропускною спроможністю і відмовою від цих механізмів ми маємо шість показників продуктивності. Досить добре відомо, що складність набору інструкцій x86 робить його досить простим для химерного розлому. У наведеному вище документі є відмінний приклад:

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

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

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

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

Я знаю, що це не ретельний аналіз, але це правдоподібне пояснення.

10
01 авг. відповідь дан Gene 01 Серпня. 2014-08-01 23:12 '14 о 23:12 2014-08-01 23:12

Я спробував це з Visual Studio 2013 Express , використовуючи покажчик замість індексу, який трохи прискорив процес. Я підозрюю, що це тому, що адресація зміщена + регістр, а не зсув + регістр + (реєстр <3). Код на С ++.

  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:

 $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 
10
02 авг. відповідь дан rcgldr 02 Серпня. 2014-08-02 06:48 '14 в 6:48 2014-08-02 6:48

Ви пробували передати -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 
9
04 авг. відповідь дан Dangelov 04 Серпня. 2014-08-04 18:37 '14 о 18:37 2014-08-04 18:37

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

Try:

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

У вас також є дивне згладжування, що я не впевнений, що він відповідає суворим правилам псевдонімів.

7
01 авг. відповідь дан Ben Voigt 01 Серпня. 2014-08-01 21:33 '14 о 21:33 2014-08-01 21:33

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: 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 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: dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt 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: 
5
04 мая '16 в 14:14 2016-05-04 14:14 відповідь дан assp1r1n3 04 травня '16 о 14:14 2016-05-04 14:14

Добре, я хочу дати невелику відповідь на один з підпитань, заданих ФП, які, здається, не розглядаються в існуючих питаннях. Застереження: я не займався ні тестуванням, ні генерацією коду, ні дизассемблирования, просто хотів поділитися думкою, яку інші могли б роз'яснити.

Чому static змінює продуктивність?

Вже згадана рядок: uint64_t size = atol(argv[1])<<20;

коротка відповідь

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

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

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

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