Hola Habr! Les presento la traducción del artículo "Wormholes in JavaScript" de Mathius Buus.
Las computadoras son máquinas interesantes. En teoría, nos parecen matemáticos mecánicos ideales que trabajan con números y realizan bien las operaciones de suma, multiplicación y resta.
Sin embargo, tal abstracción es bastante engañosa. Nos aleja de la comprensión de que una computadora procesa diferentes operaciones matemáticas a diferentes velocidades. Si escribe en JavaScript (o en cualquier otro idioma) y le preocupa el rendimiento de los algoritmos que escribió, es muy importante comprender cómo funcionan las computadoras bajo el capó.
Si sabemos de lo que es capaz la computadora, podemos usar los caminos más cortos o agujeros de gusano para hacer que nuestros programas sean mucho más rápidos de lo que esperábamos.
Wormhole en la operación de obtener el resto de la división
¿Qué significa exactamente esto? Veamos un ejemplo: imagine que queremos implementar una lista de anillo . Una lista de anillo es una lista de tamaño fijo en la que las inserciones más grandes que el tamaño de la lista se mueven a la parte superior de la lista y en un círculo. Las listas de llamadas son muy convenientes para muchas cosas, como la recopilación de estadísticas para intervalos de tiempo específicos, el almacenamiento en búfer de datos y más, pero observe esta implementación:
const list = new Array(15000) function set (i, item) {
¿Qué tan rápido se ejecuta este código? Hagamos una prueba de velocidad simple
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
En mi computadora, tardó ~ 4 segundos para mil millones de insertos. No esta mal.
Sin embargo, apliquemos un agujero de gusano computacional y cambiemos el tamaño de la matriz a un número mágico:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
Intentemos ejecutar la prueba de rendimiento nuevamente. En mi computadora, la prueba se completó en ~ 1.5 segundos. Más del doble de aumento debido al simple cambio de tamaño. Para entender por qué sucede esto, debemos entender lo siguiente, debajo del capó, la computadora funciona con números con base 2. Es importante saber si obtenemos el resto de la división (% de operación). Tal cálculo es mucho más simple si el número es múltiplo de 2 (2 ^ n) b 16384 es 2 ^ 14. De hecho, la computadora mira el número en forma binaria y simplemente toma los últimos n bits.
Por ejemplo: ¿qué sucederá cuando se realice dicha operación 353 500% 16 384? 353 500 en representación binaria se verá como 1010110010011011100. Desde 16384 == 2 ^ 14 - necesitamos tomar los últimos 14 bits - 10101 (10010011011100) o 9 346.
Podemos usar este conocimiento en relación con otro agujero de gusano. Para una computadora, es muy simple y rápido tomar los últimos n bits. De hecho, solo es necesario producir binario y (operación &) con el número (2 ^ n) - 1
const list = new Array(16384) function set (i, item) {
Al ejecutar la prueba de rendimiento nuevamente en mi computadora, veremos que el tiempo de ejecución disminuirá a ~ 1s o habrá un aumento de cuatro veces en el rendimiento en comparación con la primera ejecución. Y todo esto debido a la comprensión de cómo funciona la computadora.
Los compiladores inteligentes o máquinas virtuales pueden hacer este tipo de optimización al convertir la operación de obtener el resto detrás de escena en una operación bit a bit y viceversa. De hecho, la última VM V8 Javascript (no implementada en NodeJS) hace exactamente eso.
Agujero de gusano numérico
Otro molehill útil es comprender cómo funciona la lectura y escritura de números. ¿Recuerdas cómo usamos computadoras de 32 bits y cómo obtuvimos 64 bits? Y hasta 32 bits teníamos 16 bits. ¿Qué significa exactamente esto? Por lo general, pensamos de esta manera: cuánta RAM tenemos en la computadora. 2 ^ 32 = 4294967296 o 4 GB, lo que significa que solo podemos acceder a 4 GB de memoria en una computadora de 32 bits. Cuando escribimos un programa JS, generalmente no necesitamos pensar en ello, porque generalmente no usamos tanta memoria.
Sin embargo, es muy importante comprender la diferencia entre las computadoras de 32 bits y las de 64 bits. Dado que los procesadores recibieron registros de 64 bits en computadoras de 64 bits, las operaciones se han vuelto 2 veces más rápidas que en computadoras de 32 bits, donde solo tenía registros de 32 bits.
¿Cómo podemos usar la información sobre este agujero de gusano?
Escribamos un programa simple que copie un Uint8Array a otro. Si no está familiarizado con Unit8Arrays, son muy similares a los Buffers en NodeJS, o simplemente "limpian" la memoria.
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
Nuevamente, midamos la velocidad ejecutando una prueba de rendimiento.
// 1MB Uint8Arrays const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd()
En mi computadora, el programa se completó en ~ 7.5 segundos. ¿Cómo podemos usar un agujero de gusano para acelerar? Usando Uint8Array solo copiamos 8 bits a la vez, pero al tener una computadora de 64 bits podemos copiar 64 bits de información al mismo tiempo. Podemos hacer esto en JavaScript convirtiendo nuestro Uint8Array en un Float64Array antes de copiar, lo que no nos costará nada.
function copy (input, output) { // input.length <= output.length // 64- // , // 64- // BigInts JavaScript, BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { // 64- output64[i] = input64[i] } }
Al ejecutar nuevamente las pruebas de rendimiento, obtenemos un tiempo de ejecución de 1 segundo, lo que da un aumento de 8 veces en la velocidad.
Para copiar, una solución aceptable sería usar el método array.set (otherArray) para Uint8Array, que nos da copia en código nativo, que es mucho más rápido que cualquier otro agujero de gusano. Como referencia, esto dará un resultado de ~ 0.2 segundos de ejecución en nuestra prueba en mi computadora, que es 5 veces más rápido que la solución anterior.
Una galaxia de JavaScript está llena de agujeros de gusano
Usar los agujeros de gusano anteriores te ayudará a hacer toneladas de algoritmos del mundo real mucho más rápido. Hay muchos más de esos agujeros de gusano. Mi favorito es Math.clz32 , un método que devuelve el número de cero bits iniciales en una representación binaria de 32 bits de un número. Podemos usar este método para muchos algoritmos interesantes. Lo usé para acelerar la implementación de campos de bits 4 veces, lo que condujo a una disminución del consumo de memoria en 4 veces y me permitió ordenar los números en algunas situaciones mucho más rápido.
Comprender los principios básicos de la computadora le permite escribir los programas más rápidos que necesitamos. Este conocimiento es importante incluso cuando escribe en un lenguaje de alto nivel como JavaScript.
PD:
Un agradecimiento especial por la ayuda en traducir y actualizar la traducción a Olga Pereverzeva