¿Por qué es <= más lento que <usando este fragmento de código en V8?

Estoy leyendo las diapositivas Rompiendo el límite de velocidad de Javascript con V8 , y hay un ejemplo como el código a continuación. No puedo entender por qué <=es más lento que <en este caso, ¿alguien puede explicar eso? Cualquier comentario es apreciado.

Lento:

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

(Sugerencia: primos es una matriz de longitud prime_count)

Más 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;
} 

[Más información] la mejora de la velocidad es significativa, en mi prueba de entorno local, los resultados son los siguientes:

V8 version 7.3.0 (candidate) 

Lento:

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

Más rápido:

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

Trabajo en V8 en Google, y quería proporcionar información adicional sobre las respuestas y comentarios existentes.

Como referencia, aquí está el ejemplo de código completo de las diapositivas :

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();

En primer lugar, la diferencia de rendimiento no tiene nada que ver con los operadores <y <=directamente. Por lo tanto, no salte los aros solo para evitar <=en su código porque leyó en Stack Overflow que es lento, ¡no lo es!

En segundo lugar, la gente señaló que la matriz es "holey". Esto no estaba claro en el fragmento de código en la publicación de OP, pero está claro cuando miras el código que se inicializa this.primes:

this.primes = new Array(iterations);

Esto da como resultado una matriz con un HOLEYtipo de elementos en V8, incluso si la matriz termina completamente llena / empaquetada / contigua. En general, las operaciones en matrices holey son más lentas que las operaciones en matrices empaquetadas, pero en este caso la diferencia es insignificante: equivale a 1 comprobación adicional de Smi ( entero pequeño ) (para proteger contra agujeros) cada vez que golpeamos this.primes[i]en el bucle interno isPrimeDivisible. ¡No es gran cosa!

TL; DR El ser de la matriz HOLEYno es el problema aquí.

Otros señalaron que el código se lee fuera de los límites. En general, se recomienda evitar leer más allá de la longitud de las matrices , y en este caso, de hecho, habría evitado la caída masiva en el rendimiento. ¿Pero por qué? V8 puede manejar algunos de estos escenarios fuera de límites con solo un impacto menor en el rendimiento. ¿Qué tiene de especial este caso particular, entonces?

La lectura fuera de límites da como resultado this.primes[i]estar undefineden esta línea:

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

Y eso nos lleva al problema real : ¡el %operador ahora se está utilizando con operandos no enteros!

• integer % someOtherIntegerse puede calcular de manera muy eficiente; Los motores de JavaScript pueden producir código de máquina altamente optimizado para este caso.

• integer % undefinedpor otro lado equivale a una forma menos eficiente Float64Mod, ya que undefinedse representa como un doble.

El fragmento de código se puede mejorar cambiando el <=en <esta línea:

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

... no porque <=sea ​​de alguna manera un operador superior <, sino simplemente porque esto evita la lectura fuera de los límites en este caso particular.

Otras respuestas y comentarios mencionan que la diferencia entre los dos bucles es que el primero ejecuta una iteración más que el segundo. Esto es cierto, pero en una matriz que crece a 25,000 elementos, una iteración más o menos solo haría una diferencia minúscula. Como suposición aproximada, si asumimos que la longitud promedio a medida que crece es de 12,500, entonces la diferencia que podríamos esperar debería ser de alrededor de 1 / 12,500, o solo 0.008%.

La diferencia de rendimiento aquí es mucho mayor de lo que se explicaría con esa iteración adicional, y el problema se explica cerca del final de la presentación.

this.primes es una matriz contigua (cada elemento tiene un valor) y los elementos son todos números.

Un motor de JavaScript puede optimizar dicha matriz para que sea una simple matriz de números reales, en lugar de una matriz de objetos que contienen números pero podrían contener otros valores o ningún valor. El acceso al primer formato es mucho más rápido: requiere menos código y la matriz es mucho más pequeña, por lo que se ajustará mejor en la memoria caché. Pero hay algunas condiciones que pueden evitar que se use este formato optimizado.

Una condición sería si faltan algunos de los elementos de la matriz. Por ejemplo:

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

Ahora, ¿cuál es el valor de a[1]? Que no tiene ningún valor . (Ni siquiera es correcto decir que tiene el valor undefined: un elemento de matriz que contiene el undefinedvalor es diferente de un elemento de matriz que falta por completo).

No hay una manera de representar esto solo con números, por lo que el motor de JavaScript se ve obligado a usar el formato menos optimizado. Si a[1]contuviera un valor numérico como los otros dos elementos, la matriz podría optimizarse potencialmente en una matriz de números solamente.

Otra razón por la que una matriz se ve forzada a adoptar el formato desoptimizado puede ser si intenta acceder a un elemento fuera de los límites de la matriz, como se discutió en la presentación.

