miglioramento dell'efficienza del buffer circolare C

Question

Vorrei aiuto per migliorare l'efficienza del mio codice buffer circolare.

Ho dato un'occhiata allo stackoverflow e ho scoperto che (quasi) tutti gli argomenti sui buffer circolari riguardano gli usi di tale buffer o l'implementazione di base di un buffer circolare. Ho davvero bisogno di informazioni su come renderlo super efficiente.

Il piano prevede l'utilizzo di questo buffer con il microcontrollore STM32F4 che ha una FPU a precettore singolo. Ho intenzione di fare un uso pesante soprattutto delle funzioni write() e readn(). Stiamo letteralmente parlando di qualche milione di chiamate al secondo qui, quindi la rasatura di alcuni cicli di clock qui e là farà davvero la differenza.

metterò i pezzi più importanti di codice qui, il codice di buffer completo è disponibile tramite http://dl.dropbox.com/u/39710897/circular%20buffer.rar

Qualcuno può fornirmi alcune indicazioni su come migliorare l'efficienza di questo 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]; 
} 

Answer 1

Come suggerito da "Oli Charlesworth", sarebbe possibile semplificare le cose se la dimensione del buffer è la potenza di 2. Vorrei scrivere i corpi delle funzioni di lettura/scrittura, in modo che l'intento sia più chiaro.

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

Alcune spiegazioni. Si noti che non vi è alcuna diramazione (if). Non limitiamo l'indice dell'array ai limiti dell'array, ma lo stiamo AND-ing con la maschera.

In readn invece di calcolare l'indice di accesso come

writeIndex - (Xn+1)

stiamo usando:

writeIndex + (~Xn)

questo funziona assumendo 2-complemento aritmetica. Cioè, per rendere negativo il numero intero, NON facciamo tutti i suoi bit, e quindi aggiungiamo 1. Ma poiché vuoi sottrarre 1 dal numero - fare solo NOT è tutto ciò che è necessario.

Answer 2

Se potete fare la vostra dimensione del buffer un power-di-2, quindi il controllo contro zero può essere sostituito con incondizionata bit-mascheramento. Nella maggior parte dei processori, dovrebbe essere più veloce.

Answer 3

Questo potrebbe non sembrare elegante ma efficiente. L'accesso agli elementi della struttura tramite il puntatore richiede molte istruzioni. Perché non rimuovere la struttura del tutto e rendere buffer e writeIndex come variabili globali? Ciò ridurrà notevolmente le dimensioni delle tue funzioni readn e write.

ho provato in gcc e qui è l'uscita con e senza la struttura

Con Struttura

_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 

senza struttura.cioè Rendere buffer e writeIndex come globale

_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

Tenere traccia di inizio e la fine del buffer circolare con puntatori, è probabilmente un po 'più veloce di matrice indicizzazione, poiché l'indirizzo verrà calcolato in runtime in caso di quest'ultimo. Prova a sostituire readIndex e writeIndex con float*. Il codice sarebbe allora

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

buffer + BUFF_SIZE sarà ancora un'espressione costante e il compilatore tradurrà che ad un indirizzo fisso in fase di compilazione.