Bbtree, ordered map em Rust, mostra em benchmarks desempenho até 5x superior ao BTreeMap

O bbtree é um ordered map em Rust, escrito por Xiangpeng Hao, que se apresenta como substituto direto do BTreeMap e do BTreeSet da biblioteca padrão (via bbtree::unsync::BBTreeMap). Segundo o post do autor, ele chega a 5x a velocidade do BTreeMap em uma thread, 12x a do crossbeam-skiplist com 96 threads, usa 30% menos memória, não tem dependências e é compatível com no_std. São números do próprio autor, medidos nos benchmarks dele e de cada projeto integrado. O post descreve o artigo e o autor; o projeto é a biblioteca, publicada no repositório oficial (versão v0.1.5 na release listada).

A lógica técnica parte de um modelo de custo: um cache miss custa cerca de 100 ns, uma instrução cerca de 0,5 ns, e o tráfego de coerência de cache também força miss. Daí a prioridade é reduzir cache misses por busca. Nós de 16 a 32 itens permitem busca linear, que o autor prefere à binária por ser mais simples para o pipeline da CPU. Para chaves em heap, como String, o bbtree usa inline_keys (códigos fixos e densos, ideia próxima de German strings e StringView do Arrow) e prefix_keys (prefixo comum do nó, deduzido dos separadores no nó pai, então só o tamanho é guardado). Dentro do nó, a busca usa SIMD escrito à mão: AVX-512 em x86 (exige -C target-cpu=native e Rust 1.89 ou superior) e NEON em ARM. Num teste em M1 Pro, contar chaves em NEON manualmente baixou uma busca de 1.678 para 407 instruções e de 390 para 174 ns.

Há ainda um modo em lote que trata cada cache miss como um Future de async do Rust, com executor próprio sem alocação, para sobrepor latências. Nos casos de uso, o autor reporta ganhos de 1,37x a 6,83x no lugar de skiplists em quatro LSM-trees (fjall, SlateDB, Tonbo e Lance), 2,22x em INSERT e 1,90x em SELECT indexado no Turso, e resposta inicial 160 a 2.500x mais rápida ao mapear um bbtree do disco com mmap, sem reconstruir. Limitações: o ganho depende de especialização manual para tipos comuns (u64, String, Vec e outros) em Rust estável, e outros tipos precisam implementar o trait InlineKey. O resumo da notícia diz que o código foi escrito por um LLM, guiado por especialista e validado com verificação formal e testes. Veja o bbtree no GitHub e o artigo original.

Para quem opera memtables de LSM-tree ou índices em memória, o recado é que a estrutura de dados ainda rende muito quando o projeto parte de cache misses. Para quem avalia adotar, vale reproduzir os benchmarks no próprio workload, já que os números vêm do autor.