Assembly: Lære assembly sier du ? Hvorfor ?

[David Brown]

David Brown, som sagt du kjører et 64 bits der med 16 registre. Mitt program er ett 32 bits program med 8 registre, altså halvparten av hva du bruker der. Du kan jo på ingen måte sammenligne det der, men det mest tragiske var at jeg likevel hadde samme hastighet enn dog du har dobbelt så mange registre tilgjengelig, det er helt latterlig. Hva jeg kunne gjort med disse ekstra registrene

 

Er det kult at du ikke klare å ta i bruk mer enn halvparten av prosessoren din?

 

Men bare for å glede deg, har jeg gjort kompilering med både 64-bit og 32-bit. Dette er på en annen maskin, så timingene er litt raskere enn før - 64-bit tok 0.186 s, mens 32-bit var faktisk litt raskere på 0.179 s. Og som jeg sa før, er assembly koden nesten identisk. (Dette var med original programmet fra bloggsiden.)

 

Vi kan se noe annet interessant dersom vi bruker 64-bit integer til summen i programmet - noe vi burde egentlig gjøre når vi finner sum3or5(100000000) for å få det rette svaret uten overflow. Med 64-bit kompilator tar det nå 0.169 sekund - raskere enn for å finne feil svar. Men med 32-bit kompilator tar det 0.237 sekunder.

 

 

Min konklusjon er:

 

1: Din forrige kode sa du var 32 bits kode (men i det nye eksemplet ditt her så er det 64 bits "kode") jeg føler at du ikke snakker sant selv om du kaller det bakoverkompatibelt så er det dobbelt opp med registre og det kan nesten kvalifiseres som 64 bits, derfor sier jeg det for å unngå forvirring.

 

 

Jeg tar som gitt at du tror jeg snakker sant, med forbehold at jeg kan ha tatt feil - jeg rettet feilen da jeg så den. Husk at det er svært sjelden jeg har sett på x86 assembly - jeg la ikke merke til bruk av registerene. Jeg liker ikke implikasjonen din at jeg bevist ikke snakket sant.

 

Og det jeg sa om at programstrukturen er likt på begge arkitekturene er selvfølgelig sant.

 

 

2: Du tar min algoritme og implementerer den.

 

3: Du implementerer den på ett hardware sett som har dobbelt så mange registre og er ikke engang et 32 bits program.

 

Det er helt klart og utvilsomt ett slag som er tapt fra din side, utvilsomt.

 

 

Jeg regner med etter de postene jeg har skrevet i det siste, at du er ikke lengre like bevist.

 

Men får å gjøre det enkelt for deg, her er C programmet med den algoritmen vi skulle implementere ifølge utfordringen og bloggen. Jeg har gjort alle kompilering med gcc 4.5, som er lett tilgjengelig på alle systemer dersom du vil prøve det selv. Kommandolinjen er:

 

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

 

Koden (den som gir feil verdi p.g.a. overflow):

 

#include <stdint.h>

#include <stdbool.h>

#include <stdio.h>

 

 

static int sum3or5(int m) {

int sum = 0;

for (int i = 0; i < m; i++) {

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

sum += i; }

}

return sum;

}

 

int main(void) {

printf("%i\n", sum3or5(100000000));

return 0;

}

 

 

Genererte assembly på 32-bit:

 

9 main:

10 0000 55 pushl %ebp

11 0001 31C9 xorl %ecx, %ecx

12 0003 89E5 movl %esp, %ebp

13 0005 83E4F0 andl $-16, %esp

14 0008 57 pushl %edi

15 0009 BF565555 movl $1431655766, %edi

15 55

16 000e 56 pushl %esi

17 000f 31F6 xorl %esi, %esi

18 0011 53 pushl %ebx

19 0012 83EC14 subl $20, %esp

20 .p2align 4,,7

21 0015 8D7600 .p2align 3

22 .L4:

23 0018 89C8 movl %ecx, %eax

24 001a 89CB movl %ecx, %ebx

25 001c F7EF imull %edi

26 001e C1FB1F sarl $31, %ebx

27 0021 29DA subl %ebx, %edx

28 0023 8D0452 leal (%edx,%edx,2), %eax

29 0026 39C1 cmpl %eax, %ecx

30 0028 7412 je .L2

31 002a B8676666 movl $1717986919, %eax

31 66

32 002f F7E9 imull %ecx

33 0031 D1FA sarl %edx

34 0033 29DA subl %ebx, %edx

35 0035 8D0492 leal (%edx,%edx,4), %eax

36 0038 39C1 cmpl %eax, %ecx

37 003a 7502 jne .L3

38 .L2:

39 003c 01CE addl %ecx, %esi

40 .L3:

