border=0

"77.95.5.4 - 77.95.5.4"

Waarom is het sneller om een ​​gesorteerde array te verwerken dan een ongesorteerde array?

Hier is een stuk C ++ code dat heel eigenaardig lijkt. Om een ​​vreemde reden, het op miraculeuze wijze sorteren van de gegevens maakt de code bijna zes keer sneller.

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

Met een enigszins vergelijkbaar, maar minder extreem resultaat.


Mijn eerste gedachte was dat sorteren de gegevens naar de cache bracht, maar toen bedacht ik hoe stom het is omdat de array net is gegenereerd.

  • Wat is er aan de hand
  • Waarom wordt de gesorteerde array sneller verwerkt dan de ongesorteerde array?
  • De code vat een aantal onafhankelijke voorwaarden samen en de volgorde doet er niet toe.
22512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG is ingesteld op 27 juni '12 om 16:51 uur 2012-06-27 16:51
@ 26 antwoorden

U bent het slachtoffer van afwijking van vertakking .


Wat is branchevoorspelling?

Overweeg het spoorwegknooppunt:

2019

Voorspelling van takken.

Met een gesorteerde array is de voorwaarde data[c] >= 128 de eerste false voor de tekenreeks, en wordt vervolgens true voor alle volgende waarden. Het is gemakkelijk te voorspellen. Met een ongesorteerde array betaalt u voor vertakkingskosten.

3815
27 июня '12 в 16:54 2012-06-27 16:54 het antwoord wordt gegeven door Daniel Fischer 27 juni '12 op 4:54 2012-06-27 16:54

De reden dat de prestaties dramatisch worden verhoogd wanneer gegevens worden gesorteerd, is dat de straf voor vertakkingsvoorspelling wordt geëlimineerd, zoals Mysticial perfect verklaart.

Nu, als we naar de code kijken

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

we kunnen merken dat de betekenis van deze bepaalde if... else... branch is om iets toe te voegen wanneer aan de voorwaarde is voldaan. Dit type branch kan eenvoudig worden omgezet in een voorwaardelijke operator, die wordt gecompileerd tot een voorwaardelijke bewegingsinstructie: cmovl in het x86 systeem. De vertakking en daarmee de potentiële straf voor vertakkingsvoorspelling wordt verwijderd.

In C , dus C++ , is de operator die direct (zonder enige optimalisatie) wordt gecompileerd tot een voorwaardelijke verplaatsinstructie in x86 een drietallige operator ...?... :... ...?... :... Daarom herschrijven we de bovenstaande verklaring als gelijkwaardig:

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

Door de leesbaarheid te behouden, kunnen we de versnellingsfactor controleren.

