Eu escrevi um simplesreferência para descobrir se a verificação de limites pode ser eliminada quando a matriz é calculada via bit a bit e. Isso é basicamente o que quase todas as tabelas de hash fazem: elas calculam

h & (table.length - 1)

como um índice para otable, Ondeh é ohashCode ou um valor derivado. oresultados mostra que a verificação dos limites não é eliminada.

A ideia do meu benchmark é bem simples: calcular dois valoresi ej, em que ambos são garantidos como índices de matriz válidos.

i é o contador de loops. Quando é usado como índice de matriz, a verificação de limites é eliminada.j é calculado comox & (table.length - 1), Ondex é algum valor alterado em cada iteração. Quando é usado como índice de matriz, a verificação de limites não é eliminada.

A parte relevante é a seguinte:

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

O outro experimento usa

    result ^= table[i] + j;

em vez de. A diferença de tempo é talvez 15% (bastante consistente nas diferentes variantes que eu tentei). Minhas perguntas:

Existem outras razões possíveis para isso além da eliminação de cheques vinculados?Existe algum motivo complicado para eu não ver por que não há eliminação de cheques vinculados paraj?Um resumo das respostas

A resposta de MarkoTopolnik mostra que tudo é mais complicado e a eliminação das verificações de limites não garante que seja uma vitória, especialmente em seu computador o código "normal" é mais lento que o "mascarado". Eu acho que isso se deve ao fato de permitir alguma otimização adicional que mostra ser realmente prejudicial nesse caso (dada a complexidade das CPUs atuais, o compilador quase nem sabe ao certo).

A resposta de leventov mostra claramente que a verificação dos limites da matriz é feita em "mascarado" e que sua eliminação torna o código tão rápido quanto "normal".

Donal Fellows aponta para o fato de que a máscara não funciona para uma tabela de comprimento zero, poisx & (0-1) igual ax. Portanto, a melhor coisa que o compilador pode fazer é substituir a verificação vinculada por uma verificação de comprimento zero. Mas isso ainda vale a pena, pois a verificação de comprimento zero pode ser movida para fora do circuito facilmente.

Otimização proposta

Por causa da equivalênciaa[x & (a.length - 1)] joga se e somente sea.length == 0, o compilador pode fazer o seguinte:

Para cada acesso à matriz, verifique se o índice foi calculado via bit a bit e.Nesse caso, verifique se um dos operandos foi calculado como comprimento menos um.Nesse caso, substitua a verificação de limites por uma verificação de comprimento zero.Deixe as otimizações existentes cuidarem disso.

Essa otimização deve ser bem simples e barata, pois apenas analisa os nós pai no diretórioSSA gráfico. Ao contrário de muitas otimizações complexas, ela nunca pode ser prejudicial, pois substitui apenas uma verificação por uma verificação um pouco mais simples; então não há problema, mesmo que não possa ser movido para fora do loop.

Vou postar isso nas listas de discussão sobre hotspot-dev.

Notícia

John Rose apresentou umaRFE e já existe um "rápido e sujo"remendo.