كيف يمكنك تنفيذ مخزن مؤقت دائري في لغة C؟
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحتاج إلى مخزن مؤقت دائري ذو حجم ثابت (يمكن تحديده في وقت التشغيل عند إنشائه، وليس وقت الترجمة) يمكنه الاحتفاظ بالكائنات من أي نوع ويجب أن يكون جداً أداء عالي.لا أعتقد أنه ستكون هناك مشكلات تتعلق بالتنافس على الموارد نظرًا لأنه على الرغم من وجوده في بيئة مضمنة متعددة المهام، إلا أنه بيئة تعاونية لذا يمكن للمهام نفسها إدارة ذلك.
كانت فكرتي الأولية هي تخزين بنية بسيطة في المخزن المؤقت والتي قد تحتوي على النوع (التعداد/التعريف البسيط) ومؤشر فارغ للحمولة النافعة ولكني أريد أن يكون هذا في أسرع وقت ممكن لذا فأنا منفتح على الاقتراحات التي تتضمن تجاوز الكومة.
في الواقع، يسعدني تجاوز أي من المكتبات القياسية للسرعة الأولية - مما رأيته من الكود، فهو ليس مُحسّنًا بشكل كبير لوحدة المعالجة المركزية:يبدو أنهم قاموا للتو بتجميع كود C لأشياء مثل strcpy() وهكذا، لا يوجد تجميع مشفر يدويًا.
سيكون موضع تقدير كبير أي رمز أو أفكار.العمليات المطلوبة هي:
- إنشاء مخزن مؤقت بحجم محدد.
- وضعت في الذيل.
- الحصول على من الرأس.
- إرجاع العد.
- حذف المخزن المؤقت.
المحلول
هل يمكنك تعداد الأنواع المطلوبة في الوقت الذي تقوم فيه بترميز المخزن المؤقت، أم أنك بحاجة إلى أن تكون قادرًا على إضافة أنواع في وقت التشغيل عبر الاستدعاءات الديناميكية؟إذا كان الأول، فسأقوم بإنشاء المخزن المؤقت كمصفوفة مخصصة من بنيات n، حيث تتكون كل بنية من عنصرين:علامة التعداد التي تحدد نوع البيانات، واتحاد كافة أنواع البيانات.ما تخسره من حيث التخزين الإضافي للعناصر الصغيرة، تعوضه من حيث عدم الاضطرار إلى التعامل مع التخصيص/إلغاء التخصيص وتجزئة الذاكرة الناتجة.ثم تحتاج فقط إلى تتبع مؤشرات البداية والنهاية التي تحدد عناصر الرأس والذيل للمخزن المؤقت، والتأكد من حساب mod n عند زيادة/تناقص المؤشرات.
نصائح أخرى
الحل الأبسط هو تتبع حجم العنصر وعدد العناصر، ثم إنشاء مخزن مؤقت بالعدد المناسب من البايتات:
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;
}
طالما أن طول المخزن المؤقت الحلقي الخاص بك هو قوة اثنين، فإن العملية الثنائية السريعة بشكل لا يصدق "&" سوف تلتف حول الفهرس الخاص بك.بالنسبة لتطبيقي، أقوم بعرض جزء من الصوت للمستخدم من المخزن المؤقت الحلقي للصوت الذي تم الحصول عليه من الميكروفون.
أتأكد دائمًا من أن الحد الأقصى لمقدار الصوت الذي يمكن عرضه على الشاشة أقل بكثير من حجم المخزن المؤقت للحلقة.وإلا فقد تكون تقرأ وتكتب من نفس القطعة.من المحتمل أن يمنحك هذا قطعًا أثرية غريبة.
أولا، العنوان.لا تحتاج إلى حساب modulo لتغليف المخزن المؤقت إذا كنت تستخدم وحدات البت للاحتفاظ بـ "مؤشرات" الرأس والذيل، وحجمها بحيث تكون متزامنة تمامًا.أي:4096 المحشو في int غير الموقع ذو 12 بت هو 0 في حد ذاته، وغير مضايق بأي شكل من الأشكال.يؤدي التخلص من الحساب المعياري، حتى بالنسبة لقوى العدد 2، إلى مضاعفة السرعة - تمامًا تقريبًا.
10 ملايين تكرار لملء واستنزاف مخزن مؤقت 4096 لأي نوع من عناصر البيانات يستغرق 52 ثانية على الجيل الثالث i7 Dell XPS 8500 باستخدام مترجم Visual Studio 2010's C++ مع التضمين الافتراضي، و1/8192 من ذلك لخدمة مسند الإسناد.
سأقوم بإعادة كتابة حلقات الاختبار في main() بحيث لم تعد تتحكم في التدفق - والذي يجب أن يتم التحكم فيه من خلال القيم المرجعة التي تشير إلى أن المخزن المؤقت ممتلئ أو فارغ، والفاصل المصاحب؛صياغات.أي:يجب أن يكون الحشو والمجفف قادرين على الاصطدام ببعضهما البعض دون تلف أو عدم استقرار.في مرحلة ما، آمل أن أقوم بدمج هذا الكود في عدة سلاسل، وعندها سيكون هذا السلوك حاسمًا.
تعمل وظيفة QUEUE_DESC (واصف قائمة الانتظار) ووظيفة التهيئة على فرض أن تكون جميع المخازن المؤقتة في هذا الرمز ذات قوة 2.لن يعمل المخطط أعلاه بطريقة أخرى.أثناء الحديث عن هذا الموضوع، لاحظ أن QUEUE_DESC ليس مشفرًا بشكل ثابت، فهو يستخدم ثابت البيان (#define BITS_ELE_KNT) لبنائه.(أفترض أن قوة 2 هي مرونة كافية هنا)
لجعل حجم المخزن المؤقت قابلاً للتحديد أثناء التشغيل، جربت طرقًا مختلفة (غير موضحة هنا)، واستقرت على استخدام USHRTs لـ Head وTail وEleKnt القادرة على إدارة المخزن المؤقت FIFO [USHRT].لتجنب حساب modulo، قمت بإنشاء قناع لـ && باستخدام Head وTail، ولكن تبين أن هذا القناع هو (EleKnt -1)، لذا استخدمه فقط.يؤدي استخدام USHRTS بدلاً من bit int إلى زيادة الأداء بنسبة 15% تقريبًا على جهاز هادئ.لقد كانت نوى وحدة المعالجة المركزية Intel دائمًا أسرع من نواقلها، لذا في جهاز مشترك مزدحم، فإن تعبئة هياكل البيانات الخاصة بك تجعلك تقوم بالتحميل والتنفيذ قبل سلاسل العمليات الأخرى المنافسة.المقايضات.
لاحظ أن التخزين الفعلي للمخزن المؤقت مخصص على الكومة باستخدام calloc()، ويكون المؤشر في قاعدة البنية، لذا فإن البنية والمؤشر لهما نفس العنوان تمامًا.أي؛لا يلزم إضافة إزاحة إلى عنوان البنية لربط السجلات.
وعلى نفس المنوال، فإن جميع المتغيرات المصاحبة لخدمة المخزن المؤقت تكون مجاورة فعليًا للمخزن المؤقت، ومرتبطة بنفس البنية، لذلك يمكن للمترجم إنشاء لغة تجميع جميلة.سيتعين عليك إيقاف التحسين المضمن لرؤية أي تجميع، وإلا فسيتم سحقه في غياهب النسيان.
لدعم تعدد الأشكال لأي نوع بيانات، استخدمت memcpy() بدلاً من المهام.إذا كنت تحتاج فقط إلى المرونة لدعم نوع متغير عشوائي واحد لكل ترجمة، فإن هذا الرمز يعمل بشكل مثالي.
بالنسبة لتعدد الأشكال، تحتاج فقط إلى معرفة النوع ومتطلبات تخزينه.توفر مجموعة الواصفات DATA_DESC طريقة لتتبع كل مرجع مرجعي يتم وضعه في QUEUE_DESC.pBuffer حتى يمكن استرجاعه بشكل صحيح.أود فقط تخصيص ذاكرة pBuffer كافية لاستيعاب كافة العناصر الخاصة بأكبر نوع من البيانات، ولكن تابع مقدار مساحة التخزين التي يستخدمها مسند معين فعليًا في DATA_DESC.dBytes.البديل هو إعادة اختراع مدير الكومة.
وهذا يعني أن UCHAR *pBuffer الخاص بـ QUEUE_DESC سيكون له مصفوفة مصاحبة متوازية لتتبع نوع البيانات وحجمها، بينما سيظل موقع تخزين مسند الإسناد في pBuffer كما هو الآن.سيكون العضو الجديد شيئًا مثل DATA_DESC *pDataDesc، أو ربما DATA_DESC DataDesc[2^BITS_ELE_KNT] إذا كان بإمكانك العثور على طريقة للتغلب على المترجم الخاص بك في الإرسال باستخدام مثل هذا المرجع الأمامي.Calloc() دائمًا أكثر مرونة في هذه المواقف.
لا يزال بإمكانك استخدام memcpy() في Q_Put(),Q_Get، ولكن سيتم تحديد عدد البايتات المنسوخة فعليًا بواسطة DATA_DESC.dBytes، وليس QUEUE_DESC.EleBytes.من المحتمل أن تكون جميع العناصر من أنواع/أحجام مختلفة لأي وضع أو الحصول عليها.
أعتقد أن هذا الكود يلبي متطلبات السرعة وحجم المخزن المؤقت، ويمكن تصميمه لتلبية متطلبات 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;
}
هنا حل بسيط في C.افترض أنه تم إيقاف تشغيل المقاطعات لكل وظيفة.لا يوجد تعدد الأشكال والأشياء، فقط المنطق السليم.
#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
}
يمكن أن يتكون التنفيذ البسيط من:
- مخزن مؤقت، يتم تنفيذه كمصفوفة بالحجم n، من أي نوع تحتاجه
- مؤشر القراءة أو الفهرس (أيهما أكثر كفاءة لمعالجك)
- مؤشر الكتابة أو الفهرس
- عداد يشير إلى كمية البيانات الموجودة في المخزن المؤقت (يمكن استخلاصها من مؤشرات القراءة والكتابة، ولكن من الأسرع تتبعها بشكل منفصل)
في كل مرة تكتب فيها بيانات، تقوم بتقديم مؤشر الكتابة وزيادة العداد.عند قراءة البيانات، يمكنك زيادة مؤشر القراءة وتقليل العداد.إذا وصل أي من المؤشرين إلى n، فاضبطه على صفر.
لا يمكنك الكتابة إذا كان العداد = n.لا يمكنك القراءة إذا كان العداد = 0.
نمط C، عازلة حلقة بسيطة للأعداد الصحيحة.استخدم init أولاً بدلاً من استخدام put و get.إذا لم يحتوي المخزن المؤقت على أية بيانات فإنه يُرجع "0" صفر.
//=====================================
// 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;
}