Voor de Intel Core i7 -2600K @ 3.4 GHz en Visual Studio 2010-releasemodus, de benchmarktest (formaat gekopieerd van 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 

Het resultaat is betrouwbaar in verschillende tests. We krijgen een aanzienlijke versnelling wanneer het resultaat van vertakking onvoorspelbaar is, maar we lijden een beetje als het voorspelbaar is. Wanneer een voorwaardelijke beweging wordt gebruikt, blijft de prestatie hetzelfde ongeacht het gegevenspatroon.

Laten we nu eens goed kijken naar de x86 build die ze genereren. Voor de eenvoud gebruiken we twee functies max1 en max2 .

max1 gebruikt de voorwaardelijke vertakking, if... else... :

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

max2 gebruikt de ternaire operator ...?... :... ...?... :... :

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

Op de x86-64-computer bouwt de GCC -S hieronder.

 :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 gebruikt veel minder code vanwege het gebruik van de cmovge instructie. Maar de echte winst is dat max2 geen max2 jmp overgangen bevat, wat kan leiden tot aanzienlijke max2 prestaties als het voorspelde resultaat max2 .

Dus waarom werkt de voorwaardelijke beweging beter?

In een typische x86 processor is x86 uitvoering van x86 onderverdeeld in verschillende fasen. Grof gezegd hebben we verschillende hardware voor verschillende fasen. Daarom hoeven we niet te wachten op het einde van een instructie om een ​​nieuwe te starten. Dit wordt pipelining genoemd .

In het geval van vertakking, wordt de volgende instructie bepaald door de vorige, daarom kunnen we pipelining niet uitvoeren. We moeten wachten of voorspellen.

In het geval van een voorwaardelijke verplaatsing, is de uitvoering van de opdracht voor voorwaardelijke verplaatsing verdeeld in verschillende fasen, maar de eerdere fasen, zoals Fetch en Decode , zijn niet afhankelijk van het resultaat van de vorige instructie; alleen de laatste fasen hebben een resultaat nodig. We wachten dus op een deel van de uitvoeringstijd van één instructie. Dat is de reden waarom de voorwaardelijke verplaatsingsversie >

Het boek Computer Systems: A Prospect voor een programmeur, tweede editie, legt dit in detail uit. U kunt paragraaf 3.6.6 voor voorwaardelijke bewegingsinstructies, het volledige hoofdstuk 4 voor de processorarchitectuur en sectie 5.11.2 raadplegen voor speciale afhandeling voor voorspellingsstraffen en foutieve voorspelling.

Soms kunnen sommige moderne compilers onze code optimaliseren voor het bouwen met hogere prestaties, soms kunnen sommige compilers dit niet (deze code gebruikt zijn eigen Visual Studio-compiler). Het kennen van het verschil in prestaties tussen vertakking en voorwaardelijke beweging, wanneer het onvoorspelbaar is, kan ons helpen code te schrijven met betere prestaties wanneer het script zo complex wordt dat de compiler ze niet automatisch kan optimaliseren.

3064
28 июня '12 в 5:14 2012-06-28 05:14 het antwoord wordt gegeven door WiSaGaN 28 juni '12 om 17:14 uur 2012-06-28 05:14

Als u geïnteresseerd bent in nog meer optimalisaties die met deze code kunnen worden gemaakt, overweeg dan het volgende:

Uitgaande van de begincyclus:

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

Met loop-swapping kunnen we deze lus veilig wijzigen in:

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

Dan kun je zien dat de if toestand constant is tijdens het uitvoeren van loop i , dus je kunt eruit trekken if uit:

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

Dan zul je zien dat de binnenste lus samengevouwen kan worden tot één enkele uitdrukking, aannemende dat het drijvende-kommaboom dit toelaat (bijvoorbeeld / fp: snel)

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

Het is 100.000 keer sneller dan voorheen.

2105
03 июля '12 в 5:25 2012-07-03 05:25 het antwoord wordt gegeven vulcan raven 03 juli '12 om 5:25 2012-07-03 05:25

Ongetwijfeld zullen sommigen van ons geïnteresseerd zijn in manieren om code te identificeren die problematisch is voor een CPU-voorspellingsprocessor. Het Valgrind cachegrind gereedschap heeft een vertakkingsvoorsporensyntaxis die wordt geactiveerd met de --branch-sim=yes . Uitgaande van de voorbeelden in deze vraag, geeft het aantal externe lussen, verminderd tot 10.000 en gecompileerd met g++ , de volgende resultaten:

Sorteer op:

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

Wat betreft de lineaire output gecreëerd door cg_annotate , zien we voor de betreffende cyclus:

Sorteer op:

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

Hiermee kunt u eenvoudig de probleemlijn identificeren - in een ongesorteerde versie veroorzaakt de if (data[c] >= 128) Bcm incorrect voorspelde conditionele vertakkingen ( Bcm ) als onderdeel van het cachegrind-vertakkingsvoorspellingsmodel, terwijl het slechts 10.006 in gesorteerd roept versie.


Als alternatief kunt u in Linux een prestatiemeter-subsysteem gebruiken om dezelfde taak uit te voeren, maar dan met zijn eigen prestaties met CPU-tellers.

 perf stat ./sumtest_sorted 

Sorteer op:

  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 

Het kan ook broncode-annotaties maken met demontage.

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

Zie de prestatiehandleiding voor meer informatie .

1758
12 окт. antwoord gegeven caf 12 oct. 2012-10-12 08:53 '12 om 8:53 2012-10-12 08:53

Ik heb deze vraag en de antwoorden net gelezen en ik denk dat het antwoord ontbreekt.

De gebruikelijke manier om vertakkingsvoorspelling te elimineren, die mij vooral goed leek te werken in beheerde talen, is om in de tabel te zoeken in plaats van vertakking te gebruiken (hoewel ik dit in dit geval niet heb gecontroleerd).

Deze aanpak werkt in het algemeen als:

  1. dit is een kleine tabel en zal hoogstwaarschijnlijk in de cache worden opgeslagen in de processor, en
  2. U werkt in een vrij smalle lus en / of de processor kan gegevens vooraf laden.

Achtergrond en waarom

Vanuit het oogpunt van de processor is je geheugen traag. Om het snelheidsverschil te compenseren, zijn een aantal caches (L1 / L2-cache) in uw processor ingebouwd. Stel je dus voor dat je goede berekeningen doet en ontdekt dat je een stukje geheugen nodig hebt. De processor voert de laadbewerking uit en laadt een deel van het geheugen in de cache en gebruikt vervolgens de cache om de resterende berekeningen uit te voeren. Aangezien het geheugen relatief traag is, zal deze "belasting" uw programma vertragen.

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