I'd like some help improving the efficiency of my circular buffer code.
I had a look around stackoverflow and found that (nearly) all of the topics on circular buffers are about the uses of such a buffer or the basic implementation of a circular buffer. I really need information about how to make it super efficient.
The plan is to use this buffer with the STM32F4 microcontroller which has a single precicion FPU. I plan to make heavy use of especially the write() and readn() functions. We're literally talking a few million calls a second here so shaving of a few clock cycles here and there is really going to make a difference.
I'll put the most important bits of code here, the full buffer code is available via http://dl.dropbox.com/u/39710897/circular%20buffer.rar
Can anyone provide me with a few pointers on how to improve the efficiency of this buffer?
#define BUFF_SIZE 3 // buffer size set at compile time
typedef struct buffer{
float buff[BUFF_SIZE];
int readIndex;
int writeIndex;
}buffer;
/********************************\
* void write(buffer* buffer, float value)
* writes value into the buffer
* @param buffer* buffer
* pointer to buffer to be used
* @param float value
* valueto be written in buffer
\********************************/
void write(buffer* buffer,float value){
buffer->buff[buffer->writeIndex]=value;
buffer->writeIndex++;
if(buffer->writeIndex==BUFF_SIZE)
buffer->writeIndex=0;
}
/********************************\
* float readn(buffer* buffer, int Xn)
* reads specified value from buffer
* @param buffer* buffer
* pointer to buffer to be read from
* @param int Xn
* specifies the value to be read from buffer counting backwards from the most recently written value
* i.e. the most recently writen value can be read with readn(buffer, 0), the value written before that with readn(buffer, 1)
\********************************/
float readn(buffer* buffer, int Xn){
int tempIndex;
tempIndex=buffer->writeIndex-(Xn+1);
while(tempIndex<0){
tempIndex+=BUFF_SIZE;
}
return buffer->buff[tempIndex];
}
As "Oli Charlesworth" suggested - you'd be able to simplify things if your buffer size is a power of 2. I'd like to write the read/write function bodies, so that the intent is more clear.
#define BUFF_SIZE (4U)
#define BUFF_SIZE_MASK (BUFF_SIZE-1U)
struct buffer {
float buff[BUFF_SIZE];
unsigned writeIndex;
};
void write(struct buffer *buffer, float value) {
buffer->buff[(++buffer->writeIndex) & BUFF_SIZE_MASK] = value;
}
float readn(struct buffer *buffer, unsigned Xn){
return buffer->buff[(buffer->writeIndex - Xn) & BUFF_SIZE_MASK];
}
Some explanations. Note that there's no branching (if
) at all. We don't limit the array index to the array bounds, instead we're AND-ing it with the mask.