Wie setzen Sie einen Ringpuffer in C?
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen Bedarf an einer festen Größe (wählbar zur Laufzeit beim Erstellen, Kompilieren Zeit nicht) Ringpuffer, die Gegenstände jeglicher Art halten kann und es muss sein sehr hoch Performance. Ich glaube nicht, dass es da Ressourcenkonflikte Probleme, obwohl es in einer Multi-Tasking-Umgebung eingebettet ist, ist es ein kooperativer ein, so dass die Aufgaben selbst, dass verwalten.
Mein erster Gedanke war, eine einfache Struktur in dem Puffer zu speichern, die den Typ (einfache Enumeration / definieren) und einen void-Zeiger auf die Nutzlast enthalten würde, aber ich möchte diese so schnell wie möglich sein, so bin ich offen für Vorschläge dass beinhalten die Halde umgangen wird.
Eigentlich ist mir glücklich für rohe Geschwindigkeit eine der Standardbibliothek zu umgehen - von dem, was ich von dem Code gesehen habe, ist es nicht schwer für die CPU optimiert: es sieht aus wie sie nur C-Code für Dinge wie strcpy() zusammengestellt und so gibt es keine handcodierte Montage.
würde Jeder Code oder Ideen sehr geschätzt. Die Operationen, die erforderlich sind:
- einen Puffer mit bestimmten Größe erstellen.
- am Heck setzen.
- aus dem Kopf bekommen.
- Rückkehr der Graf.
- löschen einen Puffer.
Lösung
Können Sie die Typen an der Zeit benötigt aufzuzählen Sie den Puffer kodieren, oder tun müssen, um Sie in der Lage Typen über dynamische Anrufe zur Laufzeit hinzufügen? Wenn der erstere, dann würde ich den Puffer als Halde zugeordnete Array von n structs erstellen, wobei jede Struktur aus zwei Elementen besteht: ein ENUM-Tag den Datentyp zu identifizieren, und eine Vereinigung aller Datentypen. Was haben Sie in Bezug auf die zusätzlichen Stauraum für kleine Elemente verlieren, machen Sie zu müssen in Bezug auf die nicht mit Zuordnung / Aufhebung der Zuordnung und der daraus resultierenden Speicherfragmentierung beschäftigen. Dann brauchen Sie nur den Überblick über den Start- und Zielindizes zu halten, dass die Kopf und Schwanz Elemente des Puffers definieren, und stellen Sie sicher, mod n zu berechnen, wenn Erhöhen / Erniedrigen den Indizes.
Andere Tipps
Die einfachste Lösung wäre es, den Überblick über die Objektgröße zu halten und die Anzahl der Elemente, und dann einen Puffer der entsprechenden Anzahl von Bytes erstellen:
typedef struct circular_buffer
{
void *buffer; // data buffer
void *buffer_end; // end of data buffer
size_t capacity; // maximum number of items in the buffer
size_t count; // number of items in the buffer
size_t sz; // size of each item in the buffer
void *head; // pointer to head
void *tail; // pointer to tail
} circular_buffer;
void cb_init(circular_buffer *cb, size_t capacity, size_t sz)
{
cb->buffer = malloc(capacity * sz);
if(cb->buffer == NULL)
// handle error
cb->buffer_end = (char *)cb->buffer + capacity * sz;
cb->capacity = capacity;
cb->count = 0;
cb->sz = sz;
cb->head = cb->buffer;
cb->tail = cb->buffer;
}
void cb_free(circular_buffer *cb)
{
free(cb->buffer);
// clear out other fields too, just to be safe
}
void cb_push_back(circular_buffer *cb, const void *item)
{
if(cb->count == cb->capacity){
// handle error
}
memcpy(cb->head, item, cb->sz);
cb->head = (char*)cb->head + cb->sz;
if(cb->head == cb->buffer_end)
cb->head = cb->buffer;
cb->count++;
}
void cb_pop_front(circular_buffer *cb, void *item)
{
if(cb->count == 0){
// handle error
}
memcpy(item, cb->tail, cb->sz);
cb->tail = (char*)cb->tail + cb->sz;
if(cb->tail == cb->buffer_end)
cb->tail = cb->buffer;
cb->count--;
}
// Note power of two buffer size
#define kNumPointsInMyBuffer 1024
typedef struct _ringBuffer {
UInt32 currentIndex;
UInt32 sizeOfBuffer;
double data[kNumPointsInMyBuffer];
} ringBuffer;
// Initialize the ring buffer
ringBuffer *myRingBuffer = (ringBuffer *)calloc(1, sizeof(ringBuffer));
myRingBuffer->sizeOfBuffer = kNumPointsInMyBuffer;
myRingBuffer->currentIndex = 0;
// A little function to write into the buffer
// N.B. First argument of writeIntoBuffer() just happens to have the
// same as the one calloc'ed above. It will only point to the same
// space in memory if the calloc'ed pointer is passed to
// writeIntoBuffer() as an arg when the function is called. Consider
// using another name for clarity
void writeIntoBuffer(ringBuffer *myRingBuffer, double *myData, int numsamples) {
// -1 for our binary modulo in a moment
int buffLen = myRingBuffer->sizeOfBuffer - 1;
int lastWrittenSample = myRingBuffer->currentIndex;
int idx;
for (int i=0; i < numsamples; ++i) {
// modulo will automagically wrap around our index
idx = (i + lastWrittenSample) & buffLen;
myRingBuffer->data[idx] = myData[i];
}
// Update the current index of our ring buffer.
myRingBuffer->currentIndex += numsamples;
myRingBuffer->currentIndex &= myRingBuffer->sizeOfBuffer - 1;
}
Solange Ihr Ringpuffers Länge eine Zweierpotenz ist, die unglaublich schnelle binäre „&“ Betrieb wird für Sie rund um Ihren Index wickeln. Für meine Anwendung, ich bin die Anzeige ein Segment von Audio an den Benutzer aus einem Ringpuffer von Audio von einem Mikrofon erfasst.
ich immer darauf achtet, dass die maximale Menge von Audiodaten, die auf dem Bildschirm angezeigt werden können, ist viel kleiner als die Größe des Ringpuffers. Ansonsten könnten Sie aus dem gleichen Brocken werden das Lesen und Schreiben. Dies würde Sie wahrscheinlich seltsame Anzeige Artefakte geben.
Zuerst wird die Überschrift. Sie brauchen nicht Moduloarithmetik die Puffer zu wickeln, wenn Sie Bit ints verwenden, um den Kopf und Schwanz „Zeiger“ zu halten und Größe sie so sind sie perfekt synchron. IE: 4096 in einen unsigned int 12-Bit gestopft 0 von selbst, unbehelligt in keiner Weise. Die Beseitigung Modulo-Arithmetik, auch für Potenzen von 2, verdoppelt sich die Geschwindigkeit -. Fast genau
10 Millionen Iterationen von Abfüll- und einen 4096-Puffer von jeder Art von Datenelementen Entleerung dauert 52 Sekunden auf meinem 3. Gen i7 Dell XPS 8500 Visual Studio 2010 der C ++ Compiler mit Standard inlining und 1 / 8192. davon unter Verwendung eines Datums zu bedienen .
Ich würde RX die Testschleifen in Haupt Umschreiben (), so dass sie nicht mehr den Fluss steuern - das ist, und sollten von den Rückgabewerten, gesteuert angibt, der Puffer voll oder leer, und die damit verbundene Pause; Aussagen. IE: die Füllstoff und Abtropffläche sollten gegeneinander ohne Korruption oder Instabilität schlagen kann. Irgendwann hoffe ich auf Multi-Thread diesen Code, wonach das Verhalten von entscheidender Bedeutung sein wird.
Die QUEUE_DESC (Warteschlangendeskriptor) und Initialisierungsfunktion zwingt alle Puffer in diesem Code eine Potenz von 2 Das obige Schema funktioniert nicht anders zu sein. Während auf dem Thema, beachten Sie, dass QUEUE_DESC nicht hart codiert wird, verwendet er einen offensichtlichen Konstante (#define BITS_ELE_KNT) für den Bau. (Ich bin eine Leistung von 2 unter der Annahme, ist eine ausreichende Flexibilität hier)
Um die Puffergröße Laufzeit wählbar zu machen, habe ich versucht, verschiedene Ansätze (hier nicht dargestellt), und ließ sich auf USHRTs für Kopf, Schwanz mit, EleKnt der Lage, einen FIFO-Puffer für die Verwaltung [USHRT]. Zur Vermeidung von Modulo-Arithmetik habe ich eine Maske mit Head to &&, Schwanz, aber diese Maske erweist sich als (EleKnt -1), so dass nur diese verwenden. Mit USHRTS statt Bit ints erhöhte Leistung ~ 15% in einer ruhigen Maschine. Intel CPU-Kerne haben immer schneller als ihre Busse, so an einer stark befahrenen, gemeinsame Maschine, Ihre Datenstrukturen Verpackung bringt Sie geladen und die Ausführung vor anderen, konkurrierenden Threads. Trade-offs.
Hinweis der tatsächliche Speicher für die Puffer wird auf dem Heap mit calloc zugeordnet () und der Zeiger an der Basis der Struktur, so dass die Struktur und der Zeiger genau die gleiche Adresse. IE; kein Offset erforderlich ist, um die Struktur-Adresse hinzugefügt werden Register zu binden.
In der gleichen Vene, alle Variablen Begleiterin mit dem Puffer Wartung sind physisch neben dem Puffer, in die gleiche Struktur gebunden, so kann der Compiler schöne Assemblersprache machen. Sie werden die Inline-Optimierung töten müssen, um jede Versammlung, um zu sehen, weil es sonst in Vergessenheit zerkleinert wird.
Um den Polymorphismus eines beliebigen Datentypen zu unterstützen, habe ich Memcpy verwendet () anstelle von Zuweisungen. Wenn Sie nur die Flexibilität benötigen eine Zufallsvariable Typ pro Kompilierung zu unterstützen, dann funktioniert dieser Code perfekt.
Für Polymorphismus, müssen Sie nur die Art wissen, und es ist Speicherbedarf. Die DATA_DESC Array von Deskriptoren bietet eine Möglichkeit, den Überblick über jedes Datum zu halten, die in QUEUE_DESC.pBuffer setzen werden, damit es ordnungsgemäß abgerufen werden kann. Ich habe gerade genug pBuffer Speicher zuteilen alle Elemente des größten Datentypen zu halten, aber im Auge behalten, wie viel von diesem Speicher ein bestimmtes Datum wird in DATA_DESC.dBytes tatsächlich verwendet wird. Die Alternative ist ein Heap-Manager neu zu erfinden.
Das bedeutet QUEUE_DESC den UCHAR * pBuffer einen parallelen Begleiter Array Spur von Datentyp zu halten haben würde und die Größe, während ein Lagerort des Bezugs in pBuffer bleiben würde wie es jetzt ist. 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, kann der Compiler in die Vorlage mit einer solchen Vorwärtsverweis zu schlagen. Calloc () ist immer flexibler in diesen Situationen.
Sie würden immer noch memcpy () in Q_Put (), Q_Get, aber die Anzahl von Bytes würde tatsächlich kopiert von DATA_DESC.dBytes bestimmt werden, nicht QUEUE_DESC.EleBytes. Die Elemente sind potenziell alle unterschiedlichTypen / Größen für jede gegebene Put- oder erhalten.
Ich glaube, dass dieser Code die Geschwindigkeit und die Puffergröße Anforderungen erfüllt, und kann gemacht werden, um die Anforderung für 6 verschiedene Datentypen gerecht zu werden. Ich habe die viele Prüfvorrichtungen in in Form von printf () Aussagen verlassen, so können Sie sich selbst (oder nicht) davon überzeugen, dass der Code ordnungsgemäß funktioniert. Der Zufallszahlengenerator zeigt, dass der Code funktioniert für jede zufällige Kopf / Schwanz-Combo.
enter code here
// Queue_Small.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <math.h>
#define UCHAR unsigned char
#define ULONG unsigned long
#define USHRT unsigned short
#define dbl double
/* Queue structure */
#define QUEUE_FULL_FLAG 1
#define QUEUE_EMPTY_FLAG -1
#define QUEUE_OK 0
//
#define BITS_ELE_KNT 12 //12 bits will create 4.096 elements numbered 0-4095
//
//typedef struct {
// USHRT dBytes:8; //amount of QUEUE_DESC.EleBytes storage used by datatype
// USHRT dType :3; //supports 8 possible data types (0-7)
// USHRT dFoo :5; //unused bits of the unsigned short host's storage
// } DATA_DESC;
// This descriptor gives a home to all the housekeeping variables
typedef struct {
UCHAR *pBuffer; // pointer to storage, 16 to 4096 elements
ULONG Tail :BITS_ELE_KNT; // # elements, with range of 0-4095
ULONG Head :BITS_ELE_KNT; // # elements, with range of 0-4095
ULONG EleBytes :8; // sizeof(elements) with range of 0-256 bytes
// some unused bits will be left over if BITS_ELE_KNT < 12
USHRT EleKnt :BITS_ELE_KNT +1;// 1 extra bit for # elements (1-4096)
//USHRT Flags :(8*sizeof(USHRT) - BITS_ELE_KNT +1); // flags you can use
USHRT IsFull :1; // queue is full
USHRT IsEmpty :1; // queue is empty
USHRT Unused :1; // 16th bit of USHRT
} QUEUE_DESC;
// ---------------------------------------------------------------------------
// Function prototypes
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz);
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew);
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q);
// ---------------------------------------------------------------------------
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz) {
memset((void *)Q, 0, sizeof(QUEUE_DESC));//init flags and bit integers to zero
//select buffer size from powers of 2 to receive modulo
// arithmetic benefit of bit uints overflowing
Q->EleKnt = (USHRT)pow(2.0, BitsForEleKnt);
Q->EleBytes = DataTypeSz; // how much storage for each element?
// Randomly generated head, tail a test fixture only.
// Demonstrates that the queue can be entered at a random point
// and still perform properly. Normally zero
srand(unsigned(time(NULL))); // seed random number generator with current time
Q->Head = Q->Tail = rand(); // supposed to be set to zero here, or by memset
Q->Head = Q->Tail = 0;
// allocate queue's storage
if(NULL == (Q->pBuffer = (UCHAR *)calloc(Q->EleKnt, Q->EleBytes))) {
return NULL;
} else {
return Q;
}
}
// ---------------------------------------------------------------------------
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew)
{
memcpy(Q->pBuffer + (Q->Tail * Q->EleBytes), pNew, Q->EleBytes);
if(Q->Tail == (Q->Head + Q->EleKnt)) {
// Q->IsFull = 1;
Q->Tail += 1;
return QUEUE_FULL_FLAG; // queue is full
}
Q->Tail += 1; // the unsigned bit int MUST wrap around, just like modulo
return QUEUE_OK; // No errors
}
// ---------------------------------------------------------------------------
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q)
{
memcpy(pOld, Q->pBuffer + (Q->Head * Q->EleBytes), Q->EleBytes);
Q->Head += 1; // the bit int MUST wrap around, just like modulo
if(Q->Head == Q->Tail) {
// Q->IsEmpty = 1;
return QUEUE_EMPTY_FLAG; // queue Empty - nothing to get
}
return QUEUE_OK; // No errors
}
//
// ---------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[]) {
// constrain buffer size to some power of 2 to force faux modulo arithmetic
int LoopKnt = 1000000; // for benchmarking purposes only
int k, i=0, Qview=0;
time_t start;
QUEUE_DESC Queue, *Q;
if(NULL == (Q = Q_Init(&Queue, BITS_ELE_KNT, sizeof(int)))) {
printf("\nProgram failed to initialize. Aborting.\n\n");
return 0;
}
start = clock();
for(k=0; k<LoopKnt; k++) {
//printf("\n\n Fill'er up please...\n");
//Q->Head = Q->Tail = rand();
for(i=1; i<= Q->EleKnt; i++) {
Qview = i*i;
if(QUEUE_FULL_FLAG == Q_Put(Q, (UCHAR *)&Qview)) {
//printf("\nQueue is full at %i \n", i);
//printf("\nQueue value of %i should be %i squared", Qview, i);
break;
}
//printf("\nQueue value of %i should be %i squared", Qview, i);
}
// Get data from queue until completely drained (empty)
//
//printf("\n\n Step into the lab, and see what's on the slab... \n");
Qview = 0;
for(i=1; i; i++) {
if(QUEUE_EMPTY_FLAG == Q_Get((UCHAR *)&Qview, Q)) {
//printf("\nQueue value of %i should be %i squared", Qview, i);
//printf("\nQueue is empty at %i", i);
break;
}
//printf("\nQueue value of %i should be %i squared", Qview, i);
}
//printf("\nQueue head value is %i, tail is %i\n", Q->Head, Q->Tail);
}
printf("\nQueue time was %5.3f to fill & drain %i element queue %i times \n",
(dbl)(clock()-start)/(dbl)CLOCKS_PER_SEC,Q->EleKnt, LoopKnt);
printf("\nQueue head value is %i, tail is %i\n", Q->Head, Q->Tail);
getchar();
return 0;
}
Hier ist eine einfache Lösung in C sind Angenommen Interrupts für jede Funktion ausgeschaltet. Kein Polymorphismus & stuff, nur gesunder Menschenverstand.
#define BUFSIZE 128
char buf[BUFSIZE];
char *pIn, *pOut, *pEnd;
char full;
// init
void buf_init()
{
pIn = pOut = buf; // init to any slot in buffer
pEnd = &buf[BUFSIZE]; // past last valid slot in buffer
full = 0; // buffer is empty
}
// add char 'c' to buffer
int buf_put(char c)
{
if (pIn == pOut && full)
return 0; // buffer overrun
*pIn++ = c; // insert c into buffer
if (pIn >= pEnd) // end of circular buffer?
pIn = buf; // wrap around
if (pIn == pOut) // did we run into the output ptr?
full = 1; // can't add any more data into buffer
return 1; // all OK
}
// get a char from circular buffer
int buf_get(char *pc)
{
if (pIn == pOut && !full)
return 0; // buffer empty FAIL
*pc = *pOut++; // pick up next char to be returned
if (pOut >= pEnd) // end of circular buffer?
pOut = buf; // wrap around
full = 0; // there is at least 1 slot
return 1; // *pc has the data to be returned
}
Eine einfache Implementierung könnte bestehen aus:
- Ein Puffer, als ein Array der Größe n implementiert, welcher Art auch immer Sie benötigen
- Ein Lesezeiger oder Index (je nachdem, was effizienter für Ihren Prozessor ist)
- Ein Schreibzeiger oder Index
- Ein Zähler angibt, wie viele Daten im Puffer (ableitbar von der Lese- und Schreibzeiger, aber schneller, sie separat zu verfolgen)
Jedes Mal, wenn Daten zu schreiben, können Sie den Schreibzeiger vorrücken und den Zähler erhöhen. Wenn Sie Daten lesen, erhöhen Sie den Lesezeiger und den Zähler verringern. Wenn entweder Zeiger n erreicht hat, ihn auf Null setzen.
Sie können nicht schreiben, wenn Zähler = n. Sie können nicht lesen, wenn Zähler = 0 ist.
C-Stil, einfache Ringpuffer für ganze Zahlen. Erster Einsatz init als genutzt und erhalten. Wenn Puffer es keine Daten enthalten, gibt „0“ Null.
//=====================================
// ring buffer address based
//=====================================
#define cRingBufCount 512
int sRingBuf[cRingBufCount]; // Ring Buffer
int sRingBufPut; // Input index address
int sRingBufGet; // Output index address
Bool sRingOverWrite;
void GetRingBufCount(void)
{
int r;
` r= sRingBufPut - sRingBufGet;
if ( r < cRingBufCount ) r+= cRingBufCount;
return r;
}
void InitRingBuffer(void)
{
sRingBufPut= 0;
sRingBufGet= 0;
}
void PutRingBuffer(int d)
{
sRingBuffer[sRingBufPut]= d;
if (sRingBufPut==sRingBufGet)// both address are like ziro
{
sRingBufPut= IncRingBufferPointer(sRingBufPut);
sRingBufGet= IncRingBufferPointer(sRingBufGet);
}
else //Put over write a data
{
sRingBufPut= IncRingBufferPointer(sRingBufPut);
if (sRingBufPut==sRingBufGet)
{
sRingOverWrite= Ture;
sRingBufGet= IncRingBufferPointer(sRingBufGet);
}
}
}
int GetRingBuffer(void)
{
int r;
if (sRingBufGet==sRingBufPut) return 0;
r= sRingBuf[sRingBufGet];
sRingBufGet= IncRingBufferPointer(sRingBufGet);
sRingOverWrite=False;
return r;
}
int IncRingBufferPointer(int a)
{
a+= 1;
if (a>= cRingBufCount) a= 0;
return a;
}
