Hi,
ich habe hier eine simple Bitzählroutine, die mir ermittelt, wie viele
1er Bits in einem Wert vorkommen und diese dann mit einem
Paritäts-Zähler vergleicht:
vx und vy sind dabei 22-Bit-Zahlenwerte. In den oberen 20 Bits wird
gezählt, wie viele Einsen darin vorkommen und das Ergebnis wird mit dem
in den unteren zwei Bits stehenden Zahlenwert verglichen (da natürlich
nur die unteren 2 Bit/max. 3 Werte, alles was darüber hinausgeht, wird
ignoriert, da nicht angenommen wird, dass mehr als 3 Bits gleichzeitig
kippen).
Mein Problem: dafür, dass diese Funktion so simpel ist, ist sie auf
einem mit 120 MHz getakteten ATSAMD unglaublich langsam und haut mir
mein ganzes Timing durcheinander.
Meine Frage jetzt: wie kann man das optimieren? Gibt es vielleicht eine
Funktion, mit der man die CPU die Bits zählen lassen kann, so dass ich
mir diese Schleife sparen kann?
Danke!
Harstad schrieb:> ist sie auf> einem mit 120 MHz getakteten ATSAMD unglaublich langsam
Wie langsam ist denn "unglaublich"?
Hab gerade meine Formelsammlung mit den Konstantendefinitionen
nicht greifbar.
ooops schrieb:> Harstad schrieb:>> ist sie auf>> einem mit 120 MHz getakteten ATSAMD unglaublich langsam>> Wie langsam ist denn "unglaublich"?>> Hab gerade meine Formelsammlung mit den Konstantendefinitionen> nicht greifbar.
So langsam, dass es für meine Belange zu langsam ist. Für die
Fragestellung ist diese Information übrigens komplett unwichtig,
schließlich möchte ich wissen, wie man das optimieren kann und nicht, ob
der Prozessor richtig arbeitet.
Schau mal nach ,,Brian Kernighan Algorithm" zum Bit-Zählen!
ich zitiere:
>We calculate n-1>We and it with n i.e n&(n-1)>Thus unset the rightmost bit>Keep repeating the above steps until we end up with 0
hmmm schrieb:> Ich schmeiß mal __builtin_popcount in die Runde - keine Ahnung, was das> beim ATSAMD ergibt...
Ergibt mit -mcpu=cortex-m0 -mthumb das hier:
Ich würde mir für ein nibble (Werte 0 bis 15) ein Konstantes Array als
Lookup-Tabelle machen. Dann hast du nur noch ein Viertel der
Iterationen. Kannst das ganze auch auf ein ganzes Byte hochziehen, dann
hätte deine Lookuptabelle 256 Einträge (mehr Speicher, mehr
Geschwindigkeit) Die Tabelle würde ich global definieren, damit sie
nicht jedes mal auf den Stack geschaufelt wird.
Vom Prinizp her:
Harstad schrieb:> Mein Problem: dafür, dass diese Funktion so simpel ist, ist sie auf> einem mit 120 MHz getakteten ATSAMD unglaublich langsam und haut mir> mein ganzes Timing durcheinander.
Ich habe das gerade mal ausprobiert auf einem ATSAME51J19A der auf
120MHz läuft, also bis auf das der zusätzlich CAN hat der gleiche
Controller.
Ich messe die Ausführungsgeschwindigkeit der Funktion mit einem Timer
der auf dem internen RC-Oscillator läuft mit TC_CTRLA_PRESCALER_DIV2,
also 24 MHz.
...
num_profile_a = parityOK(val_a, val_b);
...
val_a+=23;
val_b+=47;
val_a &= 0x0002ffffd;
val_b &= 0x0002ffffd;
Ein bisschen "Chaos" rein gefüttert damit das nicht weg optimiert wird.
Das "num_profile_a" ist in dem Zusammenhang einfach nur eine Variable
die woanders auch noch benutzt und demnach nicht weg optimiert wird.
Die Funktion habe ich einfach so übernommen, das führt zu der Warnung:
"warning: always_inline function might not be inlinable [-Wattributes]"
Wie auch immer, das Ergebnis sind konstante 49 Timer-Ticks, oder auch
2µs.
Oder auch 240 Taktzyklen bezogen auf die 120MHz Core-Takt.
Zu langsam mag ja gut sein, aber ist "unglaublich langsam" nicht doch
ein klein wenig übertrieben?
Du bist Dir aber sicher, das nicht irgendein IRQ da reingrätscht?
Wackel mal mit einem PIN in Deiner Schleife und seh Dir an wie konstant
und wie lange der überhaupt darin herumwerkelt.
Ist überhaupt sichergestellt das diese Routine mit höchster Prio läuft
und andere Prozesse unterbrechen kann?
Harstad schrieb:> So langsam, dass es für meine Belange zu langsam ist.
Das ist keine Aussage.
Wie langsam und wie sind Deine Belange?
Schau Dir an was der Compiler daraus macht und zähl die Takte.
Ggf. ist das Softwaremäßig garnicht zu lösen.
Wir wissen ja nicht wohl Du hinwillst mit dem Timing und was der
Rechenknecht noch alles tun muss.
M. K. schrieb:> Schau Dir an was der Compiler daraus macht> und zähl die Takte.
Nicht notwendig.
Er behandelt jedes Bit einzeln, d.h. es gibt
20 Durchläufe mit etwa 3 Befehlen je Durchlauf.
Vergleiche das mit Jörgs Assemblertext: Der
braucht 20 Befehle .
Egon D. schrieb:> Vergleiche das mit Jörgs Assemblertext
Nicht meiner, sondern der der libgcc. ;-) (Die wird hinter dem genannten
__builtin_popcount() vom Compiler aufgerufen.)
Jörg W. schrieb:> Ergibt mit -mcpu=cortex-m0 -mthumb das hier:
Gerade erst gesehen, der Controller ist aber ein M4F.
Das kommt dabei raus wenn man nur "SAMD" schreibt und nicht die Nummer
dazu.
Jörg W. schrieb:> Egon D. schrieb:>> Vergleiche das mit Jörgs Assemblertext>> Nicht meiner, sondern der der libgcc. ;-)
Ich weiss.
Du bist halt der Überbringer der Nachricht,
nicht der Verfasser :)
Die Routine ist übrigens ziemlich hoch optimiert;
besonders das Umschwenken auf die Addition der
8Bit-Gruppen am Ende finde ich elegant, das spart
nochmal ein paar Befehle.
Rudolph R. schrieb:> Jörg W. schrieb:>> Ergibt mit -mcpu=cortex-m0 -mthumb das hier:>> Gerade erst gesehen, der Controller ist aber ein M4F.> Das kommt dabei raus wenn man nur "SAMD" schreibt und nicht die Nummer> dazu.
OK, hier nochmal mit -mcpu=cortex-m4 -mthumb. Wird kürzer. :)
Egon D. schrieb:> Die Routine ist übrigens ziemlich hoch optimiert;
Dafür ist es ja auch gut, wenn man für solcherlei Dinge Informatiker
hat, die einem das als Library zur Verfügung stellen.
Der oben gegebene Hinweis auf __builtin_popcount() war daher m.E. der
wirklich zielführendste im Thread.
(Zu Hause steht noch irgendwo das Buch "Hacker's Delight" rum, da sind
solche Algorithmen für Standardaufgaben erklärt. Hatte ich vorhin nicht
zur Hand.)
Thread beobachten
Seitenaufteilung abschalten