Compiler Multiplikation verbieten

[Siro]

Hallo zusammen,

in einem kleinen 8 Bitter ist eine Multiplikation ja nicht grad optimal, da sie in Software ausgeführt wird.
Wenn ich nun einen Wert mit 3 multiplizieren möchte, habe ich ja so einiges an Möglichkeiten.
Ich habe mal verschiedene Möglichkeiten compiliert und war doch sehr erstaunt über das Ergebnis:
Um den Compiler auszutricksen habe ich folgenden Code verwendet und genau der ist laufzeitmässig der absolut Schlechteste:

Compiler ist der XC8 Version V2.00

char cnt;

cnt  = cnt + cnt + cnt;    // 57 Zyklen

So wie ich es in Assembler gemacht hätte, hat auch der Compiler die beste Laufzeit.

cnt  = (cnt << 1) + cnt;   //  5 Zyklen

Hier mal die Übersicht:

cnt *=3;                   // 45 Zyklen
cnt  = (cnt << 1) + cnt;   //  5 Zyklen
cnt  = cnt + cnt + cnt;    // 57 Zyklen
cnt += (cnt + cnt);        // 56 Zyklen

Ich möchte halt vermeiden, dass der schlaue C-Compiler mir eine Multiplikation erzeugt.
Kann man das noch irgendwie steuern ?

Siro

Wie so oft macht der C-Compiler nicht das was da steht, er konzentriert sich nur auf das Ergebnis. Hier fehlt eigentlich eine Option: Bitte das so kodieren wie es dort steht. Natürlich ironisch gemeint....

[Klebwax]

Ein paar Sachen fallen mir dazu ein, die die Laufzeit bei einem 8-Bitter beeinflussen könnte.

Was für ein Typ ist cnt? Unsigned oder signed? Und welche Größe hat es? Char oder Int? Und zu guter letzt, ist cnt lokal oder global?

Wie so oft macht der C-Compiler nicht das was da steht, er konzentriert sich nur auf das Ergebnis. Hier fehlt eigentlich eine Option: Bitte das so kodieren wie es dort steht. Natürlich ironisch gemeint....

Alle von dir gezeigten Ausdrücke brauchen eigentlich eine zusätzliche temporäre Variable, da es mathematische Operationen mit 3 Operanden nicht gibt. Der Compiler erledigt das schon richtig, Seine Strategie mag da aber nicht so leicht zu erkennen sein. Lös das mal in mehrere Zeilen so auf, daß rechts nur eine Operation steht. Dann bleibt dem Compiler nichts anderes übrig, genau das zu tun, was du hinschreibst. So als Beispiel

   t = cnt + cnt;
   cnt = cnt + t;

MfG Klebwax

[Siro]

Hallo Klebwax,
ertsmal Danke für deine Info:

ich habe deinen Code ausprobiert.
Ich habe beide Variablen als "unsigned char" definiert. GLOBAL
ohne volatile klaut er den gesamten Code, völlig okay, weil er ihn ja nicht braucht
Er ruft schon bei der ersten Zeile ein Unterprogramm (Multiplier) auf.

33 Zyklen

volatile unsigned char t,cnt;

void main(void)
{
   t = cnt + cnt;   // hier ruft er wieder eine Multiplikation auf. 
   cnt = cnt + t;    
}

so macht er aber besseren Code ohne Multiplikation: 15 Zyklen

  t = cnt;
  t = t + cnt;
  cnt = t + cnt;

Ich hoffe, das hängt nicht mit der Lizenz zusammen, da ich ja nur die freie Version vom XC8 benutze...

[Klebwax]

Er ruft schon bei der ersten Zeile ein Unterprogramm (Multiplier) auf.

33 Zyklen

volatile unsigned char t,cnt;

void main(void)
{
   t = cnt + cnt;   // hier ruft er wieder eine Multiplikation auf. 
   cnt = cnt + t;    
}

Ist schon lustig, daß der Compiler in cnt + cnt 2*cnt erkennt. Ich hab anderes ähnliches gefunden: für t = 1 erzeugt er clear t und dann inc t.

so macht er aber besseren Code ohne Multiplikation: 15 Zyklen

  t = cnt;
  t = t + cnt;
  cnt = t + cnt;

Das wäre das, was ich in Assembler schreiben würde, wobei t dann der Akku wäre.

MfG Klebwax

[Siro]

Die Algorithmen sind teils schon lustig.
für dein Beispiel t=1 kann er alles direkt in den Registern abarbeiten. Er muss dazu keine Konstante (die 1) aus dem Speicher laden. So ist es bei einigen Prozessoren eventuell schneller.

Ein echtes "Steuern" für den Code scheint aber nicht direkt möglich zu sein, bzw. nicht sicher nachvollziehbar.
Am schnellsten geht es in diesem Falle (unsigned multiplikation mit 3) immer noch mit
cnt = (cnt << 1) + cnt;

mit signed geht das natürlich dann nicht mehr.

Siro

[HaWe]

moinmoin!
für cnt=3 geht das ntl mit 1x shiften und 1x addieren, aber für cnt >= 4 brauchst du ja wieder Zähler und/oder eine Fallunterscheidung ob cnt gerade oer ungerade.


Aber nur interessehalber,
was macht er per

for(int i=1; i<cnt;i++) t+=x;

[Siro]

Guten Morgen,
hab ich auch mal getestet:

for(i=0; i<3;i++) cnt+=cnt;      // 44 Zyklen, normaler Schleifencode, wenn i ein unsigned char ist

for(int i=0; i<3;i++) cnt+=cnt;  // 76 Zyklen, normaler Schleifencode, weil i ein int ist,

wobei mir grad auffällt, da kommt ja was anderes raus...

Siro

[HaWe]

Hatte mich vertippt
Ntl
... t+=x

cnt ist bei mir der Multiplikator

PS
Welche Compileroptimierungsstufe hast du?
Offenbar musst den Schleifenzähler wirklich auch global definieren

[Siro]

t=cnt; 
for(i=0; i<2;i++) cnt+=t;

hier benötigt er 34 Zyklen.

The current licence does not permit the selected optimization level, using level -O1

[HaWe]

Edit
Stimmt
Hatte mich vertan

cnt war bei mir der Multiplikator
x der Multiplikant
t das Ergebnis

Also anstelle
t=x*cnt
Alternativ:


int i, x, cnt;
t=x;
for( i=1; i<cnt;i++) t+=x;