最も簡単な解決策は、アイテムのサイズと数を追跡し、適切なバイト数のバッファーを作成することです:
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;
}
リング バッファーの長さが 2 のべき乗である限り、信じられないほど高速なバイナリ "&" 操作がインデックスをラップします。私のアプリケーションでは、オーディオのリング バッファーからオーディオのセグメントをユーザーに表示しています。マイクから取得。
私は常に、画面に表示できるオーディオの最大量がリング バッファーのサイズよりもはるかに少ないことを確認しています。そうしないと、同じチャンクから読み書きしている可能性があります。これにより、奇妙な表示アーティファクトが発生する可能性があります。
まずは見出し。ビット整数を使用してヘッドとテールの「ポインター」を保持し、完全に同期するようにサイズを設定する場合、バッファーをラップするためのモジュロ演算は必要ありません。 IE:12 ビットの unsigned int に詰め込まれた 4096 は、それ自体ですべて 0 であり、いかなる方法でも妨害されません。モジュロ演算を排除すると、2 の累乗であっても速度が 2 倍になります - ほぼ正確です。
Visual Studio 2010 の C++ コンパイラとデフォルトのインライン化を使用して、第 3 世代の i7 Dell XPS 8500 で、任意のタイプのデータ要素の 4096 バッファを埋めて排出する 1,000 万回の反復に 52 秒かかり、その 1/8192 でデータを処理します。
RX で main() のテスト ループを書き直して、フローを制御しないようにします。これは、バッファーがいっぱいか空であることを示す戻り値とそれに付随するブレークによって制御される必要があります。ステートメント。 IE:フィラーとドレーナーは、破損したり不安定になったりすることなく、互いに衝突できる必要があります。ある時点で、このコードをマルチスレッド化し、その動作が重要になることを願っています。
QUEUE_DESC (キュー記述子) と初期化関数は、このコード内のすべてのバッファーを強制的に 2 の累乗にします。上記のスキームは、それ以外の場合は機能しません。この件に関しては、QUEUE_DESC はハードコードされていないことに注意してください。その構築にはマニフェスト定数 (#define BITS_ELE_KNT) が使用されます。 (ここでは 2 のべき乗で十分な柔軟性があると想定しています)
バッファー サイズを実行時に選択できるようにするために、さまざまなアプローチを試し (ここには示していません)、FIFO バッファーを管理できる Head、Tail、EleKnt の USHRT を使用することにしました [USHRT]。モジュロ演算を避けるために、Head、Tail で &&するマスクを作成しましたが、そのマスクは (EleKnt -1) であることが判明したので、そのまま使用してください。ビット整数の代わりに USHRTS を使用すると、静かなマシンでパフォーマンスが最大 15% 向上しました。 Intel CPU コアは常にバスよりも高速であるため、ビジー状態の共有マシンでは、データ構造をパッキングすると、競合する他のスレッドより先にロードして実行できます。トレードオフ。
バッファの実際のストレージは calloc() でヒープに割り当てられ、ポインタは構造体のベースにあるため、構造体とポインタはまったく同じアドレスを持つことに注意してください。 IE;レジスタを結合するために構造体アドレスにオフセットを追加する必要はありません。
同様に、バッファーの処理に付随するすべての変数は物理的にバッファーに隣接しており、同じ構造体にバインドされているため、コンパイラーは美しいアセンブリ言語を作成できます。アセンブリを表示するには、インライン最適化を強制終了する必要があります。そうしないと、無視されてしまいます。
あらゆるデータ型のポリモーフィズムをサポートするために、代入の代わりに memcpy() を使用しました。コンパイルごとに 1 つの確率変数タイプをサポートするだけの柔軟性が必要な場合、このコードは完全に機能します。
ポリモーフィズムの場合、タイプとそのストレージ要件を知る必要があります。記述子の DATA_DESC 配列は、QUEUE_DESC.pBuffer に入れられる各データを追跡する方法を提供し、適切に取得できるようにします。最大のデータ型のすべての要素を保持するのに十分な pBuffer メモリを割り当てますが、DATA_DESC.dBytes で特定のデータが実際に使用しているストレージの量を追跡します。別の方法は、ヒープ マネージャーを再発明することです。
つまり、QUEUE_DESC の UCHAR *pBuffer には、データ型とサイズを追跡するための並列コンパニオン配列があり、pBuffer 内のデータの格納場所は現在のままです。新しいメンバーは DATA_DESC *pDataDesc のようなものか、おそらく DATA_DESC DataDesc[2^BITS_ELE_KNT] のようなものになります。このような前方参照でコンパイラを打ち負かして送信する方法を見つけることができる場合です。このような状況では、Calloc() の方が常に柔軟です。
Q_Put(),Q_Get で memcpy() を実行しても、実際にコピーされるバイト数は、QUEUE_DESC.EleBytes ではなく、DATA_DESC.dBytes によって決まります。要素は、特定の put または get に対してすべて異なるタイプ/サイズである可能性があります。
このコードは速度とバッファ サイズの要件を満たし、6 つの異なるデータ型の要件を満たすように作成できると思います。多くのテスト フィクスチャを printf() ステートメントの形式で残したので、コードが適切に機能することを自分で確認できます (または確認できません)。乱数ジェネレーターは、ランダムな頭と尾の組み合わせに対してコードが機能することを示しています。
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;
}