Чому швидше обробляти відсортований масив, ніж несортоване масив?

Ось шматок коду на С ++, який здається дуже своєрідним. З якоїсь дивної причини сортування даних дивом робить код майже в шість разів швидше.

 import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } 

З трохи схожим, але менш екстремальним результатом.


Моя перша думка полягала в тому, що сортування наводить дані в кеш, але потім я подумав, як це нерозумно, тому що масив тільки що згенерований.

  • Що відбувається?
  • Чому швидше обробляється відсортований масив, ніж несортоване масив?
  • Код підсумовує деякі незалежні терміни, і порядок не має значення.
22512
27 июня '12 в 16:51 2012-06-27 16:51 заданий GManNickG 27 червня '12 о 16:51 2012-06-27 16:51
@ 26 відповідей

Ви є жертвою відхилення від розгалуження .


Що таке пророцтво гілок?

Розглянемо залізничний вузол:

2019

Прогнозування гілок.

З відсортованим масивом умова data[c] >= 128 є першим false для рядка значень, а потім стає true для всіх наступних значень. Це легко передбачити. При несортоване масиві ви платите за витрати на розгалуження.

3815
27 июня '12 в 16:54 2012-06-27 16:54 відповідь дан Daniel Fischer 27 червня '12 о 16:54 2012-06-27 16:54

Причина, по якій продуктивність різко підвищується при сортуванні даних, полягає в тому, що штраф за пророкування розгалужень усунутий, як прекрасно пояснено у відповіді Mysticial .

Тепер, якщо ми подивимося на код

 if (data[c] >= 128) sum += data[c]; 

ми можемо виявити, що сенс цієї конкретної гілки if... else... полягає в тому, щоб додати щось, коли умова виконана. Цей тип гілки може бути легко перетворений в оператор умовного переміщення, який буде скомпільовано в інструкцію умовного переміщення: cmovl , в системі x86 . Розгалуження і, отже, потенційне покарання за пророкування розгалуження видаляються.

У C , таким чином, C++ , оператор, який буде безпосередньо (без будь-якої оптимізації) компілюватися в інструкцію умовного переміщення в x86 , є потрійним оператором ...?... :... ...?... :... Тому ми переписуємо наведене вище твердження в еквівалентну:

 sum += data[c] >=128 ? data[c] : 0; 

Підтримуючи читабельність, ми можемо перевірити коефіцієнт прискорення.

Для Intel Core i7 -2600K @ 3,4 ГГц і режиму випуску Visual Studio 2010 еталонний тест (формат скопійовано з Mysticial):

x86

 // Branch - Random seconds = 8.885 // Branch - Sorted seconds = 1.528 // Branchless - Random seconds = 3.716 // Branchless - Sorted seconds = 3.71 

x64

 // Branch - Random seconds = 11.302 // Branch - Sorted seconds = 1.830 // Branchless - Random seconds = 2.736 // Branchless - Sorted seconds = 2.737 

Результат є надійним в декількох тестах. Ми отримуємо значне прискорення, коли результат розгалуження непередбачуваний, але ми трохи страждаємо, коли він передбачуваний. Фактично, при використанні умовного переміщення продуктивність залишається однаковою незалежно від шаблону даних.

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

max1 використовує умовну гілка, if... else... :

 int max1(int a, int b) { if (a > b) return a; else return b; } 

max2 використовує потрійний оператор ...?... :... ...?... :... :

 int max2(int a, int b) { return a > b ? a : b; } 

На комп'ютері x86-64 GCC -S створює збірку нижче.

 :max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret 

max2 використовує набагато менше коду через використання інструкції cmovge . Але реальний виграш в тому, що max2 не включає переходи по max2 , jmp , що може привести до значного max2 продуктивності, якщо прогнозований результат max2 .

Так чому ж умовний хід працює краще?

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

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

У разі умовного переміщення виконання команди умовного переміщення ділиться на кілька етапів, але більш ранні етапи, такі як Fetch і Decode , що не залежать від результату попередньої інструкції; тільки останні етапи потребують результаті. Таким чином, ми чекаємо частину часу виконання однієї інструкції. Ось чому версія умовного переміщення повільніше, ніж гілка, коли пророкування легко.

Книга " Комп'ютерні системи: перспектива для програміста", друге видання, пояснює це докладно. Ви можете перевірити Розділ 3.6.6 для умовних Інструкцій Переміщення, всю Главу 4 для Архітектури процесора і Розділ 5.11.2 для спеціальної обробки для Штрафів Пророцтва і помилково передбачення.

Іноді деякі сучасні компілятори можуть оптимізувати наш код для збірки з більшою продуктивністю, іноді деякі компілятори не можуть (розглянутий код використовує власний компілятор Visual Studio). Знаючи різницю в продуктивності між розгалуженням і умовним переміщенням, коли він непередбачуваний, може допомогти нам написати код з кращою продуктивністю, коли сценарій стає настільки складним, що компілятор не може їх оптимізувати автоматично.

3064
28 июня '12 в 5:14 2012-06-28 05:14 відповідь дан WiSaGaN 28 червня '12 в 5:14 2012-06-28 5:14

Якщо вам цікаво, що ще більше оптимізацій, які можуть бути зроблені з цим кодом, розгляньте наступне:

Починаючи з вихідного циклу:

 for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } } 

З перестановкою циклу ми можемо безпечно змінити цей цикл на:

 for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } } 

Потім ви можете бачити, що умова if є постійним під час виконання циклу i , тому ви можете витягнути if out:

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } } 

Потім ви побачите, що внутрішній цикл може бути згорнутий в одне єдине вираження, якщо припустити, що модель з плаваючою комою допускає її (наприклад, / fp: fast)

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } } 

Це на 100 000 разів швидше, ніж раніше

2105
03 июля '12 в 5:25 2012-07-03 05:25 відповідь дан vulcan raven 03 липня '12 о 5:25 2012-07-03 5:25

Безсумнівно, деякі з нас будуть цікавитися способами ідентифікації коду, який є проблематичним для процесора-провісника CPU. Інструмент Valgrind cachegrind має синтаксис розгалуження-провісника, який активується за допомогою прапора --branch-sim=yes . Запустивши його за прикладами в цьому питанні, кількість зовнішніх циклів, зменшених до 10000 і скомпільованих за допомогою g++ , дає наступні результати:

Сортування:

 ==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind) ==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind) ==32551== Mispred rate: 0.0% ( 0.0% + 1.2% ) 

Unsorted:

 ==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind) ==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind) ==32555== Mispred rate: 25.0% ( 25.0% + 1.2% ) 

Звернувши в лінійний висновок, створений cg_annotate , ми бачимо для розглянутого циклу:

Сортування:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 10,006 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Unsorted:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 164,050,007 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Це дозволяє вам легко ідентифікувати проблемну рядок - в несортованої версії рядок if (data[c] >= 128) викликає 164 050 007 невірно передбачених умовних гілок ( Bcm ) в рамках моделі розгалуження-провісника cachegrind, тоді як вона викликає лише 10 006 в відсортованої версії.


В якості альтернативи, в Linux ви можете використовувати підсистему лічильників продуктивності для виконання тієї ж задачі, але з власною продуктивністю з використанням лічильників CPU.

 perf stat ./sumtest_sorted 

Сортування:

  Performance counter stats for './sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K/sec 14 CPU-migrations # 0.001 K/sec 337 page-faults # 0.029 K/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed 

Unsorted:

  Performance counter stats for './sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K/sec 18 CPU-migrations # 0.001 K/sec 335 page-faults # 0.012 K/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed 

Він також може створювати анотацію вихідного коду з дизассемблирования.

 perf record -e branch-misses ./sumtest_unsorted perf annotate -d sumtest_unsorted 
  Percent | Source code  Disassembly of sumtest_unsorted ------------------------------------------------ ... : sum += data[c]; 0.00 : 400a1a: mov -0x14(%rbp),%eax 39.97 : 400a1d: mov %eax,%eax 5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax 4.60 : 400a26: cltq 0.00 : 400a28: add %rax,-0x30(%rbp) ... 

Детальніше див. Посібник з продуктивності .

тисяча сімсот п'ятьдесят-вісім
12 окт. відповідь дан caf 12 Жовтня. 2012-10-12 08:53 '12 о 8:53 2012-10-12 8:53

Я просто прочитав це питання і його відповіді, і я відчуваю, що відповідь відсутня.

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

Цей підхід працює в цілому, якщо:

  1. це невелика таблиця і, швидше за все, буде кешироваться в процесорі, і
  2. ви працюєте в досить вузькому циклі і / або процесор може попередньо завантажити дані.

Фон і чому

З точки зору процесора, ваша пам'ять працює повільно. Щоб компенсувати різницю в швидкості, в ваш процесор вбудована пара кешей (кеш L1 / L2). Отже, уявіть, що ви робите свої хороші обчислення і з'ясуйте, що вам потрібен шматок пам'яті. Процесор виконає операцію завантаження і завантажить частина пам'яті в кеш, а потім використовує кеш для виконання інших обчислень. Оскільки пам'ять щодо повільна, ця "завантаження" сповільнить вашу програму.

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

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

Перше, що нам потрібно знати, це те, що мало? Хоча менший розмір, як правило, краще, практичне правило полягає в тому, щоб дотримуватися таблиць пошуку розміром <= 4096 байт. Як верхньої межі: якщо ваша довідкова таблиця більше 64 КБ, її, ймовірно, варто переглянути.

побудова столу

Отже, ми з'ясували, що можемо створити невелику таблицю. Наступне, що потрібно зробити, це встановити на місце функцію пошуку. Функції пошуку зазвичай є невеликими функції, які використовують кілька основних цілочисельних операцій (і, або, xor, shift, add, remove і, можливо, множення). Ви хочете, щоб ваш введення був переведений за допомогою функції пошуку в якийсь "унікальний ключ" у вашій таблиці, який потім просто дає вам відповідь на всю роботу, яку ви хотіли, щоб він робив.

У цьому випадку:> = 128 означає, що ми можемо зберегти значення, <128 означає, що ми позбавимося від нього. Найпростіший спосіб зробити це - використовувати 'І': якщо ми зберігаємо це, ми І це з 7FFFFFFF; если мы хотим избавиться от него, мы И это с 0. Отметим также, что 128 - это степень 2 - так что мы можем пойти дальше и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и большим количеством 7FFFFFFFF годов.

Управляемые языки