41 003e 83C101 addl $1, %ecx

42 0041 81F900E1 cmpl $100000000, %ecx

42 F505

43 0047 75CF jne .L4

44 0049 89742404 movl %esi, 4(%esp)

45 004d C7042400 movl $.LC0, (%esp)

45 000000

46 0054 E8FCFFFF call printf

46 FF

47 0059 83C414 addl $20, %esp

48 005c 31C0 xorl %eax, %eax

49 005e 5B popl %ebx

50 005f 5E popl %esi

51 0060 5F popl %edi

52 0061 89EC movl %ebp, %esp

53 0063 5D popl %ebp

54 0064 C3 ret

 

Genererte assembly på 64-bit:

 

9 main:

10 .LFB12:

11 .cfi_startproc

12 0000 4883EC08 subq $8, %rsp

13 .cfi_def_cfa_offset 16

14 0004 31F6 xorl %esi, %esi

15 0006 31C9 xorl %ecx, %ecx

16 0008 41B85655 movl $1431655766, %r8d

16 5555

17 000e 41B96766 movl $1717986919, %r9d

17 6666

18 .p2align 4,,10

19 0014 0F1F4000 .p2align 3

20 .L4:

21 0018 89C8 movl %ecx, %eax

22 001a 89CF movl %ecx, %edi

23 001c 41F7E8 imull %r8d

24 001f C1FF1F sarl $31, %edi

25 0022 29FA subl %edi, %edx

26 0024 8D1452 leal (%rdx,%rdx,2), %edx

27 0027 39D1 cmpl %edx, %ecx

28 0029 7410 je .L2

29 002b 89C8 movl %ecx, %eax

30 002d 41F7E9 imull %r9d

31 0030 D1FA sarl %edx

32 0032 29FA subl %edi, %edx

33 0034 8D1492 leal (%rdx,%rdx,4), %edx

34 0037 39D1 cmpl %edx, %ecx

35 0039 7502 jne .L3

36 .L2:

37 003b 01CE addl %ecx, %esi

38 .L3:

39 003d FFC1 incl %ecx

40 003f 81F900E1 cmpl $100000000, %ecx

40 F505

41 0045 75D1 jne .L4

42 0047 BF000000 movl $.LC0, %edi

42 00

43 004c 31C0 xorl %eax, %eax

44 004e E8000000 call printf

44 00

45 0053 31C0 xorl %eax, %eax

46 0055 4883C408 addq $8, %rsp

47 .cfi_def_cfa_offset 8

48 0059 C3 ret

 

 

Bortsett fra prologue og epilogue, er det eneste fordelen med 64-bit versjonen at begge de to "imull" konstantene er lagret i register.

[LonelyMan]

Overflow er ikke ett problem for å måle hastigheten. Men om noe annet så ser jeg en veldig interessant sak i koden din, det gjør ting litt suspekte, men jeg skal ikke si noe sikkert, det er uansett irrelevant da vi snakker to forskjellige ting her uansett så det blir bare bagateller i en sak som allerede er så til de grader satt ut i proporsjoner.

 

Er det kult at du ikke klare å ta i bruk mer enn halvparten av prosessoren din?

 

Punkt 1: Jeg KAN ta i bruk mer enn halvparten av prosessoren. Men jeg gjør det ikke under omstendigheter hvor det ikke er mulig.

 

Punkt 2: Du kjører i bakoverkompatibel modus, det er ikke REN x86, forstår du hva det betyr? Det betyr at du har dobbelt opp med registre å bruke i en modus som er "fiktiv" i x86 verdenen.

 

Punkt 3: Når du fikk til 0.2 sekunder som du sa i tidligere innleg (altså over 200 millisekunder) og jeg klarte på 31 millisekunder, når du da kompilerer samme koden på ett annen maskinvaresett og får 34 ms (hvis jeg husker rett) så er det jo noe riv ruskende galt.

 

Men hovedproblemet her er at du kjører en kode på en annen arkitektur enn min kode så det blir ikke sammenlignbart, i tillegg så fikk du mer eller mindre samme resultat så konklusjonen er den samme.

 

DavidBrown, jeg vil at du skal poste kildekoden i c++ da du fikk

256 millisekunder og koden da du fikk 34 millisekunder. Ikke debugger kode, men kildekoden.

Endret 18. desember 2011 av LonelyMan

[LonelyMan]

Og det jeg sa om at programstrukturen er likt på begge arkitekturene er selvfølgelig sant.

 

Nei det er ikke det. Du har brukt øyet ditt til å analysere om det er likt, og øyet ditt søker etter om "bildet" av de to sammenligningene ser likt ut. Du bruker øyet til å kjapt skanne over instruksjonene for å se om bildet er likt, men dette har ingen verdens ting å gjøre med hva som skjer i maskinen.

 

