¿Cómo implementar un buffer circular en C?
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito un búfer circular de tamaño fijo (seleccionable en tiempo de ejecución al crearlo, no en tiempo de compilación) que pueda contener objetos de cualquier tipo y debe ser muy alto actuación. No creo que haya problemas de contención de recursos ya que, aunque se encuentra en un entorno integrado de tareas múltiples, es una cooperativa para que las tareas en sí puedan manejar eso.
Mi idea inicial era almacenar una estructura simple en el búfer que contuviera el tipo (enumeración simple / definir) y un puntero de vacío a la carga útil, pero quiero que sea lo más rápido posible, así que estoy abierto a sugerencias. que implican eludir el montón.
En realidad, me complace omitir cualquiera de las bibliotecas estándar por velocidad bruta; por lo que he visto del código, no está muy optimizado para la CPU: parece que simplemente compilaron el código C para cosas como
Cualquier código o idea sería muy apreciado. Las operaciones requeridas son:
- crea un búfer con un tamaño específico.
- poner en la cola.
- salir de la cabeza.
- devolver el recuento.
- eliminar un búfer.
Solución
¿Puede enumerar los tipos necesarios en el momento en que codifica el búfer, o necesita poder agregar tipos en tiempo de ejecución mediante llamadas dinámicas? Si fuera el primero, crearía el búfer como una matriz de n estructuras asignada al montón, donde cada estructura consta de dos elementos: una etiqueta enum que identifica el tipo de datos y una unión de todos los tipos de datos. Lo que pierde en términos de almacenamiento adicional para elementos pequeños, lo hace en términos de no tener que lidiar con la asignación / desasignación y la fragmentación de la memoria resultante. Luego, solo debe realizar un seguimiento de los índices de inicio y finalización que definen los elementos de cabecera y cola del búfer, y asegurarse de calcular el modo n al aumentar / disminuir los índices.
Otros consejos
La solución más sencilla sería hacer un seguimiento del tamaño del elemento y la cantidad de elementos, y luego crear un búfer con el número apropiado de bytes:
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;
}
Mientras la longitud del búfer de tu anillo sea una potencia de dos, el binario increíblemente rápido " & amp; " La operación se ajustará a su índice para usted. Para mi aplicación, muestro un segmento de audio al usuario desde un búfer de anillo de audio adquirido desde un micrófono.
Siempre me aseguro de que la cantidad máxima de audio que se puede mostrar en la pantalla sea mucho menor que el tamaño del búfer de anillo. De lo contrario, podrías estar leyendo y escribiendo desde la misma parte. Esto probablemente le dará artefactos de visualización extraños.
Primero, el titular. No necesita aritmética de módulo para envolver el búfer si usa entradas de bits para sostener la cabeza & amp; tail " punteros " ;, y dimensiona para que estén perfectamente sincronizados. IE: 4096 metido en un int sin signo de 12 bits es 0 por sí mismo, sin molestar de ninguna manera. Eliminar la aritmética del módulo, incluso para potencias de 2, duplica la velocidad, casi exactamente.
10 millones de iteraciones de llenado y vaciado de un búfer 4096 de cualquier tipo de elementos de datos toman 52 segundos en mi 3ra Gener i7 Dell XPS 8500 usando el compilador C ++ de Visual Studio 2010 con inline predeterminado, y 1/8192 de eso para dar servicio a un datum .
RX reescribiría los bucles de prueba en main () para que ya no controlen el flujo, que está, y debería estar, controlado por los valores de retorno que indican que el búfer está lleno o vacío, y que la operadora se interrumpe; declaraciones IE: el llenador y el drenador deben poder golpearse unos a otros sin corrupción o inestabilidad. En algún momento, espero multiprocesar este código, por lo que ese comportamiento será crucial.
El QUEUE_DESC (descriptor de cola) y la función de inicialización obligan a todos los buffers en este código a ser una potencia de 2. El esquema anterior NO funcionará de otra manera. Mientras que en el tema, tenga en cuenta que QUEUE_DESC no está codificado, utiliza una constante manifiesta (#define BITS_ELE_KNT) para su construcción. (Supongo que un poder de 2 es suficiente flexibilidad aquí)
Para hacer que el tiempo de ejecución del tamaño del búfer sea seleccionable, probé diferentes enfoques (que no se muestran aquí), y decidí usar USHRT para Head, Tail, EleKnt capaz de administrar un búfer FIFO [USHRT]. Para evitar la aritmética de módulo, creé una máscara para & amp; & amp; con Head, Tail, pero esa máscara resulta ser (EleKnt -1), así que solo usa eso. El uso de USHRTS en lugar de bits incrementa el rendimiento ~ 15% en una máquina silenciosa. Los núcleos de CPU de Intel siempre han sido más rápidos que sus buses, por lo que en una máquina ocupada y compartida, empacar sus estructuras de datos lo carga y ejecuta por delante de otros hilos competidores. Compensaciones.
Tenga en cuenta que el almacenamiento real para el búfer se asigna en el montón con calloc (), y el puntero se encuentra en la base de la estructura, por lo que la estructura y el puntero tienen EXACTAMENTE la misma dirección. ES DECIR; no es necesario agregar una compensación a la dirección de la estructura para atar los registros.
En ese mismo sentido, todas las variables relacionadas con el mantenimiento del búfer están físicamente adyacentes al búfer, unidas a la misma estructura, por lo que el compilador puede crear un bello lenguaje ensamblador. Tendrá que eliminar la optimización en línea para ver cualquier ensamblaje, porque de lo contrario queda aplastado en el olvido.
Para admitir el polimorfismo de cualquier tipo de datos, he usado memcpy () en lugar de asignaciones. Si solo necesita la flexibilidad para admitir un tipo de variable aleatoria por compilación, entonces este código funciona perfectamente.
Para el polimorfismo, solo necesita saber el tipo y su requisito de almacenamiento. El conjunto de descriptores DATA_DESC proporciona una forma de realizar un seguimiento de cada dato que se coloca en QUEUE_DESC.pBuffer para que se pueda recuperar correctamente. Acabo de asignar suficiente memoria pBuffer para contener todos los elementos del tipo de datos más grande, pero hacer un seguimiento de la cantidad de almacenamiento que un dato determinado está utilizando realmente en DATA_DESC.dBytes. La alternativa es reinventar un gestor de pila.
Esto significa que UCHAR * pBuffer de QUEUE_DESC tendría una matriz paralela para realizar un seguimiento del tipo de datos y el tamaño, mientras que la ubicación de almacenamiento de un dato en pBuffer se mantendría tal como está ahora. El nuevo miembro sería algo como DATA_DESC * pDataDesc, o, quizás, DATA_DESC DataDesc [2 ^ BITS_ELE_KNT] si puedes encontrar una manera de ganarle al compilador con una referencia tan avanzada. Calloc () siempre es más flexible en estas situaciones.
Aún así, memcpy () en Q_Put (), Q_Get, pero la cantidad de bytes realmente copiados estaría determinada por DATA_DESC.dBytes, no QUEUE_DESC.EleBytes. Los elementos son potencialmente todos los diferentes tipos / tamaños para cualquier put u get dado.
Creo que este código satisface los requisitos de velocidad y tamaño del búfer, y puede hacerse para satisfacer el requisito de 6 tipos de datos diferentes. He dejado los muchos accesorios de prueba en forma de declaraciones printf (), para que pueda asegurarse (o no) de que el código funciona correctamente. El generador de números aleatorios demuestra que el código funciona para cualquier combo cabeza / cola aleatorio.
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;
}
Aquí hay una solución simple en C. Supongamos que las interrupciones están desactivadas para cada función. Sin polimorfismo & amp; cosas, solo sentido común.
#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
}
Una implementación simple podría consistir en:
- Un búfer, implementado como una matriz de tamaño n, del tipo que necesite
- Un puntero o índice de lectura (el que sea más eficiente para su procesador)
- Un puntero o índice de escritura
- Un contador que indica la cantidad de datos que hay en el búfer (derivado de los punteros de lectura y escritura, pero más rápido para rastrearlos por separado)
Cada vez que escribe datos, avanza el puntero de escritura e incrementa el contador. Cuando lee datos, aumenta el puntero de lectura y disminuye el contador. Si cualquiera de los punteros llega a n, configúrelo en cero.
No puedes escribir si counter = n. No puedes leer si counter = 0.
Estilo C, búfer de anillo simple para enteros. Primero use init que use put y get. Si el búfer no contiene ningún dato, devuelve " 0 " cero.
//=====================================
// 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;
}
