Java: o loop desenrolado manualmente ainda é mais rápido que o loop original. Por quê?

Considere os dois trechos de código a seguir em uma matriz de comprimento 2:

boolean isOK(int i) {
    for (int j = 0; j < filters.length; ++j) {
        if (!filters[j].isOK(i)) {
            return false;
        }
    }
    return true;
}

e

boolean isOK(int i) {
     return filters[0].isOK(i) && filters[1].isOK(i);
}

Eu assumiria que o desempenho dessas duas peças deveria ser semelhante após aquecimento suficiente.
Eu verifiquei isso usando a estrutura de micro-benchmarking JMH conforme descrito, por exemplo, aqui e aqui e observei que o segundo trecho é 10% mais rápido.

Pergunta: por que o Java não otimizou meu primeiro snippet usando a técnica básica de desenrolamento de loop?
Em particular, gostaria de entender o seguinte:

1. I pode facilmente produzir um código que é ideal para casos de 2 filtros e ainda pode trabalhar no caso de um outro número de filtros (imagine um construtor simples):
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). O JITC pode fazer o mesmo e, se não, por quê?
2. O JITC pode detectar que ' filters.length == 2 ' é o caso mais frequente e produzir o código ideal para esse caso após algum aquecimento? Isso deve ser quase tão ideal quanto a versão desenrolada manualmente.
3. O JITC pode detectar que uma instância específica é usada com muita frequência e produzir um código para essa instância específica (para a qual sabe que o número de filtros é sempre 2)?
   Atualização: obteve uma resposta de que o JITC funciona apenas em nível de classe. OK, entendi.

Idealmente, gostaria de receber uma resposta de alguém com um profundo entendimento de como o JITC funciona.

Detalhes de execução de referência:

• Tentado nas versões mais recentes do Java 8 OpenJDK e Oracle HotSpot, os resultados são semelhantes
• Sinalizadores Java usados: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (obteve resultados semelhantes sem os sinalizadores extravagantes)
• A propósito, obtenho uma taxa de tempo de execução semelhante se eu a executar vários bilhões de vezes em um loop (não via JMH), ou seja, o segundo trecho é sempre claramente mais rápido

Saída típica de benchmark:

Modo de referência (filterIndex) Modo Cnt Score Error Units
LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44.202 ± 0.224 ns / op
LoopUnrollingBenchmark.runBenchmark 1 avgt 400 38.347 ± 0.063 ns / op

(A primeira linha corresponde ao primeiro trecho, a segunda linha - à segunda.

Código de referência completo:

public class LoopUnrollingBenchmark {

    @State(Scope.Benchmark)
    public static class BenchmarkData {
        public Filter[] filters;
        @Param({"0", "1"})
        public int filterIndex;
        public int num;

        @Setup(Level.Invocation) //similar ratio with Level.TRIAL
        public void setUp() {
            filters = new Filter[]{new FilterChain1(), new FilterChain2()};
            num = new Random().nextInt();
        }
    }

    @Benchmark
    @Fork(warmups = 5, value = 20)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public int runBenchmark(BenchmarkData data) {
        Filter filter = data.filters[data.filterIndex];
        int sum = 0;
        int num = data.num;
        if (filter.isOK(num)) {
            ++sum;
        }
        if (filter.isOK(num + 1)) {
            ++sum;
        }
        if (filter.isOK(num - 1)) {
            ++sum;
        }
        if (filter.isOK(num * 2)) {
            ++sum;
        }
        if (filter.isOK(num * 3)) {
            ++sum;
        }
        if (filter.isOK(num * 5)) {
            ++sum;
        }
        return sum;
    }


    interface Filter {
        boolean isOK(int i);
    }

    static class Filter1 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 3 == 1;
        }
    }

    static class Filter2 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 7 == 3;
        }
    }

    static class FilterChain1 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            for (int j = 0; j < filters.length; ++j) {
                if (!filters[j].isOK(i)) {
                    return false;
                }
            }
            return true;
        }
    }

    static class FilterChain2 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            return filters[0].isOK(i) && filters[1].isOK(i);
        }
    }

    private static Filter[] createLeafFilters() {
        Filter[] filters = new Filter[2];
        filters[0] = new Filter1();
        filters[1] = new Filter2();
        return filters;
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

TL; DR A principal razão da diferença de desempenho aqui não está relacionada ao desenrolar do loop. É antes a especulação de tipo e os caches embutidos .

Desenrolando estratégias

De fato, na terminologia do HotSpot, esses loops são tratados como contados e, em certos casos, a JVM pode desenrolá-los. Não no seu caso, no entanto.

O HotSpot possui duas estratégias de desenrolamento de loop: 1) desenrole ao máximo, ou seja, remova o loop completamente; ou 2) cole várias iterações consecutivas.

O desenrolar máximo pode ser feito, apenas se o número exato de iterações for conhecido .

  if (!cl->has_exact_trip_count()) {
    // Trip count is not exact.
    return false;
  }

No seu caso, no entanto, a função pode retornar cedo após a primeira iteração.

O desenrolamento parcial provavelmente pode ser aplicado, mas a seguinte condição interrompe o desenrolamento:

  // Don't unroll if the next round of unrolling would push us
  // over the expected trip count of the loop.  One is subtracted
  // from the expected trip count because the pre-loop normally
  // executes 1 iteration.
  if (UnrollLimitForProfileCheck > 0 &&
      cl->profile_trip_cnt() != COUNT_UNKNOWN &&
      future_unroll_ct        > UnrollLimitForProfileCheck &&
      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
    return false;
  }

