C18 Multikplikation geht auch um Vielfaches schneller

[Christoph M. (chrito)]

Moin moin!

Mir geht nicht in den Schädel, was die Entwickler von C18 sich da 
gedacht haben:
Wenn ich eine Multiplikation à la

unsigned char A, B;     // 8-Bit-Variable
unsigned int Ergebnis;  // 16-Bit-Variable

Ergebnis = A*B;

schreibe, dann macht er in Assembler auf einem Pic18F eine 8x8=16Bit 
Multiplikation, verwirft jedoch die oberen 8Bit und übergibt an Ergebnis 
nur die unteren 8Bit. Beispiel: 20*20 ist dann nicht 400, sondern 144, 
in dem Hardware-Ergebnis-Register des Multiplizierers (nämlich 
PRODH:PRODL) ist aber das korrekte obere Byte drin!!! Das kann man dann 
auch benutzen, klaro.

Aber wieso haben die das so gemacht??? Der Code wird falsch ausgeführt, 
der Controller baut aber das korrekte Ergebnis.

Und: Gleiches Spiel für die "größeren" Multiplikationen, also z.B. 
32Bit=16x16Bit, de facto macht das Ding diese Operation, gibt aber nur 
16 Bit zurück und die oberen beiden sind dann in AARGB2:AARGB1.

Viele programmieren dann 16bit=16x16, weil sie's nicht wissen oder 
merken, und intern werden dann 32Bit erzeugt (was überflüssig ist). 
16=8x8 wäre dann außreichend und um Welten schneller (kein call, kein 
doppeltes mulf, kein Addieren). Typcasting bring übrigens keine 
Unterschiede.

Was haben die sich dabei gedacht und wie geht man damit elegant um?
100 Gummipunkte für den mit der besten Antwort!
Beste Grüße,
Christoph

[Marcus O. (marcus6100)]

Das ist bedingt durch den C Standard. Am besten baust du dir eine 
assembler inline Funktion wenn du diese multiplikation häufig brauchst. 
Was ist eigentlich C18...

uint16_t mul8x8(uint8_t a, uint8_t b)

[Christoph M. (chrito)]

ah ok...
Aber würde es nicht ebenfalls dem C-Standard entsprechen, wenn der 
Controller intern 8x8 = 16 Bit rechnet, nach außen ist das doch 
dasselbe?!

An inline assembler hab ich auch schon gedacht. Es macht Sinn, das Ganze 
grundsätzlich anders zu lösen, weil man dadurch keine Nachteile hat und 
das Programm schneller wird und weniger Flash benötigt.

C18 ist ein C-Compiler für 18F- Controller.

Grüße

[Klaus D. (kolisson)]

.. und was ist nun C18 ?

k.

[chrito (Gast)]

Huhu!
Hab ne Lösung :-)
Is für den ein oder anderen sicherlich nützlich...

1. Möglichkeit: mit Struct

Ergebnis.Byte[1]=a*b;  
Ergebnis.Byte[0] = PRODH;

... benötigt 11 Takte (schneller geht es quasi nicht), aber man muss den 
struct definieren.

2. Möglichkeit: Teile zusammenpappen

  a*b;
  Ergebnis= ((unsigned int) PRODH<<8) | PRODL;

... benötigt 22 Takte, geht immer

3. Möglichkeit: Type-Casting! (geht doch, man muss nur wissen wie)

  a*b;
  Ergebnis= * (unsigned int * ) &PRODL;

... nur 12 Takte! und geht immer :-)

zur Info: Die Standard-Multiplikation 16=16x16Bit dauert 56 Takte, das 
hier ist 16=8x8Bit

bin neugierig auf Kommentare!
Grüße!

[Martin S. (drunkenmunky)]

Hi,

hab's grad mal selber ausprobiert.

So funktioniert es korrekt:

Ergebnis = (unsigned int)A * B;

Kannst ja mal schauen, wie lang diese Anweisung benötigt.

Bin mir jetzt nur nicht sicher, ob das ein Bug ist oder nicht. Würde 
eigentlich schon Sinn machen, wenn man bei einer Multiplikation von zwei 
8-bit breiten Zahlen ein 16-bit Ergebnis verwenden würde.

Vielleicht weiß ja jemand, ob das dem C-Standard entspricht und was es 
für einen Grund hat.

[Martin S. (drunkenmunky)]

Habe gerade noch was dazu gefunden:
http://www.microchip.com/forums/tm.aspx?m=350252&high=multiplication

Du kannst in der Compiler Options die Option "Enable Integer Promotions" 
einschalten, dann macht er es immer automatisch.

Scheint also schon korrekt so zu sein...

[Meister E. (edson)]

Klaus De lisson schrieb:
> .. und was ist nun C18 ?

Er meint damit den MCC18, ein proprietärer ANSI-C89 konformer C-Compiler 
von Microchip.

Gruß,
Edson

[Christoph M. (chrito)]

Martin S. schrieb:
> Hi,
>
> hab's grad mal selber ausprobiert.
>
> So funktioniert es korrekt:Ergebnis = (unsigned int)A * B;
>
> Kannst ja mal schauen, wie lang diese Anweisung benötigt.

