Zašto je brža obrada sortiranog niza od nesortiranog niza?

Ovdje je dio C + + koda koji se čini vrlo osebujan. Iz nekog čudnog razloga, sortiranje podataka čudesno čini kod gotovo šest puta bržim.

 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); } } 

S nešto sličnim, ali manje ekstremnim rezultatom.


Moja prva misao je bila da sortiranje donosi podatke u cache, ali onda sam pomislio kako je to glupo, jer je polje samo generirano.

  • Što se događa
  • Zašto je sortirano polje obrađeno brže od nesortiranog niza?
  • Kôd sumira neke nezavisne pojmove, a redoslijed nije važan.
22.512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG je postavljen 27. lipnja 2012. u 4:51 2012-06-27 16:51
@ 26 odgovora

Vi ste žrtva odstupanja od grananja .


Što je predviđanje grana?

Razmotrite željeznički čvor:

2019

Predviđanje grana.

Kod sortiranog niza, uvjet data[c] >= 128 je prvi false za niz vrijednosti, a zatim postaje true za sve naknadne vrijednosti. Lako je predvidjeti. S nesortiranim nizom plaćate troškove podjele.

3815
27 июня '12 в 16:54 2012-06-27 16:54 odgovor je dao Daniel Fischer 27. lipnja 2012. u 4:54 pm 2012-06-27 16:54

Razlog zbog kojeg se performanse dramatično poboljšavaju pri sortiranju podataka je da je kazna za predviđanje grana eliminirana, kao što je Mysticial savršeno objasnio.

Sada, ako pogledamo kod

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

možemo ustanoviti da značenje ove, if... else... grane, znači dodavanje nečega kada je uvjet zadovoljen. Ovaj tip grane može se lako pretvoriti u uvjetnog operatora, koji će se sastaviti u uvjetnu naredbu kretanja: cmovl , u x86 sustavu. Podružnica i, prema tome, potencijalna kazna za predviđanje grane je uklonjena.

U C , dakle, C++ , operator koji će biti izravno (bez ikakve optimizacije) sastavljen u naredbu uvjetnog pomaka u x86 je ternarni operator ...?... :... ...?... :... Stoga, prepisujemo gornju izjavu da bude ekvivalentna:

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

Održavajući čitljivost, možemo provjeriti faktor ubrzanja.

Za Intel Core i7 -2600K @ 3.4 GHz i referentni test za izdanje Visual Studio 2010 (format kopiran iz Mysticial-a):

x86

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

64

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

Rezultat je pouzdan u nekoliko testova. Dobivamo značajno ubrzanje kada je rezultat grananja nepredvidljiv, ali malo smo patili kada je predvidljivo. Zapravo, kada se koristi uvjetni potez, izvedba ostaje ista bez obzira na uzorak podataka.

Pogledajmo sada bliže, istražujući x86 gradnju koju generiraju. Radi jednostavnosti koristimo dvije funkcije max1 i max2 .

max1 koristi uvjetnu granu, if... else... :

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

max2 koristi ternarni operator ...?... :... ...?... :... :

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

Na računalu x86-64, GCC -S izgrađuje skupinu ispod.

 :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 koristi mnogo manje koda zbog korištenja cmovge instrukcije. No, pravi dobitak je da max2 ne uključuje prijelaze na max2 , jmp , što može dovesti do značajnih performansi max2 ako je predviđeni rezultat max2 .

Zašto onda uvjetno kretanje funkcionira bolje?

U tipičnom x86 procesoru, izvršavanje x86 je podijeljeno u nekoliko faza. Grubo govoreći, imamo različite hardverske za različite stupnjeve. Stoga ne moramo čekati kraj jednog uputa da započnemo novi. To se zove cjevovod .

U slučaju grananja, sljedeća naredba određena je prethodnom, tako da ne možemo izvoditi pipelining. Moramo ili čekati ili predvidjeti.

U slučaju uvjetnog pomaka, izvršenje naredbe uvjetnog pomaka podijeljeno je u nekoliko stupnjeva, ali raniji stadiji, kao što su Fetch i Decode , ne ovise o rezultatu prethodne instrukcije; samo posljednje faze trebaju rezultat. Dakle, čekamo dio vremena izvršenja jedne instrukcije. Zato je verzija uvjetnog poteza sporija od grane kada je predviđanje jednostavno.

Knjiga " Računalni sustavi: perspektiva za programera", drugo izdanje, to detaljno objašnjava. Možete provjeriti odjeljak 3.6.6 za upute o uvjetnom kretanju, cijelo poglavlje 4 za arhitekturu procesora i odjeljak 5.11.2 za posebno rukovanje za kazne predviđanja i pogrešnu predviđanje.

Ponekad neki moderni prevodioci mogu optimizirati naš kod za izgradnju s višim performansama, ponekad neki kompilatori ne mogu (ovaj kod koristi vlastiti Visual Studio prevodilac). Poznavanje razlike u performansama između grananja i uvjetnog kretanja, kada je nepredvidivo, može nam pomoći u pisanju koda s boljim performansama kada skripta postane toliko složena da ih prevodilac ne može automatski optimizirati.

3064
28 июня '12 в 5:14 2012-06-28 05:14 odgovor je dao WiSaGaN 28. lipnja '12 u 5:14 am 2012-06-28 05:14

