¿Hay una manera más eficiente de obtener la longitud de un entero de 32 bits en bytes?

Question

Me gustaría un atajo para la siguiente función poco, donde rendimiento es muy importante (la función se llama más de 10.000.000 veces):

inline int len(uint32 val) 
{ 
    if(val <= 0x000000ff) return 1; 
    if(val <= 0x0000ffff) return 2; 
    if(val <= 0x00ffffff) return 3; 
    return 4; 
} 

¿Alguien tiene alguna idea ... un lugar fresco truco de bitoperación? ¡Gracias por su ayuda con anticipación!

Answer 1

¿Qué tal este?

inline int len(uint32 val) 
{ 
    return 4 
     - ((val & 0xff000000) == 0) 
     - ((val & 0xffff0000) == 0) 
     - ((val & 0xffffff00) == 0) 
    ; 
} 

Extracción de la palabra clave inline, g++ -O2 compila este código a la siguiente sin sucursales:

movl 8(%ebp), %edx 
movl %edx, %eax 
andl $-16777216, %eax 
cmpl $1, %eax 
sbbl %eax, %eax 
addl $4, %eax 
xorl %ecx, %ecx 
testl $-65536, %edx 
sete %cl 
subl %ecx, %eax 
andl $-256, %edx 
sete %dl 
movzbl %dl, %edx 
subl %edx, %eax 

Si no le importa soluciones específicas de la máquina, puede utilizar la instrucción bsr el que busca la primera 1 bit Entonces sólo tiene que divide por 8 para convertir los bits a bytes y agregar 1 para desplazar la gama 0..3 1..4 a:

int len(uint32 val) 
{ 
    asm("mov 8(%ebp), %eax"); 
    asm("or $255, %eax"); 
    asm("bsr %eax, %eax"); 
    asm("shr $3, %eax"); 
    asm("inc %eax"); 
    asm("mov %eax, 8(%ebp)"); 
    return val; 
} 

Tenga en cuenta que no soy un dios ensamblado en línea, así que tal vez hay una mejor a la solución para acceder al val en lugar de abordar la pila de forma explícita. Pero deberías obtener la idea básica.

El compilador GNU también tiene una interesante función integrada llamada __builtin_clz:

inline int len(uint32 val) 
{ 
    return ((__builtin_clz(val | 255)^31) >> 3) + 1; 
} 

Esto se ve mucho mejor que la versión en línea de montaje a mí :)

Answer 2

Si ops bits son más rápidos que la comparación en el equipo de destino se puede hacer esto:

inline int len(uint32 val) 
{ 
    if(val & 0xff000000) return 4; 
    if(val & 0x00ff0000) return 3; 
    if(val & 0x0000ff00) return 2; 
    return 1; 
} 

Answer 3

Puede evitar los saltos condicionales que pueden ser costoso si la distribución de los números no hace predicción fácil:

return 4 - (val <= 0x000000ff) - (val <= 0x0000ffff) - (val <= 0x00ffffff); 

Cambio de la <= a & no cambiará mucho en un procesador moderno. ¿Cuál es su plataforma objetivo?

Este es el código generado para x86-64 con gcc -O:

cmpl $255, %edi 
    setg %al 
    movzbl %al, %eax 
    addl $3, %eax 
    cmpl $65535, %edi 
    setle %dl 
    movzbl %dl, %edx 
    subl %edx, %eax 
    cmpl $16777215, %edi 
    setle %dl 
    movzbl %dl, %edx 
    subl %edx, %eax 

Hay instrucciones de comparación cmpl por supuesto, pero estos son seguidos por setg o setle en lugar de saltos condicionales (como sería habitual). Es la rama condicional que es costosa en un procesador moderno canalizado, no la comparación. Entonces esta versión ahorra las costosas ramas condicionales.

Mi intento de ensamblaje de la optimización de la mano de gcc:

cmpl $255, %edi 
    setg %al 
    addb $3, %al 
    cmpl $65535, %edi 
    setle %dl 
    subb %dl, %al 
    cmpl $16777215, %edi 
    setle %dl 
    subb %dl, %al 
    movzbl %al, %eax 

