A Máquina por Baixo do Algoritmo: Tipos, Cache e Desvios

O Artigo 1 terminou com uma derrota incômoda. Uma hash table (tabela indexada por uma função de hash), que faz $O(n)$ operações para contar valores distintos, perdeu para uma ordenação que faz $O(n\log n)$. A contagem estava certa. A suposição por trás dela, de que todas as operações elementares custam o mesmo, estava errada. Cada inserção na tabela escondia uma alocação de memória e um salto para um endereço distante, e o processador pagou caro por cada um desses saltos.

Este artigo abre a máquina que executa os algoritmos. Vamos começar pelo menor objeto de um programa, uma variável, e descobrir que a escolha do seu tipo já é uma decisão de correção e de desempenho. Depois, vamos preparar o ambiente de compilação em C++23 e medir três forças que a notação assintótica ignora: a ordem em que o programa percorre a memória, a previsibilidade dos desvios condicionais e as promessas que o programador pode fazer ao compilador. No fim, vamos aprender a escrever a saída de um programa com a biblioteca de formatação do C++23, porque um juiz que compara saídas não perdoa um espaço fora do lugar.

Todos os tempos deste artigo foram medidos com o compilador do Visual Studio 18.10.3, versão 19.51 do cl, com as opções /std:c++latest /O2 /EHsc /W4 /permissive- /utf-8, em um notebook com processador Intel Core i7-10750H, de seis núcleos. Cada medição segue o protocolo do Artigo 1: uma execução de aquecimento descartada, cinco execuções cronometradas e a mediana como resumo. Os números mudam de máquina para máquina. As relações entre eles, que são o assunto do artigo, mudam muito menos.

1. Objetos, tipos e inicialização

Antes de usar C++23 como linguagem de trabalho, precisamos desacelerar diante de uma única linha:

1

int contador{1};

A linha parece inofensiva. É inofensiva da mesma forma que uma chave de fenda é inofensiva antes de alguém usá-la em um fio energizado. Ela contém seis ideias: um tipo, um nome, um objeto, uma região de armazenamento, um tempo de vida e um valor inicial.

O tipo é int. Um tipo diz ao compilador quais valores podem ser representados e quais operações são válidas sobre eles. Um int aceita aritmética, comparações, operações bit a bit e atribuição. Ele não promete uma faixa infinita. No MSVC, no GCC e no Clang, em todas as plataformas de 64 bits que os juízes usam, int tem 32 bits, e sua faixa será dada por

$$-2^{31}\le x\le 2^{31}-1,$$

isto é, de $-2147483648$ até $2147483647$. O expoente $31$, e não $32$, aparece porque um dos 32 bits é gasto com o sinal, na representação em complemento de dois que o C++20 tornou obrigatória.