Har du virkelig analysert koden til punkt og prikke? Hvordan likestiller du de to, hvilke kriterier setter du for å måle og sammenligne en elefant og en flodhest?

 

Det å "Se" med øyet på koden om den er "mer eller mindre lik" er jo katastrofalt, det er årsaker som dette at man burde laget offisielle regler for dette.

 

Du kan virkelig ikke sammenligne eller forsøke å erstatte registre (mentalt) og så tenke (aha, dette er jo en liknende sak, så den er jo lik med den andre). Det er katastrofalt

 

Men jeg føler at jeg har tingene på min side så jeg sier takk for diskusjonen, nå må jeg kode

Endret 18. desember 2011 av LonelyMan

[LonelyMan]

Det kalles for loop unrolling, og det er noe som er tungvindt å gjøre manuelt i assembly, men enkelt å gjøre i en kompilator. Det er ikke alltid at det øker hastighet - det er en balanse mellom pipelining, branch kostnader,

 

Den koden du nettopp la frem kjører på 32 ms, min kjørte på 31 så her har du bomma kraftig, optimalisering er helt klart ikke din ting, det skal du overlate til kompilatoren din. Ja jeg er fullt klar over hva loop unrolling er, om det er tungvint eller ikke har ingenting med testen å gjøre. Poenget er når jeg sier "det er ikke mer å unrolle" så betyr det at det ikke er relevant eller at algoritmen er laget slik at det ikke er mulig å gjøre det bedre. Og det har jeg nettopp vist det, din kode kjørte 1 ms tregere, mens det du påstår skulle gjort at den kjørte noen millisekunder raskere, hvilket det ikke gjorde.

 

Og dersom du noen gang prøve å jobbe med en annen cpu som ikke er like register-fattig som x86

 

Vel, om vi skal måle c++ opp mot asm, så må vel begge bruke x86, jeg blir så frustrert av å lytte til dette. Det var c++ mot asm, ikke AT&T reversert notasjon med doble registre. Det du sier om register-fattig, det er ikke en negativ ting for meg, det er en positiv i mitt favør, da vi skulle måle c++ mot asm, og du behøver doble registre.

 

Problemet ditt med forståelsen av ekstra registre er at du ikke skjønner "impacten" av å ha ekstra registre.

Endret 18. desember 2011 av LonelyMan

[Matsemann]

En algoritme som bruker konstant tid på å gjøre noe.

Slik som å utføre noen beregninger som tar like lang tid uansett input.

 

Er noe O (n) sier man det tar lineær tid. Da er antall operasjoner som må gjøres proporsjonal med input.

F. eks det å finne minste tall i en liste. Da må du gå igjennom hele listen, og blir listen større tar det tilsvarende lang tid. Altså O (n)

Skal du finne første element i en liste spiller det jo ingen rolle hvor mange elementer som kommer etterpå, så det er O (1)

Sorteringsproblemer er typisk O (n*n)

 

Sortering er vanligvis O(n.log(n)) tid, ihvertfall med vanlige effektive algoritmer (heap sort, quick sort, insertion sort). Det fins O(n^2) sorting algoritmer, som bubblesort, som er greit når du trenger noe liten og enkelt, og ikke skal sortere store lister. Det fins også algoritmer som nærmer seg O(n), som bucket sort, men de er kun bedre enn O(n.log(n)) i bestemte omstendigheter.

Hehe, er ikke bare du som roter her. Meningen var å skrive n log n, men brukte så lang tid på å finne gangetegnet på telefonen at jeg gikk meg bort

 

Hadde faktisk eksamen i algoritmer og datastrukturer på onsdag, hadde jeg skrevet hva jeg skrev på eksamen hadde jeg fortjent å stryke

Endret 18. desember 2011 av Matsemann

[LonelyMan]

Nå har jeg kompilert koden din på en ren x86 plattform og den kjørte på 1 sekund blank med full optimalisering. Commandline options: -Tx86-coff -Ot -Ob1 -fp:precise -W1 -Gd

 

Bare sånn at du ser forskjellen på ren x86 kode med 8 registre.

Så du har ikke mye troverdighet igjen nå, og dermed tar jeg kvelden (eller formiddagen av forumet) Ha en god dag.

 

static int sum3or5(int m) {
int sum = 0;
for (int i = 0; i < m; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i; }
}
return sum;
}

int main(void) {
printf("%i\n", sum3or5(100000000));
return 0;
}

Endret 18. desember 2011 av LonelyMan

[LonelyMan]

390 ms, gcc -O3 (i5-2520M prosessor)

