Защо е по-бързо да се обработва сортиран масив от несортиран масив?

Тук е част от C + + код, който изглежда много странно. По някаква странна причина, сортирането на данните по чудо прави кода почти шест пъти по-бърз.

 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 юни 2012 г. в 4:51 ч. 2012-06-27 16:51
@ 26 отговора

Вие сте жертва на отклонение от разклонението .


Какво е предсказание на клон?

Помислете за железопътния възел:

2019

Предвиждане на клонове.

Със сортиран масив условието data[c] >= 128 е първото false за стойността на низ, а след това става true за всички следващи стойности. Лесно е да се предскаже. С несортиран масив плащате разходи за разклоняване.

3815
27 июня '12 в 16:54 2012-06-27 16:54 отговорът е даден от Даниел Фишер на 27 юни 2012 г. в 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 GHz и референтен тест за освобождаване на 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 процесор, изпълнението на 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 05: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 :

 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 отговорът е даден на вулкан гарван на 3 юли '12 в 5:25 ч. 2012-07-03 05:25

Несъмнено някои от нас ще се интересуват от начините за идентифициране на код, който е проблематичен за процесора за предсказване на процесора. Инструментът Valgrind cachegrind има синтаксис на клоновия предиктор, който се активира с помощта на --branch-sim=yes . Изпълнявайки го чрез примерите в този въпрос, броят на външните контури, намален до 10 000 и компилиран с 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% ) 

Несортирани:

 ==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 към линейния изход, създаден от 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]; . . . . } . . . . } 

Несортирани:

  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) причинява Bcm неправилно прогнозирани условни разклонения ( Bcm ) като част от модела на предсказуем клон на кейгеринг, докато причинява само 10 006 сортирани версия.


Алтернативно, в Linux можете да използвате подсистема за брояч на производителности, за да изпълните същата задача, но със собствена производителност, използваща броячи на процесори.

 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 

Несортирани:

  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) ... 

За подробности вижте ръководството за изпълнение .

1758
12 окт. отговор, даден caf 12 oct. 2012-10-12 08:53 '12 в 8:53 2012-10-12 08:53

Просто прочетох този въпрос и неговите отговори и чувствам, че отговорът липсва.

Обичайният начин за премахване на предсказанието на клонове, което ми се струваше, че работи особено добре в управляваните езици, е да се търси в таблицата, вместо да се използва разклоняване (въпреки че в този случай не съм го проверил).

Този подход работи по принцип, ако:

  1. това е малка таблица и най-вероятно ще бъде кеширана в процесора и
  2. Работите в доста тесен кръг и / или процесорът може да зарежда данни.

История и защо

От гледна точка на процесора, вашата памет е бавна. За да компенсира разликата в скоростта, няколко процесора (L1 / L2 кеш) са вградени в процесора. Представете си, че правите добри изчисления и откривате, че имате нужда от част от паметта. Процесорът ще изпълни операцията на зареждане и ще зареди част от паметта в кеша, след което ще използва кеша, за да извърши останалите изчисления. Тъй като паметта е сравнително бавна, това "натоварване" ще забави вашата програма.

Подобно на предсказването на разклоненията, той беше оптимизиран в процесорите Pentium: процесорът прогнозира, че трябва да зареди някои от данните и се опитва да ги зареди в кеша, преди операцията да влезе в кеша. Както вече видяхме, предсказанието на клоновете понякога става ужасно погрешно - в най-лошия случай, трябва да се върнете и всъщност да чакате натоварване на паметта, което ще трае вечно (с други думи: неуспешно предсказване на разклонението, натоварването на паметта след грешка при предсказване на разклонение е ужасно! ).

За щастие за нас, ако схемата за достъп до паметта е предсказуема, процесорът ще я зареди в своя бърз кеш, и всичко е наред.

Първото нещо, което трябва да знаем е, че има малко? Въпреки че по-малък размер обикновено е по-добър, основното правило е да се придържате към таблици за търсене <= 4096 байта. Като горна граница: ако референтната ти таблица е по-голяма от 64 KB, вероятно би трябвало да се преразгледа.

Направете масата

Така открихме, че можем да създадем малка маса. Следващото нещо е да замените функцията за търсене. Функциите за търсене обикновено са малки функции, които използват няколко основни операции по цяло число (и, или, xor, смяна, добавяне, премахване и евентуално умножение). Искате вашите данни да бъдат преведени чрез търсене на някакъв "уникален ключ" в таблицата, който след това просто ви дава отговор на цялата работа, която искате да направите.

В този случай:> = 128 означава, че можем да запазим стойността, <128 означава, че ще се отървем от нея. Най-лесният начин да направите това е да използвате 'AND': ако го запазим, ние И това е с 7FFFFFFF; ако искаме да се отървем от него, ние И това е от 0. Отбележете също, че 128 е степен 2 - така че можем да отидем по-далеч и да направим таблица с 32768/128 цели числа и да я запълним с една нула и голям брой 7FFFFFFFF's.

Управлявани езици