itoa langsam

itoa der AVR-LibC steht bereits in asm und verwendet eine optimierte[tm] 
Division.

Ditto for utoa, ltoa und ultoa.

Oder meinst du eine andere libc?

Du kannst es weiter optimieren wenn du die Funktion nur für eine 
bestimmte Bases (radix) brauchst und dein µC multiplizieren kann.

Warum stört die Geschwindigkeit, ist doch eh nur für die Ausgabe. 
Humans are slooow devices.

Florian_unbekannto schrieb:
> Hi,
>
> nachdem ich jetzt das problem mit der Multiplikation gelöst habe,
> wolltre ich Fragen ob es einen asm Code für die itoa Funkrion gibt. Ich
> finde diese Funktion braucht recht lange. Warscheinlich wegen der
> Division. Gibt es da was effektivieres?

Sukzessive Subtraktion.
Das Prinzip ist einfache.
Wie oft kannst du 10000 subtrahieren, bis das Ergebnis unter 10000 
fällt? Das ist die Zahl die an die Zehntausenderstelle ausgegeben werden 
muss.

Mit dem Rest geht es dann weiter:
WIe oft kann 1000 subtrahiert werden?

usw. usw.

Das ganze wird speziell dann effektiv, wenn du den Zahlenbereich von 
vorne herein begrenzen kannst. Um zb Zahlen im Bereich bis 10000 
auszugeben, benötigt man nur 3 Stellen, entsprechend einfacher wird dann 
die Umwandlung

1

void deztoa( uint8_t number, char* ascii )

2

{

3

  uint8_t i;

4

5

  i = 0;

6

  while( number > 1000 )

7

  {

8

    i++;

9

    number -= 1000;

10

  }

11

  ascii[0] = i + '0';

12

13

  i = 0;

14

  while( number > 100 )

15

  {

16

    i++;

17

    number -= 100;

18

  }

19

  ascii[1] = i + '0';

20

21

  ascii[2] = number + '0';

22

23

  ascii[3] = '\0';

24

}

Im Prinzip kann man das natürlich auch mit größeren Zahlenbereichen 
machen, speziell wenn die ansonsten notwendigen Divisionen bei größeren 
Bitbreiten schon aufwändig werden.


Aber:
Ist das wirklich dein Bottleneck?
derartige Umwandlungen sind normalerweise nur notwendig, wenn es gilt 
für den Benutzer etwas wo hinzuschreiben. Ein Vorgang der aus Sicht des 
µC nur alle heiligen Zeiten notwendig ist und bei dem es ziemlich egal 
ist, wie lang er benötigt.

Hier ist übrigens die aktuelle Quelle. Wenn du das signifikant schneller 
hinbekommst gewinnst du nen Keks!

http://svn.savannah.nongnu.org/viewvc/trunk/avr-libc/libc/misc/utoa_ncheck.S?revision=2298&root=avr-libc&view=markup

Florian_unbekannto schrieb:
> ja, weil er das oft machen muss...dann addieren sich die 500 taktzyklen
> schon.

Ah geh.
Ist doch völlig uninteressant.
WIe oft in der Sekunde hast du denn den Fall, dass du eine Zahl wandeln 
musst? 3 mal - 4 mal?
Pro Sekunde 1500 Taktzyklen bei 10 Millionen zur Verfügung stehenden 
Taktzyklen - interessiert doch keinen wirklich. Am allerewenigsten den 
µC.



Du optimierst im Moment an Dingen rum, die du nicht optimieren musst. 
Vergeudete Zeit.
Kümmere dich lieber darum, dass der Rest deines Programmes sauber und 
wartbar ist. Da haben alle mehr davon.

@ Florian_unbekannto (Gast)

>nachdem ich jetzt das problem mit der Multiplikation gelöst habe,

Welches?

>wolltre ich Fragen ob es einen asm Code für die itoa Funkrion gibt.

Brauchst du den?

>Ich finde diese Funktion braucht recht lange.

Hast du es GEMESSEN? Im Simulator?

>Warscheinlich wegen der Division.

Die braucht hat etwas Zeit.

>Gibt es da was effektivieres?

Warum? Wieviel tausend Zahlen musst du pro Sekunde erzeugen? Wer soll 
die alle lesen? Wenn du nicht mehrere Megabyte an Textdatein mit Daten 
erzeugen willst, ist die Funktin für ein paar Ausgaben auf dem Terminal 
oder LCD mehr als schnell genug.

Johann L. schrieb:
> Hier ist übrigens die aktuelle Quelle. Wenn du das signifikant schneller
> hinbekommst gewinnst du nen Keks!
>
> 
http://svn.savannah.nongnu.org/viewvc/trunk/avr-libc/libc/misc/utoa_ncheck.S?revision=2298&root=avr-libc&view=markup