340-370 ms med -O2 med samme prosessor.

 

Det er helt klart at du driver gjøn her David Brown. Nå har jeg 3 tester på samme plattform med din kode, og alle har elendige timings med din kode.

 

Jeg har testet koden din på 3 forskjellige prosessorer, noen er raskere enn din og så har jeg testet med 2 forskjellige c kompilatorer. Alle sammen har elendig timings.

 

Jeg skal nå teste på en av intel's beste kompilatorer, men det orker jeg ikke nå. Spent å se hva den gir ut.

Endret 18. desember 2011 av LonelyMan

[LonelyMan]

David Brown, ny test: (Fjerde test)

 

243 ms på en 2600K overklokket prosessor på 4 GHz med den nøyaktig samme koden du la ut, full optimalisering spesifisert i kompilatoren.

 

he-he (den prosessoren er ikke noe småtull heller)

 

Når du påstår at du:

 

1: Fikk 24 ms på en 2.5 GHz prosessor med den gitte koden, og jeg får

2: 243 ms på en 4 GHz prosessor, så må du skjønne at jeg ikke kan ta deg seriøst

Endret 18. desember 2011 av LonelyMan

[LonelyMan]

Enten må vi holde oss til akkurat samme algoritme, med optimisering av implementasjon men ikke metoden, ellers må vi finne et annet problem som ikke har samme forbedringsmuligheter.

 

Jeg bruker samme algoritme, det er bare du som ikke ser det Helt prikk lik algoritme. Om du har problemer med å se det så kan jeg lage kommentarer på instruksjonene for å vise deg det (om du ønsker)

 

Problemet er at du ser div instruksjonen som ett problem, mens i realiteten vil kompilatoren din uansett erstatte den med det optimale. Derfor er algoritmene lik i prinsipp.

Endret 18. desember 2011 av LonelyMan

[David Brown]

Overflow er ikke ett problem for å måle hastigheten. Men om noe annet så ser jeg en veldig interessant sak i koden din, det gjør ting litt suspekte, men jeg skal ikke si noe sikkert, det er uansett irrelevant da vi snakker to forskjellige ting her uansett så det blir bare bagateller i en sak som allerede er så til de grader satt ut i proporsjoner.

 

Er det kult at du ikke klare å ta i bruk mer enn halvparten av prosessoren din?

 

Punkt 1: Jeg KAN ta i bruk mer enn halvparten av prosessoren. Men jeg gjør det ikke under omstendigheter hvor det ikke er mulig.

 

Punkt 2: Du kjører i bakoverkompatibel modus, det er ikke REN x86, forstår du hva det betyr? Det betyr at du har dobbelt opp med registre å bruke i en modus som er "fiktiv" i x86 verdenen.

 

Punkt 3: Når du fikk til 0.2 sekunder som du sa i tidligere innleg (altså over 200 millisekunder) og jeg klarte på 31 millisekunder, når du da kompilerer samme koden på ett annen maskinvaresett og får 34 ms (hvis jeg husker rett) så er det jo noe riv ruskende galt.

 

Men hovedproblemet her er at du kjører en kode på en annen arkitektur enn min kode så det blir ikke sammenlignbart, i tillegg så fikk du mer eller mindre samme resultat så konklusjonen er den samme.

 

DavidBrown, jeg vil at du skal poste kildekoden i c++ da du fikk

256 millisekunder og koden da du fikk 34 millisekunder. Ikke debugger kode, men kildekoden.

 

Jeg er enige at overflow er ikke et stort problem her - vi kan late som om problemet er definert modulo 2^32 og konsentrere oss om hastighet. Men det er likevel viktig å poengtere det - det er ikke vits i et program som kjører fort men gir feil svar.

 

Jeg kjører ikke i "bakoverkompatibel" modus. Jeg har gjort de fleste av forsøkende mine i renn amd64 modus (eller "x86-64" modus - men jeg foretrekker å gi AMD kreditt for å ha dratt pc verden motvillig framover). Hvis du ser på koden - som jeg postet i #141 - ser du at kompilatoren bruker både ekstra registers (r8d og r9d) og 64-bit register (rdx). Det vil si, den bruker "64-bit mode". Når jeg testet med 32-bit, kjørte jeg på en 32-bit virtuell maskin på samme PC. Da er det gode gammeldags "protected mode", noe som er klar fra koden jeg postet.

 

<http://en.wikipedia.org/wiki/X86-64#Operating_modes>

[David Brown]

Og det jeg sa om at programstrukturen er likt på begge arkitekturene er selvfølgelig sant.

 

