c - आप सी में गोलाकार बफर कैसे कार्यान्वित करते हैं?




data-structures circular-buffer (5)

एक सरल कार्यान्वयन में शामिल हो सकता है:

  • एक बफर, आकार की एक सरणी के रूप में लागू किया गया है, जो भी आपको चाहिए
  • एक पठन सूचक या सूचकांक (जो भी आपके प्रोसेसर के लिए अधिक कुशल है)
  • एक लिखने सूचक या सूचकांक
  • एक काउंटर इंगित करता है कि बफर में कितना डेटा है (पढ़ने और लिखने वाले पॉइंटर्स से व्युत्पन्न, लेकिन इसे अलग से ट्रैक करने के लिए तेज़)

हर बार जब आप डेटा लिखते हैं, तो आप लिखने वाले पॉइंटर को अग्रिम करते हैं और काउंटर को बढ़ाते हैं। जब आप डेटा पढ़ते हैं, तो आप पठन पॉइंटर बढ़ाते हैं और काउंटर को कम करते हैं। यदि कोई सूचक n तक पहुंचता है, तो इसे शून्य पर सेट करें।

काउंटर = एन अगर आप लिख नहीं सकते हैं। काउंटर = 0 अगर आप पढ़ नहीं सकते हैं।

मुझे एक निश्चित आकार की आवश्यकता है (इसे बनाने के दौरान रन-टाइम पर चयन योग्य, संकलन-समय नहीं) परिपत्र बफर जो किसी भी प्रकार की वस्तुओं को पकड़ सकता है और इसे बहुत अधिक प्रदर्शन की आवश्यकता होती है। मुझे नहीं लगता कि संसाधन विवाद के मुद्दे होंगे क्योंकि यह एक बहु-कार्यरत एम्बेडेड वातावरण में है, यह एक सहकारी है इसलिए कार्य स्वयं इसे प्रबंधित कर सकते हैं।

मेरा प्रारंभिक विचार बफर में एक साधारण संरचना को स्टोर करना था जिसमें टाइप (सरल एनम / परिभाषित) और पेलोड के लिए एक शून्य सूचक शामिल होगा, लेकिन मैं इसे जितना तेज़ हो सकता हूं, इसलिए मैं उन सुझावों के लिए खुला हूं जिनमें बाईपासिंग शामिल है ढेर

दरअसल, मुझे कच्ची गति के लिए किसी भी मानक लाइब्रेरी को बाईपास करने में प्रसन्नता हो रही है - जो मैंने कोड के बारे में देखा है, उसे सीपीयू के लिए अत्यधिक अनुकूलित नहीं किया गया है: ऐसा लगता है कि उन्होंने strcpy() और इस तरह की चीजों के लिए सी कोड संकलित किया है। , कोई हाथ कोडित असेंबली नहीं है।

किसी भी कोड या विचारों की सराहना की जाएगी। आवश्यक संचालन हैं:

  • विशिष्ट आकार के साथ एक बफर बनाएँ।
  • पूंछ पर रखो।
  • सिर से निकल जाओ।
  • गिनती वापस करो।
  • एक बफर हटाएं।

क्या आप बफर को कोड करते समय आवश्यक प्रकारों की गणना कर सकते हैं, या क्या आपको गतिशील कॉल के माध्यम से रन टाइम पर प्रकार जोड़ने में सक्षम होना चाहिए? यदि पूर्व, तो मैं बफर को एन structs के ढेर-आवंटित सरणी के रूप में बनाउंगा, जहां प्रत्येक संरचना में दो तत्व होते हैं: डेटा प्रकार की पहचान करने वाला एक enum टैग, और सभी डेटा प्रकारों का एक संघ। छोटे तत्वों के लिए अतिरिक्त भंडारण के मामले में आप क्या खोते हैं, आप आवंटन / विलोपन और परिणामी स्मृति विखंडन से निपटने के मामले में नहीं बनाते हैं। फिर आपको केवल शुरुआत और अंत सूचकांक का ट्रैक रखने की आवश्यकता है जो बफर के सिर और पूंछ तत्वों को परिभाषित करते हैं, और सूचकांक में वृद्धि / घटते समय मॉड एन की गणना करना सुनिश्चित करें।


