👦🏻 👊🏻 🏞️ Sobre a implementação da estrutura de dados do mapa no V8 💅🏼 🚫 🔽

O padrão ECMAScript 2015 , conhecido como o ES6, há muitos novos JavaScript-coleções, como Map, Set, WeakMape WeakSet. Eles parecem ser um ótimo complemento para os recursos JavaScript padrão. Eles são amplamente usados em várias bibliotecas, em aplicativos, no núcleo do Node.js. Hoje vamos falar sobre a coleção Map, tentar descobrir as especificidades de sua implementação no V8 e tirar algumas conclusões práticas com base no conhecimento adquirido.

O padrão ES6 não fornece uma indicação clara da abordagem que deve ser adotada para implementar o suporte à estrutura de dados Map. Ele apenas dá algumas dicas sobre as maneiras possíveis de implementá-lo. Ele também contém informações sobre o esperado deMapmétricas de desempenho:

O objeto Map deve ser implementado usando tabelas hash ou outros mecanismos que, em média, fornecem acesso sublinear aos elementos da coleção. As estruturas de dados usadas na especificação do mapa destinam-se apenas a descrever a semântica observável dos objetos do mapa. Eles não foram concebidos como um modelo real para a implementação desses objetos.

Como você pode ver, a especificação dá a quem cria motores JS muita liberdade. Mas, ao mesmo tempo, não há diretrizes específicas sobre a abordagem específica usada para implementação Map, seu desempenho e características de consumo de memória. Se as estruturas de dados são usadas em uma parte crítica de seu aplicativoMape se você gravar grandes quantidades de informações nessas estruturas de dados, um conhecimento sólido da implementação Mapcertamente será de grande benefício para você.

Tenho experiência em desenvolvimento Java, estou acostumado com coleções Java, onde você pode escolher entre diferentes implementações da interface Mape até mesmo ajustar a implementação selecionada se a classe correspondente suportar. Além disso, em Java, você sempre pode ler o código-fonte aberto de qualquer classe da biblioteca padrão e se familiarizar com sua implementação (ela, é claro, pode mudar em novas versões, mas apenas no sentido de aumentar a eficiência). É por isso que não resisti a aprender como os objetos funcionam Mapno V8.

Antes de começar, quero observar que o que será discutido abaixo se refere ao mecanismo V8 8.4, que é integrado à nova versão dev do Node.js (mais precisamente, estamos falando do commit 238104c) Você não precisa esperar nada fora das especificações.

O algoritmo por trás da implementação do mapa

Em primeiro lugar, direi que as estruturas de dados são Mapbaseadas em tabelas hash. Abaixo, estou assumindo que você sabe como funcionam as tabelas de hash. Se você não está familiarizado com as tabelas de hash, deve primeiro ler sobre elas ( aqui , por exemplo) e só então continuar lendo este artigo.

Se você tem experiência significativa com objetos Map, então pode já ter notado uma contradição. Ou seja, as tabelas de hash não têm garantia de retornar itens em alguma ordem constante ao iterar sobre eles. E a especificação ES6 afirma que para implementar um objeto, Mapé necessário, ao percorrê-lo, retornar os elementos na ordem em que foram adicionados a ele. Como resultado, o algoritmo "clássico" para a implementaçãoMapnão serve. Mas há a sensação de que, com algumas alterações, ainda pode ser usado.

O V8 usa as chamadas " tabelas hash determinísticas " propostas por Tyler Close. O seguinte pseudocódigo, com base no TypeScript, demonstra as estruturas de dados básicas usadas para implementar essas tabelas de hash:

interface Entry {
    key: any;
    value: any;
    chain: number;
}
 
interface CloseTable {
    hashTable: number[];
    dataTable: Entry[];
    nextSlot: number;
    size: number;
}

Aqui, a interface CloseTablerepresenta uma tabela hash. Ele contém uma matriz hashTablecujo tamanho é equivalente ao número de contêineres de hash. O elemento da matriz com o índice Ncorresponde ao N-ésimo contêiner hash e armazena o índice de seu elemento principal que está na matriz dataTable. E essa matriz contém os registros da tabela na ordem em que foram inseridos nela. As entradas são apresentadas pela interface Entry. Por fim, cada entrada possui uma propriedade chainque aponta para a próxima entrada na cadeia de entradas do contêiner de hash (ou, mais precisamente, em uma lista vinculada individualmente).

Cada vez que um novo registro é inserido na tabela, ele é armazenado no elemento da matriz dataTablecom índicenextSlot... Esse processo também requer a atualização dos dados no contêiner de hash correspondente, o que faz com que o registro inserido se torne o novo último elemento da lista vinculada individualmente.