Answer 4

La búsqueda binaria salve a algunos ciclos, dependiendo de la arquitectura del procesador.

inline int len(uint32 val) 
{ 
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3; 
    return (val & 0x0000ff00)? 2: 1; 
} 

O, descubriendo que es el caso más común podría reducir el número promedio de ciclos, si la mayoría de las entradas son un byte (por ejemplo, en la construcción de codificaciones UTF-8, pero luego sus puntos de ruptura no sería 32/24/16/8):

inline int len(uint32 val) 
{ 
    if (val & 0xffffff00) { 
     if (val & 0xffff0000) { 
      if (val & 0xff000000) return 4; 
      return 3; 
     } 
     return 2; 
    } 
    return 1; 
} 

Ahora el caso corto hace la menor cantidad de pruebas condicionales.

Answer 5

Ok, una versión más. Similar al de Fred, pero con menos operaciones.

inline int len(uint32 val) 
{ 
    return 1 
     + (val > 0x000000ff) 
     + (val > 0x0000ffff) 
     + (val > 0x00ffffff) 
    ; 
} 

Answer 6

¿Realmente tiene pruebas de que este es un cuello de botella significativo en su aplicación? Simplemente hazlo de la manera más obvia y solo si el perfil muestra que es un problema (lo cual dudo), entonces intenta mejorar las cosas. Lo más probable es que obtenga la mejor mejoría al reducir la cantidad de llamadas a esta función que cambiando algo dentro de ella.

Answer 7

Esto le da menos comparaciones. Pero puede ser menos eficiente si la operación de acceso a la memoria cuesta más que un par de comparaciones.

int precalc[1<<16]; 
int precalchigh[1<<16]; 
void doprecalc() 
{ 
    for(int i = 0; i < 1<<16; i++) { 
     precalc[i] = (i < (1<<8) ? 1 : 2); 
     precalchigh[i] = precalc[i] + 2; 
    } 
} 
inline int len(uint32 val) 
{ 
    return (val & 0xffff0000 ? precalchigh[val >> 16] : precalc[val]); 
} 

Answer 8

lo hice un mini punto de referencia científico simplemente midiendo la diferencia en GetTickCount() llama al llamar a la función en un bucle de 0 a veces MAX_LONG bajo el compilador VS 2010.

Aquí es lo que vi:

Esto tomó 11497 garrapatas

inline int len(uint32 val) 
{ 
    if(val <= 0x000000ff) return 1; 
    if(val <= 0x0000ffff) return 2; 
    if(val <= 0x00ffffff) return 3; 
    return 4; 
} 

Si bien esto tomó 14399 garrapatas

inline int len(uint32 val) 
{ 
    return 4 
     - ((val & 0xff000000) == 0) 
     - ((val & 0xffff0000) == 0) 
     - ((val & 0xffffff00) == 0) 
    ; 
} 

edición: mi idea acerca de por qué uno era más rápido está mal porque:

inline int len(uint32 val) 
{ 
    return 1 
     + (val > 0x000000ff) 
     + (val > 0x0000ffff) 
     + (val > 0x00ffffff) 
     ; 
} 

Esta versión usó solo 11107 tics. Dado que + es más rápido que, ¿quizás? No estoy seguro.

Aún más rápido, aunque era la búsqueda binaria en 7161 garrapatas

inline int len(uint32 val) 
{ 
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3; 
    return (val & 0x0000ff00)? 2: 1; 
} 

y más rápida hasta el momento es el uso de la función intrínseca de MS, en 4399 garrapatas

#pragma intrinsic(_BitScanReverse) 

inline int len2(uint32 val) 
{ 
    DWORD index; 
    _BitScanReverse(&index, val); 

    return (index>>3)+1; 

} 

Como referencia - aquí está el código que utilicé al perfil:

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int j = 0; 
    DWORD t1,t2; 

    t1 = GetTickCount(); 

    for(ULONG i=0; i<-1; i++) 
     j=len(i); 

    t2 = GetTickCount(); 

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j); 


    t1 = GetTickCount(); 

    for(ULONG i=0; i<-1; i++) 
     j=len2(i); 

    t2 = GetTickCount(); 

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j); 
} 

