Forum: Mikrocontroller und Digitale Elektronik Ringbuffer in C optimieren?


von Be B. (bebo)


Lesenswert?

Hallo,

mich würde mal interessieren, wie man in C am besten das Umbrechen des 
Adresszeigers auf den Anfang realiesiert (Pointer ist 32 groß).

In Assembler auf einem 8-Bitter habe ich meißt einen Buffer von 256 
Bytes Größe auf Adressen wie 0x200, 0x300, 0x400,... gelegt. Dann habe 
ich nur das Low-Byte incrementiert. Auf diese Weise brauchte ich mich 
garnicht darum kümmern, daß der Pointer nach 0x2FF auf 0x200 springt, 
daß hat schon die Beschränkung auf 8 Bit in Verbindung mit der fixen 
Adresse, die durch 256 teilbar war, erledigt.

Wie aber mache ich sowas nun in C (Microchip C32), ohne Konstruktionen 
wie:
1
if (ptr>Buffer+BufferSize) ptr = Buffer;
zu verwenden?
Wobei ich mich mit der Frage mal auf Buffergrößen beschränken möchte, 
die eine Optimierung zulassen, wie in dem Assemblerbeispiel genannt.

von Karl H. (kbuchegg)


Lesenswert?

In C ist so etwas schwieriger :-)

Viele C-Compiler können auch hier Variablen an bestimmte 
Speicheradressen schieben. Das hängt aber vom Compiler ab, ob das geht. 
Eine andere Möglichkeit wäre es, gar keine 'Variable' in dem Sinne zu 
benutzen sondern sich einfach nur einen Pointer auf zb 0x200 zu 
konstruieren und dem Linker mitzuteilen, dass diese Speicherbereich von 
ihm nicht benutzt werden kann.

Aber gesetzt dem Fall, du kriegst das hin: Du hast einen Pointer auf 
0x200 und der dortige Speicher steht auch zu deiner Verfügung. Dann hast 
du noch das Problem, dass du eigentlich nur das Low-Byte des Pointers 
inkrementieren willst. Das geht erst mal so gar nicht, denn eines der 
Grundprinzipien von C (eigentlich allen höheren Programmiersprachen) ist 
es ja, dass diese Aufteilung eines Datentyps auf maschinenspezifische 
Bytes vor dir verborgen beliben soll. Das bringt Komfort, ist aber in 
deinem Ausnahmefall natürlich kontraproduktiv. Aber wie so oft in C: 
Wenn man will gibt es auch einen Weg. Und oft genug führt der Weg über 
Casts, mit denen man den Compiler zwingen kann etwas zu tun, was 
eigentlich gegen jede Regel ist.
Du castest dir einen Pointer auf den Buffer-Pointer zurecht, so dass du 
einen unsigned char Pointer auf das Low-Byte des Buffer Pointers hast. 
Dann kannst du über diesen Hilfspointer das Low-byte des Buffer Pointers 
inkrementieren. Es wird sicherlich auch noch andere Möglichkeiten geben. 
Zb könnte man den Pointer in einer union mit einem byte Array überlagern 
und den Inkrement über das richtige Byte im Array regeln. Man könnte 
auch den Compiler mit einem Cast davon überzeugen, dass der Pointer in 
Wirklichkeit ein Array von 4 Bytes ist, und du das 0-te (oder 3-te je 
nach Endianess) inkrementieren willst.

So weit so gut.
Jetzt sollten wir uns mal die Gretchenfrage stellen:
Hast du mit einem Profiler kontrolliert, ob dein Bottleneck wirklich 
beim
1
   ptr++;
2
   if (ptr>Buffer+BufferSize)
3
     ptr = Buffer;
sitzt. Die Addition könnte man leicht mit einem 2-ten Zeiger auf das 
Bufferende loswerden, so dass eigentlich nur noch ein Vergleich und 
eventuell eine Zuweisung übrig bleibt
1
   ptr++;