Nei det er ikke det. Du har brukt øyet ditt til å analysere om det er likt, og øyet ditt søker etter om "bildet" av de to sammenligningene ser likt ut. Du bruker øyet til å kjapt skanne over instruksjonene for å se om bildet er likt, men dette har ingen verdens ting å gjøre med hva som skjer i maskinen.

 

Har du virkelig analysert koden til punkt og prikke? Hvordan likestiller du de to, hvilke kriterier setter du for å måle og sammenligne en elefant og en flodhest?

 

Det å "Se" med øyet på koden om den er "mer eller mindre lik" er jo katastrofalt, det er årsaker som dette at man burde laget offisielle regler for dette.

 

Du kan virkelig ikke sammenligne eller forsøke å erstatte registre (mentalt) og så tenke (aha, dette er jo en liknende sak, så den er jo lik med den andre). Det er katastrofalt

 

Men jeg føler at jeg har tingene på min side så jeg sier takk for diskusjonen, nå må jeg kode

 

Jeg er enige at jeg bare har brukt øyene for å sammenligne koden. Men jeg ber deg se på de to kodelistingene i post #141, og sammenligne dem selv. Det fins et par forskjeller - den som er på 64-bit tar fordelen av ekstra registerer for å lagre en konstant i register istedenfor å bruke en immediate konstant senere. Dette fører også til litt forskjeller i register bruk. Men ellers er koden identisk.

 

Jeg er fullstendig klar over at kode som virker overfladisk likt kan ha betydelige forskjeller i kjøringshastighet. Alt som trengs er en uventet dependency i registers, eller forskjeller i hvordan prosessoren kan benytte seg av de forskjellige instruction units. Jeg ser ingen slike problemer her. Jeg er ingen ekspert på x86 assembly - og selv de alle mest erfaren x86 assembly programmerere har ikke alle detaljer til alle x86 cpu'er i hodet. Men ved å teste koden bekreftet jeg at det er ihvertfall ikke store forskjeller.

[David Brown]

Det kalles for loop unrolling, og det er noe som er tungvindt å gjøre manuelt i assembly, men enkelt å gjøre i en kompilator. Det er ikke alltid at det øker hastighet - det er en balanse mellom pipelining, branch kostnader,

 

Den koden du nettopp la frem kjører på 32 ms, min kjørte på 31 så her har du bomma kraftig, optimalisering er helt klart ikke din ting, det skal du overlate til kompilatoren din. Ja jeg er fullt klar over hva loop unrolling er, om det er tungvint eller ikke har ingenting med testen å gjøre. Poenget er når jeg sier "det er ikke mer å unrolle" så betyr det at det ikke er relevant eller at algoritmen er laget slik at det ikke er mulig å gjøre det bedre. Og det har jeg nettopp vist det, din kode kjørte 1 ms tregere, mens det du påstår skulle gjort at den kjørte noen millisekunder raskere, hvilket det ikke gjorde.

 

Jeg har ikke misforstått her, men det har du. Kanskje jeg ikke var særlig klar i mine forklaringer. Jeg skulle vise deg hva "loop unrolling" betyr, og en eksempel over hvordan denne koden kunne "unrolles" - jeg prøvde ikke å gi ferdig kode, og testet ikke koden. Når jeg ba kompilatoren til å kjøre ekstra loop unrolling, gjorde den noe omtrent sånt - men ikke akkurat som jeg skrev. Kompilatoren kjenner de detaljene som trengs for å få lagt raskere kode, men jeg brukte en eksempel som var lettere å forstå for å illustrere poenget.

 

Og ja, det <i>er</i> mulig å unrolle koden mer og få raskere kode. Ihvertfall klarte kompilatoren min det uten problem. Som sagt, er kompilatoren sin kode litt mer komplisert enn den enkel eksempel jeg ga deg.

 

Og dersom du noen gang prøve å jobbe med en annen cpu som ikke er like register-fattig som x86

 

Vel, om vi skal måle c++ opp mot asm, så må vel begge bruke x86, jeg blir så frustrert av å lytte til dette. Det var c++ mot asm, ikke AT&T reversert notasjon med doble registre. Det du sier om register-fattig, det er ikke en negativ ting for meg, det er en positiv i mitt favør, da vi skulle måle c++ mot asm, og du behøver doble registre.

 

Problemet ditt med forståelsen av ekstra registre er at du ikke skjønner "impacten" av å ha ekstra registre.

 

Om det plager deg at jeg brukte 64-bit kompilator, kan jeg begrense meg til en 32-bit kompilator i framtiden i tråden. Jeg er enige at den mest korrekte sammenligningen får vi ved å holde oss til samme modellen - selv om jeg vet (og har bevist gjennom testing) at det er nokså lite forskjell i dette tilfelle, der man kan ikke dra særlig fordel av ekstra registerene.

[David Brown]

