javascript - tag - title html w3schools

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

Question

Estoy leyendo las diapositivas Rompiendo el límite de velocidad de Javascript con V8 , y hay un ejemplo como el siguiente código. 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: primes 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 del 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

Answer 1

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 una aproximación aproximada, si asumimos que la longitud promedio a medida que crece es de 12,500, entonces la diferencia que podemos esperar debería ser de alrededor de 1 / 12,500, o solo de 0.008%.

La diferencia de rendimiento aquí es mucho mayor de lo que se explicaría por 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 matriz simple de números reales, en lugar de una matriz de objetos que contienen números pero que podrían contener otros valores o ningún valor. El primer formato es mucho más rápido de acceder: requiere menos código y la matriz es mucho más pequeña, por lo que cabe mejor en el caché. Pero hay algunas condiciones que pueden impedir que se utilice 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] ? No tiene valor . (Ni siquiera es correcto decir que tiene el valor undefined : un elemento de matriz que contiene el valor undefined 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] contenía un valor numérico como los otros dos elementos, la matriz podría potencialmente optimizarse en una matriz de números solamente.

Otra razón para forzar una matriz en el formato desoptimizado puede ser si intenta acceder a un elemento fuera de los límites de la matriz, como se explica en la presentación.

El primer bucle con <= intenta 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 como undefined porque i está más allá del final del array.
• candidate % undefined (para cualquier valor de candidate ) se evalúa como NaN .
• NaN == 0 evalúa como false .
• Por lo tanto, el return true no se ejecuta.

Así que es como si la iteración adicional nunca ocurriera, no tiene 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í, intentó 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 bucle con < lee solo los elementos 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.

Resulta que asistí a esta presentación de Google I / O y hablé con el orador (uno de los autores de V8) después. Había estado utilizando 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 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, entonces leer más allá del final de la matriz evitaría que se optimice y tendría que volver al formato más lento.

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

Answer 2

Para agregar algo de cientificidad, he aquí un jsperf

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

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

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

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

Answer 3

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

Para 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. Así que, por favor, no salte a través de los aros solo para evitar <= en su código porque usted lee en Overflow de pila que es lento, ¡no lo es!

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

this.primes = new Array(iterations);

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

TL; DR La matriz que es HOLEY no es el problema aquí.

Otros señalaron que el código se lee fuera de límites. Generalmente se recomienda evitar la lectura más allá de la longitud de los arreglos , y en este caso, de hecho, habría evitado la caída masiva del 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?

Los resultados de lectura fuera de límites en this.primes[i] undefined están undefined en 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 % someOtherInteger se puede calcular de manera muy eficiente; Los motores de JavaScript pueden producir un código de máquina altamente optimizado para este caso.

• integer % undefined por otro lado equivale a una forma menos eficiente de Float64Mod , ya que undefined se representa como un doble.

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

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

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

Answer 4

TL; DR El bucle 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 a no compilar la función con ninguna de estas optimizaciones para comenzar ( si el (JIT-) Compiler detectó / sospechó esta condición antes de la primera ''versión'' de la compilación), lea más abajo por qué;

Alguien solo tiene que decir esto (completamente asombrado que nadie ya lo hizo):
Solía ​​haber un momento en el que el fragmento de OP sería un ejemplo de facto en un libro de programación para principiantes destinado a resumir / enfatizar que las "matrices" en javascript están indexadas a partir de 0, no 1, y como tal, se pueden usar como ejemplo de un ''error de principiantes'' común (¿no te encanta cómo evité la frase ''error de programación'' ;) ): acceso a la matriz fuera de los límites .

Ejemplo 1:
una Dense Array (que es contigua (significa que no hay espacios entre los índices) Y en realidad un elemento en cada índice) de 5 elementos que utilizan la indizació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 de un implementador de lenguaje ES262 ambas son formas de optimización):

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

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

Más precisamente: compilación JIT y, lo que es más importante, compilación JIT RE .

La especificación del lenguaje es básicamente una descripción de un conjunto de algoritmos (''pasos a seguir para lograr un resultado final definido''). Lo cual, como resultado, es una manera muy hermosa de describir un idioma. Y deja el método real que un motor utiliza 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 que cumpla con las especificaciones debe proporcionar resultados que cumplan con las especificaciones para cualquier entrada definida.

Ahora, con el código / bibliotecas / uso de javascript en aumento, y recordando la cantidad de recursos (tiempo / memoria / etc) que usa un compilador "real", está claro que no podemos hacer que los usuarios que visiten una página web esperen tanto tiempo (y les exijan) tener tantos recursos disponibles).

Imagina 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 función nombrado 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 es apenas raspando las permutaciones masivas posibles ... Ni siquiera sabemos qué tipo de TIPO la función REGRESAR hasta que hayamos terminado ...

Ahora imagine esta misma función: el código realmente se usa en diferentes tipos o incluso en variaciones de entrada, ambas descritas de forma completamente literal (en el código fuente) y dinámicamente ''en el programa'' arrays ''.

Por lo tanto, si tuviera que compilar la sum función JUST UNA VEZ, entonces la única manera que siempre devuelva el resultado definido por la especificación para todos y cada uno de los tipos de entrada, entonces, obviamente, solo al realizar TODOS los pasos principales Y secundarios prescritos por las especificaciones puede garantizar la conformidad con la especificación resultados (como un navegador sin nombre pre-y2k). No hay optimizaciones (porque no hay suposiciones) y se conserva el lenguaje de scripts interpretado de manera lenta.

La compilación JIT (JIT como Just In Time) es la solución popular actual.