सबसे आसान समाधान आइटम आकार और वस्तुओं की संख्या का ट्रैक रखना होगा, और उसके बाद उचित बाइट्स का बफर बनाएं:

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--;
}

सबसे पहले, शीर्षक। यदि आप सिर और पूंछ "पॉइंटर्स" को पकड़ने के लिए बिट इंट्स का उपयोग करते हैं, तो उन्हें बफर को लपेटने के लिए मॉड्यूलो अंकगणित की आवश्यकता नहीं है, और उन्हें आकार दें ताकि वे पूरी तरह से synch में हैं। आईई: 4096 एक 12-बिट unsigned int में भरा हुआ है 0 सभी अपने आप से, किसी भी तरह से unmestested। मॉड्यूलो अंकगणित को खत्म करना, यहां तक ​​कि 2 की शक्तियों के लिए, गति को दोगुना करना - लगभग बिल्कुल।

किसी भी प्रकार के डेटा तत्वों के 4096 बफर को भरने और निकालने के 10 मिलियन पुनरावृत्तियों में मेरे तीसरे जनरल आई 7 डेल एक्सपीएस 8500 पर विजुअल स्टूडियो 2010 के सी ++ कंपाइलर का उपयोग करके डिफ़ॉल्ट इनलाइनिंग के साथ 52 सेकंड और 1/8192 वें डाटाम की सेवा करने के लिए 52 सेकंड लगते हैं।

मैं आरएक्स मुख्य () में टेस्ट लूप को फिर से लिखना चाहता हूं, इसलिए वे अब प्रवाह को नियंत्रित नहीं करते हैं - जो कि बफर पूर्ण या खाली है, और परिचर तोड़ने वाले संकेत मूल्यों द्वारा नियंत्रित किया जाना चाहिए; बयान। आईई: भराव और नालीदार भ्रष्टाचार या अस्थिरता के बिना एक-दूसरे के खिलाफ धमाके करने में सक्षम होना चाहिए। किसी बिंदु पर मैं इस कोड को बहु-थ्रेड करने की आशा करता हूं, जहां वह व्यवहार महत्वपूर्ण होगा।

