Eine Zeile Code, 2K flash

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Hallo,
ich gucke mir gerade mal den erzeugten Code für einen Bluetooth 
Bootloader an. Compile ist GCC 4.8.4. Target ist ein Cortex-M0 
(nrf51488). Folgende Zeile Code ist für 2 KByte des Binaries 
verantwortlich:

    delta_time delta_time::ppm( unsigned part ) const
    {
        return delta_time( std::uint64_t( usec_ ) * part / 1000000 );
    }

Wobei usec_ vom Typ std::uint32_t ist. Diese Zeile zieht 64 bit support 
für Muliplikation und Division aus der runtime libary an (__aeabi_lmul 
und __aeabi_uldivmod).

Wie würdet Ihr so etwas optimieren? Ich würde jetzt mal ganz naiv die 
Multiplikation und Division von Hand implementieren (erst C++, dann ggf. 
noch mal in Assembler).

mfg Torsten

[Stefan F. (Gast)]

Erstaunlich, ich bin gespannt, was des Rätsels Lösung ist.

Welchem Typ entspricht denn delta_time?

[Peter II (Gast)]

Torsten R. schrieb:
> Folgende Zeile Code ist für 2 KByte des Binaries
> verantwortlich:

einfach mal ins lss - File schauen.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Stefan U. schrieb:
> Erstaunlich, ich bin gespannt, was des Rätsels Lösung ist.
>
> Welchem Typ entspricht denn delta_time?

Hm, habe ich mich wohl wieder unklar ausgedrückt. Entschuldigt! Hier 
noch mal in einfacher:

std::uint32_t usec_ = ...;
const std::uint32_t r = std::uint64_t( usec_ ) * part / 1000000;

Der Code sieht völlig normal aus, es werden die Funktionen __aeabi_lmul
und __aeabi_uldivmod aufgerufen, welche zusammen allerdings 2K Byte groß 
sind. Auf diese 2K Byte würde ich gerne verzichten, bzw. diese 
reduzieren.

[2⁵ (Gast)]

Kannst du nicht usec_ bzw part vorher schon durch 10, 100 oder 1000 usw. 
teilen, damit du sicher innerhalb eines 32 bit ints bleibst? Oder wird 
es dann zu ungenau?

[Nop (Gast)]

Torsten R. schrieb:

> Wie würdet Ihr so etwas optimieren?

Ich würd erstmal in die Linker-Optionen schauen, ob ungenutzte 
Funktionen wirklich entfernt werden.

[2⁵ (Gast)]

div ist beim Coretx-M0 eh recht langsam. Kannst du nicht dein usec_ so 
definieren, dass es nicht auf 10^6 bezogen ist, sondern auf 2^20?. Dann 
kannst du z.B. sowas schreiben (usec_ / 1024) * (part / 1024). Der 
Compiler macht dann right shifts draus. Dazu müsste man halt wissen, wie 
groß in etwa usec_ oder part werden kann. Du kannst ja auch sowas 
machen: (usec_ / 256) * (part / 256) / 16.
Idee klar?

[Max G. (l0wside)]

Du dividierst durch eine Konstante. Wenn der Compiler es (auch mit 
Optimierung) nicht schafft, das durch eine Multiplikation + Rechtsshift 
zu ersetzen, musst du es eben von Hand tun. Wertebereiche beachten, aber 
in einem uint64 hat es eine Menge Platz.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Nop schrieb:
> Torsten R. schrieb:

> Ich würd erstmal in die Linker-Optionen schauen, ob ungenutzte
> Funktionen wirklich entfernt werden.

Ja, werden sie, sonst könnte ich den Unterschied ja nicht messen.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

2⁵ schrieb:
> div ist beim Coretx-M0 eh recht langsam. Kannst du nicht dein usec_ so
> definieren, dass es nicht auf 10^6 bezogen ist, sondern auf 2^20?.

