Wie implementiere ich einen Ringpuffer in C?

70

Ich benötige einen Ringpuffer mit fester Größe (zur Laufzeit beim Erstellen auswählbar, nicht zur Kompilierungszeit), der Objekte aller Art aufnehmen kann und eine sehr hohe Leistung aufweisen muss. Ich denke nicht, dass es Probleme mit Ressourcenkonflikten geben wird, da es sich zwar um eine eingebettete Multitasking-Umgebung handelt, es sich jedoch um eine kooperative handelt, sodass die Aufgaben dies selbst verwalten können.

Mein erster Gedanke war, eine einfache Struktur im Puffer zu speichern, die den Typ (einfache Aufzählung / Definition) und einen ungültigen Zeiger auf die Nutzlast enthält, aber ich möchte, dass dies so schnell wie möglich ist, damit ich für Vorschläge offen bin, die das Umgehen beinhalten der Haufen.

Eigentlich bin ich froh, eine der Standardbibliotheken für die Rohgeschwindigkeit zu umgehen - nach dem, was ich vom Code gesehen habe, ist er nicht stark für die CPU optimiert: Es sieht so aus, als hätten sie nur C-Code für Dinge wie strcpy()und so kompiliert , es gibt keine handcodierte Baugruppe.

Jeder Code oder Ideen wäre sehr dankbar. Die erforderlichen Operationen sind:

  • Erstellen Sie einen Puffer mit einer bestimmten Größe.
  • am Schwanz setzen.
  • vom Kopf bekommen.
  • Geben Sie die Zählung zurück.
  • Puffer löschen.
paxdiablo
quelle
1
Benötigen Sie einen Ringpuffer oder eine Warteschlange? Die erforderlichen Vorgänge lassen es wie eine Warteschlange klingen. Ich gebe zu, dass mit der Anforderung einer festen Größe die Verwendung eines Ringpuffers sinnvoll ist, aber ich bin nicht sicher, ob der Fragentitel Ihre eigentliche Frage widerspiegelt.
Logan Capaldo
Ich bin offen für andere Datenstrukturen, wenn Sie glauben, dass sie schneller sein können, aber ich bin mir ziemlich sicher, dass ein im Speicher festgelegter Ringpuffer malloc / frei von den Elementen in der Warteschlange übertrifft. Obwohl ich denke, ich muss sowieso malloc / frei von der Nutzlast machen: Wenn ich ein malloc für den Gegenstand und die Nutzlast machen könnte, könnte sich das lohnen.
Paxdiablo
"Wenn Sie denken, dass sie schneller sein können"? - Ich würde vorschlagen, dass Sie Benchmarking benötigen. Übrigens, was klassifizieren Sie als "sehr hohe Leistung"?
Mitch Wheat
Ich werde alle Ideen vergleichen (ich habe Testdatengenerierungsfunktionen basierend auf dem tatsächlichen Durchsatz). "Hohe Leistung" ist alles, was es der aktuellen CPU ermöglicht, diese neue, kürzlich erhöhte Last zu bewältigen, die der Kunde für angebracht gehalten hat :-)
paxdiablo
Ich werde das klarstellen. Ich brauche nicht die Leistung einer Quad-Way-CPU mit dem neuesten Intel-Screamer. Es läuft auf einer 8051-Variante, die nicht die schnellste ist, also suche ich wirklich nur nach Optimierungsideen zum Testen. Wenn keiner von ihnen ausfällt, muss der Client neue Hardware basierend auf einer anderen CPU erstellen, und das wird nicht billig. Die Artikelbehandlung in den aktuellen Warteschlangen wurde als primärer Engpass identifiziert.
Paxdiablo

Antworten:

10

