// Representacao interna e custo real
Uma ponte entre a enfase de Donald Knuth em representacao interna e a hierarquia moderna de memoria: L1, L2, L3 e RAM. A ideia central e simples: a mesma complexidade assintotica pode ter comportamento muito diferente dependendo de localidade e layout.
Base conceitual
Em The Art of Computer Programming, a analise nao para na abstracao da estrutura: ela observa como os dados sao representados, como sao ligados e como isso afeta custo.
A pagina aqui estende essa lente para hardware moderno. A nomenclatura
L1, L2, L3 e RAM e mais recente,
mas a preocupacao com localidade, acesso sequencial e saltos de ponteiro conversa diretamente
com a forma de pensar do livro.
Regra pratica
Estruturas que guardam elementos lado a lado em memoria costumam aproveitar melhor prefetch, cache lines e acesso sequencial.
Estruturas baseadas em nos espalhados pela heap costumam sofrer mais com misses de cache, especialmente quando a travessia depende de perseguir ponteiros.
Hierarquia
Os niveis abaixo estao em ordem do mais proximo ao core para o mais distante. Os tamanhos e latencias exatos variam por arquitetura; o objetivo aqui e mostrar a relacao relativa.
O diagrama abaixo mostra um acesso partindo do core e atravessando a hierarquia de memoria. Quando o dado nao e encontrado no nivel mais proximo, a busca avanca para um nivel maior e mais lento.
A leitura correta e esta: L1 responde primeiro, L2 entra quando ha miss em L1,
L3 amplia a chance de reaproveitamento entre nucleos, e a RAM fica como ultimo salto,
com custo muito maior de latencia.
Ilustracao didatica em loop continuo. Os valores de ciclos sao faixas aproximadas para comunicar relacao relativa, nao uma medicao exata de uma CPU especifica.
~3-5 ciclos
Mais perto do core. Melhor cenário para dados quentes e loops apertados.
~10-20 ciclos
Camada intermediária que absorve misses de L1 antes de chegar ao nível compartilhado.
~30-70 ciclos
Maior e normalmente compartilhado. Ainda é muito melhor do que buscar direto na RAM.
~100-300 ciclos
Último salto. Quando o acesso chega aqui, o custo real da operação sobe bastante.
Primeiro nivel de cache do core. Ideal para dados quentes e loops apertados.
Segundo nivel, ainda muito rapido, mas menos agressivo que L1.
Ultimo nivel de cache antes da memoria principal. Costuma ser compartilhado entre nucleos.
Memoria principal. Quando a busca chega aqui, o custo do acesso cresce bastante.
Localidade
Elementos vizinhos ficam proximos em memoria, o que ajuda prefetch e acesso sequencial.
Os nos podem estar espalhados pela heap, e cada salto depende de ponteiros.
Quando implementadas de forma contigua, herdam boa parte das vantagens de localidade do array.
Navegacao por ponteiros pode saltar entre regioes distantes de memoria, sobretudo em heaps fragmentadas.
Podem ser excelentes em complexidade media, mas o comportamento real depende do espalhamento das chaves, colisao e resize.
Em listas de adjacencia com ponteiros, a travessia pode perder localidade rapidamente. Layouts compactados melhoram isso.
Leituras praticas
Dois percursos O(n) podem ter tempos bem diferentes se um caminha por memoria contigua e o outro salta por ponteiros.
O formato da estrutura nao basta; a representacao concreta afeta cache lines, misses, prefetch e fragmentacao.
Escolher entre array, lista, arvore ou hash nao e so questao de Big-O, mas tambem de padrao de acesso e memoria.
// Gerenciamento de memoria
Entender quem controla a memoria ajuda a prever onde os dados vivem — e quando desaparecem.
Alocacao automatica
Alocacao automatica ao entrar num escopo (funcao ou bloco) e desalocacao imediata ao sair. O ponteiro de pilha e apenas incrementado ou decrementado — acesso ultra-rapido.
Limitada em tamanho (tipicamente 1 MB–8 MB por thread). Comporta variaveis locais, parametros e arrays de tamanho fixo pequenos.
Alocacao dinamica
Alocacao explicita ou implicita em runtime. Tamanho flexivel — limitado pela RAM disponivel. Acesso mais lento por causa do bookkeeping do allocator.
Listas encadeadas, arvores e qualquer estrutura de tamanho variavel vivem na heap. Quem controla a liberacao depende da plataforma.
Plataformas
O programador chama malloc() para alocar e free() para liberar.
Sem isso, ocorre vazamento de memoria. Arrays e listas encadeadas vivem inteiramente na heap.
Toda estrutura de dados precisa de cleanup explicito.
Smart pointers (unique_ptr, shared_ptr) automatizam a liberacao via
destruidores. std::vector, std::list e std::map gerenciam
seu proprio heap internamente. O padrao RAII garante desalocacao ao sair do escopo, sem GC.
O compilador decide em tempo de compilacao se uma variavel escapa para a heap via escape analysis. Variaveis que nao escapam ficam na stack — mais rapido e sem pressao no GC. O GC tricolor mark-and-sweep libera a heap em pausas curtas (tipicamente abaixo de 1 ms).
O GC divide a heap em geracoes: Gen 0 (objetos novos), Gen 1 (sobreviventes) e Gen 2
(longa duracao), alem do LOH para objetos acima de 85 KB. Coletas de Gen 0 sao frequentes
e rapidas. Dispose e using liberam recursos nao gerenciados.
Similar ao .NET: Young Generation (Eden e Survivor) e Old Generation (Tenured).
Diversas implementacoes: G1GC (default desde Java 9), ZGC e Shenandoah atingem pausas
abaixo de 10 ms. Finalizadores foram depreciados em favor de AutoCloseable.
Tudo em Python e um objeto na heap — inclusive inteiros e strings. O gerenciamento combina contagem de referencias (CPython) com um GC ciclico para coletar referencias circulares. Quando o contador chega a zero, o objeto e liberado imediatamente.
O borrow checker garante em tempo de compilacao que nao ha dois donos simultaneos nem
referencias dangling. Sem GC — a memoria e liberada deterministicamente ao sair do escopo
do dono (trait Drop). Box<T>, Vec<T>,
Rc<T> e Arc<T> cobrem diferentes cenarios de posse.
Impacto nas estruturas
GC — Java · .NET · Go
Cada no de uma lista encadeada e um objeto separado na heap. Com muitos nos, as coletas de Gen 0 ficam mais frequentes e o GC precisa rastrear mais referencias.
Arrays contiguos geram um unico objeto: uma alocacao, uma coleta. Em aplicacoes sensiveis a latencia, preferir arrays sobre listas pode reduzir pausas perceptiveis.
Manual — C · C++
Em C, cada no exige malloc() + free() separados.
Em C++, RAII garante destruicao automatica, mas cada no continua sendo
uma alocacao individual na heap — mais fragmentada que um array.
Um array contigo precisa de uma unica alocacao. A liberacao e simples e previsivel, sem risco de vazamento por no esquecido.
Ownership — Rust
Vec<T> aloca um unico bloco contiguos na heap, liberado
deterministicamente ao sair do escopo do dono — sem pausas, sem GC.
Listas encadeadas com Box<T> por no sao mais fragmentadas,
mas ainda previseis: cada no e liberado ao sair do proprio escopo.
O borrow checker elimina uso-apos-liberacao e double-free em tempo de compilacao, sem custo algum em runtime.
A explicacao desta pagina e uma inferencia guiada: ela combina a enfase de Knuth em
representacao interna e custo de acesso com a hierarquia moderna de memoria usada em CPUs atuais.
Os termos L1, L2, L3 e RAM nao sao apresentados aqui
como citacao literal do boxed set, mas como extensao contemporanea do mesmo raciocinio tecnico.
Fontes