La forma más rápida de determinar si un número entero está entre dos números enteros (inclusive) con conjuntos de valores conocidos
¿Existe una manera más rápida que x >= start && x <= enden C o C++ de probar si un número entero está entre dos números enteros?
ACTUALIZACIÓN : Mi plataforma específica es iOS. Esto es parte de una función de desenfoque de cuadro que restringe los píxeles a un círculo en un cuadrado determinado.
ACTUALIZACIÓN : Después de probar la respuesta aceptada , obtuve una aceleración de orden de magnitud en una línea de código en comparación con hacerlo de la x >= start && x <= endmanera normal.
ACTUALIZACIÓN : Aquí está el código anterior y posterior con ensamblador de XCode:
NUEVA MANERA
// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)
Ltmp1313:
ldr r0, [sp, #176] @ 4-byte Reload
ldr r1, [sp, #164] @ 4-byte Reload
ldr r0, [r0]
ldr r1, [r1]
sub.w r0, r9, r0
cmp r0, r1
blo LBB44_30
VIEJA FORMA
#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)
Ltmp1301:
ldr r1, [sp, #172] @ 4-byte Reload
ldr r1, [r1]
cmp r0, r1
bls LBB44_32
mov r6, r0
b LBB44_33
LBB44_32:
ldr r1, [sp, #188] @ 4-byte Reload
adds r6, r0, #1
Ltmp1302:
ldr r1, [r1]
cmp r0, r1
bhs LBB44_36
Es bastante sorprendente cómo reducir o eliminar las ramificaciones puede proporcionar una aceleración tan espectacular.
Hay un viejo truco para hacer esto con una sola comparación/rama. Si realmente mejorará la velocidad puede ser cuestionable, e incluso si lo hiciera, probablemente sea muy poco para notarlo o preocuparse, pero cuando solo comienzas con dos comparaciones, las posibilidades de una gran mejora son bastante remotas. El código se parece a:
// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
// upper-lower, simply add + 1 to upper-lower and use the < operator.
if ((unsigned)(number-lower) <= (upper-lower))
in_range(number);
Con una computadora típica y moderna (es decir, cualquier cosa que use complemento a dos), la conversión a sin signo es realmente un error, solo un cambio en la forma en que se ven los mismos bits.
Tenga en cuenta que, en un caso típico, puede realizar un cálculo previo upper-lowerfuera de un bucle (presunto), por lo que normalmente no aporta mucho tiempo. Además de reducir la cantidad de instrucciones de bifurcación, esto también (generalmente) mejora la predicción de bifurcaciones. En este caso, se toma la misma rama ya sea que el número esté por debajo del extremo inferior o por encima del extremo superior del rango.
En cuanto a cómo funciona esto, la idea básica es bastante simple: un número negativo, visto como un número sin signo, será mayor que cualquier cosa que comience como un número positivo.
En la práctica, este método traslada numbery el intervalo al punto de origen y comprueba si numberestá en el intervalo [0, D], donde D = upper - lower. Si numberestá por debajo del límite inferior: negativo y si está por encima del límite superior: mayor queD .
Es raro poder realizar optimizaciones significativas del código a una escala tan pequeña. Se obtienen grandes mejoras en el rendimiento al observar y modificar el código desde un nivel superior. Es posible que pueda eliminar por completo la necesidad de realizar la prueba de rango, o solo hacer O(n) de ellas en lugar de O(n^2). Es posible que puedas reordenar las pruebas de modo que siempre esté implícito un lado de la desigualdad. Incluso si el algoritmo es ideal, es más probable que se obtengan ganancias cuando vea cómo este código realiza la prueba de rango 10 millones de veces y encuentre una manera de agruparlos y usar SSE para realizar muchas pruebas en paralelo.