Können Sie die Typen auflisten, die zum Zeitpunkt des Codierens des Puffers benötigt werden, oder müssen Sie in der Lage sein, Typen zur Laufzeit über dynamische Aufrufe hinzuzufügen? Wenn erstere, würde ich den Puffer als ein Heap-zugewiesenes Array von n Strukturen erstellen, wobei jede Struktur aus zwei Elementen besteht: einem Enum-Tag, das den Datentyp identifiziert, und einer Vereinigung aller Datentypen. Was Sie an zusätzlichem Speicherplatz für kleine Elemente verlieren, machen Sie dadurch wieder wett, dass Sie sich nicht mit Zuweisung / Freigabe und der daraus resultierenden Speicherfragmentierung befassen müssen. Dann müssen Sie nur noch die Start- und Endindizes verfolgen, die die Kopf- und Endelemente des Puffers definieren, und beim Erhöhen / Dekrementieren der Indizes sicherstellen, dass mod n berechnet wird.

Dewtell
quelle
Die benötigten Typen werden aufgelistet, ja. Es gibt nur ungefähr sechs von ihnen und das wird sich nie ändern. Die Warteschlangen, in denen sich die Elemente befinden, müssen jedoch alle sechs Typen enthalten können. Ich bin mir nicht sicher, ob ein ganzes Element in der Warteschlange und nicht ein Zeiger gespeichert werden soll - das bedeutet, dass Elemente (mehrere hundert Bytes) anstelle eines Zeigers kopiert werden. Aber ich mag die Idee einer Gewerkschaft - mein Hauptanliegen ist hier eher die Geschwindigkeit als der Speicher (wir haben genug davon, aber die CPU ist ein Schock :-).
Paxdiablo
Ihre Antwort hat mir eine gute Idee gegeben - der Speicher für die Elemente könnte von malloc () vorab zugewiesen und von einem mymalloc () ausgegeben werden, das speziell für die Verarbeitung dieser Speicherblöcke entwickelt wurde. Und ich könnte immer noch nur Zeiger verwenden. +1 dafür.
Paxdiablo
Abhängig vom Zugriffsmuster auf die Daten müssen Sie möglicherweise zusätzliches Kopieren durchführen oder nicht. Wenn Sie die Elemente an Ort und Stelle erstellen und sie referenzieren könnten, während sie sich noch im Puffer befinden, bevor Sie sie öffnen, wird möglicherweise nicht zusätzlich kopiert. Aber es ist sicherlich sicherer und flexibler, sie von Ihrem eigenen Allokator zu verteilen und ein separates Array von Zeigern (oder Indizes) als Puffer zu verwenden.
Dewtell
81

Die einfachste Lösung wäre, die Artikelgröße und die Anzahl der Artikel zu verfolgen und dann einen Puffer mit der entsprechenden Anzahl von Bytes zu erstellen:

Adam Rosenfield
quelle
5
Sehr Standardlösung - genau nach Spezifikation. dass das OP als das beinhaltete, was er zu vermeiden versuchte. : P
Anthony
Adam, diese Lösung geht davon aus, dass Elemente derselben Größe immer dieselbe Position im Puffer einnehmen müssen. Ich glaube, das OP verlangte, dass jede Eingabe, die an einer beliebigen Stelle im Puffer gespeichert ist, einen von 6 Datentypen unterschiedlicher Größe hat. Dies lässt 2 Alternativen. Verwenden Sie für jedes neu angekommene Datum den Speicherplatz calloc () und realloc () oder weisen Sie einen Puffer zu, der groß genug ist, um an jeder Position im Puffer den größten Bezugstyp aufzunehmen. Der letztere Ansatz wäre, wenn möglich, schneller und sauberer.
Könnten Sie bitte eine Möglichkeit angeben, einen Ringpuffer zu initiieren? Verwenden dieses Codes: Circular_Buffer * cb; cb_init (cb, 20, 4); Ich bekomme diesen Fehler Prozess beendet mit Exit-Code 139 (unterbrochen durch Signal 11: SIGSEGV) Vielen Dank im Voraus und Entschuldigung für das Schreiben von Code in den Kommentaren.
Dimitris Filippou
Ich wollte nur einen Hinweis hinzufügen, dass diese Implementierung für Multithread-Fälle nicht funktioniert, dh Produzent und Konsument sind separate Threads, da beide auf "count" zugreifen und diese ändern. Wir müssen "count" schützen.
user138645
15

Solange die Länge Ihres Ringpuffers eine Zweierpotenz ist, wird die unglaublich schnelle binäre "&" -Operation Ihren Index für Sie umschließen. Für meine Anwendung zeige ich dem Benutzer ein Audiosegment aus einem Ringpuffer von Audio an, der von einem Mikrofon erfasst wurde.

