snabb och snål tio gånger i c

C, C++, Pascal, Assembly, Raspberry, Java, Matlab, Python, BASIC, SQL, PHP, etc.
persika
EF Sponsor
Inlägg: 1347
Blev medlem: 31 juli 2006, 22:14:37
Ort: Österlen, Skåne

snabb och snål tio gånger i c

Inlägg av persika »

Har gjort en jämförelse med olika sätt att multiplicera med 10.

Fyra olika grupper med olika metoder: Multiplikation, Shift, Addition, Loopar.

Snabbast: shiftoperationer med "((a << 2) + a) << 1"
Snålast med programminne: Nedåträknande loopar "while" eller "for"
Snålast med ramminne: Ingen som är bäst eftersom många av metoderna tog bara 6 byte.

Vilken som är bäst totalt sett går nog inte att utse.

En intressant sak man kan se att det är bra att använda *= eller += .
En annan intressant sak är att while och for är lika bra.
Först trodde jag while var bättre, men när jag även gjort for-loopen nedåträknande var den lika bra.
Personligen gillar jag while bättre, eftersom den är mera lättläst.

För testerna har jag använt MPLAB 8.88, Hitech C 9.83, MPLAB SIM, PIC 16F1825

Kod: Markera allt

// Multiplikation

uInt16 a;
a = 123;  
a = a * 10;
// programminne: 59  ram: 8  instruktionscykler: 211

uInt16 a;
a = 123;  
a *= 10;
// programminne: 59  ram: 8  instruktionscykler: 133


// Shift

uInt16 a;
a = 123;   
a = (a << 3) + a + a;
// programminne: 25  ram: 6  instruktionscykler: 35

uInt16 a;
a = 123;   
a = (a << 3) + (a << 1);
// programminne: 28  ram: 6  instruktionscykler: 38

uInt16 a;
a = 123;   
a = ((a << 2) + a) << 1;
// programminne: 28  ram: 6  instruktionscykler: 33


// Addition

uInt16 a;
a = 123;   
a = a + a + a + a + a + a + a + a + a + a;
// programminne: 62  ram: 18  instruktionscykler: 62

uInt16 a;
uInt16 c;
a = 123;   
c = a + a;
c = c + c + a;
c = c + c;
// programminne: 45  ram: 6  instruktionscykler: 45

uInt16 a;
uInt16 c;
a = 123;   
c = a + a;
c = c + c + c + c + c;
// programminne: 44  ram: 10  instruktionscykler: 44

uInt16 a;
uInt16 c;
a = 123;   
c = a + a;
c += c + a;
c += c;
// programminne: 35  ram: 6  instruktionscykler: 35

uInt16 a;
uInt16 c;
a = 123;   
c = a + a;
c += c + c + c + c;
// programminne: 42  ram: 10  instruktionscykler: 42


// Loopar

uInt16 a;
uInt8 b;
uInt16 c;
a = 123;   
c = 0; 
for ( b=0; b<10; b++ )
  c += a;  
// programminne: 29  ram: 6  instruktionscykler: 163

uInt16 a;
uInt8 b;
uInt16 c;
a = 123;   
c = 0; 
b = 10;
while (b)
  {
  c += a;
  b--;  
  }
// programminne: 22  ram: 6  instruktionscykler: 137

uInt16 a;
uInt8 b;
uInt16 c;
a = 123;   
c = 0; 
for ( b=10; b; b-- )
  c += a;  
// programminne: 22  ram: 6  instruktionscykler: 137

spaderkung
Inlägg: 138
Blev medlem: 12 maj 2007, 11:24:24
Ort: Sjöbo

Re: snabb och snål tio gånger i c

Inlägg av spaderkung »

I hitech c kunde rubriken varit även om det nämns sen
Användarvisningsbild
ffredrik
Inlägg: 341
Blev medlem: 20 oktober 2009, 17:52:18
Ort: Göinge

Re: snabb och snål tio gånger i c

Inlägg av ffredrik »