Nå har jeg kompilert koden din på en ren x86 plattform og den kjørte på 1 sekund blank med full optimalisering. Commandline options: -Tx86-coff -Ot -Ob1 -fp:precise -W1 -Gd

 

Bare sånn at du ser forskjellen på ren x86 kode med 8 registre.

Så du har ikke mye troverdighet igjen nå, og dermed tar jeg kvelden (eller formiddagen av forumet) Ha en god dag.

 

static int sum3or5(int m) {
int sum = 0;
for (int i = 0; i < m; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i; }
}
return sum;
}

int main(void) {
printf("%i\n", sum3or5(100000000));
return 0;
}

 

Hvilken kompilatoren brukte du her? Jeg har bare brukt gcc på x86 platform, men en forsøk på google på kommandolinje switches viser at det kanskje er noe som heter "Pelles C compiler" du har brukt, som er basert på LCC. LCC regnes som en liten og enkel kompilator, som er godt skrevet og lett å forstå, men ingen tungvekt når det gjelder å lage effektivt kode. Skal du lage raskt kode fra C, trenger du en voksen kompilator - gcc, llvm, Intel sin kompilator, MS VC++, etc.

[David Brown]

David Brown, ny test: (Fjerde test)

 

243 ms på en 2600K overklokket prosessor på 4 GHz med den nøyaktig samme koden du la ut, full optimalisering spesifisert i kompilatoren.

 

he-he (den prosessoren er ikke noe småtull heller)

 

Når du påstår at du:

 

1: Fikk 24 ms på en 2.5 GHz prosessor med den gitte koden, og jeg får

2: 243 ms på en 4 GHz prosessor, så må du skjønne at jeg ikke kan ta deg seriøst

 

Jeg regner med det er post nummer #127 av meg som du ikke forstår. La meg prøve å forklare igjen, og poster C koden for å gjøre det klinkende klart.

 

Vi ble enige om å implementer en funksjon med "if (i % 3 == 0 || i % 5 == 0)" testen. Du implementerte den i assembly, jeg implementerte den i C (d.v.s., kopi-og-lim fra bloggen). Din forsøk på dette med en nokså klar assembly kode tok 0.858 s hos deg, og 0.978 s på min i7-920 maskin. Min forsøk med C tok 0.254 s (med 64-bit kompilator - selv om det var ubetydelig). Ref post #101.

 