Ich stelle immer sicher, dass die maximale Menge an Audio, die auf dem Bildschirm angezeigt werden kann, viel geringer ist als die Größe des Ringpuffers. Andernfalls lesen und schreiben Sie möglicherweise aus demselben Block. Dies würde Ihnen wahrscheinlich seltsame Anzeigeartefakte geben.

alexbw
quelle
Ich mag die Verwendung von & und ringBuffer-> sizeOfBuffer als Bitmaske. Ich gehe davon aus, dass das Problem mit "seltsamen Anzeigeartefakten" auf das Schreiben in das FIFO zurückzuführen ist, ohne zu prüfen, ob Sie vor dem Schreiben über den Schwanz schreiben werden.
1
Ich habe einige Tests durchgeführt und denke, dass beide Arten von% und & mit diesem Snippet gleich sind: uint8_t tmp1,tmp2; tmp1 = (34 + 1) & 31; tmp2 = (35 ) % 32; printf("%d %d",tmp1,tmp2); Also, was ist der eigentliche Unterschied oder es ist nur ein Codierungsstil?
R1S8K
11

Erstens die Überschrift. Sie benötigen keine Modulo-Arithmetik, um den Puffer zu umbrechen, wenn Sie Bit-Ints verwenden, um die "Zeiger" von Kopf und Schwanz zu halten und sie so zu dimensionieren, dass sie perfekt synchron sind. IE: 4096, gefüllt mit einem 12-Bit-Int ohne Vorzeichen, ist 0 für sich und in keiner Weise belästigt. Das Eliminieren der Modulo-Arithmetik, selbst bei Zweierpotenzen, verdoppelt die Geschwindigkeit - fast genau.

10 Millionen Iterationen zum Füllen und Entleeren eines 4096-Puffers mit Datenelementen aller Art dauern auf meinem Dell XPS 8500 der 3. Generation i7 mit dem C ++ - Compiler von Visual Studio 2010 mit Standard-Inlining 52 Sekunden, und 1/8192. davon, um ein Datum zu warten.

Ich würde RX die Testschleifen in main () neu schreiben, damit sie den Fluss nicht mehr steuern - was durch die Rückgabewerte gesteuert wird und sollte, die anzeigen, dass der Puffer voll oder leer ist, und die damit verbundene Unterbrechung; Aussagen. IE: Der Füllstoff und der Abfluss sollten in der Lage sein, ohne Korruption oder Instabilität gegeneinander zu schlagen. Irgendwann hoffe ich, diesen Code mit mehreren Threads zu versehen, woraufhin dieses Verhalten entscheidend sein wird.