Ako vas zanimaju još optimizacije koje se mogu izvršiti ovim kôdom, razmislite o sljedećem:

Počevši od početnog ciklusa:

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

S permutacijom ciklusa možemo sigurno promijeniti ovaj ciklus u:

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

Tada možete vidjeti da je uvjet if konstantan tijekom izvršavanja petlje i , tako da možete izvući if se:

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

Tada ćete vidjeti da se unutarnja petlja može srušiti u jedan izraz, uz pretpostavku da to dopušta model s pomičnim zarezom (na primjer, / fp: brzo)

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

To je 100.000 puta brže nego prije.

2105
03 июля '12 в 5:25 2012-07-03 05:25 odgovor je dan vulkan gavran 3. srpnja '12 u 5:25 am 2012-07-03 05:25

Nesumnjivo, neki od nas će biti zainteresirani za načine identificiranja koda koji je problematičan za procesor predviđanja CPU-a. Alat Valgrind cachegrind ima sintaksu grane prediktora grane koja se aktivira pomoću --branch-sim=yes . Pokrećući ga primjerima u ovom pitanju, broj vanjskih petlji, smanjenih na 10.000 i sastavljenih s g++ , daje sljedeće rezultate:

Poredaj po:

 ==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% ) 

nerazvrstani:

 ==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% ) 

Vraćajući se na linearni izlaz koji je stvorio cg_annotate , vidimo za cg_annotate ciklus:

Poredaj po:

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

nerazvrstani:

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

To vam omogućuje da lako identificirate problemsku liniju - u nesortiranoj verziji linija if (data[c] >= 128) uzrokuje Bcm pogrešno predviđenih uvjetnih Bcm ( Bcm ) kao dijela modela prediktora grane cachegrinda, dok uzrokuje samo 10.006 sortiranih verzija.


Alternativno, u Linuxu možete koristiti podsustav brojača performansi za izvođenje istog zadatka, ali s vlastitom izvedbom pomoću CPU brojača.

 perf stat ./sumtest_sorted 

Poredaj po:

  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 

nerazvrstani:

  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 

Također može stvoriti zabilješke izvornog koda s rastavljanjem.

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

Pojedinosti potražite u priručniku za izvedbu .

1758
12 окт. odgovor dao caf 12 oct. 2012-10-12 08:53 '12 u 8:53 2012-10-12 08:53

Upravo sam pročitao ovo pitanje i njegove odgovore i smatram da odgovor nedostaje.

Uobičajeni način za ukidanje predviđanja grana, koje mi se činilo da dobro rade na upravljanim jezicima, jest pretraživanje tablice umjesto korištenja grananja (iako u ovom slučaju nisam je provjerio).

Ovaj pristup djeluje općenito ako:

  1. ovo je mala tablica i najvjerojatnije će biti spremljena u procesor i
  2. Radite u prilično uskoj petlji i / ili procesor može unaprijed učitati podatke.

Pozadina i zašto

S točke gledišta procesora, vaša memorija je spora. Kako bi se nadoknadila razlika u brzini, nekoliko procesora (L1 / L2 cache) ugrađeno je u vaš procesor. Zamislite da radite svoje dobre izračune i otkrijete da vam je potreban dio memorije. Procesor će izvršiti operaciju učitavanja i učitati dio memorije u predmemoriju, a zatim upotrijebiti predmemoriju za obavljanje preostalih izračuna. Budući da je memorija relativno spora, ovo "opterećenje" će usporiti vaš program.

Poput predviđanja grana, optimiziran je u Pentium procesorima: procesor predviđa da treba učitati neke podatke i pokušava ih učitati u predmemoriju prije nego operacija dođe u cache. Kao što smo već vidjeli, predviđanje grananja ponekad je jako pogrešno - u najgorem slučaju, morate se vratiti i zapravo čekati na memorijsko opterećenje koje će trajati vječno ( drugim riječima: neuspješno predviđanje grana je loše, opterećenje memorije nakon kvara predikcije grane je strašno! ).

Srećom za nas, ako je shema pristupa memoriji predvidljiva, procesor će je učitati u svoju brzu memoriju i sve je u redu.

Prvo što trebamo znati je da je malo? Iako je manja veličina obično bolja, pravilo je držati se tablica pretraživanja <= 4096 bajtova. Kao gornja granica: ako je referentna tablica veća od 64 KB, vjerojatno bi trebala biti revidirana.

Izradite stol

Tako smo otkrili da možemo napraviti mali stol. Sljedeća stvar koju trebate učiniti je zamijeniti funkciju pretraživanja. Funkcije pretraživanja obično su male funkcije koje koriste nekoliko osnovnih cjelobrojnih operacija (i, ili, xor, pomak, dodavanje, uklanjanje i eventualno množenje). Želite da vaš unos bude preveden tražeći neku vrstu "jedinstvenog ključa" u vašoj tablici, koji vam onda jednostavno daje odgovor na sav posao koji ste željeli učiniti.

U ovom slučaju:> = 128 znači da možemo spremiti vrijednost, <128 znači da ćemo je se riješiti. Najlakši način da to učinite je da koristite 'AND': ako ga spremimo, mi I to je sa 7FFFFFFF; если мы хотим избавиться от него, мы И это с 0. Отметим также, что 128 - это степень 2 - так что мы можем пойти дальше и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и большим количеством 7FFFFFFFF годов.

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