Trevlig test!
Mycket intressantast vore att jämföra olika processorer, t ex olika AVR-typer m fl.
Användarvisningsbild
AndLi
Inlägg: 17098
Blev medlem: 11 februari 2004, 18:17:59
Ort: Knivsta
Kontakt:

Re: snabb och snål tio gånger i c

Inlägg av AndLi »

Undra varför inte kompilatorn genererar samma kod av a = a*10 och a*=10...

Man ska vara medveten om att det inte alls är säker att kompilatorn optimerar på samma sätt bara det att man ändrar koden bara så lite... (eller vad som händer före och efter)
Behöver man optimerad kod och vill veta hur många klockcykler saker kommer ta är det fortfarande assembler som gäller, man vet aldrig vad kompilatorutvecklarna hittar på mellan sina uppgraderingar...

Det handlar ju också om vilka assembler instruktioner som finns tillgängliga på den processor kompilatorn framställer kod för, och om kompilatorn faktiskt använder dem...
johano
Inlägg: 1943
Blev medlem: 22 januari 2008, 10:07:45
Ort: Stockholm

Re: snabb och snål tio gånger i c

Inlägg av johano »

WTF, en kompilator som inte genererar samma kod för "a *= 10" som för "a = a * 10" ??

GCC producerar exakt samma kod för de båda varianterna:

Kod: Markera allt

int a = 123;
   8:	c7 45 f8 7b 00 00 00 	mov    DWORD PTR [rbp-0x8],0x7b
int b = 123;
   f:	c7 45 fc 7b 00 00 00 	mov    DWORD PTR [rbp-0x4],0x7b

a = a * 10;
  16:	8b 55 f8             	mov    edx,DWORD PTR [rbp-0x8]
  19:	89 d0                	mov    eax,edx
  1b:	c1 e0 02             	shl    eax,0x2
  1e:	01 d0                	add    eax,edx
  20:	01 c0                	add    eax,eax
  22:	89 45 f8             	mov    DWORD PTR [rbp-0x8],eax

b *= 10;
  25:	8b 55 fc             	mov    edx,DWORD PTR [rbp-0x4]
  28:	89 d0                	mov    eax,edx
  2a:	c1 e0 02             	shl    eax,0x2
  2d:	01 d0                	add    eax,edx
  2f:	01 c0                	add    eax,eax
  31:	89 45 fc             	mov    DWORD PTR [rbp-0x4],eax
/j
Användarvisningsbild
ffredrik
Inlägg: 341
Blev medlem: 20 oktober 2009, 17:52:18
Ort: Göinge

Re: snabb och snål tio gånger i c

Inlägg av ffredrik »

Kompilatorn måste naturligtvis ställas in för att utnyttja processorns instruktioner optimalt, och all optimering disablas.
Användarvisningsbild
AndLi
Inlägg: 17098
Blev medlem: 11 februari 2004, 18:17:59
Ort: Knivsta
Kontakt:

Re: snabb och snål tio gånger i c

Inlägg av AndLi »

hehe IAR C cortex är då lite för smart

Kod: Markera allt

  int a=123;
  int b=123;
  
  a=a*10;
  b*=10;
genererar exakt 0 instruktioner...

Vilket ju är helt korrekt eftersom jag aldrig använde värdena a & b...

>och all optimering disablas.
Va?
johano
Inlägg: 1943
Blev medlem: 22 januari 2008, 10:07:45
Ort: Stockholm

Re: snabb och snål tio gånger i c

Inlägg av johano »

Du får lägga till en "printf("%d", a)" så 'används' dem och optimeras inte bort.. :-)
Användarvisningsbild
ffredrik
Inlägg: 341
Blev medlem: 20 oktober 2009, 17:52:18
Ort: Göinge

Re: snabb och snål tio gånger i c

Inlägg av ffredrik »

Sådana här tester är meningslösa om kompilatorn optimerar. Använd -O0 i gcc.
gkar
Inlägg: 1453
Blev medlem: 31 oktober 2011, 15:28:29
Ort: Linköping

Re: snabb och snål tio gånger i c

Inlägg av gkar »