2
   if (ptr > BufferEnde)
3
     ptr = BufferStart;

Und wenn das jetzt tatsächlich nachweislich das Bottleneck in deinem 
Programm darstellt, dann fress ich einen Besen :-)

von Ralf (Gast)


Lesenswert?

> ... (Pointer ist 32 groß)
32 was? Bytes? Bits? Nibbles?

> Wie aber mache ich sowas nun in C ...
> Wobei ich mich mit der Frage mal auf Buffergrößen beschränken möchte,
> die eine Optimierung zulassen, wie in dem Assemblerbeispiel genannt.
Hm...vielleicht etwas in der Art wie "(low)ptr++" -> Compiler-abhängig, 
jedenfalls das C-Äquivalent zur Inkrementierung des Lowbytes -> 
Compiler-Handbuch fragen.

Ralf

von Udo. R. S. (Gast)


Lesenswert?

Kann man vieleicht machen wenn man entsprechend uchar (256) oder ushort 
(64K) incrementiert und dann als offset in einem Array benutzt, muss man 
aber nicht machen!
Wofür soll diese 'Optimierung' gut sein?
Brauchst Du jeden Taktzyklus? Dann programmiere in Assembler
Willst du deinen Code schwer verständlich machen?

Macht alles keinen Sinn, das eine if macht den Bock nicht fett und dann 
kannst Deinen Ringpuffer auch mit beliebiger Größe machen.

von Peter D. (peda)


Lesenswert?

Be Bo schrieb:
> Wie aber mache ich sowas nun in C (Microchip C32), ohne Konstruktionen
> wie:
>
1
if (ptr>Buffer+BufferSize) ptr = Buffer;
> zu verwenden?


Was stört Dich daran?
Das ist doch nur ein Vergleich und eine Zuweisung, besser gehts nicht.

Der AVR-GCC erzeugt daraus leider keinen optimalen Code, da compiliert 
dieses Macro deutlich besser:
1
#define ROLLOVER( x, max )      x = ++x >= max ? 0 : x
2
                                        // count up and wrap around
3
//..
4
  ROLLOVER( rx_out, RX0_SIZE );


Peter

von Peter D. (peda)


Lesenswert?

Udo. R. S. schrieb:
> Macht alles keinen Sinn, das eine if macht den Bock nicht fett und dann
> kannst Deinen Ringpuffer auch mit beliebiger Größe machen.

Stimmt.
Es hat keinen Zweck, krampfhaft am falschen Ende zu optimieren. Das 
kostet nur unnötig Arbeitszeit ohne Effekt.

Vor dem Optimieren muß man erstmal feststellen, welcher Code die meiste 
CPU-Zeit verbraucht.
Als Faustregel, alles unter 1% ist optimal genug.


Peter

von Rufus Τ. F. (rufus) Benutzerseite


Lesenswert?

Selbst ziemlich alte 8-Bit-Architekturen* sind in der Lage, ein 
16-Bit-Adressregister zu nutzen und den darin stehenden Wert ohne 
besondere Anstrengungen zu in- bzw. dekrementieren.
Wird dann relativ zu diesem Adress- bzw. Index-Register adressiert, so 
muss weder die Puffergröße ein Vielfaches von 0x100, noch irgendwie 
ausgerichtet sein.

Und das nutzt ein halbwegs brauchbarer C-Compiler, so daß da keine 
weitere Optimierung erforderlich ist.

Kann das so ein PIC etwa nicht?


*) 8080, Z80, 6800 und folgend, 6502 hingegen nicht

von spess53 (Gast)


Lesenswert?

Hi

>#define ROLLOVER( x, max )      x = ++x >= max ? 0 : x

Hat C keinen Modulo-Operator?

In Delphi wüde ich das so schreiben:

  x:=(x+1) mod max;

MfG Spess

von Reinhard Kern (Gast)


Lesenswert?

Hallo,

