Búsqueda de sitios web

javascript - ¿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 explicarlo? 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;
}

(Pista: primes es un arreglo 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 velocidad es significativa, en mi prueba en el 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

Respuesta #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 un arreglo que crece hasta 25,000 elementos, una iteración más o menos solo haría una diferencia mínima. Como estimació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 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 extra, y el problema se explica cerca del final de la presentación.

this.primes es un arreglo contiguo (cada elemento contiene un valor) y todos los elementos son números.

Un motor de JavaScript puede optimizar tal arreglo para que sea un arreglo simple de números reales, en lugar de un arreglo de objetos que resultan contener números pero 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 el arreglo es mucho más pequeño, por lo que se ajustará mejor en la memoria caché. Pero hay algunas condiciones que pueden impedir que se use este formato optimizado.

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

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

¿Ahora cuál es el valor de a[1]? No tiene valor. (No es correcto decir que tiene el valor undefined - un elemento de un arreglo que contiene el valor undefined es diferente de un elemento de un arreglo 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 potencialmente optimizarse en una matriz de solo números.

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

El primer bucle con <= intenta leer un elemento más allá del final del arreglo. El algoritmo todavía funciona correctamente, porque en la última iteración extra:

  • this.primes[i] se evalúa como undefined porque i está más allá del final del arreglo.
  • candidate % undefined (para cualquier valor de candidate) se evalúa como NaN.
  • NaN == 0 se evalúa como false.
  • Por lo tanto, el return true no se ejecuta.

Así que es como si la iteración extra nunca hubiera ocurrido: no tiene ningún efecto en el resto de la lógica. El código produce el mismo resultado que produciría sin la iteración extra.

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

El segundo bucle con < lee solo los elementos que existen dentro del arreglo, por lo que permite un arreglo 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 antes y después de eso.

Tuve la oportunidad de asistir a esta misma presentación de Google I/O y hablé con el ponente (uno de los autores de V8) después. Yo había estado usando una técnica en mi propio código que implicaba leer más allá del final de un arreglo como un intento equivocado (en retrospectiva) de optimizar una situación particular. Él confirmó que si intentabas incluso leer más allá del final de un arreglo, eso impediría que se usara el formato optimizado simple.

Si lo que dijo el autor de V8 sigue siendo cierto, entonces leer más allá del final del arreglo impedirí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 este caso de manera eficiente, o que otros motores de JavaScript lo manejen de manera diferente. No sé a ciencia cierta sobre eso, pero esta desoptimización es de lo que hablaba la presentación.

Respuesta #2

Trabajo en V8 en Google y quería proporcionar información adicional además de 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();

Primero y ante todo, la diferencia de rendimiento no tiene nada que ver directamente con los operadores < y <=. Así que, por favor, no te compliques innecesariamente solo para evitar <= en tu código porque leíste en Stack Overflow que es lento — ¡no lo es!

En segundo lugar, la gente señaló que la matriz está "perforada". Esto no era evidente en el fragmento de código del mensaje del OP, pero se hace evidente cuando se observa el código que inicializa this.primes:

this.primes = new Array(iterations);

Esto da como resultado un arreglo con un tipo de elementos HOLEY en V8, incluso si el arreglo termina completamente lleno/empacado/contiguo. En general, las operaciones en arreglos con huecos son más lentas que las operaciones en arreglos empacados, pero en este caso la diferencia es despreciable: equivale a una verificación adicional de Smi (entero pequeño) (para protegerse contra los huecos) cada vez que accedemos a this.primes[i] en el bucle dentro de isPrimeDivisible. ¡No es gran cosa!

TL;DR El hecho de que el arreglo sea HOLEY no es el problema aquí.

Otros señalaron que el código 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 gran caída en el rendimiento. ¿Pero por qué? V8 puede manejar algunos de estos escenarios fuera de los límites con solo un impacto menor en el rendimiento. ¿Qué tiene de especial este caso en particular, entonces?

La lectura fuera de los límites resulta en que this.primes[i] sea undefined en esta línea:

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

Y eso nos lleva a el verdadero problema: ¡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 código máquina altamente optimizado para este caso.

  • integer % undefined por otro lado equivale a un Float64Mod mucho menos eficiente, ya que undefined se representa como un double.

El fragmento de código puede mejorarse de hecho cambiando el <= por < 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 los límites en este caso particular.

Respuesta #3

TL;DR El bucle más lento se debe a acceder a la matriz 'fuera de los 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 desde el principio (si el compilador (JIT) detectó/sospechó esta condición antes de la primera 'versión' de compilación), sigue leyendo más abajo para saber por qué;

Alguien simplemente tiene que decir esto (totalmente asombrado de que nadie lo haya hecho ya):
Solía haber un tiempo en que el fragmento del OP sería un ejemplo de facto en un libro de programación para principiantes destinado a ilustrar/enfatizar que las 'matrices' en JavaScript se indexan comenzando desde 0, no desde 1, y como tal, se usaba como ejemplo de un 'error común de principiantes' (¿no te encanta cómo evité la frase 'error de programación' ;)): acceso a Array fuera de los límites.

Ejemplo 1:
un Array Denso (siendo contiguo (significa sin espacios entre los índices) Y realmente un elemento en cada índice) de 5 elementos usando 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, en realidad no estamos hablando de la diferencia de rendimiento entre < y <= (o 'una iteración extra'), sino que estamos hablando de:
'¿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 del lenguaje ES262, ambos son formas de optimización):

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

El ítem 1 está suficientemente (y correctamente en mi opinión) explicado por la respuesta aceptada, pero eso solo dedica 2 palabras ('el código') a Ítem 2: compilación.

Más precisamente: ¡Compilación JIT e incluso más importante, recompilación JIT-RE!

La especificación del lenguaje es básicamente solo una descripción de un conjunto de algoritmos ('pasos a seguir para lograr un resultado definido'). Lo cual, como resulta, es una manera muy hermosa de describir un lenguaje. Y deja abierto el método real que un motor utiliza para lograr los resultados especificados a los implementadores, dando amplia oportunidad de idear formas más eficientes de producir resultados definidos. Un motor que cumpla con la especificación debería dar resultados conforme a la especificación para cualquier entrada definida.

Ahora, con el aumento del código/librerías/uso de javascript, y recordando cuántos recursos (tiempo/memoria/etc.) utiliza un compilador 'real', está claro que no podemos hacer que los usuarios que visitan una página web esperen tanto tiempo (y requerirles que tengan disponibles tantos recursos).

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 pases 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 considera que esto apenas está rascando las enormes posibles permutaciones... Ni siquiera sabemos qué tipo de TIPO devuelve la función hasta que terminemos...

Ahora imagina esta misma función-código siendo realmente utilizada en diferentes tipos o incluso variaciones de entrada, tanto completamente de manera literal (en el código fuente) descrita como dinámicamente en el programa generando 'arreglos'.

Así que, si compilaras la función sum SOLO UNA VEZ, entonces la única manera de que siempre devuelva el resultado definido por la especificación para cualquier tipo de entrada y para todas, 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 sin nombre anterior al año 2000). No hay optimizaciones (porque no hay suposiciones) y sigue siendo un lenguaje de scripting interpretado extremadamente lento.

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