Deretter endret du algoritmen, og fikk 31 ms (ref post #108). Jeg sa i post #127 at dette var meningsløs til sammenligning fordi det er ikke samme algoritme. Og for å forklare videre sa jeg at da jeg implementere samme algoritme som deg, tok det 34 ms på min PC. Kompilatoren min lagte nesten identisk kode til den du hadde skrevet, og kjøringstiden var omtrent identisk (etter skalering fordi din PC er litt raskere enn den i7-920 jeg testet på). Jeg noterte også at dersom jeg presset kompilatoren litt mer med "-funroll-all-loops", kjørte den i 26 ms host meg. Jeg postet ikke C koden min - jeg så ingen vits i å fylle plassen med koden, ettersom det er temmelig klar når man først har forstått algoritmen i din assembly kode. Men her er den:

 

static int sum3or5(int m) {

int sum = 0;

int i = 3;

while (i < m) {

sum += i;

i += 3;

}

i = 5;

while (1) {

sum += i;

i += 5;

if (i >= m) return sum;

sum += i;

i += 10;

if (i >= m) return sum;

}

}

 

 

Jeg er ikke vant til at folk ikke tror på meg. Alle kan ta feil inn i blant, og man skal være skeptisk til veldig overraskende resultater. Men utgangspunkt skal vanligvis være at dersom "motstanderen" sier noe man kan ikke helt tro er mulig, er det fordi noen har misforstått noe. Tror du virkelig at jeg har skrevet alle disse poster med løgn, bare for å plage deg? Jeg syns faktisk det er interessant å sammenligne assembly og C som språk, og jeg bruke begge i arbeid på mange forskjellige prosessorer. Jeg var nysgjerrig om påstandene dine om hastigheter til assembly programmering på x86 faktisk holdt mål - x86 prosessor er ganske komplisert, så det er mulig at i assembly programmering du kan bruke triks som kompilatoren ikke kan. Men det virker temmelig klar at dette ikke er tilfelle med denne oppgaven - kompilatoren lager raskere koden enn deg til samme algoritme.

[Drogin]

Hehe, artig lesing i denne tråden.

Men jeg må si meg enig med David Brown - en kompilator sitter på sabla mange gode triks, og skal man klare å skrive raskere kode i assembly, må man ha en veldig smart løsning til et spesialisert problem, slik at man kan gjøre noe spesielt kompilatoren ikke tenkte på.

 

Og til LonelyMan vil jeg nå si det er juks å implementere en ny algoritme, når målet er å sammenlikne C og assembly kode.

Det blir som om man skulle teste 2 fly-motorer på 2 identiske fly, og en av partene plutselig satte motoren i et fly med bedre aerodynamisk design.

Endret 19. desember 2011 av Drogin

[torbjørn marø]

Og til LonelyMan vil jeg nå si det er juks å implementere en ny algoritme, når målet er å sammenlikne C og assembly kode.

Det blir som om man skulle teste 2 fly-motorer på 2 identiske fly, og en av partene plutselig satte motoren i et fly med bedre aerodynamisk design.

 

Det blir en vurderingssak. Da jeg gav LonelyMan oppgaven sa jeg ikke noe om hvordan den måtte løses - jeg var mer interessert i å se beste løsning i assembler. Dvs. beste O(n)-løsning, å bruke fremgangsmåten beskrevt i denne kommentaren, eller bare skrive ut svaret direkte, ville selvsagt vært juls

 

Jeg er interessert i å se hvordan man raskest og best kommer seg fra A til B, for å si det sånn, uavhengig av hvilke type fly eller motor vi snakker om. Så begge måter å sammenligne på gir interessant informasjon.

[blackbrrd]

Det som er litt interessant er når man begynner å si at det er juks å bruke en 64-bits kompilator. På mange måter er det jo det, man kan skrive koden i c++ en gang og kompilere til både 32bit og 64bit uten noe vesentlig mer arbeid. Dette blir imotsetning til hvis man skriver i assembly og må skrive for enten 32bit eller 64bit.

 

Er ikke dette et veldig godt argument for å skrive i c++ og la kompilatoren lage maskinkoden?

 

Linux kom svært for i 64bit etter at AMD kom med den første 64bits prosessoren. Hvis hele greia hadde vært skrevet i 32bit assembly så måtte dette mer eller mindre ha måttet bli laget på nytt. Siden mesteparten var laget i C så kunne det rekompileres og fungerte fint i 64bit.

[David Brown]

Hehe, artig lesing i denne tråden.

Men jeg må si meg enig med David Brown - en kompilator sitter på sabla mange gode triks, og skal man klare å skrive raskere kode i assembly, må man ha en veldig smart løsning til et spesialisert problem, slik at man kan gjøre noe spesielt kompilatoren ikke tenkte på.

 

Og til LonelyMan vil jeg nå si det er juks å implementere en ny algoritme, når målet er å sammenlikne C og assembly kode.

Det blir som om man skulle teste 2 fly-motorer på 2 identiske fly, og en av partene plutselig satte motoren i et fly med bedre aerodynamisk design.

 

Korrekt.

 

Det fins en tid og plass til assembly - jeg har selv skrevet i assembly i nærmere 30 år på forskjellige prosessorer. Poenget mitt er ikke å bevise at C er alltid raskere enn assembly, fordi det ikke er sant. Poenget mitt er at i de fleste tilfelle, er C et bedre valg enn assembly av veldig mange grunn - og at det faktisk ofte er omtrent like raskt, eller ennå raskere, enn programmene man skriver på assembly. Hvis man lege mye arbeid i tenking, måling, prøving og feiling, kan man skrive assembly kode som er raskere enn det kompilatoren klarer. Men man gjør ikke det i praksis, uten at man har veldig gode grunn. Det er bare så mye mer arbeid dersom man skal lage noe i assembly som er klar, vedlikeholdsvennlig, og bevislig korrekt.

 

For å gjøre C koden komplett til en profesjonelt standard ville C koden i denne tråden bare trenger et par kommentarlinje som sier hva funksjonen skal gjøre - virkemoten er selvforklarende. Men assembly koden hadde trengt minst noen sider med dokumentasjon. Og alt sammen måte gjøres på nytt for å kjøre koden på en ny prosessor - det trengs endringer bare for å kjøre på 64-bit modus på samme prosessor.

 

En del programmer drar nytte av assembly. Hvis du ser inn i koden til VLC eller andre media spillerer, de innerste loopene i codec'ene er ofte i assembly (eller rettere sagt har de assembly implementasjonene i tillegg til C kode, for å dekke flest mulig cpu'er). Skal man få det meste ut av SIMD, må man som regel ti til assembly. Ser du inn i koden til en operativsystem, ser man også en del assembly her og der. Men disse er små bitter av koden, der man har store gevinst av tunge optimisering av bestemte oppgaver.

 