Tuve que imprimir j para evitar que los bucles se optimicen fuera.

Answer 9

El número mínimo de bits de necesarios para almacenar un número entero es:

int minbits = (int)ceil(log10(n)/log10(2)) ; 

El número de bytes es:

int minbytes = (int)ceil(log10(n)/log10(2)/8) ; 

Esta es una solución totalmente FPU límite, el rendimiento puede o puede que no sea mejor que una prueba condicional, pero tal vez valga la pena investigarla.

[EDITAR] Hice la investigación; un bucle simple de diez millones de iteraciones de lo anterior tomó 918ms, mientras que la solución aceptada de FredOverflow tomó solo 49ms (VC++ 2010). Por lo tanto, esta no es una mejora en términos de rendimiento, aunque puede seguir siendo útil si fuera la cantidad de bits necesaria, y es posible realizar más optimizaciones.

Answer 10

Solo para ilustrar, basado en la respuesta de FredOverflow (que es buen trabajo, felicitaciones y +1), una trampa común con respecto a las sucursales en x86. Aquí está la asamblea de FredOverflow como salida por gcc:

movl 8(%ebp), %edx #1/.5 
movl %edx, %eax  #1/.5 
andl $-16777216, %eax#1/.5 
cmpl $1, %eax  #1/.5 
sbbl %eax, %eax  #8/6 
addl $4, %eax  #1/.5 
xorl %ecx, %ecx  #1/.5 
testl $-65536, %edx #1/.5 
sete %cl    #5 
subl %ecx, %eax  #1/.5 
andl $-256, %edx  #1/.5 
sete %dl    #5 
movzbl %dl, %edx  #1/.5 
subl %edx, %eax  #1/.5 
# sum total: 29/21.5 cycles 

(la latencia, en ciclos, se ha de leer como Prescott/Northwood)

conjunto optimizado a mano (también kudos) de Pascal Cuoq:

cmpl $255, %edi  #1/.5 
setg %al    #5 
addb $3, %al   #1/.5 
cmpl $65535, %edi #1/.5 
setle %dl    #5 
subb %dl, %al  #1/.5 
cmpl $16777215, %edi #1/.5 
setle %dl    #5 
subb %dl, %al  #1/.5 
movzbl %al, %eax  #1/.5 
# sum total: 22/18.5 cycles 

Editar: la solución de FredOverflow usando __builtin_clz():

movl 8(%ebp), %eax #1/.5 
popl %ebp   #1.5 
orb $-1, %al  #1/.5 
bsrl %eax, %eax  #16/8 
sarl $3, %eax  #1/4 
addl $1, %eax  #1/.5 
ret 
# sum total: 20/13.5 cycles 

una nd el conjunto de gcc para su código:

movl $1, %eax  #1/.5 
movl %esp, %ebp  #1/.5 
movl 8(%ebp), %edx #1/.5 
cmpl $255, %edx  #1/.5 
jbe .L3    #up to 9 cycles 
cmpl $65535, %edx #1/.5 
movb $2, %al   #1/.5 
jbe .L3    #up to 9 cycles 
cmpl $16777216, %edx #1/.5 
sbbl %eax, %eax  #8/6 
addl $4, %eax  #1/.5 
.L3: 
ret 
# sum total: 16/10 cycles - 34/28 cycles 

en la que va a buscar la línea de caché de instrucciones que vienen como el efecto secundario de las instrucciones jcc tal vez le cueste nada para una función tan corto.

Las sucursales pueden ser una elección razonable, dependiendo de la distribución de entrada.

Editar: se agregó la solución de FredOverflow que está usando __builtin_clz().

Answer 11

En algunos sistemas, esto podría ser más rápido en algunas arquitecturas:

inline int len(uint32_t val) { 
    return (int)(log(val)/log(256)); // this is the log base 256 of val 
} 

Esto también puede ser un poco más rápido (si la comparación lleva más tiempo que a nivel de bits y):