Entonces, comienzas a compilar la función utilizando suposiciones sobre lo que hace, devuelve y acepta.
Ideas comprobaciones tan simples como sea posible para detectar si la función podría comenzar a devolver resultados que no cumplen la especificación (como porque reciba entradas inesperadas). Luego, desechas el resultado compilado anterior y recompilas en algo más elaborado, decides qué hacer con el resultado parcial que ya tienes (si es válido para confiar en él o calcular nuevamente para estar seguro), vuelves a conectar la función al programa y pruebas de nuevo. Finalmente, recurres a la interpretación por pasos del script como en la especificación.

¡Todo esto lleva tiempo!

Todos los navegadores funcionan con sus propios motores, para cada subversión verás cosas que mejoran y otras que retroceden. En algún momento de la historia, las cadenas eran realmente cadenas inmutables (de ahí que array.join fuera 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 la especificación y eso es lo que importa!

En resumen: el hecho de que la semántica del lenguaje de JavaScript a menudo nos respalde (como con este error silencioso en el ejemplo del OP) no significa que los errores 'estúpidos' aumenten nuestras posibilidades de que el compilador genere código máquina rápido. Se asume que escribimos las instrucciones 'usualmente' correctas: el mantra actual que nosotros, los 'usuarios' (del lenguaje de programación), debemos tener es: ayuda al compilador, describe lo que queremos, favorece los idioms comunes (toma pistas de asm.js para entender de manera básica qué puede tratar de optimizar el navegador y por qué).

Debido a esto, hablar sobre el rendimiento es tanto importante PERO TAMBIÉN 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 inexistentes y a elementos de arreglo fuera de los límites devuelve el valor undefined en lugar de generar una excepción. Estas características dinámicas hacen que programar en JavaScript sea conveniente, pero también dificultan compilar JavaScript en código máquina eficiente.

...

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

Fuente:
"JITProf: Localizando código JavaScript poco amigable con 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 a arrays fuera de los límites):

Compilación anticipada

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, asm.js validado es susceptible de compilación anticipada (AOT). Además, el código generado por un compilador AOT puede ser bastante eficiente, presentando:

  • representaciones desempaquetadas de enteros y números de punto flotante;
  • ausencia de comprobaciones de tipo en tiempo de ejecución;
  • ausencia de recolección de basura; y
  • cargas y almacenamientos eficientes en el heap (con estrategias de implementación que varían según la plataforma).

El código que no logra validarse 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 internas de rendimiento del motor al eliminar la verificación de límites (mientras que solo levantar la verificación de límites fuera del bucle ya tuvo una mejora del 40%).

EDICIÓN:
tenga en cuenta que múltiples fuentes hablan sobre diferentes niveles de recompilación JIT hasta la interpretación.

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

  • Llamar a isPrimeDivisible
  • Compilar isPrimeDivisible usando supuestos generales (como no acceder fuera de los límites)
  • Haz el trabajo
  • BAM, de repente accesos a arreglos fuera de los límites (justo al final).
  • Mierda, dice el motor, recompilaremos esa función isPrimeDivisible usando diferentes (menos) suposiciones, y este motor de ejemplo no intenta averiguar si puede reutilizar el resultado parcial actual, así que
  • Recalcula todo el trabajo usando una función más lenta (esperemos que termine, de lo contrario repite y esta vez solo interpreta el código).
  • Devolver resultado

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

EDICIÓN 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 en realidad explicar la razón más dominante de esta 'penalización' sobre el fragmento erróneo a (o la bonificación por rendimiento en el fragmento b, dependiendo de cómo lo veas), precisamente por lo que estoy tan firme en llamar al fragmento a un error de programación:

Es bastante tentador asumir que this.primes es un 'array denso' puramente numérico que fue o

  • Literal codificado directamente en el código fuente (conocido como excelente candidato para convertirse en un 'array real' ya que todo ya es conocido por el compilador antes del tiempo de compilación) O
  • probablemente generado usando una función numérica que llena un (new Array(/*valor de tamaño*/)) pre-dimensionado en orden secuencial ascendente (otro candidato conocido desde hace mucho tiempo para convertirse en un array 'real').

También sabemos que la longitud del arreglo primes está almacenada 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 los Arrays como copy-on-modify (cuando es necesario), lo que hace que manejarlos sea mucho más rápido (si no los modificas).

Por lo tanto, es razonable suponer que el array primes probablemente ya es un array optimizado internamente, que no se modifica después de su creación (fácil de saber para el compilador si no hay código que modifique el array después de su creación) y, por lo tanto, ya está (si es aplicable al motor) almacenado de manera optimizada, casi como si fuera un Typed Array.

Como he intentado dejar claro con mi ejemplo de la función sum, el/los argumento(s) que se pasan influyen fuertemente en lo que realmente necesita ocurrir y, como tal, en cómo ese código particular se compila a código máquina. Pasar un String a la función sum no debería cambiar la cadena, ¡sino cambiar cómo la función se compila en tiempo de ejecución (JIT)! Pasar un Array a sum debería compilar una versión diferente (quizás incluso adicional para este tipo, o 'forma' como llaman, del objeto que se pasó) de código máquina.

¡Parece un poco absurdo convertir sobre la marcha el Array similar a Typed_Array primes a algo_más mientras el compilador sabe que esta función ni siquiera lo va a modificar!

Bajo estas suposiciones, eso deja 2 opciones:

  1. Compilar como procesador de números asumiendo que no hay desbordamiento, encontrarse con un problema de desbordamiento al final, recompilar y rehacer el trabajo (como se describe en el ejemplo teórico en la edición 1 arriba)
  2. El compilador ya había detectado (¿o sospechado?) un acceso fuera de los límites de antemano y la función fue compilada en JIT como si el argumento pasado fuera un objeto disperso, lo que resultó en un código máquina funcional más lento (ya que tendría más comprobaciones/conversiones/coerciones, etc.). En otras palabras: la función nunca fue elegible para ciertas optimizaciones, se compiló como si hubiera recibido un argumento 'similar a un array disperso'.

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

Artículos relacionados