wenn so eine Optimierung wichtig ist (zweifelhaft), dann schreibt man 
den Zugriff auf den Ringpuffer als ASM-Funktion und den Rest in C. Und 
wenn du z.B. weisst bzw. festlegst, dass Register HL als Pointer dient 
und die Basisadresse ausgerichtet ist und der Puffer 256 Bytes lang, 
dann genügt ein einziger eingefügter Assembler-Befehl INC L, um die 
ganze Frage zu erledigen.

Gruss Reinhard

von Karl H. (kbuchegg)


Lesenswert?

spess53 schrieb:
> Hi
>
>>#define ROLLOVER( x, max )      x = ++x >= max ? 0 : x
>
> Hat C keinen Modulo-Operator?

Natürlich.
Aber dazu muss gerechnet werden.
Und das kann bei Nicht-2er-Potenzen Aufwand bedeuten.

>
>   x:=(x+1) mod max;
>

Auf einem PC würde ich das auch so machen. Aber ein AVR ist mit einer 
Division durch 38 nicht so glücklich. Da macht er lieber einen Vergleich 
mit anschliessendem 0-setzen.

von Olaf (Gast)


Lesenswert?

> n Assembler auf einem 8-Bitter habe ich meißt einen Buffer von 256
> Bytes Größe auf Adressen wie 0x200, 0x300, 0x400,... gelegt.

Halte ich auch in Assembler fuer Quatsch weil man sich damit auf eine 
bestimmte Buffergroesse beschraenkt und bei Microcontroller sehr viel 
Ram verschwendet den man vielleicht fuer anderes wichtigeres braucht.

Ausserdem setzt es vorraus das die Fifo mit Byte-grossen Datentypen 
arbeitet. Was machst du wenn du einen Struct der 3Byte gross ist in 
deine Fifo wirfst und es zum Ueberlauf kommt?

Bei den paar Assemblerbfehlen die eine uebliche >= Abfrage in C 
letztlich erzeugen wird, mache ich mir keinen Gedanken ueber die 
Effizienz und Geschwindigkeit.

Optimieren wuerde ich die Zugriffe auf die FIFO eher dahingehend das man 
darauf achtet die IRQs bei Variablenaenderungen abzuschalten damit man 
z.b im Interrupt etwas in einer Fifo reinwerfen und es im Hauptprogramm 
wieder rausholen kann.

Olaf

von Peter D. (peda)


Lesenswert?

spess53 schrieb:
> Hat C keinen Modulo-Operator?

Natürlich.
Aber meinst Du, der Aufruf einer Divisionsroutine ist schneller?

Auch will man nicht unnötig SRAM verschenken und auf die nächste 2-er 
Potenz aufrunden müssen.


Peter

von Be B. (bebo)


Lesenswert?

So viele Antworten auf einmal ;-)

Also, es geht mir hier nicht darum ein bestimmtes Programm zu 
optimieren, sondern nur darum, ob es vielleicht Möglichkeiten gibt so 
etwas eleganter zu machen.

Es geht hier auch nicht darum ein Projekt in einem Zeitrahmen fertig zu 
bekommen oder dergleichen. Es geht mir hier einzig und alleine um eine 
Optimierung der Optimierung wegen. Also aus Spaß an der Sache ;-)

Also:
@Karl heinz Buchegger: Buffer+BufferSize (beide sind dem Compiler 
bekannt, werden also wärend des Compilierens bereits zusammengefasst.

Die Sache mit dem Linker habe ich heute schon ausprobiert. Mit einem 
Custom-Linker-Script kann man sich Wunschbereiche für eigene Zwecke 
reservieren. Ist aber natürlich compilerspezifisch, denke ich. Ich kenne 
mich mit in Make sachen nicht so aus. Bei den meißten IDEs machen die 
das alles für einen. Bisher also erfolgreich davor gedrückt;-)