Ne, dann wäre die ganze Fehlerrechnung ja schon von vorhinein kaput. 
Part kann Werte von 0 bis 1000 annehmen.

> Idee klar?

Ja, aber dann habe ich bereits einen Fehler von 2% in der Rechnung. Das 
Ergebnis wird direct in µs benötigt.

[2⁵ (Gast)]

Und direkt usec_ zu teilen? ich würde eine Abfrage machen: Wenn usec_ > 
2^32/1000 ist, wird usec_ erst durch 1000 geteilt und dann erst mit part 
mutipliziert, also sowas:

if (usec_ > (2^32/1000)) {
  return delta_time( (usec_ / 1000 ) * part / 1000 );
}
else {
  return delta_time( usec_ * part / 1000000 );
}

Dann musst du zwar 2x dividieren, aber sparst dir das 64 bit geraffel.
Die geringe Ungenauigkeit, wenn usec_ wirklich so groß ist, dürfte 
vernachlässigbar sein!

[2⁵ (Gast)]

2⁵ schrieb:
> 2^32/1000

Ist natürlich quatsch:4294967296/1000

[Rene K. (xdraconix)]

Selbst ein Blinky auf einem M0 belegt mitunter 2kb ;-) Das hat aber 
nichts mit dem Programm an sich zu tun, sondern mit der 
Speicherverwaltung und der Bereich in dem die Startadresse liegt. Da gab 
es hier schon einige Threads zu.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Rene K. schrieb:
> Selbst ein Blinky auf einem M0 belegt mitunter 2kb ;-) Das hat aber
> nichts mit dem Programm an sich zu tun, sondern mit der
> Speicherverwaltung und der Bereich in dem die Startadresse liegt. Da gab
> es hier schon einige Threads zu.

Ach Meno! Ich habe doch nicht geschrieben, dass ein "Blinky" 2k belegt. 
Sondern die zitierte Zeile Code. Wenn ich die z.B. durch:

return delta_time( 0 );

ersetze, dann verschwinden die beiden genannten Funktionen aus dem 
Binary und das Binary ist 2K kleiner.

[Rene K. (xdraconix)]

Torsten R. schrieb:
> Ach Meno! Ich habe doch nicht geschrieben, dass ein "Blinky" 2k belegt.
> Sondern die zitierte Zeile Code. Wenn ich die z.B. durch:
> return delta_time( 0 );
>
> ersetze, dann verschwinden die beiden genannten Funktionen aus dem
> Binary und das Binary ist 2K kleiner.

Ahhh... Okay. Das habe ich überlesen :-D Sorry.

[Stefan F. (Gast)]

Hast du die Linker-Option für die nano Version der newlib Library 
benutzt?
http://stefanfrings.de/stm32/index.html#newlib

[Max G. (l0wside)]

Nochmal zum Mitmeißeln: warum um alles in der Welt brauchst du die 
Division?

Multiplikation mit 168 und anschließender Rechtsshift um 24 Bit ergibt 
das gleiche Ergebnis (mit 0,15% Fehler). Und dürfte eher 20 Byte als 2k 
verbrauchen.
Wenn du es genauer brauchst, kannst du auch z.B. mit 10737 
multiplizieren und um 30 Bit nach rechts schieben. Restfehler dann 
irgendwo im Bereich 10^-5. Musst nur auf den Wertebereich aufpassen und 
Überläufe vermeiden.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Max G. schrieb:
> Nochmal zum Mitmeißeln: warum um alles in der Welt brauchst du die
> Division?

Weil ich hier durchaus im Bereich von 20ppm rechnen muss, da ist ein 
Fehler von 0,15% (150000ppm) zu groß.


> Wenn du es genauer brauchst, kannst du auch z.B. mit 10737
> multiplizieren und um 30 Bit nach rechts schieben. Restfehler dann
> irgendwo im Bereich 10^-5. Musst nur auf den Wertebereich aufpassen und
> Überläufe vermeiden.

