Assembly: Lære assembly sier du ? Hvorfor ?

[torbjørn marø]

Kanskje t.o.m. C++ template løsningen min skulle være tillatt.

Jeg syntes den var veldig interessant.

 

Det jeg forsøkte å påpeke her var at det ikke er sikkert alle har samme agenda. Min agenda er å se hva folk får til, hvordan de løser ting. Dermed:

1. Spiller det ingen rolle for MEG om algoritmene er de samme
   
2. er det ganske uinteressant å se implementasjoner av O(1)-løsninger
   

 

Din template-løsning er jo heller ikke O(1). Den er O(1) i runtime, men må jo fortsatt gjøre jobben i compiletime (om jeg forstod det riktig)

 

Ja, din vinkling på hva som er juks og ikke er riktig om man skal studere effektiviteten av en kompilator. Men du/dere behøver ikke legge disse restriksjonene på alle som deltar i debatten.

[jonny]

Jeg skrev selv en litt raskere algoritme, her er den:

 

#include <stdio.h>

int main() {
 const int I = 100000000;
 int sum = 0;
 int i;
 // first add all numbers dividable by 3...
 for(i=3; i<I; i+=3) sum += i;
 // ...then all numbers dividable by 5, but not 3...
 for(i=5; i<(I-5); i+=15) sum += 2*i+5;
 // ...at last the few remaining numbers...
 i -= 5;
 while(i<I) {
   if(i % 3 > 0) sum += i;
   i += 5;
 }
 printf("%d\n",sum);
}

 

Den kjører på ca 60 ms (eller 38 ms med -O3) på Intel Core 2 U7300 1.3GHz.

[David Brown]

Kanskje t.o.m. C++ template løsningen min skulle være tillatt.

Jeg syntes den var veldig interessant.

 

Det jeg forsøkte å påpeke her var at det ikke er sikkert alle har samme agenda. Min agenda er å se hva folk får til, hvordan de løser ting. Dermed:

1. Spiller det ingen rolle for MEG om algoritmene er de samme
   
2. er det ganske uinteressant å se implementasjoner av O(1)-løsninger
   

 

Din template-løsning er jo heller ikke O(1). Den er O(1) i runtime, men må jo fortsatt gjøre jobben i compiletime (om jeg forstod det riktig)

 

Ja, din vinkling på hva som er juks og ikke er riktig om man skal studere effektiviteten av en kompilator. Men du/dere behøver ikke legge disse restriksjonene på alle som deltar i debatten.

 

Ja, template løsningen var O(1) i runtime (eller "O(0)", siden det var ingen kalkulasjoner i det hele tatt), men O(n) i kompiletime. Selv om det ikke er en god løsning, siden det fungere kun med konstant verdier, syns jeg at det likevel er en interessant applikasjon av templates.

 

Jeg ønsket å la restriksjonene om algoritmen fordi jeg syns det gjorde debatten mer realistisk, og for å få fram forskjellene mellom assembly og C er det viktig at man bruker samme algoritme. Jeg syntes også det passet bedre med bloggen din, der alle eksemplarene bruker den algoritmen (hensikten er å vise fram forskjellige språk, ikke å kalkulere resultanten av funksjonen). Men jeg ser også poenget ditt - alle kan ha sine mening her.

 

Det du egentlig ønsker er da en algoritme med O(f(n)) der O(1) < O(f(n)) < O(n) - som f.eks. O(log n). Jeg kan ikke tenke på noe gode løsninger der, bortsett fra en loopup table av forhåndskalkulærte verdier for sum3or5(n).

 

 

Jeg skal prøve å tenke på en oppgave som gir både kompilatoren og assembly programmereren mer frihet til å vise fram triksene sine. Det burde være noe som drar nytte av SIMD, med nok kalkulasjoner samtidig for at pipelining, scheduling og bruk av flere register (på amd64) er viktig. Kanskje noe som jobber med mattrikser hadde passet.

[LostOblivion]

Interessant lesing dette, jeg ville hyret dere begge.