Tiden da det var fornuftig å bruke assembly som hovedspråk i generelle programmering er for lengst forbi i PC verden. Det samme gjelder til et mindre grad også C og også C++ - kan man gjøre samme oppgaven med raskere utvikling med et høyre nivå språk med bedre sikkerhet mot programmeringsfeil, burde man som regel velge slike språk. Forbedret JIT kompilatorer og andre tekniske forbedringer redusere kostnadene for mer avanserte språk. (Men det er viktig at mange av bibliotekene til slike språk skrives i C/C++, for å holde opp gjennomsnitt hastighet.) Det meste av min PC programmering gjør jeg på Python.

 

Balansene er annerledes med andre prosessorer. Noen av de jeg bruker eller har brukt er dårlig tilpasset til C - hvis jeg brukte C istedenfor assembly, måte jeg velge en større, raskere og dyrere brikke. Da er assembly et solid valg.

 

Et annet punkt i denne tråden er hvorfor man skulle lære assembly. Jeg liker veldig godt at programmerere lærer assembly på de prosessorene de skal bruke - det gir en mye bedre forståelse for brikken, og man skriver langt bedre og raskere kode i C som resultat. Man blir en bedre sjåfør av å ha litt forståelse av hvordan bilen og motoren fungere, selv om man ikke blir bilmekaniker.

[David Brown]

Og til LonelyMan vil jeg nå si det er juks å implementere en ny algoritme, når målet er å sammenlikne C og assembly kode.

Det blir som om man skulle teste 2 fly-motorer på 2 identiske fly, og en av partene plutselig satte motoren i et fly med bedre aerodynamisk design.

 

Det blir en vurderingssak. Da jeg gav LonelyMan oppgaven sa jeg ikke noe om hvordan den måtte løses - jeg var mer interessert i å se beste løsning i assembler. Dvs. beste O(n)-løsning, å bruke fremgangsmåten beskrevt i denne kommentaren, eller bare skrive ut svaret direkte, ville selvsagt vært juls

 

Jeg er interessert i å se hvordan man raskest og best kommer seg fra A til B, for å si det sånn, uavhengig av hvilke type fly eller motor vi snakker om. Så begge måter å sammenligne på gir interessant informasjon.

 

Det var din oppgave, men likevel syns jeg du tar feil her (som du sier, det er en vurderingssak). Oppgaven - som jeg tolker det - var ikke å kalkulere summen. Som beskrevet i bl.a. Post #140, er den raskeste måten å gjøre kalkulasjonen å bruke litt matematikk og O(1) tid. Så enten er oppgaven "implementere denne algoritme i forskjellige språk", eller "kalkulere denne summen i forskjellige språk" - det er ikke helt meningsfullt å si "kalkulere denne summen i forskjellige språk, med hvilken som helst algoritme bare det er i O(n) tid". Etter min mening, dersom LonelyMan sin endringer i algoritme er tillatt, er også den O(1) løsningen tillatt. Kanskje t.o.m. C++ template løsningen min skulle være tillatt. (Og jeg sier dette til tross for at kompilatoren min implementerte LonelyMan sin algoritme raskere enn han gjorde i assembly.)

 

Jeg tolker oppgaven som en implementeringsoppgave, ikke en algoritme oppgave. Skal vi jobbe med algoritmer, må du finne på en oppgave som ikke har en så pass enkel løsning!

[David Brown]

Det som er litt interessant er når man begynner å si at det er juks å bruke en 64-bits kompilator. På mange måter er det jo det, man kan skrive koden i c++ en gang og kompilere til både 32bit og 64bit uten noe vesentlig mer arbeid. Dette blir imotsetning til hvis man skriver i assembly og må skrive for enten 32bit eller 64bit.

 

Er ikke dette et veldig godt argument for å skrive i c++ og la kompilatoren lage maskinkoden?

 

Linux kom svært for i 64bit etter at AMD kom med den første 64bits prosessoren. Hvis hele greia hadde vært skrevet i 32bit assembly så måtte dette mer eller mindre ha måttet bli laget på nytt. Siden mesteparten var laget i C så kunne det rekompileres og fungerte fint i 64bit.

 

Ja, dette er en av grunnene til å skrive i C (eventuelt C++ - men Linux er skrevet i C) istedenfor assembly.

 

Linux var faktisk klar på amd64 før brikkene var tilgjengelig - AMD hadde laget gode simulatorer, og hadde hjulpet gcc amd64 target.

 

Men Linux hadde kjørt på 64-bit DEC Alpha siden 1995 - 8 år før AMD kom med 64-bit cpu'er. Så vidt jeg vet kjørte den også på 64-bit på PPC, Sparc, MIPS og IA-64 før amd64 var klar. Hovedgrunnen til at Linux fins på alle disse, og mange flere på 32-bit, er at det er skrevet i C.