Повышение эффективности кольцевого буфера C

Я хотел бы помочь улучшить эффективность моего кода циклического буфера.

Я осмотрел stackru и обнаружил, что (почти) все темы циклических буферов касаются использования такого буфера или базовой реализации циклического буфера. Мне действительно нужна информация о том, как сделать его супер эффективным.

План состоит в том, чтобы использовать этот буфер с микроконтроллером 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];
}
Источник

4 ответа

Решение

Как предположил "Оли Чарльзуорт" - вы могли бы упростить вещи, если бы размер буфера был степенью 2. Я хотел бы написать тела функций чтения / записи, чтобы цель была более ясной.

#define BUFF_SIZE 4
#define BUFF_SIZE_MASK (BUFF_SIZE-1)

typedef struct buffer{
    float buff[BUFF_SIZE];
    int writeIndex;
}buffer;

void write(buffer* buffer,float value){
    buffer->buff[(buffer->writeIndex++) & BUFF_SIZE_MASK] = value;
}

float readn(buffer* buffer, int Xn){
    return buffer->buff[(buffer->writeIndex + (~Xn)) & BUFF_SIZE_MASK];
}

Несколько объяснений. Обратите внимание, что нет разветвления (if) совсем. Мы не ограничиваем индекс массива границами массива, вместо этого мы используем И маску.

В readn вместо расчета индекса доступа как

writeIndex - (Xn+1)

мы используем:

writeIndex + (~Xn)

Это работает, предполагая арифметику с 2 дополнениями. То есть, чтобы сделать целое число отрицательным, мы делаем НЕ для всех его битов, а затем добавляем 1. Но так как вы хотите вычесть 1 из числа - делать просто НЕ - это все, что нужно.

Источник

Если вы можете сделать размер буфера степенью 2, то проверка на ноль может быть заменена безусловной битовой маскировкой. На большинстве процессоров это должно быть быстрее.

Источник

Это может показаться не элегантным, но эффективным. Доступ к элементам структуры через указатель занимает много инструкций. Почему бы не удалить структуру вообще и сделать 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
Источник

Отслеживание начала и конца циклического буфера с помощью указателей, вероятно, немного быстрее, чем индексирование массива, поскольку в случае последнего адрес будет вычисляться во время выполнения. Попробуйте заменить readIndex и writeIndex на float* вместо. Код будет тогда

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

buffer + BUFF_SIZE останется постоянным выражением, и компилятор переведет его на фиксированный адрес во время компиляции.

Источник

Принятый ответ содержит неверный код и вызовет неопределенное поведение. Исправление ниже:

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

Ошибка в исходном ответе состояла в том, что предполагалось, что in t будет меняться. Использование двоичных масок с in t также неразумно.

Источник
Другие вопросы по тегам