java - ¿Por qué no se elimina el control de límites?

optimization microbenchmark

Question

Escribí un benchmark de benchmark simple para descubrir si se puede eliminar la verificación de límites cuando la matriz se computa en modo bit a bit y. Esto es básicamente lo que hacen casi todas las tablas hash: Ellos computan

h & (table.length - 1)

como un índice en la table , donde h es el hashCode o un valor derivado. Los results muestran que la verificación de límites no se elimina.

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

• i es el contador de bucles. Cuando se utiliza como índice de matriz, la verificación de límites se elimina.
• j se calcula como x & (table.length - 1) , donde x es un cambio de valor 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 lo utiliza.

    result ^= table[i] + j;

en lugar. La diferencia en el tiempo es quizás del 15% (lo he intentado bastante a través de diferentes variantes). Mis preguntas:

• ¿Existen otras razones posibles para esto además de la eliminación del cheque vinculado?
• ¿Hay alguna razón complicada por la que no puedo ver por qué no hay una eliminación de control de límite para j ?

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 en realidad es perjudicial en este caso (dada la complejidad de las CPU actuales, el compilador apenas lo sabe a ciencia cierta).

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 que x & (0-1) es igual a x . Por lo tanto, lo mejor que puede hacer el compilador es reemplazar la verificación de límite por una verificación de longitud cero. Pero esto es IMHO aún vale la pena, ya que la verificación de longitud cero se puede mover fuera del bucle fácilmente.

Optimización propuesta

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

• Para cada acceso a la matriz, verifique si el índice se ha computado a través de un bit y.
• Si es así, compruebe 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.
• Deja que las optimizaciones existentes se encarguen de ello.

Dicha optimización debería ser bastante simple y barata, ya que solo se ve en los nodos principales en el gráfico SSA . A diferencia de muchas optimizaciones complejas, nunca puede ser perjudicial, ya que solo reemplaza un cheque por uno ligeramente más simple; así que no hay problema, ni siquiera si no se puede mover fuera del bucle.

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

Noticias

John Rose presentó una RFE y ya hay un patch "rápido y sucio".

Answer 1

1. No, esto es evidentemente un efecto de la eliminación de la verificación de límites no suficientes.

He ampliado un punto de referencia por Marko Topolnik:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(BCElimination.N)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 10, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(2)
public class BCElimination {
    public static final int N = 1024;
    private static final Unsafe U;
    private static final long INT_BASE;
    private static final long INT_SCALE;
    static {
        try {
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            U = (Unsafe) f.get(null);
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }

        INT_BASE = U.arrayBaseOffset(int[].class);
        INT_SCALE = U.arrayIndexScale(int[].class);
    }

    private final int[] table = new int[BCElimination.N];

    @Setup public void setUp() {
        final Random random = new Random();
        for (int i=0; i<table.length; ++i) table[i] = random.nextInt();
    }

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

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

    @GenerateMicroBenchmark public int maskedIndexUnsafe() {
        int result = 0;
        final int[] table = this.table;
        long x = 0;
        for (int i=0; i<=table.length-1; ++i) {
            x += i * INT_SCALE;
            final long j = x & ((table.length-1) * INT_SCALE);
            result ^= i + U.getInt(table, INT_BASE + j);
        }
        return result;
    }
}

Resultados:

Benchmark                                Mean   Mean error    Units
BCElimination.maskedIndex               1,235        0,004    ns/op
BCElimination.maskedIndexUnsafe         1,092        0,007    ns/op
BCElimination.normalIndex               1,071        0,008    ns/op

2. La segunda pregunta es para las listas de correo hotspot-dev en lugar de , IMHO.

Answer 2

Para comenzar, la principal diferencia entre sus dos pruebas es definitivamente la eliminación de los controles; sin embargo, la forma en que esto influye en el código de la máquina está lejos de lo que sugeriría la ingenua expectativa.

Mi conjetura:

Los límites de verificación de las cifras son más fuertes como un punto de salida de bucle que como un código adicional que introduce sobrecarga .

El punto de salida del bucle impide la siguiente optimización que he eliminado del código de máquina emitido:

• el bucle se desenrolla (esto es cierto en todos los casos);
• Adicionalmente, la recuperación desde la etapa de matriz se realiza primero para todos los pasos desenrrollados, luego se realiza la extracción en el acumulador para todos los pasos.

Si el bucle se puede romper en cualquier paso, esta puesta en escena resultaría en un trabajo realizado para los pasos del bucle que nunca se tomaron realmente.

Considera esta ligera modificación de tu código:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.N)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(1)
 public class Measure {
  public static final int N = 1024;

  private final int[] table = new int[N];
  @Setup public void setUp() {
    final Random random = new Random();
    for (int i = 0; i < table.length; ++i) {
      final int x = random.nextInt();
      table[i] = x == 0? 1 : x;
    }
  }
  @GenerateMicroBenchmark public int normalIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }
  @GenerateMicroBenchmark public int maskedIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[j];
      result ^= i + entry;
      if (entry == 0) break;
    }
    return result;
  }
}

Solo hay una diferencia: he añadido el cheque.

if (entry == 0) break;

para dar al bucle una forma de salir prematuramente en cualquier paso. (También introduje un protector para asegurar que ninguna entrada de matriz sea realmente 0).

En mi máquina, este es el resultado:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.378        0.229    ns/op
o.s.Measure.normalIndex     avgt         5        0.924        0.092    ns/op

la variante de "índice normal" es sustancialmente más rápida, como se espera generalmente.

Sin embargo, vamos a eliminar el cheque adicional :

// if (entry == 0) break;

Ahora mis resultados son estos:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.130        0.065    ns/op
o.s.Measure.normalIndex     avgt         5        1.229        0.053    ns/op

El "índice enmascarado" respondió de manera predecible (gastos generales reducidos), pero el "índice normal" de repente es mucho peor . Aparentemente, esto se debe a un mal ajuste entre el paso de optimización adicional y mi modelo de CPU específico.

Mi punto:

El modelo de rendimiento a un nivel tan detallado es muy inestable y, como se puede observar en mi CPU, incluso errático.

Answer 3

Para eliminar de forma segura ese control de límites, es necesario probar que

h & (table.length - 1)

Está garantizado para producir un índice válido en la table . No lo hará si table.length es cero (ya que terminará con & -1 , un noop efectivo). Tampoco lo hará de manera útil si table.length no es una potencia de 2 (perderá información; considere el caso en que table.length es 17).

¿Cómo puede el compilador HotSpot saber que estas malas condiciones no son ciertas? Tiene que ser más conservador de lo que puede ser un programador, ya que el programador puede saber más acerca de las restricciones de alto nivel en el sistema (por ejemplo, que la matriz nunca está vacía y siempre como un número de elementos que es una potencia de poder). dos).