Comment implémentez-vous un tampon circulaire en C?
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai besoin d'un tampon circulaire de taille fixe (sélectionnable au moment de l'exécution lors de sa création, et non au moment de la compilation) pouvant contenir des objets de tout type et dont le contenu doit être très . performance. Je ne pense pas qu'il y aura des problèmes de conflits de ressources car, même s'il s'agit d'un environnement intégré multi-tâches, il s'agit d'un environnement coopératif permettant aux tâches elles-mêmes de gérer cela.
Ma pensée initiale était de stocker une structure simple dans le tampon qui contiendrait le type (simple enum / define) et un pointeur vide sur la charge, mais je veux que cela soit aussi rapide que possible, donc je suis ouvert aux suggestions. qui impliquent de contourner le tas.
En fait, je suis heureux de contourner une bibliothèque standard pour la vitesse brute - d'après ce que j'ai vu du code, elle n'est pas optimisée pour le processeur: il semblerait qu'ils viennent de compiler du code C pour des choses comme strcpy () et ainsi de suite, il n'y a pas d'assembly codé à la main.
N'importe quel code ou idée serait grandement apprécié. Les opérations requises sont:
- créer un tampon de taille spécifique.
- mis à la queue.
- obtenir de la tête.
- renvoyer le compte.
- supprimer un tampon.
La solution
Pouvez-vous énumérer les types nécessaires au moment de coder la mémoire tampon ou devez-vous pouvoir ajouter des types au moment de l'exécution via des appels dynamiques? Si c'était le cas, je créerais le tampon sous la forme d'un tableau de n structs alloué par tas, chaque structure étant composée de deux éléments: une balise enum identifiant le type de données et une union de tous les types de données. Ce que vous perdez en termes d'espace de stockage supplémentaire pour les petits éléments, vous êtes compensé par le fait de ne pas avoir à gérer l'allocation / désallocation et la fragmentation de la mémoire qui en résulte. Ensuite, il vous suffit de suivre les index de début et de fin qui définissent les éléments de tête et de queue du tampon et de calculer le mod n lors de l’incrémentation / décrémentation des index.
Autres conseils
La solution la plus simple serait de garder trace de la taille et du nombre d’éléments, puis de créer un tampon du nombre d’octets approprié:
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;
}
Tant que la longueur de votre mémoire tampon est de deux, la binaire " incroyablement rapide l'opération va envelopper votre index pour vous. Pour mon application, j'affiche un segment audio à l'utilisateur à partir d'une mémoire tampon en anneau audio acquise à partir d'un microphone.
Je m'assure toujours que la quantité maximale d'audio pouvant être affichée à l'écran est bien inférieure à la taille de la mémoire tampon. Sinon, vous pourriez lire et écrire à partir du même morceau. Cela vous donnerait probablement des artefacts d’affichage étranges.
D'abord, le titre. Vous n'avez pas besoin de l'arithmétique modulo pour envelopper le tampon si vous utilisez des bits pour contenir la tête & amp; tail "pointeurs", et les dimensionner pour qu’ils soient parfaitement synchronisés. IE: 4096 inséré dans un unsigned int de 12 bits vaut 0 tout seul, sans aucune altération. L'élimination de l'arithmétique modulo, même pour des puissances de 2, double la vitesse - presque exactement.
10 millions d’itérations de remplissage et de vidage d’une mémoire tampon 4096 de tout type d’éléments de données prennent 52 secondes sur mon Dell XPS 8500 de troisième génération utilisant le compilateur C ++ de Visual Studio 2010 avec inlining par défaut, et 1 / 8192e de celui-ci pour gérer un datum .
Je voudrais réécrire les boucles de test dans main () afin qu'elles ne contrôlent plus le flux - ce qui est et devrait être contrôlé par les valeurs de retour indiquant que la mémoire tampon est pleine ou vide, ainsi que la pause de l'opérateur; déclarations. IE: le remplisseur et l'égouttoir devraient pouvoir se cogner l'un contre l'autre sans corruption ni instabilité. A un moment donné, j'espère multi-threader ce code, après quoi ce comportement sera crucial.
Les fonctions QUEUE_DESC (descripteur de file d'attente) et d'initialisation imposent à tous les tampons de ce code une puissance de 2. Le schéma ci-dessus NE fonctionnera PAS. Sur le sujet, notez que QUEUE_DESC n'est pas codé en dur, il utilise une constante manifeste (#define BITS_ELE_KNT) pour sa construction. (Je suppose qu'une puissance de 2 est une flexibilité suffisante ici)
Pour que la taille de la mémoire tampon puisse être sélectionnée au moment de l’exécution, j’ai essayé différentes approches (non illustrées ici), puis j’ai décidé d’utiliser les méthodes USHRT pour Head, Tail, EleKnt capables de gérer un tampon FIFO [USHRT]. Pour éviter l’arithmétique modulo, j’ai créé un masque dans & amp; & amp; avec Head, Tail, mais ce masque s'avère être (EleKnt -1), alors utilisez-le. L'utilisation de USHRTS au lieu d'in bits a augmenté les performances d'environ 15% sur une machine silencieuse. Les cœurs de processeurs Intel ont toujours été plus rapides que leurs bus. Par conséquent, sur une machine partagée occupée, le compactage de vos structures de données vous permet de charger et d’exécuter vos tâches plus rapidement que les autres threads concurrents. Compromis.
Notez que la mémoire réelle du tampon est allouée sur le tas avec calloc () et que le pointeur se trouve à la base de la structure. Par conséquent, la structure et le pointeur ont EXACTEMENT la même adresse. C'EST À DIRE; aucun décalage requis pour être ajouté à l'adresse de structure pour attacher des registres.
Dans le même ordre d'idées, toutes les variables associées à la gestion de la mémoire tampon sont physiquement adjacentes à la mémoire tampon, liées dans la même structure, afin que le compilateur puisse créer un beau langage d'assemblage. Vous devrez supprimer l'optimisation en ligne pour voir tout assemblage, car sinon, il serait écrasé par l'oubli.
Pour prendre en charge le polymorphisme de tout type de données, j'ai utilisé memcpy () à la place des assignations. Si vous avez seulement besoin de la souplesse nécessaire pour prendre en charge un type de variable aléatoire par compilation, ce code fonctionne parfaitement.
Pour le polymorphisme, il vous suffit de connaître le type et les conditions de stockage. Le tableau de descripteurs DATA_DESC fournit un moyen de garder trace de chaque donnée qui est placée dans QUEUE_DESC.pBuffer afin qu'elle puisse être récupérée correctement. J'allais juste allouer suffisamment de mémoire pBuffer pour contenir tous les éléments du type de données le plus grand, mais garder une trace de la quantité de stockage utilisée par une donnée donnée dans DATA_DESC.dBytes. L’alternative consiste à réinventer un gestionnaire de tas.
Cela signifie que le fichier UCHAR * pBuffer de QUEUE_DESC aurait un tableau compagnon parallèle pour garder une trace du type et de la taille des données, tandis que l'emplacement de stockage d'une donnée dans pBuffer resterait tel qu'il est maintenant. Le nouveau membre serait quelque chose comme DATA_DESC * pDataDesc, ou peut-être DATA_DESC DataDesc [2 ^ BITS_ELE_KNT] si vous pouvez trouver un moyen de faire passer votre compilateur à la soumission avec une telle référence en aval. Calloc () est toujours plus flexible dans ces situations.
Vous auriez toujours memcpy () dans Q_Put (), Q_Get, mais le nombre d'octets réellement copiés serait déterminé par DATA_DESC.dBytes et non par QUEUE_DESC.EleBytes. Les éléments sont potentiellement tous de types / tailles différents pour un achat ou un achat donné.
Je crois que ce code satisfait aux exigences de vitesse et de taille de la mémoire tampon, et peut être conçu pour répondre aux exigences de 6 types de données différents. J'ai laissé les nombreux appareils de test dans, sous la forme d'instructions printf (), afin que vous puissiez vous assurer (ou non) que le code fonctionne correctement. Le générateur de nombres aléatoires démontre que le code fonctionne pour tout combo tête / queue aléatoire.
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;
}
Voici une solution simple en C. Supposons que les interruptions soient désactivées pour chaque fonction. Pas de polymorphisme & amp; des choses, juste le bon sens.
#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
}
Une implémentation simple pourrait consister en:
- Un tampon, implémenté sous la forme d'un tableau de taille n, quel que soit le type dont vous avez besoin
- Un pointeur ou un index de lecture (celui qui est le plus efficace pour votre processeur)
- Un pointeur ou un index d'écriture
- Un compteur indiquant la quantité de données dans la mémoire tampon (pouvant être dérivé des pointeurs de lecture et d'écriture, mais plus rapide pour le suivre séparément)
Chaque fois que vous écrivez des données, vous avancez le pointeur d'écriture et incrémentez le compteur. Lorsque vous lisez des données, vous augmentez le pointeur de lecture et décrémentez le compteur. Si l'un des deux pointeurs atteint n, définissez-le sur zéro.
Vous ne pouvez pas écrire si counter = n. Vous ne pouvez pas lire si compteur = 0.
Style C, tampon circulaire simple pour les entiers. Utilisez d'abord init que use put and get. Si le tampon ne contient aucune donnée, il renvoie "0". zéro.
//=====================================
// 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;
}