Die Sache mit dem Array und dem Offset muß ich mal ausprobieren. Könnte 
auf einem PIC32 ganz gut funktionnieren. Mal sehen, was der Compiler 
daraus macht. Allerdings würde das auf den meißten 8-Bittern wohl 
Probleme (viele unnötige Befehle) machen.

>Kann das so ein PIC etwa nicht?
Der PIC18 hat da auf jeden Fall Probleme. Allerdings habe ich hier ja 
einen PIC32 (MIPS-Core). Der sollte das können.

> Als Faustregel, alles unter 1% ist optimal genug.
Die Frage ist, ob so eine If-Anweisungslösung gezogen auf den Rest der 
Funktion unter 1% bleibt. Will ich beispielsweise ein Array in/aus so 
einem Ringbuffer kopieren, dauert der Kopiervorgang nur 2 Zyklen. Ich 
weiß jetzt allerdings garnicht ob der PIC32 dabei die Zeiger auch gleich 
incrementieren kann. Ansonsten kommen noch mal 2 Zyklen drauf. Wenn die 
If-Anweisung jetzt also "nur" 2 Zyklen brauchen würde, wären es bereits 
33% bezogen auf den Kopiervorgang. Ok, klar, ihr meint 1% der gesammten 
Rechenzeit, aber mir geht es halt darum gewisse Dinge "in sich" optimal 
zu gestellten.

von Karl H. (kbuchegg)


Lesenswert?

Be Bo schrieb:

> 33% bezogen auf den Kopiervorgang. Ok, klar, ihr meint 1% der gesammten
> Rechenzeit, aber mir geht es halt darum gewisse Dinge "in sich" optimal
> zu gestellten.

Das ist nicht wirklich interessant. Optimierung macht nur im 
Zusammenhang eines ganzen Programmes Sinn.

Selbst wenn du deine Ringbufferroutine um einen Faktor 10 schneller 
machen könntest; wenn die Ringbufferbehandlung im kompletten Programm 
nur 1% der Rechenzeit ausmacht, drückst du die Rechenzeit lediglich von 
100% auf 99.9% herunter. Dabei hast du den Ringbuffer aber 10-fach 
beschleunigt! Im Endprogramm ist davon aber nichts zu bemerken.

Ich hab hier bei mir auch ein paar solcher Spezialisten sitzen. 
Optimieren um jeden Preis. Und wenn es eine Funktion ist, die bei 1 
Million Aufrufe nur 1 einziges mal in einen bestimmten Zweig hineingeht. 
Dieser Zweig muss optimiert werden, koste es was es wolle. Selbst wenn 
dadurch der Code unleserlich wird, selbst wenn dadurch andere 
Codestellen langsamer werden. Hauptsache wir haben optimiert.

von STK500-Besitzer (Gast)


Lesenswert?

Puffer von 0 bis 63:

ptr++:
ptr &= 63:

geht halt nur bei Puffergrößen von Zweierpotenzen.
Universeller ist natürlich die Abfrage, ob das Ende erreicht wurde.

von Peter D. (peda)


Lesenswert?

Be Bo schrieb:
> Die Frage ist, ob so eine If-Anweisungslösung gezogen auf den Rest der
> Funktion unter 1% bleibt.

Das bezog sich natürlich auf die gesamte CPU-Last.
In Funktionen zu optimieren, die selten aufgerufen werden, macht keinen 
Sinn.


> Will ich beispielsweise ein Array in/aus so
> einem Ringbuffer kopieren, dauert der Kopiervorgang nur 2 Zyklen.

Wow, gleich ein ganzes Array, das ist echt sportlich.
Hast Du mal ins Assemblerlisting geschaut, was da alles gemacht wird?

Z.B. der AVR muß erstmal die nötigen Register sichern (im Interrupt), 
dann die Variablen aus dem SRAM laden und jedes Byte einzeln kopieren. 
Das sind etwa 40 Zyklen Prolog+Epilog und dann nochmal 8 Zyklen je Byte.


Peter

von Manuel S. (thymythos) Benutzerseite


