La forma más rápida de verificar la condición l + 1 < r para int l, r en Java

Question

¿Cuál es la forma más rápida de verificar la condición?

l + 1 < r

para int l, r en Java?

l y r no son constantes y sé que l < = r . La comparación es una condición de detención para un bucle while en una implementación de búsqueda binaria. Por supuesto, estoy comparando mi código, tanto en una prueba separada (buscando en una gran matriz) como en el código que lo usa.

Lo que estoy buscando, me imagino, es una especie de operación un poco más rápida que la condición actual. Pero no lo sé.

Answer 1

Creo que probablemente sea tan rápido como sea posible. Eso se reducirá a un bytecode muy simple, y el JIT (compilador justo a tiempo) probablemente lo reducirá a una implementación nativa muy simple.

(Sin relación: es interesante ver que un 'desarrollo cuantitativo' usa Java por cierto. No sucede tan a menudo)

Answer 2

Este tipo de microoptimización es casi siempre una mala idea; su rendimiento para un bit tan pequeño dependerá por completo de cómo el compilador de puntos de acceso optimice su código y los sutiles efectos de caché que tengan que ver con el código circundante.

Answer 3

Bueno, la comparación subyacente debe:

agregue 1 a l, compare el resultado con r

o

reste 1 de r y compare el resultado con l

Todo el hardware moderno tendrá el mismo rendimiento bruto para cualquier operación (donde la suma y resta de cualquier tipo de datos nativo tiene un rendimiento idéntico en términos de ciclos para completar y canalizar los efectos secundarios).

La única forma en que esto tendrá algún efecto es si:

una de lor son constantes conocidas en tiempo de compilación. por ejemplo.

l + 1 < 5
5 + 1 < r

en este caso, un compilador de optimización deficiente puede no darse cuenta de que puede convertir el primero en l < 4

Se requieren

pero todos compiladores de Java para detectar que el segundo caso es 6 < r

La otra es si los tipos de datos de l y r son diferentes.

La operación de:

1. suma / resta de punto flotante y luego comparación con un int
   versos
2. suma / resta integral, luego la comparación con un doble puede ser diferente.

Es justo decir que las posibilidades de que esto sea un problema grave en su solicitud son insignificantes, ya que el costo del ciclo de cualquiera de estos es muy pequeño en comparación con el impacto en la tubería de cualquier predicción errónea de la rama asociada con la decisión.

También un JIT decente puede hacer todo tipo de optimizaciones en relación con el código circundante que supera la micro optimización realizada.

Answer 4

Tener una variable lr1 que siempre es igual a (l - r + 1) . Siempre que incremente o disminuya l , haga lo mismo con lr1 . De manera similar para r .

Luego su prueba se convierte en (lr1 < 0) , y las instrucciones para modificar lr1 no se ejecutan más de lo necesario.

Me siento un poco tonto dándote una microoptimización, que en la mayoría de los casos es un centavo, una tontería. Al igual que si estás comparando cadenas, la prueba quedará totalmente desbordada.

AGREGADO: Ya que estás haciendo una búsqueda binaria, mencionaría la genial evolución de la búsqueda binaria de Jon Bentley. Primero rellena la tabla A hasta una potencia de 2, como 1024. Luego escribe algo como esto:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

y finalmente pruebe si (X == A [i]) . O, si no desea rellenarlo, deje que las instrucciones if sean algo como
if (i + 512 < N & amp; & amp; X > = A [ i + 512]) i + = 512;

Answer 5

Lo que dijeron todos estos tipos. El compilador lo optimizará para usted. Escríbelo para que se vea y se lea correctamente y sigue adelante.

Answer 6

Su mejor opción es ajustar la JVM en lugar del código, dado que este es su cuello de botella.

Intente iniciar jvm con los argumentos -server -XX: + AggressiveOpts .

Answer 7

¿Qué tal si mueve su prueba de igualdad fuera del ciclo while, para que verifique .equals () solo después de la finalización? por cierto, no pude encontrar ninguna manera de probar si l + 1 < r. Si se sabe que las longitudes de su matriz son menores que ciertos tamaños, ¿qué sucede si usa un tipo de datos diferente para los índices? char / short / byte?