Die Funktion QUEUE_DESC (Warteschlangendeskriptor) und die Initialisierung erzwingen, dass alle Puffer in diesem Code eine Potenz von 2 haben. Das obige Schema funktioniert sonst NICHT. Beachten Sie, dass QUEUE_DESC nicht fest codiert ist, sondern eine Manifestkonstante (#define BITS_ELE_KNT) für seine Konstruktion verwendet. (Ich gehe davon aus, dass eine Potenz von 2 hier ausreichend Flexibilität ist)

Um die Laufzeit der Puffergröße auswählbar zu machen, habe ich verschiedene Ansätze (hier nicht gezeigt) ausprobiert und mich für die Verwendung von USHRTs für Head, Tail, EleKnt entschieden, die einen FIFO-Puffer [USHRT] verwalten können. Um Modulo-Arithmetik zu vermeiden, habe ich eine Maske für && mit Head, Tail erstellt, aber diese Maske stellt sich als (EleKnt -1) heraus. Verwenden Sie sie also einfach. Die Verwendung von USHRTS anstelle von Bit-Ints erhöhte die Leistung auf einer leisen Maschine um ~ 15%. Intel-CPU-Kerne waren schon immer schneller als ihre Busse. Wenn Sie also auf einem ausgelasteten, gemeinsam genutzten Computer Ihre Datenstrukturen packen, werden Sie vor anderen konkurrierenden Threads geladen und ausgeführt. Kompromisse.

Beachten Sie, dass der tatsächliche Speicher für den Puffer mit calloc () auf dem Heap zugewiesen wird und sich der Zeiger an der Basis der Struktur befindet, sodass die Struktur und der Zeiger genau dieselbe Adresse haben. IE; Es muss kein Offset zur Strukturadresse hinzugefügt werden, um Register zu binden.

In diesem Sinne befinden sich alle Variablen, die mit der Wartung des Puffers verbunden sind, physisch neben dem Puffer und sind in dieselbe Struktur eingebunden, sodass der Compiler eine schöne Assemblersprache erstellen kann. Sie müssen die Inline-Optimierung beenden, um eine Baugruppe zu sehen, da sie sonst in Vergessenheit gerät.

Um den Polymorphismus eines beliebigen Datentyps zu unterstützen, habe ich memcpy () anstelle von Zuweisungen verwendet. Wenn Sie nur die Flexibilität benötigen, einen Zufallsvariablentyp pro Kompilierung zu unterstützen, funktioniert dieser Code einwandfrei.

Für Polymorphismus müssen Sie nur den Typ und die Speicheranforderungen kennen. Das DATA_DESC-Array von Deskriptoren bietet eine Möglichkeit, jedes Datum zu verfolgen, das in QUEUE_DESC.pBuffer abgelegt wird, damit es ordnungsgemäß abgerufen werden kann. Ich würde nur genug pBuffer-Speicher zuweisen, um alle Elemente des größten Datentyps aufzunehmen, aber verfolgen, wie viel von diesem Speicher ein bestimmtes Datum tatsächlich in DATA_DESC.dBytes verwendet. Die Alternative besteht darin, einen Heap-Manager neu zu erfinden.

Dies bedeutet, dass der UCHAR * pBuffer von QUEUE_DESC über ein paralleles Begleitarray verfügt, um den Datentyp und die Größe zu verfolgen, während der Speicherort eines Datums in pBuffer unverändert bleibt. Das neue Mitglied wäre so etwas wie DATA_DESC * pDataDesc oder vielleicht DATA_DESC DataDesc [2 ^ BITS_ELE_KNT], wenn Sie einen Weg finden, Ihren Compiler mit einer solchen Vorwärtsreferenz zur Übermittlung zu bewegen. Calloc () ist in diesen Situationen immer flexibler.

Sie würden noch memcpy () in Q_Put (), Q_Get, aber die Anzahl der tatsächlich kopierten Bytes wird durch DATA_DESC.dBytes bestimmt, nicht durch QUEUE_DESC.EleBytes. Die Elemente haben möglicherweise alle unterschiedliche Typen / Größen für einen bestimmten Put oder Get.

Ich glaube, dieser Code erfüllt die Anforderungen an Geschwindigkeit und Puffergröße und kann erstellt werden, um die Anforderungen für 6 verschiedene Datentypen zu erfüllen. Ich habe die vielen Testgeräte in Form von printf () -Anweisungen belassen, damit Sie sich davon überzeugen können (oder nicht), dass der Code ordnungsgemäß funktioniert. Der Zufallszahlengenerator zeigt, dass der Code für jede zufällige Kopf / Schwanz-Kombination funktioniert.

Luftkissenfahrzeug voller Aale
quelle
5
Ihr Code ist aus mehreren Gründen fehlerhaft. Erstens wird der Vergleich Q->Tail == (Q->Head + Q->EleKnt)in Ihrer Q_PutMethode niemals true zurückgeben, da Q->Head + Q->EleKntes sich nicht um eine Modulo-Addition handelt, was bedeutet, dass Sie den Kopf beim nächsten Schreiben einfach überschreiben. Wenn EleKntja 4096, ist das ein Wert, den Sie Tailniemals erreichen werden. Als nächstes würde die Verwendung als Warteschlange für Produzenten / Konsumenten Chaos anrichten, da Ihr Q_Put"zuerst schreibt, später Fragen stellt" und das aktualisiert, Tailselbst wenn Sie feststellen, dass die Warteschlange voll ist. Der nächste Anruf bei Q_Putüberschreibt einfach den Kopf, als wäre nie etwas passiert.
Groo
2
Sie sollten verschiedene Algorithmen analysieren, die auf der Wikipedia-Seite für Kreispuffer vorgestellt werden , dh das Problem der Unterscheidung zwischen vollständigem oder leerem Puffer . Bei Ihrem aktuellen Ansatz müssen Sie ein Element weniger in Ihrem Puffer behalten, um den Unterschied zwischen voll und leer zu erkennen.
Groo
5
@RocketRoy: Ich habe es gerade getan, Visual Studio 2012. Und hier können Sie die Ergebnisse auch online überprüfen (stdout befindet sich unten), sodass wir sicher sind, dass wir denselben Code betrachten. Die Ausgabe des Testprogramms befindet sich am Ende der Seite und bestätigt, was ich geschrieben habe: Es funktioniert "perfekt", solange Sie nicht versuchen, es zu füllen. Deshalb ist es als FIFO-Puffer nutzlos. :)
Groo
5
Ironischerweise bin ich zu diesem Beitrag gekommen, obwohl Sie diese andere Antwort kommentiert haben , in der Sie behauptet haben, dass das Snippet von @AdamDavis nicht funktioniert hat, und es ist eigentlich umgekehrt. Beachten Sie auch, wie Adam zurückkommt, Putsobald er feststellt, dass es voll ist, während Sie dennoch die Daten kopieren und dann die Überprüfung durchführen.
Groo
4
@RocketRoy: Also sagst du mir tatsächlich, dass du immer noch nicht damit einverstanden bist, dass dein Code kaputt ist? Ja, ich bin mir ziemlich sicher, dass Ihr Code die Lücke nicht "verschiebt", da er einfach perfekt funktioniert und den Kopf überschreibt, ohne zu erkennen, wann er voll ist. Ich hoffe, Sie verwenden dies nicht in lebenskritischen Systemen, da Sie ernsthafte Probleme bekommen könnten.
Groo
8