:-)
Ist genau die Subtraktionsmethode, die ich weiter oben angerissen habe.

Karl Heinz Buchegger schrieb:
> Um zb Zahlen im Bereich bis 10000
> auszugeben, benötigt man nur 3 Stellen

irgendwie blicke ich durch dein Beispiel nicht durch... 10000 sind für 
mich 4 Stellen. Und ich vermisse die 10er. Oder bin ich mal wieder mit 
Blindheit geschlagen?

Georg G. schrieb:
> Karl Heinz Buchegger schrieb:
>> Um zb Zahlen im Bereich bis 10000
>> auszugeben, benötigt man nur 3 Stellen
>
> irgendwie blicke ich durch dein Beispiel nicht durch... 10000 sind für
> mich 4 Stellen.

Ähm. Moment
(Finger rauskram)
Jep, du hast recht. Zu schnell getippt.

> Und ich vermisse die 10er. Oder bin ich mal wieder mit
> Blindheit geschlagen?

Auch hier: zu schnell getippt und auf senden gedrückt.

(OK, nimm den Code als Prinzipskizze mit 'kleinen' Fehlern)

Florian_unbekannto schrieb:
> ja gut, vielleicht habt ihr ja recht. Nur habe Angst dass ich nachher
> total überlastet mit(also der Xmega;-))...Die komplette ADC Wandlung
> benötigt 1500 Taktzyklen..

Was braucht da 1500 Taktzyklen?

> Und das mal vierzig oder so...

40 mal 1500 macht 60000, also 60 tausend.

Wie schnell taktet dein XMega?
Bei angenommenen 10Mhz und einem durchschnittlichen 
Befehl/Zyklenverhätlnis von sagen wir mal 1.5 (nicht alle Befehle 
brauchen 1 Taktzyklus), bedeutet das rund 100 Durchgänge pro Sekunde 
durch alle 40 ADC!

Kannst du wirklich so schnell schauen, dass du 40 Messerte die sich 100 
mal in der Sekunde ändern noch überblicken bzw. überwachen kannst?

Die integer-zu-BCD Wandlung muss man ja nur fuer den Benutzer machen, 
und der kann mehr als 3-4mal pro Sekunde gar nicht verarbeiten. Das 
waeren dann ein paar hundert zyklen.

Florian_unbekannto schrieb:
> Fettes Danke Karl Heinz!
>
> bin jetzt von 1550 Zyklen auf 300 runter! Sehr Geil.
>
> hatte folgendes 9.987.750 war mein ausgangswert. Das stand für 99,87
> Grad Celcius. Vorer musste ich durch 10000 teilen und dann itoa
> ausführen. Folge: 1550 Taktzyklen . mit dem Substrahieren geht es in 300
> mit super wenig Code!
>
> Da bekommt man 4000 Takte geschenkt, nur weil man einen besseren Algo
> hat. :-D

Da stimmt was nicht.
Das in itoa integrierte Verfahren unterscheidet sich nur marginal von 
dem in C ausprogrammierten. Einziger Unterschied: es ist von Hand in 
Assembler ausoptimiert worden. itoa bzw utoa müsste eigentlich schneller 
sein als die händische Version.

Florian_unbekannto schrieb:
> deshalb bin ich gezwungen erst zu dividieren.

niemand zwingt dich, du kannst auch itoa machen und das Komma 
entsprechend setzen

>

1

>  if( snumber < 0 ) {

2

>       ascii[0] = '-';

3

>       number = ( (unsigned)-(snumber+1) ) + 1; 

4

>     }

5

>   else { 

6

>       number = (uint32_t)snumber;

7

>     }

du trickst dich selber aus.

1

  if( snumber < 0 ) {

2

      ascii[0] = '-';

3

      number = -snumber;

4

    }

5

  else { 

6

      number = (uint32_t)snumber;

7

    }

kurze Zwischenfrage: was steht in ascii[0], wenn die Zahl nicht negativ 
ist?

Karl Heinz Buchegger schrieb:

> Da stimmt was nicht.
> Das in itoa integrierte Verfahren unterscheidet sich nur marginal
> von dem in C ausprogrammierten.

Schau dir die Verfahren nochmals an; sie unterscheiden sich deutlich!

Deine C-Variante beginnt mit der höchstwertigen Ziffer während itoa mit 
der kleinsten Ziffer beginnt und am Ende ein strrev macht.

Florian_unbekannto schrieb:
> while( number > 1000 )

Wenn du einen Wettbewerb im Takte sparen gewinnen möchtest, könntest du 
ab hier mit einer uint16_t weiter rechnen.

Johann L. schrieb:
>
> Schau dir die Verfahren nochmals an; sie unterscheiden sich deutlich!
>
> Deine C-Variante beginnt mit der höchstwertigen Ziffer während itoa mit
> der kleinsten Ziffer beginnt und am Ende ein strrev macht.