Quando um registro é removido de uma tabela, ele é removido dataTable(por exemplo, escrevendo em suas propriedades keye valuevalores undefined). Então, a entrada que o precede e a que o segue são vinculadas diretamente uma à outra. Como você deve ter notado, isso significa que todas as entradas excluídas continuam a ocupar espaço no dataTable.

Agora, para a última peça do nosso quebra-cabeça. Quando uma tabela está cheia de registros (atuais e excluídos), ela deve ser refeita (reconstruída) com um aumento em seu tamanho. O tamanho da mesa pode ser alterado para baixo.

Com essa abordagem, percorrer a estrutura de dados é o Mapmesmo que percorrer uma matriz dataTable. Isso garante que a ordem em que os registros são inseridos na tabela seja preservada e que o padrão seja atendido. Com isso em mente, eu esperaria que a maioria (se não todos) os mecanismos JS usassem tabelas de hash determinísticas como um dos mecanismos de implementação subjacentes Map.

Pesquisa prática do algoritmo

Vamos dar uma olhada em alguns exemplos para nos ajudar a explorar o algoritmo na prática. Suponha que temos CloseTable2 contêineres de hash ( hastTable.length), a capacidade total dos quais é de 4 elementos ( dataTable.length). Esta tabela é preenchida com o seguinte conteúdo:

// ,    -, 
// ,     ,   function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)

A representação interna da tabela obtida neste exemplo pode ser assim:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: 0,
            value: 'a',
            chain: 2 //  <2, 'c'>
        },
        {
            key: 1,
            value: 'b',
            chain: -1 // -1    
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3, //    
    size: 3
}

Se você excluir um registro usando o método table.delete(0), a tabela de hash terá a seguinte aparência:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: undefined, //  
            value: undefined,
            chain: 2 
        },
        {
            key: 1,
            value: 'b',
            chain: -1
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3,
    size: 2 //  
}

Se adicionarmos mais alguns registros à tabela, será necessário fazer o hash. Discutiremos esse processo em detalhes abaixo.

A mesma abordagem pode ser aplicada ao implementar estruturas de dados Set. A única diferença é que essas estruturas de dados não precisam de uma propriedade value.

Agora que descobrimos o que está por trás dos objetos Mapno V8, estamos prontos para seguir em frente.

Detalhes de implementação

A implementação da estrutura de dados Mapno V8 é escrita em C ++, após o qual o código JS recebe acesso aos mecanismos correspondentes. A maior parte do código relacionado Mapestá nas classes OrderedHashTablee OrderedHashMap. Já sabemos como funcionam essas aulas. Se você quiser dar uma olhada no código deles, poderá encontrá-lo aqui , aqui e aqui .

Como estamos especialmente interessados nos detalhes práticos da implementação Mapno V8, primeiro precisamos entender como a capacidade da tabela é definida.

Capacidade da mesa

No V8, a capacidade da tabela hash (estrutura de dados Map) é sempre uma potência de dois. Se falamos da taxa de utilização de contêineres hash, ela é sempre representada pelo número 2. Ou seja, a capacidade máxima da tabela 2 * number_of_bucketsé 2 vezes o número de contêineres hash. Ao criar um objeto vazio, Mapexistem 2 contêineres hash em sua tabela hash interna. Como resultado, a capacidade de tal objeto é igual a 4 registros.

Existe uma limitação na capacidade máxima de objetos Map. Em sistemas de 64 bits, isso será cerca de 16,7 milhões de registros. Essa limitação se deve às peculiaridades de representar estruturas de dados Mapno heap. Falaremos sobre isso mais tarde.

E, finalmente, o fator de aumento ou diminuição da tabela também é sempre representado pela multiplicação de algum número por 2. Isso significa que após 4 registros serem adicionados à tabela descrita, a próxima operação de inserção causará a necessidade de refazer o hash da tabela, durante o qual o tamanho da tabela aumentará em dois vezes. Com a diminuição do tamanho da mesa, ela, respectivamente, pode ficar 2 vezes menor.

Para ter certeza de que o que vi no código-fonte funciona exatamente como eu o entendi, modifiquei o código do motor V8 embutido no Node.js, tornando-o uma Mapnova propriedade bucketscontendo informações sobre o número de contêineres de hash. Você pode encontrar os resultados desta modificação aqui... Nesta montagem especial do Node.js, o seguinte script pode ser executado:

const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
  map.set({}, {});
}

Este script simplesmente insere Map100 registros na estrutura de dados . Isso é o que é exibido no console após iniciá-lo:

$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128