Hier ist eine einfache Lösung in C. Angenommen, Interrupts sind für jede Funktion deaktiviert. Kein Polymorphismus & Zeug, nur gesunder Menschenverstand.


SoloPilot
quelle
1
pIn> pEnd sollte anstelle von pIn> = pEnd verwendet werden, da Sie sonst niemals den letzten Slot des Buf füllen. Gleiches gilt für pOut> = pEnd
Dmitry Kurilo
2

Eine einfache Implementierung könnte bestehen aus:

  • Ein Puffer, implementiert als Array der Größe n, egal welchen Typs Sie benötigen
  • Ein Lesezeiger oder Index (je nachdem, was für Ihren Prozessor effizienter ist)
  • Ein Schreibzeiger oder Index
  • Ein Zähler, der angibt, wie viele Daten sich im Puffer befinden (ableitbar von den Lese- und Schreibzeigern, aber schneller, um sie separat zu verfolgen)

Jedes Mal, wenn Sie Daten schreiben, bewegen Sie den Schreibzeiger vor und erhöhen den Zähler. Wenn Sie Daten lesen, erhöhen Sie den Lesezeiger und verringern den Zähler. Wenn einer der Zeiger n erreicht, setzen Sie ihn auf Null.

Sie können nicht schreiben, wenn counter = n. Sie können nicht lesen, wenn Zähler = 0 ist.

Steve Melnikoff
quelle
Wie kann der Zähler aus den Zeigern abgeleitet werden, wenn sowohl der Lese- als auch der Schreibzeiger auf dieselbe Position zeigen? In diesem Fall könnte der Puffer entweder leer oder voll sein und ein Zähler wäre erforderlich (oder ein Flag, das speichert, ob der Puffer voll ist oder nicht).
Dimitrios Dedoussis
@DimitriosDedoussis: einer dieser Vorschläge - oder Sie sagen, dass der Puffer leer ist, wenn die Zeiger auf dieselbe Position zeigen, und der Puffer voll ist, wenn der Schreibzeiger auf die Position unmittelbar vor dem Lesezeiger zeigt (und Sie dies nicht zulassen) den Schreibzeiger, der vorgerückt wird, um mit dem Lesezeiger übereinzustimmen).
Steve Melnikoff
Genau. In diesem Fall muss der Puffer die Länge n + 1 haben, um eine Kapazität von n zu ermöglichen. Was ich an erster Stelle hervorheben wollte, war, dass der Zähler nicht von den Zeigern abgeleitet werden kann, es sei denn, man führt einige Problemumgehungen in ihrer Puffermechanik durch (z. B. Erhöhen der Länge des Puffers) oder Hinzufügen eines zustandsbehafteten booleschen Flags.
Dimitrios Dedoussis
@ DimitriosDedoussis Das stimmt.
Steve Melnikoff
2