Hallo Martin!
wenn du

 Ergebnis= (unsigned int) A * B;  // * Variante 1 *

 machst, dann erzeugt er intern ein 32Bit-Ergebnis und verwirft die 
oberen 16! Also total überflüssig und von der Performance her mieß. 
Genau das meinte ich ja...
Und wenn du halt

a*b;
  Ergebnis= * (unsigned int * ) &PRODL;  // * Variante 2 *

machst, dann führt er tatsächlich 16Bit=8x8Bit aus und gibt dir die 
korrekten 16 Bit zurück.
Oben hatte ich bereits geschrieben: Variante 1 benötigt 56 Takte, 
Variante 2 nur 11 Takte. Und typischerweise probiert man erst mal 
Variante 1, weil 2 halt etwas kryptisch ist und man erst mal kappieren 
muss, was da effektiv passiert.

Ihr könnt euch das gut anschauen, wenn ihr auf "View=>Disassembly 
Listing" klickt und mit "Strg+F" nach eurem C-Code sucht, dessen 
Assembler-Äquivalent ihr sehen wollt.
Viele Grüße,
Christoph

[(prx) A. K. (prx)]

Christoph M. schrieb:

> Aber wieso haben die das so gemacht??? Der Code wird falsch ausgeführt,
> der Controller baut aber das korrekte Ergebnis.

Wie von Martin schon angerissen wurde verhalten sich manche Compiler für 
8-Bit Mikrocontroller je nach Einstellung nicht regelkonform. Eine der 
fundamentalen C Regeln für Arithmetik, nämlich die implizite Annahme von 
Rechnung mindestens in "int", ist bei den 8-Bit PICs mitunter recht 
schmerzhaft.

Folglich wird in einer der Einstellungsvarianten die integer promotion 
auch dann unterlassen, wenn in einer reinen 8-Bit Rechnung ein formal 
falsches Ergebnis herauskommt. Und das wird dann konsequent 
durchgezogen, d.h. eine Rechnung mit 8-Bit Operanden hat verlässlich ein 
8-Bit Ergebnis.

Und genau dieser Aspekt greift hier. a*b mit 8-Bit Operanden hat ein 
8-Bit Ergebnis und (unsigned)a * b hat aufgrund der erzwungenen 
Konvertierung ein 16-Bit Ergebnis.

[Christoph M. (chrito)]

Hallo AK!
Ja, stimmt genau, was du da schreibst. Der Compiler verhält sich 
"konsequent" und Regelkonform, bleibt bei 8 Bit. Aber wenn ihr euch den 
Assebler mal anseht, den C18 erzeugt, dann seht ihr auch, dass intern 
die oberen 8 Bit vorhanden ausgerechnet werden (oder bei H16:L16=A16*B16 
die oberen 16). Das könnte sich der Compiler auch knicken, und er wäre 
trotzdem noch C-konform, man würde nach außen keinen Unterschied merken!

Also Leute, das hier funktioniert wirlich und benötigt nur 11 Takte, der 
Code wird unwesentlich länger:

unsigned char a, b;
unsigned int Ergebnis;
a*b;                // Hardware-Multiplizierer erzeugt 16 Bit-Ergebnis
Ergebnis= * (unsigned int * ) &PRODL;      // hole dir alle 16 Bit

aber es schreibt sich nich so gut und auch nicht in einer Zeile mit 
anderen Operationen.

Und Martin, du meintest integer promotion wäre vielleicht eine 
Möglichkeit... ich hab's mir mal angeschaut, und die schreiben, dass 
damit aus

unsigned char a, b;
unsigned int Ergebnis;
Ergebnis=a*b;

auch wieder eine 32=16*16 Bit Multiplikation (also 56 Takte) wird. :-(

Hab ihr das hier gelesen: 
http://www.microchip.com/forums/m3727-print.aspx
Der Typ hier hatte das gleiche Problem, der Microchip-Mensch rät ihm 
dazu, inline Assembly zu verwenden:

Inline Assembly ist aber irgendwie nicht mehr so ohne, sobald sich in 
Funktionsaufrufen mit dynamischen Variablen befindet... das hieße, ich 
müsste meine "Ergebnis, A, B" statisch anlegen, wäre hier also 
eingeschränkt. Deshalb halte ich den C-Code oben für besser. Oder halt 
die Variante mit dem struct. :-)

[(prx) A. K. (prx)]

Christoph M. schrieb:

> Ja, stimmt genau, was du da schreibst. Der Compiler verhält sich
> "konsequent" und Regelkonform, bleibt bei 8 Bit.

Genau das ist nicht regelkonform. Korrekterweise müsste er ein Produkt 
mit vollen 16 Bits abliefern. Dummerweise betreibst du den Compiler aber 
in einem nicht regelkonformen Modus, in dem er unter Verletzung des C 
Standards konsequent mit 8-Bit Rechnung arbeitet. Und damit das nicht 
vom Wasserstand abhängt, sondern leicht nachvollziehbar ist, tut er es 
auch bei der Multiplikation.

