Olá Habr! Apresento a você a tradução do artigo "Buracos de Minhoca em JavaScript", de Mathius Buus.
Computadores são máquinas interessantes. Em teoria, eles nos parecem matemáticos mecânicos ideais, trabalhando com números e realizando operações de adição, multiplicação e subtração.
No entanto, essa abstração é bastante enganadora. Isso nos afasta da compreensão de que um computador processa diferentes operações matemáticas em diferentes velocidades. Se você escreve em JavaScript (ou qualquer outro idioma) e se preocupa com o desempenho dos algoritmos que escreveu, é muito importante entender como os computadores funcionam sob o capô.
Se soubermos do que o computador é capaz, podemos usar os caminhos mais curtos ou buracos de minhoca para tornar nossos programas muito mais rápidos do que esperávamos.
Buraco de minhoca na operação de obtenção do restante da divisão
O que exatamente isso significa? Vejamos um exemplo: imagine que queremos implementar uma lista de toques . Uma lista de toques é uma lista de tamanho fixo na qual as inserções maiores que o tamanho da lista são movidas para o topo da lista e em um círculo. As listas de toques são muito convenientes para muitas coisas - como coletar estatísticas para intervalos de tempo específicos, armazenar dados em buffer e muito mais, mas observe esta implementação:
const list = new Array(15000) function set (i, item) {
Com que rapidez esse código é executado? Vamos executar um teste de velocidade simples
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
No meu computador, levou ~ 4 segundos para 1 bilhão de inserções. Nada mal.
No entanto, vamos aplicar um buraco de minhoca computacional e alterar o tamanho da matriz para um número mágico:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
Vamos tentar executar o teste de desempenho novamente. No meu computador, o teste foi concluído em ~ 1,5 segundos. Aumento mais que o dobro devido ao redimensionamento simples. Para entender por que isso acontece, precisamos entender o seguinte, sob o capô, o computador trabalha com números com base 2. É importante saber se obtemos o restante da divisão (operação%). Esse cálculo é muito mais simples se o número é um múltiplo de 2 (2 ^ n) b 16384 e é 2 ^ 14. De fato, o computador olha para o número na forma binária e simplesmente pega os últimos n bits.
Por exemplo: o que acontecerá quando uma operação desse tipo for realizada 353 500% 16 384? 353 500 na representação binária será semelhante a 1010110010011011100. Desde 16384 == 2 ^ 14 - precisamos pegar os últimos 14 bits - 10101 (10010011011100) ou 9 346.
Podemos usar esse conhecimento em relação a outro buraco de minhoca. Para um computador, é muito simples e rápido obter os últimos n bits. De fato, é necessário apenas produzir binário e (operação &) com o número (2 ^ n) - 1
const list = new Array(16384) function set (i, item) {
Ao executar o teste de desempenho novamente no meu computador, veremos que o tempo de execução diminuirá para ~ 1s ou haverá um aumento de quatro vezes no desempenho em comparação com a primeira execução. E tudo isso devido à compreensão de como o computador funciona.
Compiladores ou VMs inteligentes podem fazer esse tipo de otimização, transformando a operação de colocar o restante dos bastidores em uma operação bit a bit e vice-versa. De fato, a VM Javascript V8 mais recente (não implementada no NodeJS) faz exatamente isso.
Buraco de Minhoca Numérico
Outro ponto útil é entender como funciona a leitura e a escrita de números. Lembra como usamos computadores de 32 bits e como obtivemos 64 bits? E até 32 bits, tínhamos 16 bits. O que exatamente isso significa? Normalmente, pensamos dessa maneira - quanta RAM temos no computador. 2 ^ 32 = 4294967296 ou 4 GB, o que significa que só podemos acessar 4 GB de memória em um computador de 32 bits. Quando escrevemos um programa JS, geralmente não precisamos pensar sobre isso, porque geralmente não usamos tanta memória.
No entanto, é muito importante entender a diferença entre computadores de 32 e 64 bits. Como os processadores receberam registros de 64 bits em computadores de 64 bits, as operações tornaram-se 2 vezes mais rápidas que nos computadores de 32 bits, nos quais você tinha apenas registros de 32 bits.
Como podemos usar informações sobre esse buraco de minhoca?
Vamos escrever um programa simples que copie um Uint8Array para outro. Se você não está familiarizado com o Unit8Arrays, eles são muito semelhantes aos buffers no NodeJS ou simplesmente "limpam" a memória.
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
Novamente, vamos medir a velocidade executando um teste de desempenho.
// 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()
No meu computador, o programa foi concluído em ~ 7,5 segundos. Como podemos usar um buraco de minhoca para acelerar? Usando o Uint8Array, copiamos apenas 8 bits por vez, mas, com um computador de 64 bits, podemos copiar 64 bits de informação ao mesmo tempo. Podemos fazer isso em JavaScript convertendo nosso Uint8Array em um Float64Array antes de copiar, o que não nos custará 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] } }
Ao executar os testes de desempenho novamente, obtemos um tempo de execução de 1 segundo, o que aumenta em 8 vezes a velocidade.
Para copiar, uma solução aceitável seria usar o método array.set (otherArray) para Uint8Array, que nos permite copiar em código nativo - que é muito mais rápido que qualquer outro buraco de minhoca. Para referência, isso resultará em aproximadamente 0,2 segundos de execução em nosso teste no meu computador, que é 5 vezes mais rápido que a solução anterior.
Uma galáxia de JavaScript está cheia de buracos de minhoca
O uso dos buracos de minhoca acima o ajudará a tornar toneladas de algoritmos do mundo real muito mais rápidos. Existem muitos outros buracos de minhoca. Meu favorito é Math.clz32 , um método que retorna o número de zero bits à esquerda em uma representação binária de um número de 32 bits. Podemos usar esse método para muitos algoritmos interessantes. Usei-o para acelerar a implementação de campos de bits em 4 vezes, o que levou a uma diminuição no consumo de memória em 4 vezes e me permitiu classificar números em algumas situações muito mais rapidamente.
Compreender os princípios básicos do computador permite que você escreva os programas mais rápidos que precisamos. Esse conhecimento é importante mesmo quando você escreve em uma linguagem de alto nível, como JavaScript.
PS:
Agradecimentos especiais pela ajuda na tradução e ajuste da tradução para Olga Pereverzeva