inline int len(uint32_t val) { 
    if (val & ~0x00FFffFF) { 
     return 4; 
    if (val & ~0x0000ffFF) { 
     return 3; 
    } 
    if (val & ~0x000000FF) { 
     return 2; 
    } 
    return 1; 

}

Si tiene un microcontrolador de 8 bits (como un 8051 o AVR), esto funcionará mejor:

inline int len(uint32_t val) { 
    union int_char { 
      uint32_t u; 
      uint8_t a[4]; 
    } x; 
    x.u = val; // doing it this way rather than taking the address of val often prevents 
       // the compiler from doing dumb things. 
    if (x.a[0]) { 
     return 4; 
    } else if (x.a[1]) { 
     return 3; 
    ... 

EDITAR por tristopia: Endianness versión conscientes de la última variante

int len(uint32_t val) 
{ 
    union int_char { 
     uint32_t u; 
     uint8_t a[4]; 
    } x; 
    const uint16_t w = 1; 

    x.u = val; 
    if(((uint8_t *)&w)[1]) { // BIG ENDIAN (Sparc, m68k, ARM, Power) 
    if(x.a[0]) return 4; 
    if(x.a[1]) return 3; 
    if(x.a[2]) return 2; 
    } 
    else {      // LITTLE ENDIAN (x86, 8051, ARM) 
    if(x.a[3]) return 4; 
    if(x.a[2]) return 3; 
    if(x.a[1]) return 2; 
    } 
    return 1; 
} 

Debido a la const, cualquier compilador que se precie sólo generará el código de la orden de bits derecha.

Answer 12

Es posible que tenga una solución más eficiente dependiendo de su arquitectura.

MIPS tiene una instrucción "CLZ" que cuenta el número de bits cero iniciales de un número. Lo que está buscando aquí es esencialmente 4 - (CLZ(x)/8) (donde / es una división entera). PowerPC tiene la instrucción equivalente cntlz, y x86 tiene BSR. Esta solución debería simplificar hasta 3-4 instrucciones (sin contar la sobrecarga de llamada de función) y cero ramificaciones.

Answer 13

a Pascal Cuoq y las otras 35 personas que votaron por-su comentario:

"Wow Más de 10 millones de veces ... ¿Quiere decir que si se aprieta tres ciclos de esta función es que ahorrara tanto como 0.03s? "

Tal comentario sarcástico es en el mejor grosero y ofensivo.

La optimización es frecuentemente el resultado acumulado del 3% aquí, 2% allí. 3% en la capacidad total es nada para estornudar. Supongamos que esta era una etapa casi saturada e inigualable en una tubería. Supongamos que la utilización de CPU pasó del 99% al 96%. La teoría de colas simples nos dice que tal reducción en la utilización de la CPU reduciría la longitud promedio de la cola en más del 75%. [el cualitativo (carga dividida por 1 carga)]

Tal reducción puede hacer o deshacer una configuración de hardware particular ya que esto tiene efectos de retroalimentación en los requisitos de memoria, almacenamiento en caché de los elementos en cola, bloqueo de convoyes y (horror de horrores debería ser un sistema paginado) incluso paginación. Es precisamente este tipo de efectos lo que causa el comportamiento del sistema de bucle de histéresis bifurcada.

Las tasas de llegada de todo parecen tender a aumentar y la sustitución de campo de una CPU en particular o la compra de una caja más rápida no suele ser una opción.

La optimización no se trata solo del tiempo del reloj de pared en un escritorio. Cualquiera que piense que tiene mucho que leer tiene que ver con la medición y el modelado del comportamiento del programa de computadora.

Pascal Cuoq le debe una disculpa al afiche original.

Answer 14

Si recuerdo 80x86 asm derecha, me gustaría hacer algo como:

 
    ; Assume value in EAX; count goes into ECX 
    cmp eax,16777215 ; Carry set if less 
    sbb ecx,ecx  ; Load -1 if less, 0 if greater 
    cmp eax,65535 
    sbb ecx,0  ; Subtract 1 if less; 0 if greater 
    cmp eax,255 
    sbb ecx,-4  ; Add 3 if less, 4 if greater 

Seis instrucciones. Creo que el mismo enfoque también funcionaría para seis instrucciones sobre el ARM que uso.