Wenn er bei eingeschalteten integer promotions mit einer 16x16=32-Bit 
Multiplikation arbeitet, dann ist das zwar ineffizient, aber 
regelkonform. Beschwerden über fehlende Optimierung sind an Microchip zu 
richten - der Compiler könnte erkennen, dass er hier mit 8x8=16-Bit 
Rechnung arbeiten kann, tut es offenbar aber nicht. Das ist Pech.

[chrito (Gast)]

Hier ist der Assembler, der bei Variante 1 (Ergebnis= (unsigned int) 
a*b;)

    MOVFF  __AARGB1,__TEMPB1

    MOVF  __AARGB1,W
    MULWF  __BARGB1
    MOVFF  PRODH,__AARGB2
    MOVFF  PRODL,__AARGB3

    MOVF  __AARGB0,W
    MULWF  __BARGB0
    MOVFF  PRODH,__AARGB0
    MOVFF  PRODL,__AARGB1

    MULWF  __BARGB1
    MOVF  PRODL,W
    ADDWF  __AARGB2,F
    MOVF  PRODH,W
    ADDWFC  __AARGB1,F
    CLRF  WREG
    ADDWFC  __AARGB0,F

    MOVF  __TEMPB1,W
    MULWF  __BARGB0
    MOVF  PRODL,W
    ADDWF  __AARGB2,F
    MOVF  PRODH,W
    ADDWFC  __AARGB1,F
    CLRF  WREG
    ADDWFC  __AARGB0,F

    RETLW  0x00


und Variante 2 (Ergebnis=a*b)
  MOVF  __BARGB0,W
  MULWF  __AARGB0
  MOVFF  PRODH,__AARGB0
  MOVFF  PRODL,__AARGB1
  RETLW  0x00


ausgeführt wird. Die Variablenübergabe und der Call-Einsprung fehlen bei 
Variante 1, Variante 2 bindet der Compiler wie ein Makro in den Code 
ein. Gut zu sehen ist, das er auch bei Variante 2 das obere Byte "PRODH" 
zur Verfügung stellt, es nach __AARGB1 verschiebt. In "Ergebnis".landet 
aber nur "PRODL".
Kann einer von euch so gut inline assembler, dass er ein Makro bauen 
kann, das beide Bytes zurück gibt? Am besten etwas, das auch mit 
dynamischen Variablen (innerhalb einer Funktion definierten) läuft...
Grüße

[Christoph M. (chrito)]

A. K. schrieb:
> - der Compiler könnte erkennen, dass er hier mit 8x8=16-Bit
> Rechnung arbeiten kann, tut es offenbar aber nicht. Das ist Pech.

Genau das meine ich :-)  Und da greift halt die Idee von oben...

[Martin S. (drunkenmunky)]

Hast du eigentlich die kostenlose Lite-Version? Oder welche sonst?

[Christoph M. (chrito)]

ja, die ohne Optimierung
... macht er wohlmöglich anders, wenn man Optimierung einschalten kann?!

[Christoph M. (chrito)]

Hallo Martin, hallo Forum!

Also das mit der Optimierung hab ich jetzt auch überprüft, bringt 
nichts. Ist aber auch logisch, weil er ja quasi ne andere Funktion 
aufruft, und das ändert sich durch Optimierung nicht.

Ich fasse noch einmal für euch zusammen:
Es geht um den C18-Compiler und 8-Bit Controller à la 18FXXXX. Für 
16=8*8Bit (int=char*char) und für 32=16*16Bit (long=int*int) empfehle 
ich euch die Variante mit Typecasting wie unten im Beispiel-Code. Die 
Multiplikation ist ungefähr vier Mal so schnell und benötigt weniger 
ROM. Besser geht's auch mit Assembler nicht :-)

Würd mich mal interessieren, ob es ähnliche Probleme auch bei 
Multiplikationen auf 8Bit-Atmels gibt oder ob das dort eleganter 
abläuft.

 unsigned char a8, b8;
 unsigned int a16, b16;
 unsigned int Ergebnis16;
 unsigned long Ergebnis32;

 a8=30;
 b8=40;
 a16=300;
 b16=400;

 // Multiplikation 16Bit = 8Bit * 8Bit
 Ergebnis16=a8*b8;          // erzeugt falsches Ergebnis: nur unteres Byte wird übergeben, 7 Takte
 Ergebnis16= (unsigned int) a8*b8;  // erzeugt richtiges Ergebnis, führt jedoch intern 32Bit=16*16Bit aus, deswegen 56 Takte
 a8*b8; Ergebnis16=*(unsigned int *) &PRODL;  // erzeugt richtiges Ergebnis, 11 Takte

 // Multiplikation 32Bit = 16Bit * 16Bit
 Ergebnis32=a16*b16;          // erzeugt falsches Ergebnis: nur unteres zwei Byte werden übergeben, 56 Takte
 Ergebnis32= (unsigned long) a16*b16;  // erzeugt richtiges Ergebnis, führt jedoch intern 64Bit=32*32Bit aus, viele viele Takte
 a16*b16; Ergebnis32=*(unsigned long *) &__AARGB3;  // erzeugt richtiges Ergebnis, 56 Takte

Viele Grüße euch allen!
Christoph