Algoritmo simplificado para calcular el espacio restante en un búfer circular

Question

Me pregunto si hay una manera más simple (única) para calcular el espacio restante en un buffer circular que esto?

int remaining = (end > start) 
       ? end-start 
       : bufferSize - start + end; 

Answer 1

Si usted está preocupado acerca de los condicionales predichos mal que retrasan la tubería de la CPU, se puede usar esto:

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize); 

Pero eso es probable que sea la optimización prematura (a menos que haya identificado realmente esto como un punto de acceso) . Sigue con tu técnica actual, que es mucho más legible.

Answer 2

Pierde el condicional:

int remaining = (end + bufferSize - start - 1) % bufferSize + 1 

Editar: El -1 y +1 son para el caso en end == start. En ese caso, este método asumirá que el buffer está vacío. Dependiendo de la implementación específica de su búfer, es posible que deba ajustar estos para evitar una situación fuera de línea.

Answer 3

De acuerdo con el estándar de C++, la sección 5.6, párrafo 4:

El binario/operador produce el cociente, y el operador binario% produce el resto de la división de la primera expresión por el segundo. Si el segundo operando de/o% es cero, el comportamiento no está definido; de lo contrario (a/b) * b + a% b es igual a a. Si ambos operandos son no negativos, el resto no es negativo; si no, el signo del resto está definido por la implementación.

Una nota al pie sugiere que se prefiere redondear el cociente hacia cero, lo que dejaría el resto negativo.

Por lo tanto, los enfoques (end - start) % bufferSize no funcionan de manera confiable. C++ no tiene aritmética modular (excepto en el sentido ofrecido por los tipos integrales sin signo).

El enfoque recomendado por j_random_hacker es diferente, y se ve bien, pero no sé si es una mejora real en la simplicidad o la velocidad. La conversión de un booleano a int es ingeniosa, pero requiere un análisis mental, y ese toque puede ser más costoso que el uso de?:, Dependiendo del compilador y la máquina.

Creo que tienes la versión más simple y la mejor, y yo no la cambiaría.

Answer 4

Hmmm ....

int remaining = (end - start + bufferSize) % bufferSize; 

13 fichas, puedo ganar?

Answer 5

Si su tamaño de búfer circular es una potencia de dos, puede hacerlo aún mejor si start y end representan posiciones en una transmisión virtual en lugar de índices en el almacenamiento del búfer circular. Suponiendo que start y end están sin firmar, lo anterior se convierte en:

int remaining= bufferSize - (end - start); 

realmente conseguir elementos fuera de la memoria intermedia es un poco más complicado, pero el tamaño es suficiente por lo general pequeñas con una potencia de búfer circular de tamaño 2 (simplemente enmascarando con bufferSize - 1) para hacer que toda la otra lógica de su búfer circular sea mucho más simple y limpia.Además, puedes usar todos los elementos ya que ya no te preocupes por end==start.

Answer 6

Tema anterior Lo sé, pero pensé que esto podría ser útil.

No está seguro de lo rápido que este implementa en C++ pero en RTL hacemos esto si el tamaño es n^2

remaining = (end[n]^start[n]) 
      ? start[n-1:0] - end[n-1:0] 
      : end[n-1:0] - start[n-1:0]; 

o

remaining = if (end[n]^start[n]) { 
       start[n-1:0] - end[n-1:0] 
      } else { 
       end[n-1:0] - start[n-1:0] 
      };