Einfacher Ringpuffer im C-Stil für ganze Zahlen. Verwenden Sie zuerst init als put und get. Wenn der Puffer keine Daten enthält, gibt er "0" Null zurück.

fi.com
quelle
0

Ich denke, dass die Erweiterung der adam-rosenfield-Lösung für das Multithread-Szenario mit einem einzigen Produzenten und einem einzigen Konsumenten funktionieren wird.

user138645
quelle
0

Die Lösung von @Adam Rosenfield könnte, obwohl sie korrekt ist, mit einer leichteren circular_bufferStruktur implementiert werden, die nicht countund capacity.

Die Struktur konnte nur die folgenden 4 Zeiger enthalten:

  • buffer: Zeigt auf den Start des Puffers im Speicher.
  • buffer_end: Zeigt auf das Ende des Puffers im Speicher.
  • head: Zeigt auf das Ende der gespeicherten Daten.
  • tail: Zeigt auf den Beginn der gespeicherten Daten.

Wir könnten das szAttribut beibehalten, um die Parametrisierung der Speichereinheit zu ermöglichen.

Sowohl die countals auch diecapacity Werte sollten unter Verwendung der obigen Zeiger ableitbar sein.

Kapazität

capacityist einfach, da es durch Teilen des Abstands zwischen dem buffer_endZeiger und dem bufferZeiger durch die Speichereinheit abgeleitet werden kann sz(das folgende Snippet ist Pseudocode):

Anzahl

Für die Zählung werden die Dinge jedoch etwas komplizierter. Zum Beispiel gibt es keine Möglichkeit festzustellen, ob der Puffer leer oder voll ist, im Szenario headund tailauf denselben Speicherort zeigend.

Um dies zu beheben, sollte der Puffer Speicher für ein zusätzliches Element zuweisen. Wenn zum Beispiel die gewünschte Kapazität unseres Ringpuffers ist 10 * sz, müssen wir zuweisen 11 * sz.

Die Kapazitätsformel wird dann (Snippet unten ist Pseudocode):

Diese zusätzliche Elementsemantik ermöglicht es uns, Bedingungen zu konstruieren, die bewerten, ob der Puffer leer oder voll ist.

Leere Zustandsbedingungen

Damit der Puffer leer ist, zeigt der headZeiger auf dieselbe Position wie der tailZeiger:

Wenn das oben Gesagte als wahr ausgewertet wird, ist der Puffer leer.

Volle Zustandsbedingungen

Damit der Puffer voll ist, sollte der headZeiger 1 Element hinter dem tailZeiger sein. Daher sollte der Raum, der zum Abspringen von headOrt zu tailOrt benötigt wird, gleich sein 1 * sz.

wenn tailgrößer ist als head:

Wenn das oben Gesagte als wahr ausgewertet wird, ist der Puffer voll.

wenn headgrößer ist als tail:

  1. buffer_end - headGibt das Leerzeichen zurück, um vom headzum Ende des Puffers zu springen .
  2. tail - buffer Gibt den Platz zurück, der benötigt wird, um vom Anfang des Puffers zum `Tail zu springen.
  3. Das Hinzufügen der obigen 2 sollte gleich dem Platz sein, der benötigt wird, um von der zu springen head zurtail
  4. Der in Schritt 3 abgeleitete Raum sollte nicht größer sein als 1 * sz

Wenn das oben Gesagte als wahr ausgewertet wird, ist der Puffer voll.

In der Praxis

Ändern von @Adam Rosenfield's, um die obige circular_bufferStruktur zu verwenden:

Dimitrios Dedoussis
quelle