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

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

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

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Zonder std::sort(data, data + arraySize);, de code wordt uitgevoerd in 11.54 seconden.
  • Met de gesorteerde gegevens loopt de code in 1,93 seconden.

Aanvankelijk dacht ik dat dit misschien maar een taal of compiler-afwijking was. Dus ik probeerde het in Java.

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 in de cache brengt, maar toen bedacht ik me hoe dom dat is omdat de array zojuist is gegenereerd.

  • Wat is er aan de hand?
  • Waarom is het sneller om een ​​gesorteerde array te verwerken dan een ongesorteerde array?
  • De code somt enkele onafhankelijke voorwaarden op, en de volgorde zou er niet toe doen.

21647
2018-06-27 13:51


oorsprong


antwoorden:


Je bent een slachtoffer van branch voorspelling mislukken.


Wat is Branch-voorspelling?

Overweeg een spoorwegknooppunt:

Licensed Image Beeld door Mecanismo, via Wikimedia Commons. Gebruikt onder de CC-By-SA 3.0 licentie.

Omwille van het argument, veronderstel dat dit teruggaat in de 19e eeuw - voor lange afstands- of radiocommunicatie.

U bent de exploitant van een knooppunt en u hoort een trein aankomen. Je hebt geen idee op welke manier het hoort te gaan. Je stopt de trein om de bestuurder te vragen welke richting ze willen. En dan zet je de schakelaar op de juiste manier.

Treinen zijn zwaar en hebben veel inertie. Dus ze nemen een eeuwigheid om te starten en te vertragen.

Is er een betere manier? Je raadt welke richting de trein zal uitgaan!

  • Als je het goed hebt geraden, gaat het verder.
  • Als je het verkeerd hebt geraden, stopt de kapitein, maakt een back-up en roept naar je om de schakelaar om te draaien. Daarna kan het het andere pad opnieuw opstarten.

Als je elke keer goed raad, de trein zal nooit moeten stoppen.
Als je te vaak verkeerd gokt, de trein zal veel tijd besteden aan stoppen, back-uppen en opnieuw opstarten.


Overweeg een if-statement: Op processorniveau is het een filiaalinstructie:

image2

U bent een bewerker en u ziet een filiaal. Je hebt geen idee welke kant het op zal gaan. Wat doe jij? U stopt de uitvoering en wacht tot de vorige instructies voltooid zijn. Dan vervolg je het juiste pad.

Moderne processors zijn gecompliceerd en hebben lange pijplijnen. Dus ze duren voor altijd om te "opwarmen" en "te vertragen".

Is er een betere manier? Je raadt in welke richting de tak zal gaan!

  • Als je het goed hebt geraden, ga je door met het uitvoeren.
  • Als je het verkeerd hebt geraden, moet je de pijpleiding doorspoelen en terug naar de tak rollen. Vervolgens kunt u het andere pad opnieuw opstarten.

Als je elke keer goed raad, de uitvoering zal nooit moeten stoppen.
Als je te vaak verkeerd gokt, je brengt veel tijd door met afslaan, terugdraaien en opnieuw opstarten.


Dit is vertakkingsvoorspelling. Ik geef toe dat het niet de beste analogie is, omdat de trein alleen de richting kon aangeven met een vlag. Maar in computers weet de processor niet welke richting een tak zal gaan tot het laatste moment.

Dus hoe zou je strategisch raden om het aantal keren te minimaliseren dat de trein een back-up moet maken en het andere pad moet verlaten? Je kijkt naar de afgelopen geschiedenis! Als de trein 99% van de tijd linksaf gaat, dan raden we je aan. Als dit wordt afgewisseld, wisselt u uw schattingen af. Als het elke 3 keer een kant op gaat, denk je dat hetzelfde ...

Met andere woorden, u probeert een patroon te identificeren en te volgen. Dit is min of meer hoe branchevoorspellers werken.

