Escribí un simplepunto de referencia para saber si la verificación de límites puede eliminarse cuando la matriz se calcula a través de bit a bit y. Esto es básicamente lo que hacen casi todas las tablas hash: calculan

h & (table.length - 1)

como un índice en eltable, dóndeh es elhashCode o un valor derivado. losresultados muestra que la verificación de límites no se elimina.

La idea de mi punto de referencia es bastante simple: calcular dos valoresi yj, donde se garantiza que ambos son índices de matriz válidos.

i Es el contador de bucles. Cuando se usa como índice de matriz, se elimina la verificación de límites.j se calcula comox & (table.length - 1), dóndex Hay algún valor que cambia en cada iteración. Cuando se usa como índice de matriz, la verificación de límites no se elimina.

La parte relevante es la siguiente:

for (int i=0; i<=table.length-1; ++i) {
    x += result;
    final int j = x & (table.length-1);
    result ^= i + table[j];
}

El otro experimento usa

    result ^= table[i] + j;

en lugar. La diferencia en el tiempo es quizás del 15% (bastante consistente en las diferentes variantes que he probado). Mis preguntas:

¿Existen otras razones posibles para esto además de la eliminación de cheques encuadernados?¿Hay alguna razón complicada por la que no puedo ver por qué no hay eliminación de cheques encuadernados paraj?Un resumen de las respuestas.

La respuesta de MarkoTopolnik muestra que todo es más complicado y no se garantiza que la eliminación de los controles de límites sea una victoria, especialmente en su computadora, el código "normal" es más lento que "enmascarado". Supongo que esto se debe a que permite una optimización adicional que demuestra ser realmente perjudicial en este caso (dada la complejidad de las CPU actuales, el compilador apenas lo sabe con certeza).

La respuesta de leventov muestra claramente que la verificación de los límites de la matriz se realiza en "enmascarado" y que su eliminación hace que el código sea tan rápido como "normal".

Donal Fellows señala el hecho de que el enmascaramiento no funciona para una tabla de longitud cero, ya quex & (0-1) igual ax. Entonces, lo mejor que puede hacer el compilador es reemplazar la verificación encuadernada por una verificación de longitud cero. Pero en mi humilde opinión, vale la pena, ya que la verificación de longitud cero se puede sacar fácilmente del bucle.

Optimización propuesta

Debido a la equivalenciaa[x & (a.length - 1)] tira si y solo sia.length == 0, el compilador puede hacer lo siguiente:

Para cada acceso a la matriz, verifique si el índice se ha calculado mediante bit a bit y.Si es así, verifique si alguno de los operandos se calculó como longitud menos uno.Si es así, reemplace la verificación de límites por una verificación de longitud cero.Deje que las optimizaciones existentes se encarguen de ello.

Dicha optimización debería ser bastante simple y económica, ya que solo mira los nodos principales en elSSA grafico. A diferencia de muchas optimizaciones complejas, nunca puede ser perjudicial, ya que solo reemplaza una verificación por una más simple; así que no hay problema, ni siquiera si no se puede sacar del ciclo.

Publicaré esto en las listas de correo de hotspot-dev.

Noticias

John Rose presentó unRFE y ya hay un "rápido y sucio"parche.