Entonces, empiezas a compilar la función usando suposiciones con respecto a lo que hace, devuelve y acepta.
usted obtiene verificaciones tan simples como sea posible para detectar si la función podría comenzar a devolver resultados no conformes a las especificaciones (como porque recibe una entrada inesperada). Luego, deseche el resultado compilado anterior y vuelva a compilarlo con algo más elaborado, decida qué hacer con el resultado parcial que ya tiene (es válido confiar o computar nuevamente para estar seguro), vuelva a vincular la función con el programa y Inténtalo de nuevo. En última instancia, volviendo a la interpretación de guiones paso a paso como en las especificaciones.

¡Todo esto lleva tiempo!

Todos los navegadores funcionan en sus motores, para cada subversión verás que las cosas mejoran y regresan. 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 que cumplen con las especificaciones y eso es lo que importa!

En pocas palabras, solo porque la semántica del lenguaje de javascript a menudo nos respalda (como con este error silencioso en el ejemplo de OP) no significa que los errores "estúpidos" aumenten nuestras posibilidades de que el compilador escupa código de máquina rápido. Asume que escribimos las instrucciones ''generalmente'' correctas: el mantra actual que debemos tener los ''usuarios'' (del lenguaje de programación) es: ayude al compilador, describa lo que queremos, favorece los modismos comunes (tome las sugerencias de asm.js para una comprensión básica Lo que los navegadores pueden tratar de optimizar y por qué).

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

El acceso a propiedades de objetos no existentes y elementos de matriz fuera de límites devuelve el valor undefined 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 una optimización JIT efectiva es que los programadores usan las características dinámicas de JavaScript de una manera sistemática. Por ejemplo, los compiladores JIT aprovechan el hecho de que las propiedades de los objetos a menudo se agregan a un objeto de un tipo dado en un orden específico o que los accesos a matrices fuera de límites ocurren raramente. Los compiladores JIT explotan estas suposiciones 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 a la interpretación del programa.

Fuente:
"JITProf: Localización precisa del código JavaScript poco amigable de JIT"
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 la matriz enlazada):

Compilación anticipada de tiempo

Debido a que 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 números enteros y números de punto flotante;
• ausencia de verificaciones de tipo runtime;
• ausencia de recolección de basura; y
• Montones de carga y almacenes eficientes (con estrategias de implementación que varían según la plataforma).

El código que no se puede validar debe volver a ejecutarse 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 en el rendimiento interno del motor al eliminar los límites de verificación (mientras que simplemente levantando los límites de verificación fuera del bucle ya tenía una mejora del 40%).

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

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

• Llamar a isPrimeDivisible
• Compile isPrimeDivisible usando suposiciones generales (como acceso sin límites)
• Hacer trabajo
• BAM, de repente, la matriz accede fuera de límites (justo al final).
• Crap, dice engine, recompilemos isPrimeDivisible usando diferentes (menos) suposiciones, y este motor de ejemplo no trata de averiguar si puede reutilizar el resultado parcial actual, por lo que
• Vuelva a calcular todo el trabajo utilizando una función más lenta (ojalá termine, de lo contrario repita y esta vez simplemente interprete el código).
• Resultado de retorno

De ahí que el tiempo fuera entonces:
¡Primero ejecute (falló al final) + haciendo todo el trabajo nuevamente 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 !

EDITAR 2: (descargo de responsabilidad: conjetura basada en los hechos a continuación)
Cuanto más lo pienso, más pienso que esta respuesta podría explicar la razón más dominante de esta "penalización" en el fragmento erróneo a (o el bono de rendimiento en el fragmento b, dependiendo de cómo lo pienses), precisamente por qué Soy un adagio en llamarlo (fragmento a) un error de programación:

Es bastante tentador suponer que this.primes es una numeración pura ''matriz densa'' que era

• Literal codificado en código fuente (se sabe que es un excelente candidato para convertirse en una matriz "real", ya que todo lo que el compilador ya conoce antes del tiempo de compilación) O
• lo más probable es que se genere utilizando una función numérica que rellene un tamaño preestablecido ( 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 longitud de la matriz de primes 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 Arrays como copia sobre modificación (cuando sea necesario), lo que hace que su manejo sea mucho más rápido (si no los cambia).

Por lo tanto, es razonable suponer que lo más probable es que Array primes ya sea una matriz optimizada internamente que no se modifique después de la creación (es fácil 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 está (si corresponde) al motor) almacenado de una manera optimizada, casi como si se Typed Array una Typed Array .

Como he tratado de aclarar con mi ejemplo de función de sum , los argumentos que se pasan influyen en gran medida en lo que realmente debe suceder y, como tal, cómo se compila ese código en particular a código de máquina. Pasar una String a la función de sum no debería cambiar la cadena, ¡sino cambiar la forma en que se compila JIT! Pasar una matriz a la sum debe compilar una versión diferente (tal vez incluso adicional para este tipo, o ''forma'', como la llaman, del objeto que se aprobó) del código de máquina.

Como parece un poco bueno para convertir los arreglos de tipo Typed_Array Array sobre la marcha en algo_else mientras el compilador sabe que esta función ni siquiera la va a modificar.

Bajo estos supuestos se deja 2 opciones:

1. Compile como triturador de números asumiendo que no hay fuera de límites, corra en un problema fuera de límites al final, vuelva a compilar y rehacer el trabajo (como se describe en el ejemplo teórico en la edición 1 anterior)
2. El compilador ya ha detectado (o sospechado?) Fuera de acceso de acceso directo y la función se compiló con JIT como si el argumento pasado fuera un objeto disperso que resultara en un código de máquina funcional más lento (ya que tendría más controles / conversiones / coerciones etc.). En otras palabras: la función nunca fue elegible para ciertas optimizaciones, se compiló como si recibiera un argumento de "matriz dispersa" (similar).

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