Nederlands
Menu

Geheugenhiërarchie en prestaties

Waarom is het doorlopen van bovenstaande gekoppelde lijst doorgaans veel trager dan het sequentieel lezen van een array met evenveel elementen?

struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
    sum += p->val;
  1. AOmdat het adres van het volgende element pas bekend is nadat het huidige is gelezen, zodat misses één voor één achter elkaar optreden
  2. BOmdat elementen van een gekoppelde lijst per definitie niet in de cache kunnen staan
  3. COmdat de sprongvoorspelling van de CPU bij bewerkingen met pointers altijd faalt
Antwoord en toelichting tonen

Antwoord: A. Omdat het adres van het volgende element pas bekend is nadat het huidige is gelezen, zodat misses één voor één achter elkaar optreden

Bij een gekoppelde lijst is het adres van het volgende element pas bekend nadat p->next is gelezen. Als de elementen over het geheugen zijn verspreid, treedt bij elke toegang een miss op, en omdat het volgende adres niet bekend is, kunnen meerdere misses niet overlappen; de volledige wachttijd van het hoofdgeheugen telt dus voor elk element op. Bij een array is het volgende adres uit te rekenen, zodat prefetching en overlappende misses werken. Ook elementen van een gekoppelde lijst komen in de cache, en de lussprong is goed te voorspellen en faalt niet altijd.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Geheugenhiërarchie en prestaties

  1. Bij een miss wordt een regel van 64 byte gelezen en de wachttijd van het hoofdgeheugen is 100 ns. Als slechts één miss tegelijk kan worden afgehandeld, blijft de leesbandbreedte beperkt tot ongeveer 0,64 GB/s. Hoeveel bedraagt de bandbreedte ongeveer wanneer 10 misses tegelijk kunnen worden afgehandeld? (Andere beperkingen worden buiten beschouwing gelaten.)
  2. Wat is het belangrijkste voordeel van stores die de cache omzeilen (non-temporal stores) bij het wegschrijven van grote data die eenmaal worden geschreven en daarna een tijd niet worden teruggelezen?
  3. Wat is de missratio wanneer de hitratio van de cache 95% is?
  4. Welke techniek stuurt, bij het inlezen van een gemiste regel uit het hoofdgeheugen, eerst het woord dat de CPU nodig heeft en pas daarna de rest?
  5. Waarom wordt het samenvoegen van de twee bovenstaande lussen tot één lus (loop fusion) bij grote N vaak sneller?

Vergelijkingen bij dit onderwerp