Nej, sådana här tester är meningslösa om kompilatorn inte optimera så bra den kan.
Det är ju den koden man använder sedan.
Det normala är ju att man utvecklar med maximal optimering på, och stänger av optimeringen när man behöver det för debug en stund.

Det är självklart att kompilatorn inte genererar någon kod om resultatet inte används.
För benchmarking går man runt det, oftast genom att sist tilldela resultatet till en volatile, göra return result, eller skicka resultatet till en annan global funktion.
Kompilatorn kan då inte följa flödet utan måste generera koden.
Användarvisningsbild
TomasL
EF Sponsor
Inlägg: 45264
Blev medlem: 23 september 2006, 23:54:55
Ort: Borås
Kontakt:

Re: snabb och snål tio gånger i c

Inlägg av TomasL »

Det normala är ju att man utvecklar med maximal optimering på, och stänger av optimeringen när man behöver det för debug en stund.
Det är en omöjlighet, eftersom koden är fullständigt väsenskilld. Du debuggar en helt annan kod än den du använder.
gkar
Inlägg: 1453
Blev medlem: 31 oktober 2011, 15:28:29
Ort: Linköping

Re: snabb och snål tio gånger i c

Inlägg av gkar »

Jag är inte helt säker på vad du menar.

Men ja, det är sällsynt att jag stänger av optimeringen. Men ibland gör jag det.
Kanske 1 gång / 10000 rader kod eller 2 gånger / år, stänger jag av optimeringen. Och då behövs det.
Användarvisningsbild
sodjan
EF Sponsor
Inlägg: 43176
Blev medlem: 10 maj 2005, 16:29:20
Ort: Söderköping
Kontakt:

Re: snabb och snål tio gånger i c

Inlägg av sodjan »

> uInt16 a;
> a = 123;
> a = (a << 3) + (a << 1);
> // programminne: 28 ram: 6 instruktionscykler: 38

Det här blir väl alltså detsamma som a = a*8 + a*2.
Det är samma metod som Nikolai Golovchenko's kodgenerator skapar.
Ange "Input register size" = 16 och "Multiply by constant:" = 10 och testa:
http://www.piclist.com/techref/piclist/ ... divmul.htm.
Denna ger ett 24 bitars resultat för a*10 för alla 16-bitars värden av a
och använder 28 instruktioner. Ej optimerat för nyare processorer, om
det nu går (har inte funderat på det).

Problemet med alla dina exempel är att det inte fungerar för alla värden
av a, bara om värdet på a är mindre än maxvärdet för a delat med 10.
Du måste ha en resultatvariabel som är större än 16 bitar. Prova med t.ex.:

> uInt16 a;
> uInt24 b;
> a = 123;
> b = (a << 3) + (a << 1);

Om det inte heter uInt24 (jag har inte en susning) så använd
vad det nu heter för 24 bitars integers... Det ger en funktion
som mer liknar den som kodgeneratorn ovan ger.

För att kolla hur smart kompilatorn är så kan du även testa med b = a * 16,
vilket bör ge kompakt kod. Generatorn ovan ger 10 instruktioner och 10 cykler.
Det fria versionen av XC8 var inte på långa vägar speciellt "smart" utan
vill använda 18 instruktioner... :-)
Användarvisningsbild
TomasL
EF Sponsor
Inlägg: 45264
Blev medlem: 23 september 2006, 23:54:55
Ort: Borås
Kontakt:

Re: snabb och snål tio gånger i c

Inlägg av TomasL »

Vad jag menar är att om du släpper ett program som genereras med alla optimeringar påslagna, så släpper du defakto ett program som är helt och hållet o-debuggat.
persika
EF Sponsor
Inlägg: 1347
Blev medlem: 31 juli 2006, 22:14:37
Ort: Österlen, Skåne

Re: snabb och snål tio gånger i c

Inlägg av persika »

tack alla för intressanta svar.

Jo, det kan behövas 24 bitar för resultatet. Jag ska göra test med det när jag är tillbaka vid datorn
Ska även prova *= 16

En annan liknande test jag gjorde, kolla även på:
http://elektronikforumet.com/forum/view ... 4&start=15
Skriv svar