tuning - java profiler

Extraño rendimiento de bifurcación

Question

Los results de mi benchmark de benchmark 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?

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 details 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.

Answer 1

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 ramas.

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