Memória e Localidade

Dois algoritmos com a mesma complexidade assintótica podem apresentar desempenhos muito diferentes porque a memória moderna é hierárquica.

Localidade

• Localidade temporal: dados acessados recentemente são provavelmente acessados novamente.
• Localidade espacial: dados próximos a um acesso recente são provavelmente acessados logo.

Arrays contíguos normalmente tornam a varredura sequencial favorável ao cache. Uma lista encadeada pode colocar nós muito distantes, exigindo o seguimento de ponteiros, embora as duas estruturas possam ser percorridas em tempo Θ(n).

Custos de representação Java

Um int[] armazena valores primitivos contiguamente. Um ArrayList<Integer> armazena referências a objetos Integer e pode exigir boxing, unboxing e objetos adicionais. Os tamanhos exatos dos objetos dependem da JVM e da configuração; portanto, não converta essa observação em uma contagem universal de bytes.

Alocação e coleta de lixo

A alocação pode ser barata, mas os objetos alocados ainda aumentam a pressão sobre a memória e o trabalho de coleta de lixo. Uma otimização que reutiliza um buffer O(n) pode ser preferível a alocar muitas coleções temporárias, mesmo quando ambas abordagens têm o mesmo limite Big-O para o pico de espaço.

Raciocínio consciente de cache

A varredura de uma matriz ilustra a localidade espacial. Em uma representação Java como array de arrays, percorrer sequencialmente cada linha costuma ser mais favorável à memória do que saltar repetidamente entre linhas.

static long sumRows(int[][] matrix) {
    long total = 0;
    for (int[] row : matrix) {
        for (int value : row) {
            total += value;
        }
    }
    return total;
}

Medir cuidadosamente

Compilação JIT, eliminação de código morto, coleta de lixo, frequência CPU, aquecimento de cache e escolha de entrada podem invalidar tempos ingênuos. Use um framework de benchmarking como o JMH para Java e relate a metodologia junto com os resultados.

Exercícios

1. Comparar localidade de heap binário e árvore binária baseada em ponteiro.
2. Explicar por que menos alocações pode ajudar sem alterar espaço assintótico.
3. Liste três razões pelas quais uma única medição com System.nanoTime() não é confiável.