QUEUE_DESC (कतार वर्णनकर्ता) और प्रारंभिक कार्य इस कोड में सभी बफर को 2 की शक्ति के लिए मजबूर करता है। उपर्युक्त योजना अन्यथा काम नहीं करेगी। विषय पर रहते हुए, ध्यान दें कि QUEUE_DESC हार्ड-कोड नहीं है, यह इसके निर्माण के लिए एक मैनिफेस्ट निरंतर (# परिभाषित BITS_ELE_KNT) का उपयोग करता है। (मुझे लगता है कि 2 की शक्ति यहां पर्याप्त लचीलापन है)

बफर आकार रन-टाइम चुनने योग्य बनाने के लिए, मैंने विभिन्न दृष्टिकोणों (यहां दिखाया नहीं गया) की कोशिश की, और फीफो बफर [यूएसएचआरटी] के प्रबंधन में सक्षम हेड, टेल, एलीकेन्ट के लिए यूएसएचआरटी का उपयोग करने पर बस गए। मॉड्यूलो अंकगणितीय से बचने के लिए मैंने हेड, टेल के साथ && पर एक मुखौटा बनाया, लेकिन वह मुखौटा (EleKnt -1) हो गया, इसलिए बस इसका उपयोग करें। बिट इनट्स के बजाय यूएसएचआरटीएस का उपयोग शांत मशीन पर प्रदर्शन ~ 15% बढ़ा। इंटेल सीपीयू कोर हमेशा अपनी बसों की तुलना में तेज़ होते हैं, इसलिए एक व्यस्त, साझा मशीन पर, आपके डेटा संरचनाओं को पैक करने से आप लोड हो जाते हैं और अन्य प्रतिस्पर्धी धागे से आगे बढ़ते हैं। व्यापार नापसंद।

ध्यान दें कि बफर के लिए वास्तविक भंडारण कॉलोक () के साथ ढेर पर आवंटित किया गया है, और सूचक संरचना के आधार पर है, इसलिए संरचना और सूचक के पास बिल्कुल वही पता है। अर्थात; रजिस्टरों को बांधने के लिए स्ट्रक्चर पते में कोई ऑफसेट जोड़ने की आवश्यकता नहीं है।

उसी नस में, बफर की सेवा के साथ सभी चर परिचर भौतिक रूप से बफर के समीप होते हैं, जो एक ही संरचना में बंधे होते हैं, इसलिए संकलक सुंदर असेंबली भाषा बना सकता है। किसी भी असेंबली को देखने के लिए आपको इनलाइन ऑप्टिमाइज़ेशन को मारना होगा, अन्यथा यह विस्मरण में कुचल जाता है।

किसी भी डेटा प्रकार के बहुरूपता का समर्थन करने के लिए, मैंने असाइनमेंट के बजाय memcpy () का उपयोग किया है। यदि आपको प्रति संकलन एक यादृच्छिक चर प्रकार का समर्थन करने के लिए केवल लचीलापन की आवश्यकता है, तो यह कोड पूरी तरह से काम करता है।

बहुरूपता के लिए, आपको केवल प्रकार और इसकी संग्रहण आवश्यकता जानने की आवश्यकता है। वर्णनकर्ताओं की DATA_DESC सरणी QUEUE_DESC.pBuffer में रखे गए प्रत्येक डेटाम का ट्रैक रखने का एक तरीका प्रदान करती है ताकि इसे ठीक से पुनर्प्राप्त किया जा सके। मैं केवल सबसे बड़े डेटा प्रकार के सभी तत्वों को पकड़ने के लिए पर्याप्त पीबीफर मेमोरी आवंटित करता हूं, लेकिन उस डेटा का कितना भंडारण वास्तव में DATA_DESC.dBytes में उपयोग किया जाता है इसका ट्रैक रखें। विकल्प एक ढेर प्रबंधक को फिर से शुरू करना है।

इसका मतलब है कि QUEUE_DESC के UCHAR * pBuffer में डेटा प्रकार और आकार का ट्रैक रखने के लिए समानांतर साथी सरणी होगी, जबकि पीबीफर में डेटाम का संग्रहण स्थान अभी भी उतना ही रहेगा। नया सदस्य DATA_DESC * pDataDesc, या शायद, DATA_DESC DataDesc [2 ^ BITS_ELE_KNT] जैसा होगा यदि आप अपने कंपाइलर को ऐसे आगे संदर्भ के साथ प्रस्तुत करने का कोई तरीका ढूंढ सकें। इन परिस्थितियों में Calloc () हमेशा अधिक लचीला है।

आप अभी भी Q_Put (), Q_Get में memcpy () करेंगे, लेकिन वास्तव में कॉपी किए गए बाइट्स की संख्या 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;
}

// 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;
}

जब तक आपकी अंगूठी बफर की लंबाई दो की शक्ति होती है, तब तक अविश्वसनीय रूप से तेज़ बाइनरी "&" ऑपरेशन आपके सूचकांक के चारों ओर लपेट जाएगा। मेरे आवेदन के लिए, मैं माइक्रोफ़ोन से प्राप्त ऑडियो के रिंग बफर से उपयोगकर्ता को ऑडियो का एक सेगमेंट प्रदर्शित कर रहा हूं।

मैं हमेशा यह सुनिश्चित करता हूं कि स्क्रीन पर प्रदर्शित होने वाली अधिकतम मात्रा में रिंग बफर के आकार से बहुत कम है। अन्यथा आप एक ही हिस्से से पढ़ और लिख सकते हैं। यह आपको अजीब प्रदर्शन कलाकृतियों की संभावना होगी।





circular-buffer