El primer ciclo con <=intentos de leer un elemento más allá del final de la matriz. El algoritmo aún funciona correctamente, porque en la última iteración adicional:

• this.primes[i]evalúa undefinedporque ies pasado el final de la matriz.
• candidate % undefined(para cualquier valor de candidate) se evalúa como NaN.
• NaN == 0evalúa a false.
• Por lo tanto, el return trueno se ejecuta.

Por lo tanto, es como si la iteración adicional nunca sucediera, no tiene ningún efecto en el resto de la lógica. El código produce el mismo resultado que lo haría sin la iteración adicional.

Pero para llegar allí, trató de leer un elemento inexistente más allá del final de la matriz. Esto obliga a la matriz a salir de la optimización, o al menos lo hizo en el momento de esta charla.

El segundo ciclo con <elementos de solo lectura que existen dentro de la matriz, por lo que permite una matriz y un código optimizados.

El problema se describe en las páginas 90-91 de la charla, con una discusión relacionada en las páginas anteriores y posteriores.

Asistí a esta presentación de Google I / O y luego hablé con el orador (uno de los autores de V8). Había estado usando una técnica en mi propio código que implicaba leer más allá del final de una matriz como un intento equivocado (en retrospectiva) de optimizar una situación particular. Confirmó que si intentaba incluso leer más allá del final de una matriz, evitaría que se utilizara el formato optimizado simple.

Si lo que dijo el autor de V8 sigue siendo cierto, leer más allá del final de la matriz evitaría que se optimizara y tendría que volver al formato más lento.

Ahora es posible que V8 haya sido mejorado mientras tanto para manejar eficientemente este caso, o que otros motores JavaScript lo manejen de manera diferente. No sé de una forma u otra sobre eso, pero esta desoptimización es de lo que hablaba la presentación.

TL; DR El ciclo más lento se debe al acceso a la matriz 'fuera de límites', lo que obliga al motor a recompilar la función con menos o incluso sin optimizaciones O para no compilar la función con ninguna de estas optimizaciones para comenzar ( si el compilador (JIT-) detectó / sospechó esta condición antes de la primera 'versión' de compilación), lea a continuación por qué;

Ejemplo 1:
a Dense Array(siendo contiguo (significa que no hay espacios entre los índices) Y en realidad un elemento en cada índice) de 5 elementos que usan indexación basada en 0 (siempre en 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

Por lo tanto, no estamos hablando realmente de la diferencia de rendimiento entre <vs <=(o 'una iteración adicional'), pero estamos hablando:
'¿por qué el fragmento correcto (b) se ejecuta más rápido que el fragmento erróneo (a)'?

La respuesta es doble (aunque desde la perspectiva del implementador del lenguaje ES262, ambas son formas de optimización):

1. Representación de datos: cómo representar / almacenar la matriz internamente en la memoria (objeto, mapa hash, matriz numérica 'real', etc.)
2. Código de máquina funcional: cómo compilar el código que accede / maneja (lee / modifica) estas 'matrices'

El ítem 1 se explica suficientemente (y correctamente en mi humilde opinión) por la respuesta aceptada , pero eso solo gasta 2 palabras ('el código') en el ítem 2: compilación .

Más precisamente: JIT-Compilation y aún más importante JIT- RE -Compilation!

La especificación del lenguaje es básicamente una descripción de un conjunto de algoritmos ('pasos a realizar para lograr un resultado final definido'). Lo cual, como resulta, es una forma muy hermosa de describir un idioma. Y deja el método real que utiliza un motor para lograr resultados específicos abierto a los implementadores, lo que brinda una amplia oportunidad para encontrar formas más eficientes de producir resultados definidos. Un motor de conformidad de especificaciones debería dar resultados de conformidad de especificaciones para cualquier entrada definida.

Ahora, con el código / las bibliotecas / el uso de JavaScript en aumento, y recordando cuántos recursos (tiempo / memoria / etc.) usa un compilador 'real', está claro que no podemos hacer que los usuarios que visitan una página web esperen tanto (y los requieran tener tantos recursos disponibles).

Imagine la siguiente función simple:

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

Perfectamente claro, ¿verdad? No requiere NINGUNA aclaración adicional, ¿verdad? El tipo de retorno es Number, ¿verdad?
Bueno ... no, no y no ... Depende de qué argumento pase al parámetro de la función nombrada 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)

¿Ves el problema? Entonces considere que esto apenas está raspando las permutaciones masivas posibles ... Ni siquiera sabemos qué tipo de TIPO la función RETORNO hasta que hayamos terminado ...

