Atree: Uma implementação de árvore simples e eficiente sem ponteiros
Uma estrutura de árvore baseada em arrays e “sem ponteiros”, chamada Atree, está gerando debate sobre se índices em vetores planos realmente trazem vantagens de desempenho e localidade de cache em relação às árvores tradicionais baseadas em ponteiros. Os defensores destacam benefícios para workloads específicos — como compiladores, computação científica e operações em lote no estilo GPU ou SIMD — em que as árvores são percorridas linearmente ou quase sempre apenas para leitura, e o armazenamento compacto e contíguo pode render grandes acelerações. Os críticos argumentam que as consultas de filhos em O(n), a falta de ordenação inerente e a dependência de seguir índices tornam a estrutura inferior a árvores com foco em cache já estabelecidas (como B-trees ou layouts Eytzinger) para muitas hierarquias dinâmicas do mundo real, defendendo que a escolha cuidadosa da estrutura de dados e benchmarks empíricos importam mais do que simplesmente evitar ponteiros.
Design Geral & Uso Pretendido
- Atree representa uma árvore como arrays planos com índices de pai (struct-of-arrays, “sem ponteiros” no sentido de não usar ponteiros brutos da linguagem).
- Objetivos: localidade de cache, menos alocações, serialização mais fácil, compatibilidade com processamento estilo array/vetor e possível amigabilidade com GPU.
- Vários comentaristas observam que esse estilo já é comum em domínios específicos (heaps, conjuntos disjuntos, árvores de ECS, hierarquias de animação esquelética, árvores científicas).
Desempenho, Big-O e Compromissos Práticos
- Principal crítica: obter os filhos de um nó é O(N) por meio de uma varredura completa, visto como inviável para muitos workloads, especialmente árvores grandes.
- Os defensores argumentam:
- Para muitos passes (por exemplo, varreduras completas no estilo de compiladores, ou workloads em que N é pequeno e limitado), varreduras O(N) são aceitáveis ou até eficientes.
- Big-O sozinho pode enganar; fatores constantes, comportamento de cache e padrões de I/O frequentemente dominam.
- Os críticos respondem que, para árvores grandes, varrer toda a estrutura a cada consulta de filhos não é realista, e melhores assintóticos importam.
- Debate sobre estilo vetorial/SIMD: se as operações são sobre “todos os nós de uma vez”, uma única passagem O(N) para todos os filhos pode ser suficiente; se você precisa repetidamente dos filhos de um único nó, isso é ruim.
Localidade de Cache, Índices vs Ponteiros
- Muitos observam que índices inteiros são, na prática, ponteiros; os principais benefícios são:
- Índices podem ser menores, melhor compactados e facilmente serializados ou enviados pela rede.
- A estrutura inteira pode viver em um único bloco contíguo, melhorando os acertos de cache.
- Contra-argumento: “seguir índices” ainda tem o mesmo caráter de falta de cache que “seguir ponteiros” se os padrões de acesso forem irregulares.
- Há consenso geral de que um layout amigável ao cache depende de contiguidade e padrões de acesso, e não apenas de evitar ponteiros da linguagem.
Estruturas Alternativas e Estendidas
- Alternativas mencionadas: árvores de Eytzinger (implícitas), B-trees cache-oblivious, B/B+ trees, layouts van Emde Boas, árvores com ponteiros alocadas em pool/arena.
- Sugestões para estender Atree:
- Adicionar índices de primeiro-filho/próximo-irmão em vez de (ou além de) pai.
- Agrupar filhos juntos, possivelmente ordenados, ao custo de inserções O(N) (memmove).
- Manter arrays explícitos de folhas com mapas de índices auxiliares para adição/remoção de folhas em O(1).
- Limitação observada: o Atree, como apresentado, não tem ordenação nem localidade inerentes entre irmãos; ordenar filhos ou tornar travessias ordenadas eficientes exige invariantes e complexidade extras.