Lesenswert?

Zumindest bei Zweierpotenzen reicht auch ein:

ptr &= 0x00ff;

um dein Modulo zu erzeugen. Ich nehm aber an bei

ptr %= 256;

macht der Compiler genau den gleichen Code draus.

von öhm (Gast)


Lesenswert?

Die *guten™* Motorola-DSPs haben für ihre Adressregister
ein zugehöriges Moduloregister.
Damit braucht man gar nicht rechnen :-)

von horst (Gast)


Lesenswert?

meine spontane Idee:

uint8_t i;

while (mir_fad_ist)
{
   Buffer[i++] = irgendein_Bloedsinn;
}


was der compiler dann draus macht weiß ich nicht, aber den Vergleich 
bist du los.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

> Zumindest bei Zweierpotenzen reicht auch ein:
> ptr &= 0x00ff;
Jetzt nur mal angenommen, dein Array beginnt (hübsch auf long aligned) 
an Adresse 0x1234   :-o

von Be B. (bebo)


Lesenswert?

Ihr habt ja alle Recht, aber wie schon gesagt, es ist kein konkretes 
Projekt. Also kann ich den Nutzen garnicht bestimmen.

Im übrigen, wenn ihr Bibliotheken verwendet, fändet ihr es nicht auch 
besser, wenn dieses so optimal wie möglich arbeiten würden? Immerhin 
möchte man sich ja im nachhinein über sowas keine Gedanken mehr machen 
müssen. Damit fällt im Grunde die Variante mit dem Linkerskript aus, da 
es unglücklich wäre, wenn man, um eine Bibliothek zu benutzen, erst ein 
spezielles Linkerscript bräuchte.

> Wow, gleich ein ganzes Array, das ist echt sportlich.
Na ja, bei dem konkreten Fall ging es halt darum, Messages aus einem 
Input-Buffer (UART, USB,...) auf Richtigkeit zu überprüfen 
(Nachrichtenlänge, Nachrichtenstart, Escapesequence,... ), bevor man sie 
der Message-Queue der Hauptanwendung hinzufügt.

Aber die Schreibweise (Macro) von Peter macht die Sache natürlich etwas 
übersichtlicher, als ich das geschrieben habe.

> Z.B. der AVR muß erstmal die nötigen Register sichern (im Interrupt),
> dann die Variablen aus dem SRAM laden und jedes Byte einzeln kopieren.
> Das sind etwa 40 Zyklen Prolog+Epilog und dann nochmal 8 Zyklen je Byte.
Ab den 16-Bit-PICs gibt es bei den UARTs mehrstufige Eingangspuffer. Und 
bei den PIC32 gibt es dann noch die Möglichkeit dieses mit DMA zu 
erschlagen. In meinem Fall kammen immer 64 Bytes auf einmal vom 
USB-Interface.

Aber gut, ich sehen, daß es offensichtlich die Standardlösung ist, die 
wohl in ihrer Leistung am Systemneutralsten ist.

von Be B. (bebo)


Lesenswert?

Hi nochmal,

ich habe jetzt mal einige Tests durchgeführt.

Die Variante
1
MQ[i++] = 0x34; i &= 0x1FF;
ist schneller als
1
MQ[i++] = 0x34; if (wi>=MESSAGEQUEUESIZE) wi = 0;
ist schneller als
1
*MQWritePtr++ = 0x54;
2
if (MQWritePtr>MQ+MESSAGEQUEUESIZE) MQWritePtr = MQ;

Die erst braucht bei maximaler Optimierung 4, die 2. 6 und die 3. 9 
Zyklen. Mit Pointer und VerUNDung liegt man bei 8 Zyklen.

Daraus folgt für den C32, daß die relative Adressierung, wie Rufus sie 
beschreibt, wohl die beste Performance bringt. Ich hätte eigentlich 
gedacht, daß das Arbeiten mit Pointer schneller wäre.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.