提高C循环缓冲效率

Question

我想帮助提高循环缓冲区代码的效率。

我看了一下stackoverflow，发现（几乎）循环缓冲区的所有主题都是关于这种缓冲区的使用或循环缓冲区的基本实现。我真的需要有关如何使其超级高效的信息。

计划是将此缓冲器与STM32F4微控制器一起使用，该微控制器具有单个精确FPU。我计划大量使用write（）和readn（）函数。我们实际上只是在这里谈了几百万个电话，所以在这里刮几个时钟周期，确实会有所作为。

我将把最重要的代码放在这里，完整的缓冲区代码可以通过http://dl.dropbox.com/u/39710897/circular%20buffer.rar获得

任何人都可以向我提供一些关于如何提高此缓冲区效率的指示吗？

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

Answer 1

正如“Oli Charlesworth”建议的那样 - 如果你的缓冲区大小是2的幂，你就能简化一些事情。我想编写读/写函数体，这样意图就更清晰了。

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

一些解释。请注意，根本没有分支（if）。我们不会将数组索引限制为数组边界，而是将其与掩码进行AND运算。

Answer 2

如果您可以使缓冲区大小为2的幂，则可以使用无条件位掩码替换零检查。在大多数处理器上，这应该更快。

Answer 3

这可能看起来不那么优雅，但效率很高。通过指针访问结构元素占用了大量指令。为什么不完全删除结构并将buffer和writeIndex作为全局变量？这将大大减少你的readn和write功能的大小。

我在gcc中试过，这里是带有和没有结构的输出

结构

_write:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    movl    8(%ebp), %eax
    movl    16(%eax), %edx
    movl    12(%ebp), %eax
    movl    %eax, (%ecx,%edx,4)
    movl    8(%ebp), %eax
    incl    16(%eax)
    movl    8(%ebp), %eax
    cmpl    $3, 16(%eax)
    jne L1
    movl    8(%ebp), %eax
    movl    $0, 16(%eax)
L1:
    popl    %ebp
    ret

没有结构。即使buffer和writeIndex成为全球性的

_write:
    pushl   %ebp
    movl    %esp, %ebp
    movl    _writeIndex, %edx
    movl    8(%ebp), %eax
    movl    %eax, _buff(,%edx,4)
    incl    _writeIndex
    cmpl    $3, _writeIndex
    jne L1
    movl    $0, _writeIndex
L1:
    popl    %ebp
    ret

Answer 4

使用指针跟踪循环缓冲区的开始和结束可能比数组索引快一点，因为在后者的情况下，地址将在运行时计算。尝试用float*替换readIndex和writeIndex。那么代码就是

*buffer->writeIndex = value;
buffer->writeIndex++;
if(buffer->writeIndex == buffer + BUFF_SIZE)
  buffer->writeIndex=buffer->buff;

buffer + BUFF_SIZE仍然是一个常量表达式，编译器会在编译时将其转换为固定地址。

Answer 5

接受的答案包含不正确的代码，并将调用未定义的行为。更正如下：

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

原始答案中的错误是假设'int'将会回绕。使用带有int的二进制掩码也是不明智的。