Microsoft har været så flinke at stille en række præmier til rådighed til lidt julespas, så derfor afholder jeg i løbet af december et par små kodekonkurrencer her på siden. Vi lægger ud med en lille konkurrence omkring performance.
Betragt nedenstående metoder, SlowSum() og FastSum().
private const int total = 1000;
private static readonly int[,] numbers = new int[total, total];
static private int SlowSum() {
var sum = 0;
for (var first = 0; first < total; first++) {
for (var second = 0; second < total; second++) {
sum += numbers[second, first];
}
}
return sum;
}
static private int FastSum() {
var sum = 0;
for (var first = 0; first < total; first++) {
for (var second = 0; second < total; second++) {
sum += numbers[first, second];
}
}
return sum;
}
De gør begge nøjagtig det samme og burde således i teorien afvikle lige hurtig, men i praksis vil SlowSum() typisk være markant langsommere end FastSum(). Hvis total f.eks. sættes til 1000 som i eksemplet, vil en simpel måling på min maskine vise, at SlowSum() er ca. dobbelt så lang tid om opgaven som FastSum().
Spørgsmålet er derfor: Hvorfor er dette tilfældet?
Send dit svar i en mail til brian@kodehoved.dk. Deadline er på fredag kl. 20.
Jeg trækker lod blandt de rigtige besvarelser om den fedeste af mine præmier. Jeg trækker også lod blandt alle besvarelser (det vil sige, noget der ligner et svar, uanset om det er korrekt eller ej) om en eller anden trøstepræmie.
Svaret, vinderne og de indkomne forslag offentliggøres i løbet af weekenden.
Spørgsmål til konkurrencen: smid en kommentar.
[...] Rasmussen om at afholde et par af jule konkurrencerne på hans egen blog. Indtil videre kan du læse opgaven og begynde at forbedre et svar til på Fredag d. 5 december. Vinderen får et par [...]
Mit gæt er at et multi dimensionelt array lægges ud i hukommelsen som følger:
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
z1 z2 z3 z4 z5
Den hurtige iteration læser x1,x2,x3,x4,x5,y1,y2,y3 osv.
Den langsomme læser x1,y1,z1,x2, y2, z2 osv.
Den hurtige iteration læser altså mere sekventielt, og hopper ikke så meget rundt.
Den langsomme hopper rundt i humokkelsen.
Jeg vil gætte på at eks. caching osv. bedre kan optimerer den hurtige.
Forresten kan følgende artikel (om C++) muligvis kaste noget lys over sagen:
http://www.fredosaurus.com/notes-cpp/arrayptr/23two-dim-array-memory-layout.html
Og nå ja, det hedder ikke humokkelsen, men hukommelse.
-> Klaus Hebsgaard
Af ren nysgerrighed: Har du selv et bud på hvorfor du kan løse en relativt kompliceret problemstilling, men overhovedet ikke forstår et simpelt budskab som “Send dit svar i en mail til brian@kodehoved.dk” ?
Så var det så at jeg vågnede lørdag morgen og opdagede at man skulle sende svaret pr. email.
Hmmm
Det er i orden Klaus