De meeste toepassingen hebben goed opgevoede takken. Dus moderne vertakkingsvoorspellers halen meestal> 90% hitpercentages. Maar wanneer geconfronteerd met onvoorspelbare takken zonder herkenbare patronen, zijn vertakkingsvoorspellers vrijwel nutteloos.

Verder lezen: Artikel "Branch-voorspeller" op Wikipedia.


Zoals hierboven wordt gesuggereerd, is de schuldige deze if-verklaring:

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

Merk op dat de gegevens gelijkmatig zijn verdeeld tussen 0 en 255. Wanneer de gegevens zijn gesorteerd, komt ruwweg de eerste helft van de iteraties niet in de if-instructie. Daarna zullen ze allemaal de if-verklaring ingaan.

Dit is erg vriendelijk voor de vertakkingsvoorspeller, omdat de tak herhaaldelijk dezelfde richting volgt. Zelfs een eenvoudige verzadigingsteller zal de vertakking correct voorspellen, behalve de paar iteraties nadat deze van richting is veranderd.

Snelle visualisatie:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Wanneer de gegevens echter volledig willekeurig zijn, wordt de vertakkingsvoorspeller nutteloos gemaakt omdat deze geen willekeurige gegevens kan voorspellen. Dus zal er waarschijnlijk ongeveer 50% mispredictie zijn. (niet beter dan willekeurig gissen)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Dus wat kan er gedaan worden?

Als de compiler de tak niet in een voorwaardelijke zet kan optimaliseren, kunt u een aantal hacks proberen als u bereid bent de leesbaarheid voor de prestaties op te offeren.

Vervangen:

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

met:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Dit elimineert de vertakking en vervangt deze door enkele bitgewijze bewerkingen.

(Merk op dat deze hack niet strikt gelijk is aan de originele if-statement. Maar in dit geval is deze geldig voor alle invoerwaarden van data[].)

Benchmarks: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - x64 Release

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

opmerkingen:

  • Met de vestiging: Er is een enorm verschil tussen de gesorteerde en ongesorteerde gegevens.
  • Met de hack: Er is geen verschil tussen gesorteerde en ongesorteerde gegevens.
  • In het geval C ++ is de hack eigenlijk een beetje langzamer dan met de filiaal wanneer de gegevens zijn gesorteerd.

Een algemene vuistregel is om gegevensafhankelijke vertakkingen in kritieke lussen te vermijden. (zoals in dit voorbeeld)


Bijwerken:

  • GCC 4.6.1 met -O3 of -ftree-vectorize op x64 kan een voorwaardelijke zet genereren. Er is dus geen verschil tussen de gesorteerde en ongesorteerde gegevens - beide zijn snel.

  • VC ++ 2010 kan geen voorwaardelijke bewegingen voor deze branche genereren, zelfs niet onder /Ox.

  • Intel Compiler 11 doet iets wonderbaarlijks. Het verwisselt de twee lussen, waardoor de onvoorspelbare tak naar de buitenste lus wordt gehesen. Dus het is niet alleen immuun voor de verkeerde voorspellingen, het is ook twee keer zo snel als wat VC ++ en GCC kunnen genereren! Met andere woorden, ICC profiteerde van de test-loop om de benchmark te verslaan ...

  • Als je de Intel Compiler de branchless-code geeft, maakt het gewoon out-right vectorizes ervan ... en is net zo snel als met de branch (met de loop-uitwisseling).

Dit laat zien dat zelfs volwassen moderne compilers enorm kunnen variëren in hun vermogen om code te optimaliseren ...


28564
2018-06-27 13:56



Branchevoorspelling.

Met een gesorteerde array, de conditie data[c] >= 128 is eerste false voor een reeks waarden, wordt dan true voor alle latere waarden. Dat is gemakkelijk te voorspellen. Met een ongesorteerde array betaalt u voor de vertakkingskosten.


3635
2018-06-27 13:54



De reden waarom de prestaties drastisch verbeteren wanneer de gegevens worden gesorteerd, is dat de vertakkingsvoorspellingsboete wordt verwijderd, zoals mooi wordt uitgelegd Mysticialhet antwoord.

