Por que <= é mais lento que <usando esse trecho de código na V8?

Estou lendo os slides Quebrando o limite de velocidade do Javascript com a V8 , e há um exemplo como o código abaixo. Não consigo descobrir por que <=é mais lento do que <neste caso, alguém pode explicar isso? Quaisquer comentários são apreciados.

Lento:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

(Dica: primes é uma matriz de comprimento prime_count)

Mais rápido:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

[Mais informações] a melhoria da velocidade é significativa, no meu teste de ambiente local, os resultados são os seguintes:

V8 version 7.3.0 (candidate) 

Lento:

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed 

Mais rápido:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

Eu trabalho no V8 no Google e queria fornecer algumas dicas adicionais sobre as respostas e comentários existentes.

Para referência, veja o exemplo de código completo dos slides :

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

Em primeiro lugar, a diferença de desempenho não tem nada a ver com os operadores <e <=diretamente. Então, por favor, não pule os aros apenas para evitar<= no seu código, porque você lê no Stack Overflow que é lento - não é!

Segundo, as pessoas apontaram que a matriz é "holey". Isso não ficou claro no snippet de código na postagem do OP, mas fica claro quando você olha para o código que inicializa this.primes:

this.primes = new Array(iterations);

Isso resulta em uma matriz com um HOLEYtipo de elemento na V8, mesmo se a matriz acabar completamente preenchida / compactada / contígua. Em geral, as operações em matrizes holey são mais lentas do que as operações em matrizes compactadas, mas nesse caso a diferença é insignificante: equivale a 1 verificação Smi ( número inteiro pequeno ) adicional (para proteção contra buracos) cada vez que atingimosthis.primes[i] o loop dentroisPrimeDivisible . Nada demais!

TL; DR A matriz HOLEYnão é o problema aqui.

Outros apontaram que o código lê fora dos limites. Geralmente, é recomendável evitar a leitura além do tamanho das matrizes e, nesse caso, teria realmente evitado a queda maciça no desempenho. Mas porque? O V8 pode lidar com alguns desses cenários fora dos limites com apenas um pequeno impacto no desempenho. O que há de tão especial nesse caso em particular, então?

A leitura fora dos limites resulta em this.primes[i]estar undefinednesta linha:

if ((candidate % this.primes[i]) == 0) return true;

E isso nos leva ao problema real : o %operador agora está sendo usado com operandos não inteiros!

• integer % someOtherIntegerpode ser calculado com muita eficiência; Os mecanismos JavaScript podem produzir código de máquina altamente otimizado para este caso.

• integer % undefinedpor outro lado, é menos eficiente Float64Mod, pois undefinedé representado como um duplo.

O trecho de código pode realmente ser aprimorado alterando o <=para <nesta linha:

for (var i = 1; i <= this.prime_count; ++i) {

... não porque, de <=alguma forma, seja um operador superior a ele <, mas apenas porque isso evita a leitura fora dos limites neste caso específico.

Outras respostas e comentários mencionam que a diferença entre os dois loops é que o primeiro executa mais uma iteração que o segundo. Isso é verdade, mas em uma matriz que cresce para 25.000 elementos, uma iteração mais ou menos faria apenas uma diferença minúscula. Como estimativa, se assumirmos que o comprimento médio à medida que cresce é de 12.500, a diferença que podemos esperar deve estar em torno de 1 / 12.500, ou apenas 0,008%.

A diferença de desempenho aqui é muito maior do que seria explicada por uma iteração extra, e o problema é explicado no final da apresentação.

this.primes é uma matriz contígua (cada elemento possui um valor) e os elementos são todos números.

Um mecanismo JavaScript pode otimizar essa matriz para ser uma matriz simples de números reais, em vez de uma matriz de objetos que contêm números, mas que podem conter outros valores ou nenhum valor. O primeiro formato é muito mais rápido de acessar: é preciso menos código e a matriz é muito menor, para que caiba melhor no cache. Mas existem algumas condições que podem impedir que esse formato otimizado seja usado.

Uma condição seria se alguns dos elementos da matriz estivessem ausentes. Por exemplo:

let array = [];
a[0] = 10;
a[2] = 20;

Agora, qual é o valor a[1]? Não tem valor . (Nem é correto dizer que tem o valor undefined- um elemento da matriz que contém o undefinedvalor é diferente de um elemento da matriz que está totalmente ausente.)

Não existe uma maneira de representar isso apenas com números; portanto, o mecanismo JavaScript é forçado a usar o formato menos otimizado. Se a[1]contivesse um valor numérico como os outros dois elementos, a matriz poderia potencialmente ser otimizada em apenas uma matriz de números.

Outro motivo para uma matriz ser forçada para o formato desoptimizado pode ser se você tentar acessar um elemento fora dos limites da matriz, conforme discutido na apresentação.

O primeiro loop com <= tentativas de ler um elemento após o final da matriz. O algoritmo ainda funciona corretamente, porque na última iteração extra:

• this.primes[i]avalia undefinedporquei já passou do final da matriz.
• candidate % undefined(para qualquer valor de candidate) é avaliado comoNaN .
• NaN == 0 avalia como false .
• Portanto, o return true não é executado.

Portanto, é como se a iteração extra nunca tivesse acontecido - não tem efeito sobre o resto da lógica. O código produz o mesmo resultado que faria sem a iteração extra.

Mas, para chegar lá, ele tentou ler um elemento inexistente após o final da matriz. Isso força a matriz a não ser otimizada - ou pelo menos ocorreu no momento desta palestra.

O segundo loop com < lê apenas os elementos existentes na matriz, permitindo uma matriz e um código otimizados.

O problema está descrito nas páginas 90-91 da palestra, com discussões relacionadas nas páginas anteriores e posteriores.

Por acaso, participei dessa apresentação de E / S do Google e conversei com o palestrante (um dos autores do V8) depois. Eu estava usando uma técnica em meu próprio código que envolvia ler além do final de uma matriz como uma tentativa equivocada (em retrospectiva) de otimizar uma situação específica. Ele confirmou que, se você tentasse ler além do final de uma matriz, impediria que o formato otimizado simples fosse usado.

Se o que o autor da V8 disse ainda for verdadeiro, a leitura após o final da matriz impediria que ela fosse otimizada e teria que voltar ao formato mais lento.

Agora é possível que o V8 tenha sido aprimorado para lidar com esse caso com eficiência ou que outros mecanismos JavaScript o tratem de maneira diferente. Eu não sei de um jeito ou de outro sobre isso, mas essa desoptimização é o que a apresentação estava falando.

TL; DR O loop mais lento se deve ao acesso à matriz 'fora dos limites', que força o mecanismo a recompilar a função com menos ou mesmo sem otimizações OU a não compilar a função com nenhuma dessas otimizações para começar ( se o compilador (JIT-) detectou / suspeitou dessa condição antes da primeira compilação 'versão'), leia abaixo o porquê;

Exemplo 1:
a Dense Array(sendo contíguo (significa que não há intervalos entre os índices) E, na verdade, um elemento em cada índice) de 5 elementos usando a indexação baseada em 0 (sempre no ES262).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

Portanto, não estamos realmente falando sobre a diferença de desempenho entre <vs <=(ou 'uma iteração extra'), mas estamos falando:
'por que o snippet correto (b) é executado mais rápido que o snippet incorreto (a)'?

A resposta é dupla (embora da perspectiva do implementador da linguagem ES262 ambas sejam formas de otimização):

1. Representação de dados: como representar / armazenar a matriz internamente na memória (objeto, mapa de hash, matriz numérica 'real' etc.)
2. Código-máquina funcional: como compilar o código que acessa / manipula (lê / modifica) essas 'matrizes'

O item 1 é suficientemente (e corretamente IMHO) explicado pela resposta aceita , mas isso gasta apenas 2 palavras ('o código') no item 2: compilação .

Mais precisamente: compilação JIT e, mais importante ainda, compilação JIT- RE !

A especificação da linguagem é basicamente apenas uma descrição de um conjunto de algoritmos ('etapas a serem executadas para alcançar o resultado final definido'). O que, como se vê, é uma maneira muito bonita de descrever uma linguagem. E deixa o método real que um mecanismo usa para alcançar resultados especificados aberto aos implementadores, dando ampla oportunidade para encontrar maneiras mais eficientes de produzir resultados definidos. Um mecanismo de conformidade de especificações deve fornecer resultados de conformidade de especificações para qualquer entrada definida.

Agora, com o código javascript / bibliotecas / uso aumentando e lembrando quantos recursos (tempo / memória / etc) um compilador 'real' usa, fica claro que não podemos fazer com que os usuários que visitam uma página da Web esperem tanto tempo (e os exigem ter tantos recursos disponíveis).

Imagine a seguinte função simples:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

Perfeitamente claro, certo? Não requer nenhum esclarecimento extra, certo? O tipo de retorno é Number, certo?
Bem .. não, não e não ... Depende de qual argumento você passa para o parâmetro de função nomeado arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

Vê o problema? Em seguida, considere que isso apenas raspa as permutações possíveis em massa ... Nós nem sabemos que tipo de TIPO a função RETURN até terminarmos ...

Agora imagine esse mesmo código de função sendo usado em diferentes tipos ou mesmo variações de entrada, ambos completamente literalmente (no código-fonte) descritos e dinamicamente 'matrizes' geradas no programa.

Portanto, se você compilar a função sumAPENAS UMA VEZ, a única maneira de sempre retornar o resultado definido por especificação para todo e qualquer tipo de entrada, obviamente, somente executando TODAS as principais etapas E sub-prescritas por especificação, poderá garantir resultados conformes às especificações (como um navegador pré-y2k sem nome). Não há otimizações (porque não há suposições) e a linguagem de script interpretada lenta morta.

JIT-Compilation (JIT como Just In Time) é a solução popular atual.

Então, você começa a compilar a função usando suposições sobre o que ela faz, retorna e aceita.
você cria verificações o mais simples possível para detectar se a função pode começar a retornar resultados não conformes à especificação (como porque recebe entrada inesperada). Em seguida, jogue fora o resultado compilado anterior e recompile para algo mais elaborado, decida o que fazer com o resultado parcial que você já possui (é válido confiar ou computar novamente para ter certeza), vincule a função novamente ao programa e tente novamente. Em última análise, voltando à interpretação de script passo a passo, como nas especificações.

Tudo isso leva tempo!

Todos os navegadores funcionam em seus mecanismos, para cada sub-versão, você verá as coisas melhorarem e regredirem. Em algum momento da história, as cordas eram realmente imutáveis ​​(portanto, array.join era mais rápido que a concatenação de cordas), agora usamos cordas (ou similares) que aliviam o problema. Ambos retornam resultados conformes às especificações e é isso que importa!

Para encurtar a história: apenas porque a semântica da linguagem javascript geralmente nos recupera (como com esse bug silencioso no exemplo do OP) não significa que erros 'estúpidos' aumentem nossas chances de o compilador cuspir código-máquina rápido. Ele pressupõe que escrevemos as instruções corretas 'geralmente': o mantra atual que nós 'usuários' (da linguagem de programação) devemos ter é: ajudar o compilador, descrever o que queremos, favorecer expressões comuns (use asm.js para obter um entendimento básico quais navegadores podem tentar otimizar e por quê).

Por causa disso, falar sobre desempenho é importante, mas TAMBÉM é um campo minado (e, por causa desse campo, eu realmente quero terminar apontando (e citando) algum material relevante:

O acesso a propriedades inexistentes de objetos e elementos da matriz fora dos limites retorna o undefinedvalor em vez de gerar uma exceção. Esses recursos dinâmicos tornam a programação em JavaScript conveniente, mas também dificultam a compilação do JavaScript em um código de máquina eficiente.

...

Uma premissa importante para a otimização eficaz do JIT é que os programadores usam recursos dinâmicos do JavaScript de maneira sistemática. Por exemplo, os compiladores JIT exploram o fato de que as propriedades do objeto geralmente são adicionadas a um objeto de um determinado tipo em uma ordem específica ou que os acessos fora da área de matriz ocorrem raramente. Os compiladores JIT exploram essas suposições de regularidade para gerar código de máquina eficiente em tempo de execução. Se um bloco de código atender às premissas, o mecanismo JavaScript executará um código de máquina eficiente e gerado. Caso contrário, o mecanismo deve retornar ao código mais lento ou à interpretação do programa.

Fonte:
"JITProf: Identificando o código JavaScript hostil para o JIT"
publicação de Berkeley, 2014, por Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (também não gosta de acessar a matriz fora do limite):

Compilação Antecipada

Como o asm.js é um subconjunto estrito de JavaScript, essa especificação define apenas a lógica de validação - a semântica de execução é simplesmente a do JavaScript. No entanto, o asm.js validado é passível de compilação antecipada (AOT). Além disso, o código gerado por um compilador AOT pode ser bastante eficiente, apresentando:

• representações sem caixa de números inteiros e de ponto flutuante;
• ausência de verificações de tipo de tempo de execução;
• ausência de coleta de lixo; e
• cargas e armazenamentos de heap eficientes (com estratégias de implementação variando por plataforma).

O código que falha na validação deve retornar à execução pelos meios tradicionais, por exemplo, interpretação e / ou compilação just-in-time (JIT).

http://asmjs.org/spec/latest/

e finalmente https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
, houve uma pequena subseção sobre as melhorias de desempenho interno do mecanismo ao remover limites- check (enquanto apenas levantando os limites - check fora do loop já teve uma melhoria de 40%).

EDIT:
observe que várias fontes falam sobre diferentes níveis de recompilação JIT até a interpretação.

Exemplo teórico com base nas informações acima, em relação ao snippet do OP:

• Ligue para isPrimeDivisible
• Compile isPrimeDivisible usando suposições gerais (como acesso fora dos limites)
• Trabalhe
• BAM, de repente, os acessos ao array fora dos limites (logo no final).
• Porcaria, diz o mecanismo, vamos recompilar que éPrimeDivisible usando diferentes (menos) suposições, e esse mecanismo de exemplo não tenta descobrir se pode reutilizar o resultado parcial atual, portanto
• Recompute todo o trabalho usando a função mais lenta (espero que termine, caso contrário, repita e desta vez apenas interprete o código).
• Resultado de retorno

Portanto, o tempo foi então:
Primeira execução (falha no final) + fazendo todo o trabalho novamente usando código de máquina mais lento para cada iteração + a recompilação etc. .. claramente leva> 2 vezes mais neste exemplo teórico !

EDIT 2: (exoneração de responsabilidade: conjectura baseada nos fatos abaixo)
Quanto mais eu penso nisso, mais acho que essa resposta pode realmente explicar a razão mais dominante dessa 'penalidade' no trecho errado a (ou bônus de desempenho no trecho b) , dependendo de como você pensa sobre isso), precisamente por que eu sou um adágio em chamá-lo (snippet a) de erro de programação:

É bastante tentador supor que this.primesseja um numérico puro de 'matriz densa' que fosse

• Literal codificado no código-fonte (candidato excelente conhecido para se tornar uma matriz 'real', pois tudo já é conhecido pelo compilador antes do tempo de compilação) OU
• provavelmente gerado usando uma função numérica preenchendo um pré-tamanho ( new Array(/*size value*/)) em ordem sequencial crescente (outro candidato conhecido há muito tempo para se tornar um array 'real').

Também sabemos que o primescomprimento da matriz é armazenado em cache como prime_count! (indicando sua intenção e tamanho fixo).

Também sabemos que a maioria dos mecanismos passa os Arrays inicialmente como copiar na modificação (quando necessário), o que os torna muito mais rápidos (se você não os alterar).

Portanto, é razoável supor que a matriz primesprovavelmente já seja uma matriz otimizada internamente, que não será alterada após a criação (simples de saber para o compilador se não houver código que modifique a matriz após a criação) e, portanto, já seja (se aplicável a o mecanismo) armazenado de maneira otimizada, quase como se fosse um Typed Array.

Como tentei deixar claro com meu sumexemplo de função, os argumentos que são passados ​​influenciam muito o que realmente precisa acontecer e, como tal, como esse código específico está sendo compilado no código de máquina. Passar um Stringpara a sumfunção não deve alterar a string, mas alterar como a função é compilada por JIT! Passar uma matriz para sumdeve compilar uma versão diferente (talvez adicional para esse tipo, ou 'forma' como eles chamam, de objeto que foi passado) do código de máquina.

Como parece um pouco estranho converter o primesArray do tipo Typed_Array on-the-fly para algo mais, enquanto o compilador sabe que essa função nem sequer a modifica!

Sob essas premissas, restam 2 opções:

1. Compile como triturador de números assumindo que não há limites, encontre um problema fora dos limites no final, recompile e refaça o trabalho (conforme descrito no exemplo teórico na edição 1 acima)
2. O compilador já detectou (ou suspeitou?) Acesso fora dos limites desde o início e a função foi compilada por JIT como se o argumento passado fosse um objeto esparso, resultando em um código-máquina funcional mais lento (pois haveria mais verificações / conversões / coerções etc.) Em outras palavras: a função nunca foi elegível para certas otimizações, foi compilada como se tivesse recebido um argumento de 'matriz esparsa' (semelhante a).

Agora eu realmente me pergunto qual desses 2 é!

Para adicionar um pouco de cientificidade, aqui está um jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

Ele testa o caso de controle de uma matriz preenchida com ints e looping, fazendo aritmética modular enquanto permanece dentro dos limites. Possui 5 casos de teste:

• 1. Looping fora dos limites
• 2. Matrizes Holey
• 3. Aritmética modular contra NaNs
• 4. Valores completamente indefinidos
• 5. Usando um new Array()

Isso mostra que os 4 primeiros casos são muito ruins para o desempenho. Fazer um loop fora dos limites é um pouco melhor que os outros 3, mas todos os 4 são aproximadamente 98% mais lentos que o melhor.
O new Array()case é quase tão bom quanto o array bruto, apenas um pouco mais lento.