[LonelyMan]

Problemet til David Brown er at han ikke forstår sammenligningene. I ett av sine første innlegg sier han at han kjørte Torbjørn's rutine på 0.254, altså 254 millisekunder, på en 2.6 GHz prosessor. Når jeg tar nøyaktig den samme rutinen (helt og fullstendig nøyaktig) samme rutine på en 4 GHz prosessor (som er bedre enn den han bruker) og får 243 ms på en ren x86 plattform, så skjønner ikke David Brown forskjellen mellom de to ulike arkitekturene.

 

254 ms på 2.6 GHz

243 ms på en 4 GHz

 

Så blir det lettere å forstå relevansen mellom de to systemene og arkitekturene. Du kan benytte kalkulatoren din for å finne en faktor her.

 

Her har du forresten en variant som kjører på 0 ms, jeg har ikke implementert den i asm enda, men da snakker vi om mikrosekunder, ikke millisekunder.

 

static unsigned long sumlol2(unsigned long m) {

unsigned long left = m % 15; m -= left;

unsigned long sum = (m - 1) / 15 * ((m - 1) / 15 + 1) / 2 * 15 * 7 + 45 * (m / 15);

for (; left != 0; m++, left--) {

if(m % 3 == 0 || m % 5 == 0) {

sum += m;

}

}

return sum;

[LonelyMan]

En annen "moro" sak er at David Brown kjørte min egen asm rutine på 34 ms og jeg kjørte den på 31 ms, dog hans prosessor er nesten dobbelt så treg som min og vi kjørte samme asm kode

[LonelyMan]

Alt blir mye klarere når vi gjør slik:

 

254 / 243 = 1,0452674897119341563786008230453

 

34 / 31 = 1,0967741935483870967741935483871

 

 

Disse to snakker veldig klart for seg, det er en klar sammenheng og man kommer ikke bort fra det.

Endret 19. desember 2011 av LonelyMan

[LonelyMan]

Og her gjør jeg tingene enda klarere:

 

David kjørte min egen asm kode på (den uoptimaliserte varianten):

978 ms

 

og jeg kjørte den samme på

959

 

978 / 959 = 1,0198123044838373305526590198123

 

Her ser vi den samme faktoren igjen for tredje gang fra forrige eksempel.

 

Hans prosessor på 2.6 GHz (som er ca 45% treigere enn min) så ser vi at forskjellen mellom arkitekturene har en stor impact i alle tallene som er samlet her.

 

Det fins bare 2 konklusjoner her.

 

1: Det er ikke sammenlignbart

2: David snakker usant

 

Han får velge ett av disse.

Endret 19. desember 2011 av LonelyMan

[David Brown]

Problemet til David Brown er at han ikke forstår sammenligningene. I ett av sine første innlegg sier han at han kjørte Torbjørn's rutine på 0.254, altså 254 millisekunder, på en 2.6 GHz prosessor. Når jeg tar nøyaktig den samme rutinen (helt og fullstendig nøyaktig) samme rutine på en 4 GHz prosessor (som er bedre enn den han bruker) og får 243 ms på en ren x86 plattform, så skjønner ikke David Brown forskjellen mellom de to ulike arkitekturene.

 

254 ms på 2.6 GHz

243 ms på en 4 GHz

 

Så blir det lettere å forstå relevansen mellom de to systemene og arkitekturene. Du kan benytte kalkulatoren din for å finne en faktor her.

 

Her har du forresten en variant som kjører på 0 ms, jeg har ikke implementert den i asm enda, men da snakker vi om mikrosekunder, ikke millisekunder.

 

static unsigned long sumlol2(unsigned long m) {

unsigned long left = m % 15; m -= left;

unsigned long sum = (m - 1) / 15 * ((m - 1) / 15 + 1) / 2 * 15 * 7 + 45 * (m / 15);

for (; left != 0; m++, left--) {

if(m % 3 == 0 || m % 5 == 0) {

sum += m;

}

}

return sum;

 

 

Jeg forstår sammenligningene fint. Jeg forstår ikke hvorfor du får så trege resultatene - kanskje maskinen din ikke er så raskt likevel. Det er tross alt flere ting som spiller inn enn bare klokkehastighet. Du har også snakket om "full optimisering", uten nærmere spesifikasjon - bl.a. gir "-O2" optimisering med gcc raskere kode her enn "-O3", fordi kortere kode kjører fortere i dette tilfellet.

 

For å gi deg de komplete tallene (igjen), har jeg tatt kompilerte originalkoden med gcc 4.5, og kommandolinje:

 

gcc euler.c -o euler -std=gnu99 -O2

 

På i7-920 PC, 64-bit Linux, for jeg 0.260s. Det er litt tregere enn tidligere, fordi maskinen holder på med noe annet og dermed kjører ikke turboklokking. Jeg kjørte tre ganger - dette er det raskeste resultatet.

 

På hjemme PC, i7-975K med litt overklokking (ca. 3.6 GHz om jeg husker rett), er tilsvarende resulter 0.185s på 64-bit og 0.180 på 32-bit på en 32-bit virtuelle maskin (som kjører i 32-bit protected mode).

 

Så det er klart at 32-bit koden faktisk kjørte litt raskere på samme hardware. Forskjellen var ikke stor, og det er ihvertfall ikke sånn som du tror at 64-bit versjon er en tredel raskere enn 32-bit versjon.

 

Jeg har allerede forklarte dette - se post #141. Der kan du også se på assembly koden.

 

 

Den nye algoritmen din er ganske fantasifullt, men er O(1) og dermed diskvalifiserte etter Torbjørn sin regler, og tregere enn andre O(1) algoritmer jeg har allerede postet. Så ikke bruk tid til å prøve å implementere den i assembly.

[LonelyMan]

Problemet til David Brown er at han ikke forstår sammenligningene. I ett av sine første innlegg sier han at han kjørte Torbjørn's rutine på 0.254, altså 254 millisekunder, på en 2.6 GHz prosessor. Når jeg tar nøyaktig den samme rutinen (helt og fullstendig nøyaktig) samme rutine på en 4 GHz prosessor (som er bedre enn den han bruker) og får 243 ms på en ren x86 plattform, så skjønner ikke David Brown forskjellen mellom de to ulike arkitekturene.

 

254 ms på 2.6 GHz

243 ms på en 4 GHz

 

Så blir det lettere å forstå relevansen mellom de to systemene og arkitekturene. Du kan benytte kalkulatoren din for å finne en faktor her.

 

Her har du forresten en variant som kjører på 0 ms, jeg har ikke implementert den i asm enda, men da snakker vi om mikrosekunder, ikke millisekunder.

 

static unsigned long sumlol2(unsigned long m) {

unsigned long left = m % 15; m -= left;

unsigned long sum = (m - 1) / 15 * ((m - 1) / 15 + 1) / 2 * 15 * 7 + 45 * (m / 15);

for (; left != 0; m++, left--) {

if(m % 3 == 0 || m % 5 == 0) {

sum += m;

}

}

return sum;

 

 

Jeg forstår sammenligningene fint. Jeg forstår ikke hvorfor du får så trege resultatene - kanskje maskinen din ikke er så raskt likevel. Det er tross alt flere ting som spiller inn enn bare klokkehastighet. Du har også snakket om "full optimisering", uten nærmere spesifikasjon - bl.a. gir "-O2" optimisering med gcc raskere kode her enn "-O3", fordi kortere kode kjører fortere i dette tilfellet.

 

For å gi deg de komplete tallene (igjen), har jeg tatt kompilerte originalkoden med gcc 4.5, og kommandolinje:

 

gcc euler.c -o euler -std=gnu99 -O2

 

På i7-920 PC, 64-bit Linux, for jeg 0.260s. Det er litt tregere enn tidligere, fordi maskinen holder på med noe annet og dermed kjører ikke turboklokking. Jeg kjørte tre ganger - dette er det raskeste resultatet.

 

På hjemme PC, i7-975K med litt overklokking (ca. 3.6 GHz om jeg husker rett), er tilsvarende resulter 0.185s på 64-bit og 0.180 på 32-bit på en 32-bit virtuelle maskin (som kjører i 32-bit protected mode).

 

Så det er klart at 32-bit koden faktisk kjørte litt raskere på samme hardware. Forskjellen var ikke stor, og det er ihvertfall ikke sånn som du tror at 64-bit versjon er en tredel raskere enn 32-bit versjon.

 

Jeg har allerede forklarte dette - se post #141. Der kan du også se på assembly koden.

 

 

Den nye algoritmen din er ganske fantasifullt, men er O(1) og dermed diskvalifiserte etter Torbjørn sin regler, og tregere enn andre O(1) algoritmer jeg har allerede postet. Så ikke bruk tid til å prøve å implementere den i assembly.

Det er ikke bare klokkehastighet som spiller inn, men begge våre prosessorer har mer eller mindre samme features, og uansett om de ikke hadde samme features så vil ikke det ha spilt noen rolle på den asm koden jeg laget, den tar ikke i bruk noen av de featurene, og uansett om det hadde gjort det så ville ikke det blitt så stor forskjell, klokkehastigheten er for stor forskjell her til at den ikke skal bety noe.

Ikke en tredel, 64% impact.

 

Apropos (kanskje min maskin ikke er så rask likevel), jeg har testet det på 4 forskjellige prosessorer. Så dette handler ikke om at "min maskin ikke er så rask likevel"

Endret 19. desember 2011 av LonelyMan

[LonelyMan]

Du har rett i at 64 bits programmer ikke er raske, men det er en viktig forskjell i at selv om ikke 64 bits programmer er så raske, så er det en utrolig forskjell når du tar i bruk 8 ekstra 64 bits registre. Det har en utrolig forskjell, selv om 64 bits programmer i helhet ikke er så raske. Det er her du ikke ser ut til å forstå. At du tar ibruk disse "trege registrene" som du kaller det, så er de likevel uhorvelig mye raskere enn om du ikke hadde de i det hele tatt. HER er forskjellen

 

Du ser ut til å ikke skjønne at

 

1: Å ha 8 ekstra registre vil alltid være raskere enn

2: Å ikke ha de i det hele tatt.

 

Håper du skjønner bedre nå.

[David Brown]

Og her gjør jeg tingene enda klarere:

 

David kjørte min egen asm kode på (den uoptimaliserte varianten):

978 ms

 

og jeg kjørte den samme på

959

 

978 / 959 = 1,0198123044838373305526590198123

 

Her ser vi den samme faktoren igjen for tredje gang fra forrige eksempel.

 

Hans prosessor på 2.6 GHz (som er ca 45% treigere enn min) så ser vi at forskjellen mellom arkitekturene har en stor impact i alle tallene som er samlet her.

 

Det fins bare 2 konklusjoner her.

 

1: Det er ikke sammenlignbart

2: David snakker usant

 

Han får velge ett av disse.

 

Jeg lurer på om du forstår hva du holder på med disse sammenligningene. Når jeg har prøvd meg på nøyaktige sammenligninger, som 32-bit mot 64-bit kompilering fordi du ikke forstod at koden var likt, gjorde jeg det på samme PC - /min/ PC, og ikke /din/. Jeg har lagt merke til omtrent samme hastigheter på noen av dine og mine kjøringer, og at vi derfor har systemer i omtrent samme klasse, men det holder bare når det er snakk om ca. 1 sekund mot ca. en kvart sekund mot ca. 30 millisekunder.

 

Du må huske at i tillegg til forskjellige cpu'er, har vi også forskjellige OS'er (jeg kjøre 64-bit Linux, og 32-bit Linux på virtuelle maskinen, mens du kjøre Windows av en eller annen type), og gjerne også andre programmer til tidsmåling (jeg bruker Linux "time", og ser på "real time" - men det er godt mulig at du ser på "user time").

 

Så du får sammenligne tider på /din/ PC med andre tider på /din/ PC, ikke på min. Skal du finne ut om forskjellene mellom 32-bit og 64-bit, må du gjøre begge tester på /din/ PC. Om du ikke er i stand til det, for du tror på mine resultatene.

 

Og om du påstår en gang til at jeg lyver, er det siste innlegg fra deg jeg kommer til å lese. Jeg prøver her med undersøking og sammenligning av assembly og kompilatorer, både for egen læring, for andre i denne tråden, og ikke minst for å prøve å vise deg hva som er viktig i valg av lavnivå programmeringsspråk. Tror du jeg hadde brukt så mye tid bare for å lyve? Jeg forstår at du har en sak du skal prøve å framføre, og du ser det som personlig viktig å bevise at assembly er alltid best, men du trenger ikke synke til et så lavt nivå som å tro at alle som motsier deg lyver. Du for heller finne en alternativt funksjon der du tror assembly implementasjon blir betydelige raskere enn C versjonen, som jeg har foreslått tidligere - jeg kan godt tenke meg å ta utfordringen. Men det blir under foresetningen at du er voksen nok til å stole på mine tall.

[LonelyMan]

Nei nei, sier ikke at du lyver, men det var ett valg du måtte ta, ett av to. Mine målinger er korrekte, jeg bruker en kernel driver til å måle hastighet i kombinasjon med rdtsc og cpuid, synkronisert med system interrupts så får jeg meget nøyaktig måling. Forskjellige operativsystemer spiller ingen rolle i måling av rask kode, da overhead of wrappere på to programmer på ulike systemer ikke går med i målingen, når man når koden en skal måle er det ingen annen forskjell enn system interrupts.

Endret 19. desember 2011 av LonelyMan

[David Brown]

Du har rett i at 64 bits programmer ikke er raske, men det er en viktig forskjell i at selv om ikke 64 bits programmer er så raske, så er det en utrolig forskjell når du tar i bruk 8 ekstra 64 bits registre. Det har en utrolig forskjell, selv om 64 bits programmer i helhet ikke er så raske. Det er her du ikke ser ut til å forstå. At du tar ibruk disse "trege registrene" som du kaller det, så er de likevel uhorvelig mye raskere enn om du ikke hadde de i det hele tatt. HER er forskjellen

 

Du ser ut til å ikke skjønne at

 

1: Å ha 8 ekstra registre vil alltid være raskere enn

2: Å ikke ha de i det hele tatt.

 

Håper du skjønner bedre nå.

 

Se på koden i post 141. Fortell meg da akkurat hvor mange ekstra register blir brukt, og hvilke forskjell det gjorde.

[LonelyMan]

Du har rett i at 64 bits programmer ikke er raske, men det er en viktig forskjell i at selv om ikke 64 bits programmer er så raske, så er det en utrolig forskjell når du tar i bruk 8 ekstra 64 bits registre. Det har en utrolig forskjell, selv om 64 bits programmer i helhet ikke er så raske. Det er her du ikke ser ut til å forstå. At du tar ibruk disse "trege registrene" som du kaller det, så er de likevel uhorvelig mye raskere enn om du ikke hadde de i det hele tatt. HER er forskjellen

 

Du ser ut til å ikke skjønne at

 

1: Å ha 8 ekstra registre vil alltid være raskere enn

2: Å ikke ha de i det hele tatt.

 

Håper du skjønner bedre nå.

 

Se på koden i post 141. Fortell meg da akkurat hvor mange ekstra register blir brukt, og hvilke forskjell det gjorde.

 

Der er noen ja. Og om det hypotetisk sett bare var 1 ekstra register, så ville det utgjort en enorm forskjell om jeg måtte lese den samme dataen fra minnet. Enorm forskjell. Men der er mange flere i bruk, jeg ser noen 64 bits registre der.

[LonelyMan]

Forresten jeg synes det er fullstendig og helt fjolsete å sammenligne:

 

1: To vidt forskjellige operativsystemer

2: å sammenligne ett 32 bits vs 64 bits

3: Sammenligne to ulike prosessorer

4: Sammenligne to ulike moduser i prosessorene

 

Og SÅ sette to tall opp mot hverandre når alt som KAN være forskjellige ER forskjellig. Fullstendig og komplett fjolsete opplegg, alt sammen.

[LonelyMan]

Vi kan enes om at koden kjørte 65% raskere på din maskin vs mine test maskiner (4 stk).

 

Og en eller annen plass må vi legge forklaringen for dette. Når 4 maskiner kjører samme kode vs din maskin og alle 4 resultatene gir ut en faktor forskjell, så må vi legge forklaringen ett sted mtp. at vi kjørte samme kode.

Endret 19. desember 2011 av LonelyMan

[David Brown]

Forresten jeg synes det er fullstendig og helt fjolsete å sammenligne:

 

1: To vidt forskjellige operativsystemer

2: å sammenligne ett 32 bits vs 64 bits

3: Sammenligne to ulike prosessorer

4: Sammenligne to ulike moduser i prosessorene

 

Og SÅ sette to tall opp mot hverandre når alt som KAN være forskjellige ER forskjellig. Fullstendig og komplett fjolsete opplegg, alt sammen.

 

Konklusjonen må da være at dersom det ikke er mulig å sammenligne assembly og C på en fornuftig måte, det fins ingen grunn til å påstå at assembly er raskere enn C. Og er ikke assembly raskere, er det ingen vits i å bruke den, siden alle er klar over de mange andre gode grunn til å foretrekke C over assembly.

 

Poenget her er at assembly er uegnet til generelle programmering på en så stor prosessor som x86/amd64.

 

Hvis du fortsatt ønsker å slåss for assembly, kan vi godt prøve å finne på en funksjon der du tror det virkelig kan skinne. Da skal vi være enige om 64-bit systemer, siden vi snakker om moderne systemer. Og vi kan ta i bruk alle registerer og SIMD instruksjoner som fins på en i7 cpu. Hvis det ikke er soleklare forskjeller i hastighet som langt overskygge forskjellene mellom systemene, så er det ikke vits i assembly koden der likevel.

[David Brown]

Vi kan enes om at koden kjørte 65% raskere på din maskin vs mine test maskiner (4 stk).

 

Og en eller annen plass må vi legge forklaringen for dette. Når 4 maskiner kjører samme kode vs din maskin og alle 4 resultatene gir ut en faktor forskjell, så må vi legge forklaringen ett sted mtp. at vi kjørte samme kode.

 

254ms på 2.6 GHz mot 243ms på 4 GHz er 32% raskere, ikke 65% raskere. Uansett er det et forskjell, og jeg er enige at det hadde vært interessant å finne ut hvorfor. Prøvde du med gcc, og i så fall hvilke versjon? Og prøvde du med samme kommandolinje:

 

gcc euler.c -o euler -std=gnu99 -O2 -Wa,-ahdls=euler.c.lst

 

Du kan da sammenligne listfilen med den jeg postet i #141.

[LonelyMan]

Jeg ser 4 ekstra registre i koden din som jeg ikke har tilgang til, noen av de opererer på 32 bit operander og noen på 64 bit. 4 ekstra registre er helt katastrofalt i en sammenligning. 4 ekstra registre betyr at du har 225% av mine general purpose registre tilgjengelig.

 

Til det du skrev over, lag gjerne en funksjon som ikke er for tidkrevende, noe enkelt så kan du skrive den ferdig så kan jeg forsøke å optimalisere den.

 

Men jeg liker ikke at du genererer assembler listing, så legger inn asm forandringer i denne listingen og så kommer på forumet og sier at dette er "compiler work", den oppførselen er kjedelig og virker dårlig.

 

Spesielt kjedelig er det når du koder 32 bits med ekstra registre. Dette tar toppen av kaka.

Endret 19. desember 2011 av LonelyMan