Como no seu caso, a contagem esperada de viagens é menor que 2, o HotSpot assume que não vale a pena desenrolar nem duas iterações. Observe que a primeira iteração é extraída no pré-loop de qualquer maneira ( otimização do peeling de loop ), portanto, desenrolar não é realmente muito benéfico aqui.

Especulação de tipo

Na sua versão desenrolada, existem dois invokeinterfacebytecodes diferentes . Esses sites têm dois perfis de tipos distintos. O primeiro receptor é sempre Filter1e o segundo receptor é sempre Filter2. Portanto, você basicamente tem dois sites de chamada monomórficos, e o HotSpot pode integrar perfeitamente as duas chamadas - o chamado "cache embutido", que tem 100% de taxa de acertos neste caso.

Com o loop, há apenas um invokeinterfacebytecode e apenas um perfil de tipo é coletado. O HotSpot JVM vê que isso filters[j].isOK()é chamado 86% vezes com o Filter1receptor e 14% vezes com o Filter2receptor. Esta será uma chamada bimórfica. Felizmente, o HotSpot também pode especularmente receber chamadas bimórficas. Ele alinha os dois destinos com uma ramificação condicional. No entanto, nesse caso, a taxa de acertos será de no máximo 86% e o desempenho sofrerá com as ramificações imprevisíveis correspondentes no nível da arquitetura.

As coisas serão ainda piores, se você tiver 3 ou mais filtros diferentes. Nesse caso, isOK()haverá uma chamada megamórfica que o HotSpot não pode incorporar. Portanto, o código compilado conterá uma chamada de interface verdadeira com maior impacto no desempenho.

Mais sobre inlining especulativo no artigo The Black Magic of (Java) Method Dispatch .

Conclusão

Para alinhar chamadas virtuais / de interface, o HotSpot JVM coleta perfis de tipo por bytecode de chamada. Se houver uma chamada virtual em um loop, haverá apenas um tipo de perfil para a chamada, independentemente de o loop ser desenrolado ou não.

Para obter o melhor das otimizações de chamadas virtuais, é necessário dividir manualmente o loop, principalmente com a finalidade de dividir perfis de tipos. O HotSpot não pode fazer isso automaticamente até agora.

O loop apresentado provavelmente se enquadra na categoria de loops "não contados", que são loops para os quais a contagem de iterações não pode ser determinada no tempo de compilação nem no tempo de execução. Não apenas por causa do argumento @Andreas sobre o tamanho da matriz, mas também por causa da condicional aleatória break(que costumava estar no seu benchmark quando escrevi este post).

Os compiladores de ponta não os otimizam agressivamente, pois o desenrolar de loops não contados geralmente envolve a duplicação também da condição de saída de um loop, o que só melhora o desempenho em tempo de execução se as otimizações subsequentes do compilador puderem otimizar o código não desenrolado. Veja este documento de 2017 para obter detalhes de onde eles fazem propostas sobre como desenrolar essas coisas também.

A partir disso, sua suposição não sustenta que você meio que desenrolou manualmente o loop. Você está considerando uma técnica básica de desenrolamento de loop para transformar uma iteração em uma matriz com quebra condicional em uma &&expressão booleana encadeada. Eu consideraria este um caso bastante especial e ficaria surpreso ao encontrar um otimizador de hot spot para fazer uma complexa refatoração em tempo real. Aqui eles estão discutindo o que realmente pode fazer, talvez essa referência seja interessante.

Isso refletiria mais de perto a mecânica de um desenrolamento contemporâneo e talvez ainda não esteja nem perto do que seria o código de máquina desenrolado:

if (! filters[0].isOK(i))
{
   return false;
} 
if(! filters[1].isOK(i))
{
   return false;
}
return true;

Você está concluindo que, porque um pedaço de código corre mais rápido que outro, o loop não desenrolou. Mesmo assim, você ainda pode ver a diferença de tempo de execução devido ao fato de comparar comparações diferentes.

Se você deseja obter mais certeza, há o analisador / visualizador jitwatch das operações reais do Jit, incluindo o código da máquina (github) (slides da apresentação) . Se houver algo para ver, eu confiaria nos meus próprios olhos mais do que qualquer opinião sobre o que o JIT pode ou não fazer em geral, uma vez que todos os casos têm suas especificidades. Aqui eles se preocupam com a dificuldade de chegar a declarações gerais para casos específicos no que diz respeito ao JIT e fornecem alguns links interessantes.

Como seu objetivo é o tempo de execução mínimo, o a && b && c ...formulário provavelmente é o mais eficiente, se você não quiser depender da esperança de desenrolar o loop, pelo menos mais eficiente do que qualquer outra coisa apresentada ainda. Mas você não pode ter isso de maneira genérica. Com a composição funcional do java.util.Function, há uma enorme sobrecarga novamente (cada função é uma classe, cada chamada é um método virtual que precisa ser despachado). Talvez nesse cenário possa fazer sentido subverter o nível do idioma e gerar código de bytes personalizado em tempo de execução. Por outro lado, uma &&lógica também requer ramificação no nível do código de bytes e pode ser equivalente a if / return (que também não pode ser gerado sem sobrecarga).