Extraño rendimiento de bifurcación

Los resultados de mi índice de referencia muestran que el rendimiento es peor cuando la sucursal tiene un 15% (o un 85%) de probabilidad en lugar de un 50%.

¿Alguna explicación?

img

El código es demasiado largo pero las partes relevantes están aquí:

private int diff(char c) { return TABLE[(145538857 * c) >>> 27] - c; } @Benchmark int timeBranching(int reps) { int result = 0; while (reps-->0) { for (final char c : queries) { if (diff(c) == 0) { ++result; } } } return result; } 

Cuenta el número de caracteres BREAKING_WHITESPACE en la cadena dada. Los resultados muestran una caída repentina de tiempo (aumento de rendimiento) cuando la probabilidad de ramificación alcanza aproximadamente 0,20.

Más detalles sobre la caída. La variación de la semilla muestra que ocurren más cosas extrañas. Tenga en cuenta que la línea negra que indica los valores mínimo y máximo es muy corta, excepto cuando está cerca del acantilado.

acantilado

Parece una falla menor de JIT. Para una probabilidad de ramificación pequeña, genera algo como lo siguiente, simplemente mucho más complicado debido al desenrollado (estoy simplificando mucho):

 movzwl 0x16(%r8,%r10,2),%r9d 

Obtenga el carácter: int r9d = queries[r10]

 imul $0x8acbf29,%r9d,%ebx 

Multiplicar: ebx = 145538857 * r9d

 shr $0x1b,%ebx 

Shift: ebx >>>= 27

 cmp %edx,%ebx jae somewhere 

Verificar límites: if (ebx > edx || ebx < 0) goto somewhere (y arrojar allí una IndexOutOfBoundsException .

 cmp %r9d,%ebx jne back 

Regrese al principio del ciclo si no es igual: if (r9d != ebx) goto back

 inc %eax 

Incrementa el resultado: eax++

 jne back 

Simplemente goto back

Podemos ver una cosa inteligente y una tonta:

  • La verificación consolidada se realiza de manera óptima con una sola comparación sin firmar .
  • Es completamente redundante ya que x >>> 27 siempre es positivo y menor que la longitud de la tabla (32).

Para una probabilidad de ramificación superior al 20%, estas tres instrucciones

 cmp %r9d,%ebx jne back inc %eax 

ser reemplazado por algo así como

 mov %eax,%ecx // ecx = result inc %ecx // ecx++ cmp %r9d,%ebx // if (r9b == index) cmoveq %ecx,%ebx // result = ecx 

usando una instrucción de movimiento condicional . Esta es una instrucción más, pero no hay ramificación y, por lo tanto, no hay penalización por errores de predicción.

Esto explica el tiempo muy constante en el rango de 20-80%. La rampa por debajo del 20% se debe claramente a errores de predicción de twigs.

Por lo tanto, parece que un JIT no utiliza el umbral adecuado de aproximadamente 0,04 en lugar de 0,18.

thr