Ik ging door lussen en ontdekte een significant verschil in toegang tot lussen.
Ik begrijp niet wat het is dat in beide gevallen zo’n verschil veroorzaakt?
Eerste voorbeeld:
Uitvoeringstijd; 8 seconden
for (int kk = 0; kk < 1000; kk++)
{
sum = 0;
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
{
sum += matrix[i][j];
}
}
Tweede voorbeeld:
Uitvoeringstijd: 23 seconden
for (int kk = 0; kk < 1000; kk++)
{
sum = 0;
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
{
sum += matrix[j][i];
}
}
Wat veroorzaakt zoveel verschil in uitvoeringstijd door alleen maar te ruilen
matrix[i][j]
naar
matrix[j][i]
?
Antwoord 1, autoriteit 100%
Het is een kwestie van geheugencache.
matrix[i][j]heeft betere cachehits dan matrix[j][i], aangezien matrix[i][j]heeft meer continu geheugentoegangskansen.
Als we bijvoorbeeld matrix[i][0]openen, kan de cache een continu geheugensegment laden dat matrix[i][0]bevat, dus , toegang tot matrix[i][1], matrix[i][2], …, profiteert van cachingsnelheid, aangezien matrix[i][1], matrix[i][2], … bevinden zich in de buurt van matrix[i][0].
Als we echter matrix[j][0]openen, is het verre van matrix[j - 1][0]en wordt het mogelijk niet in de cache opgeslagen, en kan niet profiteren van de cachesnelheid. In het bijzonder wordt een matrix normaal gesproken opgeslagen als een continu groot segment van het geheugen, en de cacher kan het gedrag van geheugentoegang voorspellen en het geheugen altijd in de cache plaatsen.
Daarom is matrix[i][j]sneller. Dit is typisch voor het optimaliseren van prestaties op basis van CPU-cache.
Antwoord 2, autoriteit 49%
Het prestatieverschil wordt veroorzaakt door de cachestrategie van de computer.
De tweedimensionale array matrix[i][j]wordt weergegeven als een lange lijst met waarden in het geheugen.
Bijvoorbeeld de array A[3][4]ziet er als volgt uit:
1 1 1 1 2 2 2 2 3 3 3 3
In dit voorbeeld is elke invoer van A[0][x] ingesteld op 1, elke invoer van A[1][x] is ingesteld op 2, …
Als uw eerste lus wordt toegepast op deze matrix, is de volgorde van toegang als volgt:
1 2 3 4 5 6 7 8 9 10 11 12
Terwijl de tweede lus de toegangsvolgorde er als volgt uitziet:
1 4 7 10 2 5 8 11 3 6 9 12
Als het programma een element van de array benadert, laadt het ook de volgende elementen.
Bijvoorbeeld als je A[0][1]opent, worden A[0][2]en A[0][3]ook geladen .
Daardoor hoeft de eerste lus minder laadbewerkingen uit te voeren, omdat sommige elementen al in de cache staan wanneer dat nodig is.
De tweede lus laadt items in de cache die op dat moment niet nodig zijn, wat resulteert in meer laadbewerkingen.
Antwoord 3, autoriteit 31%
Andere mensen hebben goed werk geleverd door uit te leggen waarom de ene vorm van uw code efficiënter gebruik maakt van de geheugencache dan de andere. Ik wil graag wat achtergrondinformatie toevoegen waarvan u zich misschien niet bewust bent: u realiseert zich waarschijnlijk niet hoe duurtoegang tot het hoofdgeheugen tegenwoordig is.
De cijfers die zijn gepost in deze vraagzien eruit om in de juiste marge voor mij te zijn, en ik ga ze hier reproduceren omdat ze zo belangrijk zijn:
Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns
Let op de verandering in eenheden voor de laatste twee items. Afhankelijk van welk model je precies hebt, werkt deze processor op 2,9-3,2 GHz; om de wiskunde eenvoudiger te maken, laten we het gewoon 3 GHz noemen. Dus één cyclus is 0,33333 nanoseconden. Dus DRAM-toegangen zijn ook 100-300 cycli.
Het punt is dat de CPU honderdeninstructies had kunnen uitvoeren in de tijd die nodig is om ééncacheregel uit het hoofdgeheugen te lezen. Dit wordt de geheugenmuurgenoemd. Daarom is efficiënt gebruik van de geheugencache belangrijker dan elke andere factorin de algehele prestaties op moderne CPU’s.
Antwoord 4, autoriteit 16%
Het antwoord hangt een beetje af van hoe de matrixprecies is gedefinieerd. In een volledig dynamisch toegewezen array zou je het volgende hebben:
T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
t[i] = new T[m];
}
Dus elke matrix[j]vereist een nieuwe geheugenzoekopdracht voor de aanwijzer. Als je de j-lus buiten doet, kan de binnenste lus de aanwijzer voor matrix[j]elk opnieuw gebruiken voor de hele binnenste lus.
Als de matrix een eenvoudige 2D-array is:
T matrix[n][m];
dan is de matrix[j]gewoon een vermenigvuldiging met 1024 * sizeof(T)– wat kan worden gedaan door 1024 * sizeof(T)de lusindex in de geoptimaliseerde code, dus zou hoe dan ook relatief snel moeten zijn.
Bovendien hebben we cachelocatiefactoren. Caches hebben “lijnen” met gegevens die doorgaans 32 tot 128 bytes per regel zijn. Dus als je code adres Xleest, wordt de cache geladen met waarden van 32 tot 128 bytes rond X. Dus als het VOLGENDE dat je nodig hebt alleen sizeof(T)vooruit is vanaf de huidige locatie, is het hoogstwaarschijnlijk al in de cache [en moderne processors detecteren ook dat je in een lus rondgaat en elk geheugen leest locatie en laadt de gegevens vooraf].
In het geval van jbinnenlus, lees je een nieuwe locatie van sizeof(T)*1024afstand voor elke lus [of mogelijk een grotere afstand als het dynamisch is toegewezen]. Dit betekent dat de gegevens die worden geladen niet nuttig zijn voor de volgende lus, omdat deze zich niet in de volgende 32 tot 128 bytes bevindt.
En tot slot is het heel goed mogelijk dat de eerste lus meer geoptimaliseerd is, dankzij SSE-instructies of iets dergelijks, waardoor de berekening nog sneller kan worden uitgevoerd. Maar dit is waarschijnlijk marginaal voor zo’n grote matrix, omdat de prestaties bij deze grootte sterk geheugengebonden zijn.
Antwoord 5, autoriteit 9%
Geheugenhardware is niet geoptimaliseerd om individuele adressen te leveren: in plaats daarvan werkt het meestal op grotere stukken continu geheugen, cachelijnengenaamd. Elke keer dat u één item van uw matrix leest, wordt de hele cacheregel waarin deze zich bevindt ook in de cache geladen.
De snellere lusvolgorde is ingesteld om het geheugen in volgorde te lezen; elke keer dat u een cacheregel laadt, gebruikt u alle vermeldingen in die cacheregel. Elke keer dat u door de buitenste lus gaat, leest u elke matrixinvoer slechts één keer.
De langzamere lusvolgorde gebruikt echter slechts één invoer van elke cacheregel voordat verder wordt gegaan. Elke cacheregel moet dus meerdere keren worden geladen, één keer voor elke matrixinvoer in de regel. bijv. als een double8 byes is en een cacheregel 64 bytes lang is, dan moet elke passage door de buitenste lus elke matrixinvoer achtkeer lezen in plaats van één keer.
Dat gezegd hebbende, als je optimalisaties had ingeschakeld, zou je waarschijnlijk geen verschil zien: optimizers begrijpen dit fenomeen, en goede zijn in staat te herkennen dat ze kunnen wisselen welke lus de binnenste lus is en welke de buitenste lus. voor dit specifieke codefragment.
(een goede optimizer zou ook maar één keer door de buitenste lus zijn gegaan, omdat het herkent dat de eerste 999 keer door niet relevant zijn voor de uiteindelijke waarde van sum)
Antwoord 6, autoriteit 7%
De matrix wordt als vector in het geheugen opgeslagen. Als u het op de eerste manier opent, krijgt u achtereenvolgens toegang tot het geheugen. Om het op de tweede manier te openen, moet je rond geheugenlocaties springen. Zie http://en.wikipedia.org/wiki/Row-major_order
Antwoord 7, autoriteit 5%
Als u j – i opent, wordt de j-dimensie in de cache opgeslagen, zodat de machinecode deze niet elke keer hoeft te wijzigen. De tweede dimensie wordt niet in de cache opgeslagen, dus u verwijdert de cache elke keer, wat het verschil veroorzaakt.
Antwoord 8, autoriteit 3%
Op basis van het concept van referentielocatie is het zeer waarschijnlijk dat een stukje code toegang krijgt tot aangrenzende geheugenlocaties. Er worden dus meer waarden in de cache geladen dan waar om wordt gevraagd. Dit betekent meer cache-hits. Je eerste voorbeeld voldoet hier goed aan, terwijl je code in het tweede voorbeeld dat niet is.