Danke, guck ich mir mal an.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Torsten R. schrieb:
> Max G. schrieb:
>> Nochmal zum Mitmeißeln: warum um alles in der Welt brauchst du die
>> Division?
>
> Weil ich hier durchaus im Bereich von 20ppm rechnen muss, da ist ein
> Fehler von 0,15% (150000ppm) zu groß.

Das ist natürlich Blödsinn :-)

[2⁵ (Gast)]

Torsten R. schrieb:
> 20ppm

Hm... wenn du meine Methode nimmst, wäre der Fehler im Extremfall
(also bei usec_ = 4294967296/1000 (also usec > 4 Millionen!) und part = 
1 maximal 0,000999775 also ca. 1 Promill = 100 ppm. Wenn usec kleiner 
ist, dann sind die Fehler identisch mit der uint64_t Version. Was 
bleibt, sind die Divisionen durch 1000 bzw. 1000000. Die könnte man so 
approximieren: 
https://stackoverflow.com/questions/5558492/divide-by-10-using-bit-shifts

[Peter D. (peda)]

Die 2kB werden doch nur einmalig eingebunden. Danach kannst Du so oft 
rechnen, wie Du lustig bist.

Ich würde intern die CPU nur Timerticks zählen lassen und erst ganz zum 
Schluß für die Ausgabe an den Menschen in µs umrechnen.
Wobei ich mich frage, wozu ein Bootloader überhaupt super genau rechnen 
können muß.

[Amateur (Gast)]

An geschätzt 500 Stellen im Internet, kannst Du erfahren, wie man zu Fuß 
multipliziert und dividiert.

Die aktuellen Compiler binden nur das ein, was auch gebraucht wird. 
Allerdings gelegentlich auch gleich die kompletten Bibliotheken.

Schreib mal Testweise eine Zeile, die Fließkommaarithmetik enthält in 
Deinen Code. Da "fliegen" Dir die Kilobytes nur so um die Ohren. Oder 
benutze das Leckerli "fprintf ()" in Deinen Ausführungen.

Wie aber bereits schon gesagt: Wenn Du das Problem ohne große Arbeit 
lösen willst, könnten eventuell die Compileroptionen helfen.

[Wolfgang (Gast)]

Torsten R. schrieb:
> Weil ich hier durchaus im Bereich von 20ppm rechnen muss, da ist ein
> Fehler von 0,15% (150000ppm) zu groß.

Woher kennt dein Code den Quartzfehler?

0.15% sind übrigens 1500ppm. Deine Schätzung (?) liegt einen Faktor 100 
zu hoch.

[c-hater (Gast)]

Peter D. schrieb:

> Ich würde intern die CPU nur Timerticks zählen lassen und erst ganz zum
> Schluß für die Ausgabe an den Menschen in µs umrechnen.

Genau so und nicht anders würde das wohl jeder vernünftbegabte 
Programmierer machen.

Solange die Daten nur für interne Zwecke benötigt werden, muß man weder 
das Dualsystem verlassen noch ist man gezwungen, irgendwelche "runden" 
Einheiten zu verwenden, die sich irgendwie aus diesem und irgendwelchen 
nichtsnutzigen SI-Enheiten ergeben. Alles Bullshit.

Nur Menschen brauchen sowas. Und selbst da können noch >90% mit den 
meisten Einheiten und Vorsätzen des SI-System selbst dann überhaupt nix 
Nützliches anfangen, wenn der eigentlich Zahlenwert als Dezimalbruch 
serviert wird...

> Wobei ich mich frage, wozu ein Bootloader überhaupt super genau rechnen
> können muß.

Erstens das und zweitens: 20ppm? Das ist genauer, als die meisten Quarze 
real laufen und die Dinger sind ja in dieser Anwendung wohl ganz 
offensichtlich letztlich das Futter für die ganzen Rechnerei. Das ergibt 
irgendwie keinen Sinn.

[(º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· (Gast)]

Mann kann die Division durch 1000000 in eine ternaere Reihe entwickeln.
Hinweise finden sich bei der Suchmaschine des geringsten Misstrauens.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Peter D. schrieb:
> Die 2kB werden doch nur einmalig eingebunden. Danach kannst Du so oft
> rechnen, wie Du lustig bist.

Ja, das ist aber die einzige Stelle, an der die Funktionen verwendet 
werden. Und bei einem Bootloader kann man schon mal über 2k sinnieren.

> Wobei ich mich frage, wozu ein Bootloader überhaupt super genau rechnen
> können muß.

Das ist ein Bluetooth LE Bootloader und da werden Zeitfenster im ppm 
Bereich ausgerechnet, wann das Radio an und aus geschaltet werden muss.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

2⁵ schrieb:
> Torsten R. schrieb:
>> 20ppm
>
> Hm... wenn du meine Methode nimmst, wäre der Fehler im Extremfall
> (also bei usec_ = 4294967296/1000 (also usec > 4 Millionen!) und part =
> 1 maximal 0,000999775 also ca. 1 Promill = 100 ppm. Wenn usec kleiner
> ist, dann sind die Fehler identisch mit der uint64_t Version. Was
> bleibt, sind die Divisionen durch 1000 bzw. 1000000. Die könnte man so
> approximieren:
> https://stackoverflow.com/questions/5558492/divide-by-10-using-bit-shifts

Danke, ich werde mir das noch mal angucken und Tests machen.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Wolfgang schrieb:
> Torsten R. schrieb:
>> Weil ich hier durchaus im Bereich von 20ppm rechnen muss, da ist ein
>> Fehler von 0,15% (150000ppm) zu groß.
>
> Woher kennt dein Code den Quartzfehler?

Die Info über die eigene Hardware muss bein Übersetzen vorgegeben 
werden. Der Fehler der Gegenseite, liefert die Gegenseite beim 
Verbindungsaufbau mit.

> 0.15% sind übrigens 1500ppm. Deine Schätzung (?) liegt einen Faktor 100
> zu hoch.

Danke.

[Patrick J. (ho-bit-hun-ter)]

Hi

Amateur schrieb:
> An geschätzt 500 Stellen im Internet, kannst Du erfahren, wie man zu Fuß
> multipliziert und dividiert.

Mit etwas Gehirnschmalz selber auf die benötigte Bitbreite erweiterbar:
http://www.avr-projekte.de/rechnen.htm
Allerdings AVR und Assembler, der Rechenweg dahinter sollte erkennbar 
sein - zur Not in der Beschreibung (Deutsch).

MfG

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

c-hater schrieb:

> Erstens das und zweitens: 20ppm? Das ist genauer, als die meisten Quarze
> real laufen und die Dinger sind ja in dieser Anwendung wohl ganz
> offensichtlich letztlich das Futter für die ganzen Rechnerei. Das ergibt
> irgendwie keinen Sinn.

Das ist das, was Bluetooth als genauste Klasse definiert. Ob es Sinn 
ergibt, oder nicht, ist mir an der Stelle egal. Selbst wenn heute selten 
so genaue Tacktgeber verbaut werden, wäre es ja toll, wenn die Library 
auch in 10 Jahren noch vernünftig funktioniert.

[Georg (Gast)]

(º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· schrieb im Beitrag 
#5096474:
> Mann kann die Division durch 1000000 in eine ternaere Reihe entwickeln.

Wieso eigentlich? Wenn man schreibt

return delta_time( std::uint64_t( usec_ )  part  0,000001 );

braucht man keine Division.

Oder ist das einfach zu einfach?

Georg

[Georg (Gast)]

Georg schrieb:
> Wieso eigentlich? Wenn man schreibt
>
> return delta_time( std::uint64_t( usec_ )  part  0,000001 );

Da klaut jemand die Mal-Zeichen (finde ich nicht nett), also

[code]
return delta_time( std::uint64_t( usec_ )  part  0,000001 );
[/code)

Georg

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Patrick J. schrieb:
> Hi
>
> Amateur schrieb:
>> An geschätzt 500 Stellen im Internet, kannst Du erfahren, wie man zu Fuß
>> multipliziert und dividiert.
>
> Mit etwas Gehirnschmalz selber auf die benötigte Bitbreite erweiterbar:
> http://www.avr-projekte.de/rechnen.htm
> Allerdings AVR und Assembler, der Rechenweg dahinter sollte erkennbar
> sein - zur Not in der Beschreibung (Deutsch).

Danke, aber Assembler wollte ich vermeiden. Ich denke die Ideen von 2^5 
und Max werden zum Erfolg führen.

Für mich erstaunlich war, dass die Multiplikation eigentlich kaum code 
benötigt, sondern dass die 2k im wesentlichen die Division ist.

[Georg (Gast)]

Georg schrieb:
> Wieso eigentlich? Wenn man schreibt
>
> return delta_time( std::uint64_t( usec_ )  part  0,000001 );

Da klaut jemand die Mal-Zeichen (finde ich nicht nett), also

return delta_time( std::uint64_t( usec_ ) * part * 0,000001 );

Georg

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Georg schrieb:
> (º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· schrieb im Beitrag
> #5096474:
>> Mann kann die Division durch 1000000 in eine ternaere Reihe entwickeln.
>
> Wieso eigentlich? Wenn man schreibt
>
> return delta_time( std::uint64_t( usec_ )  part  0,000001 );

Du meinst wahrscheinlich ... * 0.000001 ?

> braucht man keine Division.

Dann braucht mal floating point support und der ist noch viel teurer.

[(º°)·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.· (Gast)]

Mit einer Multiplikation mit 1/1000000 hat eine ternaere
Reihenentwicklung nichts zu tun.

[Helfer (Gast)]

Hast du die Optimierung des Compilers eingeschaltet? Wenn ja auf welche 
Optimierung?

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Helfer schrieb:
> Hast du die Optimierung des Compilers eingeschaltet? Wenn ja auf welche
> Optimierung?

Ja, -Os

[Jim M. (turboj)]

Torsten R. schrieb:
> Target ist ein Cortex-M0
> (nrf51488).

Der hat konstante 16MHz Takt. Wieso rechnest Du da so kompliziert? Eine 
µs sind genau 16 Takte.

Außerdem stören da die 2KB überhaupt nicht, der Chip hat 256KB Flash. 
Selbst mit Softdevice bleiben IIRC 128KB frei.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Jim M. schrieb:

> Der hat konstante 16MHz Takt. Wieso rechnest Du da so kompliziert? Eine
> µs sind genau 16 Takte.

Ja, aber ich muss z.T. wissen, was z.B. 40ppm von 1,25s sind.

> Außerdem stören da die 2KB überhaupt nicht, der Chip hat 256KB Flash.
> Selbst mit Softdevice bleiben IIRC 128KB frei.

Mich stören sie. Und bei einem Bootloader, der ansonsten 19k groß ist, 
sind 2k schon eine Menge. Der Bluetooth-Stack ist ausserdem Teil des 
Bootloaders, deswegen brauche ich ja die obige Berechnung.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Ich bin jetzt noch mal die Spec durch gegangen und habe geguckt, in 
welchem Bereich meine Parameter liegen und habe dann die Idee von 2^5 
umgesetzt:

return delta_time( ( std::uint64_t( usec_ ) * part * 140737488 ) >> 47 );

Größe des Binaries: 17604

Zum Vergleich vorher:

return delta_time( std::uint64_t( usec_ ) * part / 1000000 );

Größe des Binaries: 19684

Der Absolute Fehler über den geammten Bereich ist nun 1(µs).

Schönen Dank an alle!