Ahora imagine que este mismo código de función se usa realmente en diferentes tipos o incluso variaciones de entrada, tanto completamente literalmente (en código fuente) como 'matrices' generadas dinámicamente en el programa.

Por lo tanto, si compilara la función sumSOLO UNA VEZ, entonces la única forma que siempre devuelve el resultado definido por la especificación para todos y cada uno de los tipos de entrada, entonces, obviamente, solo realizando TODOS los pasos principales Y secundarios prescritos por la especificación puede garantizar resultados conformes a la especificación (como un navegador anterior y2k sin nombre). No hay optimizaciones (porque no hay suposiciones) y queda un lenguaje de secuencias de comandos interpretado lentamente.

JIT-Compilation (JIT como en Just In Time) es la solución popular actual.

Entonces, comienza a compilar la función utilizando suposiciones con respecto a lo que hace, devuelve y acepta.
se le ocurren comprobaciones lo más simples posible para detectar si la función puede comenzar a devolver resultados no conformes a las especificaciones (como porque recibe una entrada inesperada). Luego, deseche el resultado compilado anterior y vuelva a compilar algo más elaborado, decida qué hacer con el resultado parcial que ya tiene (¿es válido confiar en él o calcular de nuevo para estar seguro?), Vuelva a vincular la función al programa y Inténtalo de nuevo. Finalmente, volviendo a la interpretación de guiones paso a paso como en la especificación.

¡Todo esto lleva tiempo!

Todos los navegadores funcionan en sus motores, para todas y cada una de las subversiones verás que las cosas mejoran y retroceden. Las cadenas fueron en algún momento de la historia cadenas realmente inmutables (por lo tanto, array.join fue más rápido que la concatenación de cadenas), ahora usamos cuerdas (o similares) que alivian el problema. ¡Ambos devuelven resultados conformes a las especificaciones y eso es lo que importa!

En pocas palabras: el hecho de que la semántica del lenguaje javascript a menudo nos respalda (como con este error silencioso en el ejemplo del OP) no significa que los errores 'estúpidos' aumenten nuestras posibilidades de que el compilador escupe código de máquina rápido. Se supone que escribimos las instrucciones "usualmente" correctas: el mantra actual que debemos tener los "usuarios" (del lenguaje de programación) es: ayudar al compilador, describir lo que queremos, favorecer modismos comunes (tomar sugerencias de asm.js para una comprensión básica) qué navegadores pueden intentar optimizar y por qué).