Nu, als we naar de code kijken

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

we kunnen de betekenis van dit specifieke vinden if... else... branch is om iets toe te voegen wanneer aan een voorwaarde is voldaan. Dit type tak kan eenvoudig worden omgezet in een voorwaardelijke verplaatsing verklaring, die zou worden gecompileerd tot een voorwaardelijke verplaatsingsinstructie: cmovl, in een x86 systeem. De vertakking en dus de potentiële vertakkingsvoorspellingstraf is verwijderd.

In C, dus C++, de verklaring, die direct (zonder enige optimalisatie) zou worden gecompileerd in de voorwaardelijke verplaatsingsinstructie x86, is de ternaire operator ... ? ... : .... Dus we herschrijven bovenstaande verklaring in een gelijkwaardige:

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

Met behoud van de leesbaarheid kunnen we de versnellingsfactor controleren.

Op een Intel Core i7-2600K bij 3,4 GHz en Release Mode Visual Studio 2010, de benchmark is (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 robuust in meerdere tests. We krijgen een geweldige versnelling wanneer het resultaat van de tak onvoorspelbaar is, maar we lijden een beetje als het voorspelbaar is. Wanneer een voorwaardelijke beweging wordt gebruikt, is de prestatie feitelijk hetzelfde, ongeacht het gegevenspatroon.

Laten we nu eens nader kijken door de x86 assemblage 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 maakt gebruik van de ternaire operator ... ? ... : ...:

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

Op een x86-64-machine, GCC -S genereert de onderstaande assembly.

: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 instructie cmovge. Maar de echte winst is dat max2 geen taksprongen, jmp, wat een aanzienlijke prestatievermindering zou opleveren als het voorspelde resultaat niet juist is.

Dus waarom presteert een voorwaardelijke beweging beter?

In een typische x86 processor, de uitvoering van een instructie is verdeeld in verschillende fasen. Grofweg hebben we verschillende hardware om met verschillende stadia om te gaan. We hoeven dus niet te wachten op één instructie om te voltooien om een ​​nieuwe te beginnen. Dit heet pipelining.

In een branch-geval wordt de volgende instructie bepaald door de vorige, dus we kunnen pipelining niet uitvoeren. We moeten wachten of voorspellen.

In een geval van voorwaardelijke verplaatsing is de uitvoerinstructie voor voorwaardelijke verplaatsing verdeeld in verschillende fasen, maar de eerdere fasen zoals Fetch en Decode is niet afhankelijk van het resultaat van de vorige instructie; alleen latere stadia hebben het resultaat nodig. We wachten dus een fractie van de uitvoeringstijd van één instructie af. Dit is de reden waarom de voorwaardelijke verplaatsingsversie langzamer is dan de vertakking wanneer voorspelling gemakkelijk is.

Het boek Computersystemen: het perspectief van een programmeur, tweede editie legt dit in detail uit. U kunt paragraaf 3.6.6 raadplegen voor Voorwaardelijke instructies voor verplaatsing, hele hoofdstuk 4 voor Processorarchitectuur, en Sectie 5.11.2 voor een speciale behandeling voor Branch Voorspelling en Misvoorspelling Sancties.

Soms kunnen sommige moderne compilers onze code optimaliseren voor assemblage met betere prestaties, soms kunnen sommige compilers dit niet (de code in kwestie gebruikt de native compiler van Visual Studio). Het kennen van het prestatieverschil tussen filiaal en voorwaardelijke verplaatsing wanneer onvoorspelbaar, kan ons helpen code te schrijven met betere prestaties wanneer het scenario zo complex wordt dat de compiler ze niet automatisch kan optimaliseren.


2958
2018-06-28 02:14



Als u nieuwsgierig bent naar nog meer optimalisaties die met deze code kunnen worden gedaan, overweeg dan dit:

Beginnend met de originele loop:

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

Met lusuitwisseling 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 het if voorwaardelijk is constant gedurende de uitvoering van de i loop, dus je kunt de if uit:

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

Vervolgens zie je dat de binnenste lus kan worden samengevouwen tot één enkele expressie, ervan uitgaande dat het floating point-model dit toestaat (/ fp: fast is thrown, bijvoorbeeld)

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

Die is 100.000x sneller dan voorheen


2024
2017-07-03 02:25



Ongetwijfeld zouden sommigen van ons geïnteresseerd zijn in manieren om code te identificeren die problematisch is voor de vertakkingsvoorspeller van de CPU. Het Valgrind-gereedschap cachegrind heeft een branch-predictor-simulator, ingeschakeld door het gebruik van de --branch-sim=yes vlag. Over de voorbeelden in deze vraag lopen, met het aantal buitenlussen teruggebracht tot 10000 en gecompileerd met g++, geeft deze resultaten:

gesorteerd:

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

Boren naar de regel voor regel uitvoer geproduceerd door cg_annotate we zien voor de lus in kwestie:

gesorteerd:

          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 problematische lijn identificeren - in de ongesorteerde versie de if (data[c] >= 128) lijn veroorzaakt 164.050.007 verkeerd voorspelde voorwaardelijke vertakkingen (Bcm) onder het vertakkingsvoorspellingsmodel van cachegrind, terwijl het slechts 10.006 in de gesorteerde versie veroorzaakt.


Als alternatief kunt u op Linux het subsysteem Prestatiemeteritems gebruiken om dezelfde taak te voltooien, maar dan met native prestaties met CPU-tellers.

perf stat ./sumtest_sorted

gesorteerd:

 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 broncodeannotatie met dissassembly doen.

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

Zien de performance-tutorial voor meer details.


1687
2017-10-12 05:53



Ik heb net gelezen over deze vraag en de antwoorden, en ik voel dat een antwoord ontbreekt.

Een gebruikelijke manier om vertakkingsvoorspelling te elimineren waarvan ik heb vastgesteld dat deze bijzonder goed werkt in beheerde talen is een opzoeking van een tabel in plaats van het gebruik van een filiaal (hoewel ik dit in dit geval niet heb getest).

Deze aanpak werkt in het algemeen als:

  1. Het is een kleine tafel en wordt waarschijnlijk in de cache in de processor opgeslagen
  2. Je draait dingen in een vrij krappe lus en / of de processor kan de gegevens vooraf laden

Achtergrond en waarom

Pfew, dus wat betekent dat in vredesnaam?

Vanuit het perspectief van een processor is je geheugen traag. Om het verschil in snelheid te compenseren, bouwen ze een paar caches in je processor (L1 / L2-cache) in die dat compenseren. Stel je voor dat je je mooie berekeningen doet en erachter komt dat je een stukje geheugen nodig hebt. De processor krijgt zijn 'load'-bewerking en laadt het stukje geheugen in de cache - en gebruikt vervolgens de cache om de rest van de berekeningen uit te voeren. Omdat het geheugen relatief langzaam is, zal deze 'belasting' uw programma vertragen.

Net als branchevoorspelling werd dit geoptimaliseerd in de Pentium-processors: de processor voorspelt dat het een stuk gegevens moet laden en probeert dat in de cache te laden voordat de bewerking daadwerkelijk de cache raakt. Zoals we al hebben gezien, loopt vertakkingsvoorspelling soms vreselijk mis - in het ergste geval moet je teruggaan en eigenlijk wachten op een geheugenbelasting, wat een eeuwigheid zal duren (met andere woorden: falende vertakkingsvoorspelling is slecht, een geheugenbelasting na mislukken van een filiaal is gewoon vreselijk!).

Gelukkig voor ons, als het geheugentoegangspatroon voorspelbaar is, zal de processor het in zijn snelle cache laden en alles is goed.

Het eerste dat we moeten weten, is wat er is klein? Hoewel kleiner over het algemeen beter is, is een vuistregel dat u zich houdt aan opzoektabellen met een grootte van <= 4096 bytes. Als een bovengrens: als uw opzoektabel groter is dan 64K, is het waarschijnlijk de moeite waard om opnieuw te overwegen.

Een tafel bouwen

Dus we hebben ontdekt dat we een kleine tafel kunnen maken. Het volgende dat u moet doen is een opzoekfunctie op zijn plaats krijgen. Lookup-functies zijn meestal kleine functies die een aantal elementaire integer-bewerkingen gebruiken (en, of, xor, shift, toevoegen, verwijderen en misschien vermenigvuldigen). U wilt uw invoer door de opzoekfunctie laten vertalen naar een soort 'unieke sleutel' in uw tabel, die u dan eenvoudig het antwoord geeft van al het werk dat u wilde doen.

In dit geval:> = 128 betekent dat we de waarde kunnen behouden, <128 betekent dat we ons ervan ontdoen. De gemakkelijkste manier om dat te doen is door een 'EN' te gebruiken: als we het houden, we AND it with 7FFFFFFF; als we er vanaf willen komen, wij EN het met 0. Merk ook op dat 128 een macht van 2 is - dus we kunnen doorgaan en een tabel maken van 32768/128 gehele getallen en deze vullen met één nul en heel veel 7FFFFFFFF's.

Beheerde talen

Je vraagt ​​je misschien af ​​waarom dit goed werkt in beheerde talen. Tenslotte controleren beheerde talen de grenzen van de arrays met een filiaal om ervoor te zorgen dat u niet verknoeit ...

Nou, niet precies ... :-)