Como você pode ver, quando a mesa é preenchida, a cada mudança de tamanho, ela aumenta 2 vezes. Agora vamos tentar reduzir a tabela removendo elementos dela:

const map = new Map();
for (let i = 0; i < 100; i++) {
  map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
 
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  map.delete(i);
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
}

Este é o resultado deste script:

$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4

Aqui, novamente, você pode ver que o tamanho da tabela é reduzido cada vez que ela tem menos number_of_buckets / 2elementos.

Função Hash

Até agora, não tocamos na questão de como o V8 calcula códigos hash para chaves armazenadas em objetos Map. E esta é uma questão importante.

Para valores que podem ser classificados como numéricos, alguma função hash conhecida com uma baixa probabilidade de colisão é usada.

Para valores de string, um código hash é calculado com base nos próprios valores. Depois disso, esse código é armazenado em cache no cabeçalho interno.

E, finalmente, para objetos, os hashes são calculados com base em um número aleatório, e o que acontece é então armazenado em cache no cabeçalho interno.

Complexidade de tempo de operações com objetos de mapa

A maioria das operações realizadas em estruturas de dados Map, como setou delete, requerem a pesquisa por meio dessas estruturas de dados. Como no caso das tabelas hash "clássicas", a complexidade de tempo da pesquisa em nosso caso é O(1).

Imagine o pior cenário, quando a mesa está cheia, ou seja, ocupada Ndesde os Nassentos. Nesse caso, todos os registros pertencem a um único contêiner hash, e o registro necessário está no final da cadeia de registros. Em um cenário como este, você precisará realizar algumas etapas para localizar essa entrada N.

Por outro lado, no melhor cenário, quando a tabela está cheia e há apenas 2 registros em cada contêiner de hash, encontrar um registro exigirá apenas 2 etapas.

Certas operações em tabelas de hash são muito rápidas, mas este não é o caso com operações de hash. A complexidade de tempo da operação hash é O(N). Ele requer que uma nova tabela hash seja alocada no heap. Além disso, o rearranjo é executado conforme necessário, como parte das operações para inserir ou remover elementos da mesa. Portanto, por exemplo, a ligação map.set()pode acabar sendo muito "mais cara" do que o esperado. Felizmente, a operação de hash raramente é executada.

Consumo de memória

Claro, a tabela de hash subjacente Mapdeve ser armazenada no heap de alguma forma. Ele é armazenado no que é chamado de "armazenamento auxiliar". E aqui temos outro fato interessante. A tabela inteira (e, portanto, tudo o que é colocado nela Map) é armazenada em uma única matriz de comprimento fixo. A estrutura dessa matriz é mostrada na figura a seguir.

Matriz usada para armazenar estruturas de dados do mapa na memória As

partes individuais da matriz têm as seguintes finalidades:

Cabeçalho: contém informações gerais, como o número de contêineres de hash ou o número de itens removidos Map.
Detalhes do Hash Container: Aqui é onde armazenamos dados sobre os containers que correspondem ao array hashTabledo nosso exemplo.
Entradas da tabela de hash: é onde os dados correspondentes ao array são armazenados dataTable. Ou seja, ele contém informações sobre entradas da tabela de hash. Cada registro ocupa três células na matriz. Um armazena a chave, o segundo armazena o valor e o terceiro armazena o "ponteiro" para o próximo registro na cadeia.

Se falarmos sobre o tamanho do array, ele pode ser estimado aproximadamente como N * 3,5. Aqui Nestá a capacidade da mesa. Para entender o que isso significa em termos de consumo de memória, vamos imaginar que temos um sistema de 64 bits e que o recurso de compressão de ponteiro do V8 está desabilitado . Nesse caso, são necessários 8 bytes para armazenar cada elemento do array. Como resultado Map, 29 MB de memória heap são necessários para armazenar uma estrutura de dados que contém aproximadamente 1 milhão de registros.

Resultado

Neste artigo, cobrimos muitos itens relacionados à estrutura de dados Mapem JavaScript. Vamos resumir:

O V8 Mapusa tabelas hash determinísticas para implementação . É muito provável que essa estrutura de dados também seja implementada em outros mecanismos JS.
Os mecanismos que suportam o trabalho Mapsão implementados em C ++, após o que são apresentados como uma API acessível a partir de JavaScript.
Se falamos sobre a complexidade de tempo das operações realizadas com objetos Map, então elas, assim como quando se trabalha com tabelas hash "clássicas", têm complexidade O(1). Nesse caso, a complexidade de tempo da operação de hashing é O(N).
64- Map 1 29 , .
, , Set.

Map JavaScript-?

Sobre a implementação da estrutura de dados do mapa no V8