Nochmal nachgesehen.
Ja, da war der Schnellschuss zu schnell. Ich hab nur den sub gesehen und 
geschlossen. Da hat der TO schon recht. In diesem itoa wird ein 
Divisionsverfahren benutzt.

Zuerst sorry, dass ich diesen Thread vom letzten Jahr ausgrabe, aber das 
Thema ist nach wie vor aktuell.

Karl Heinz schrieb:
> Du optimierst im Moment an Dingen rum, die du nicht optimieren musst.
> Vergeudete Zeit.

Genau das Gleiche habe ich auch gedacht, als ich damals den Thread 
verfolgt hab.
Inzwischen ist mir aber selber ein solches Problem über den Weg 
gelaufen:
Messwerte sollen Terminal-lesbar in ASCII rausgeschleudert werden. Auf 
dem Terminal werden sie live mitverfolgt und geloggt. Es kommt also 
schon etwas auf die Geschwindigkeit an.

Nach einiger Optimiererei kam ich zu diesem Ergebnis:

1

#define UTOA(v,d) \

2

  /* returns a single ASCII digit of the number v */ \

3

  /* v: number (in) / remainder (out), */ \

4

  /* d: unsigned divisor (in, e.g. 100000U, 10000U...) */ \

5

  ( v<2U*d? (v<1U*d? '0': (v-= d, '1')): v<6U*d? (v<4U*d? \

6

    (v<3U*d? (v-= 2U*d, '2'): (v-= 3U*d, '3')): \

7

    (v<5U*d? (v-= 4U*d, '4'): (v-= 5U*d, '5')) ): \

8

  v<8U*d? (v<7U*d? (v-= 6U*d, '6'): (v-= 7U*d, '7')): \

9

  v<9U*d? (v-= 8U*d, '8'): (v-= 9U*d, '9') )

10

11

// Anwendungsbeispiel für eine 6-stellige Zahl:

12

uint32_t zahl= 123456;

13

char out[7];

14

out[0]= UTOA(zahl,100000U);

15

out[1]= UTOA(zahl,10000U);

16

out[2]= UTOA(zahl,1000U);

17

out[3]= UTOA(zahl,100U);

18

out[4]= UTOA(zahl,10U);

19

out[5]= UTOA(zahl,1U);

20

out[6]= 0;

21

// (Bitte beachten: am Ende hat die Variable zahl den Wert 0.)

Lässt sich daran noch etwas beschleunigen?
Den Tipp, unter 10000 auf eine uint16 umzusteigen werde ich sowieso noch 
berücksichtigen, danke an Josef.

Svenska schrieb:
> Wenn es lesbar sein muss, hexadezimal übertragen. Zweierpotenzen
> sind
> angenehmer.

Immer Nibbles shiften und maskieren, dann Nibble durch eine Lookuptable 
(oder ein ascii = x + 0x30; if(x>9) ascii += 16; müsste hinhauen).

Michael schrieb:
> Und hinter dem Terminal sitzt ein Mensch, der schon bei 10Hz Update-Rate
> mit den Augen rollt ...

Das kommt immer auf die Art der Anzeige an, nech. Ein Bewegtbild mit 10 
Hz ruckelt schon ordentlich und eine z.B. Abgleichsanzeige mit 1 Hz 
Aktualisierungsrate stelle ich mir auch eher uncool vor.

Markus Weber schrieb:
> Karl Heinz schrieb:
>> Du optimierst im Moment an Dingen rum, die du nicht optimieren musst.
>> Vergeudete Zeit.
>
> Genau das Gleiche habe ich auch gedacht, als ich damals den Thread
> verfolgt hab.
> Inzwischen ist mir aber selber ein solches Problem über den Weg
> gelaufen:
> Messwerte sollen Terminal-lesbar in ASCII rausgeschleudert werden. Auf
> dem Terminal werden sie live mitverfolgt und geloggt. Es kommt also
> schon etwas auf die Geschwindigkeit an.

Kann ich mir ehrlich gesagt überhaupt nicht vorstellen. Der UART ist 
doch schnarchlangsam im Vergleich zur CPU. Da kannst du eine 32-Bit Zahl 
doch dreimal nach ASCII konvertieren, bevor der UART auch nur ein 
Zeichen übertragen hat. Und warum hampelst du da so närrisch mit dem 
Makro herum? Paßt dir irgendwas an ultoa() nicht?


XL

pasteiner stefan schrieb:
> verwend doch einfach sprintf geht am einfachsten!

sprintf() zieht einen Rattenschwanz an Bibliotheksfunktionen hinter sich 
her. Das kann leicht ein paar KB Flash brauchen. Wenn man es auch 
anderswo verwendet, ist das kein Problem. Sonst ist u(l)toa() dem 
Problem eher angemessen.


XL