Er is behoorlijk wat werk gedaan aan het elimineren van deze tak voor beheerde talen. Bijvoorbeeld:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

In dit geval is het voor de compiler duidelijk dat de randvoorwaarde nooit wordt geraakt. Ten minste de Microsoft JIT-compiler (maar ik verwacht dat Java vergelijkbare dingen doet) zal dit opmerken en de controle helemaal verwijderen. WOW - dat betekent geen filiaal. Evenzo zal het andere voor de hand liggende gevallen behandelen.

Als u problemen ondervindt met zoekopdrachten in beheerde talen, is het belangrijk om een ​​taal toe te voegen & 0x[something]FFFnaar je opzoekfunctie om de grenscontrole voorspelbaar te maken - en kijk hoe het sneller gaat.

Het resultaat van deze zaak

// 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.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

1158
2018-04-24 06:26



Aangezien de gegevens worden verdeeld tussen 0 en 255 wanneer de array is gesorteerd, wordt de eerste helft van de iteraties om de eerste helft niet ingevoerd if-statement (de if verklaring wordt hieronder gedeeld).

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

De vraag is: wat doet de bovenstaande verklaring niet uitvoeren in bepaalde gevallen zoals in het geval van gesorteerde gegevens? Hier komt de "vertakkingsvoorspeller". Een vertakkingsvoorspeller is een digitaal circuit dat probeert te raden op welke manier een tak (bijvoorbeeld een if-then-else structuur) zal gaan voordat dit zeker bekend is. Het doel van de vertakkingsvoorspeller is om de stroom in de instructiepijplijn te verbeteren. Branchevoorspellers spelen een cruciale rol bij het bereiken van hoge effectieve prestaties!

Laten we wat bench marking doen om het beter te begrijpen

De uitvoering van een if-afspraak is afhankelijk van of de conditie ervan een voorspelbaar patroon heeft. Als de voorwaarde altijd waar of altijd onwaar is, zal de vertakkingsvoorspellingslogica in de processor het patroon oppikken. Aan de andere kant, als het patroon onvoorspelbaar is, de if-statement zal veel duurder zijn.

Laten we de prestaties van deze lus meten met verschillende omstandigheden:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Dit zijn de timings van de loop met verschillende true-false patronen:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

EEN "slecht"Waar-fout patroon kan een maken if-statement tot zes keer langzamer dan een "goed" patroon! Natuurlijk, welk patroon goed is en wat slecht is, hangt af van de precieze instructies gegenereerd door de compiler en van de specifieke processor.

Er is dus geen twijfel over de impact van branchevoorspelling op prestaties!


1033
2018-02-15 07:24