Debido a esto, hablar sobre el rendimiento es importante, PERO TAMBIÉN es un campo de minas (y debido a dicho campo de minas, realmente quiero terminar señalando (y citando) material relevante:

El acceso a propiedades de objeto inexistentes y elementos de matriz fuera de límites devuelve el undefinedvalor en lugar de generar una excepción. Estas características dinámicas hacen que la programación en JavaScript sea conveniente, pero también dificultan la compilación de JavaScript en un código de máquina eficiente.

...

Una premisa importante para la optimización efectiva de JIT es que los programadores usan características dinámicas de JavaScript de manera sistemática. Por ejemplo, los compiladores JIT explotan el hecho de que las propiedades del objeto a menudo se agregan a un objeto de un tipo determinado en un orden específico o que raramente se producen accesos fuera de los límites de la matriz. Los compiladores JIT explotan estos supuestos de regularidad para generar código de máquina eficiente en tiempo de ejecución. Si un bloque de código satisface los supuestos, el motor de JavaScript ejecuta un código de máquina eficiente y generado. De lo contrario, el motor debe recurrir a un código más lento o para interpretar el programa.

Fuente:
"JITProf: Pinpointing JIT-unfriendly Code JavaScript"
Publicación de Berkeley, 2014, por Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (tampoco le gusta el acceso fuera de matriz):

Compilación anticipada

Como asm.js es un subconjunto estricto de JavaScript, esta especificación solo define la lógica de validación: la semántica de ejecución es simplemente la de JavaScript. Sin embargo, validado asm.js es susceptible de compilación anticipada (AOT). Además, el código generado por un compilador AOT puede ser bastante eficiente, con:

• representaciones sin caja de enteros y números de punto flotante;
• ausencia de verificaciones de tipo de tiempo de ejecución;
• ausencia de recolección de basura; y
• cargas y almacenes eficientes (con estrategias de implementación que varían según la plataforma).

El código que no se valida debe recurrir a la ejecución por medios tradicionales, por ejemplo, interpretación y / o compilación justo a tiempo (JIT).

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

y finalmente https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/ donde
hay una pequeña subsección sobre las mejoras de rendimiento interno del motor al eliminar límites- check (mientras solo levantaba los límites, check fuera del ciclo ya tenía una mejora del 40%).

EDITAR:
tenga en cuenta que varias fuentes hablan sobre diferentes niveles de JIT-Recompilation hasta la interpretación.

Ejemplo teórico basado en la información anterior, con respecto al fragmento del OP:

• Llamar a isPrimeDivisible
• Compile isPrimeDivisible usando suposiciones generales (como no tener acceso fuera de límites)
• Hacer trabajo
• BAM, repentinamente el acceso a la matriz está fuera de los límites (justo al final).
• Mierda, dice motor, recompilemos que esPrimeDivisible usando diferentes (menos) suposiciones, y este motor de ejemplo no intenta averiguar si puede reutilizar el resultado parcial actual, por lo que
• Vuelva a calcular todo el trabajo con una función más lenta (esperemos que termine; de ​​lo contrario, repita y esta vez solo interprete el código).
• Resultado devuelto

Por lo tanto, el tiempo era:
primera ejecución (falló al final) + hacer todo el trabajo de nuevo usando un código de máquina más lento para cada iteración + la recompilación, etc. ¡claramente toma> 2 veces más en este ejemplo teórico !

EDIT 2: (descargo de responsabilidad: conjetura basada en los hechos a continuación)
Cuanto más lo pienso, más creo que esta respuesta podría explicar la razón más dominante de esta 'penalización' en el fragmento erróneo a (o bonificación de rendimiento en el fragmento b , dependiendo de cómo lo piense), precisamente por qué estoy convencido de llamarlo (fragmento a) un error de programación:

Es bastante tentador suponer que se this.primestrata de una 'matriz densa' puramente numérica que era

• Literal codificado en el código fuente (candidato excelente conocido para convertirse en una matriz 'real' ya que todo lo conoce el compilador antes del tiempo de compilación) O
• Lo más probable es que se genere utilizando una función numérica que rellena un tamaño predeterminado ( new Array(/*size value*/)) en orden secuencial ascendente (otro candidato conocido desde hace mucho tiempo para convertirse en una matriz 'real').

También sabemos que la primeslongitud de la matriz se almacena en caché como prime_count! (indicando su intención y tamaño fijo).

También sabemos que la mayoría de los motores inicialmente pasan las matrices como copiar y modificar (cuando es necesario), lo que hace que manipularlos sea mucho más rápido (si no los cambia).

Por lo tanto, es razonable suponer que Array primesprobablemente ya sea una matriz optimizada internamente que no cambia después de la creación (simple de saber para el compilador si no hay código que modifique la matriz después de la creación) y, por lo tanto, ya lo es (si corresponde a el motor) almacenado de manera optimizada, más o menos como si fuera un Typed Array.

Como he tratado de aclarar con mi sumejemplo de función, los argumentos que se pasan influyen mucho en lo que realmente tiene que suceder y, como tal, cómo se compila ese código en particular en código máquina. ¡Pasar a Stringa la sumfunción no debería cambiar la cadena, sino cambiar cómo se compila la función JIT! Pasar una matriz a sumdebería compilar una versión diferente (quizás incluso adicional para este tipo, o 'forma' como lo llaman, de objeto que se pasó) de código de máquina.

¡Ya que parece un poco extraño convertir el Array tipo Typed_Array sobre la marcha en algo_else primesmientras el compilador sabe que esta función ni siquiera lo va a modificar!

Bajo estos supuestos que deja 2 opciones:

1. Compile como un generador de números, suponiendo que no haya límites fuera de juego, encuentre un problema fuera de límites al final, vuelva a compilar y rehaga el trabajo (como se describe en el ejemplo teórico en la edición 1 anterior)
2. El compilador ya detectó (¿o sospecha?) Fuera del acceso enlazado por adelantado y la función se compiló en JIT como si el argumento pasado fuera un objeto escaso que resulta en un código de máquina funcional más lento (ya que tendría más comprobaciones / conversiones / coacciones) etc.) En otras palabras: la función nunca fue elegible para ciertas optimizaciones, se compiló como si recibiera un argumento de 'matriz dispersa' (como).

¡Ahora realmente me pregunto cuál de estos 2 es!

Para agregarle algo científico, aquí hay un jsperf

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

Prueba el caso de control de una matriz llena de entradas y bucles haciendo aritmética modular mientras se mantiene dentro de los límites. Tiene 5 casos de prueba:

• 1. Bucle fuera de límites
• 2. matrices Holey
• 3. Aritmética modular contra NaNs
• 4. Valores completamente indefinidos
• 5. Usando un new Array()

Muestra que los primeros 4 casos son realmente malos para el rendimiento. Loop fuera de los límites es un poco mejor que los otros 3, pero los 4 son aproximadamente un 98% más lentos que el mejor de los casos.
El new Array()caso es casi tan bueno como la matriz en bruto, solo un poco más lento.