Entrada e Saída de Alto Desempenho

Um algoritmo $O(n\log n)$ pode perder para a leitura da própria entrada. Suponha que um programa ordene ${10}^6$ inteiros em $70$ ms, mas leve $360$ ms para ler esses mesmos inteiros com std::cin. A análise assintótica estava certa, a implementação estava certa, e o gargalo entrou pela porta da frente, carregando espaços em branco.

Este artigo trata a entrada e a saída como parte do projeto do algoritmo. O percurso desce por camadas: primeiro, os fluxos da biblioteca padrão com as duas configurações obrigatórias; depois, a leitura e a escrita com buffer (área intermediária de memória) próprio, feitas com fread e fwrite; em seguida, arquivos com nome, com std::expected para os erros e std::string_view para analisar sem copiar; por fim, arquivos mapeados na memória e entrada e saída assíncronas. A ordem é deliberada. Começamos pela interface mais clara e só descemos quando a carga de trabalho paga pela descida. Código rápido não é o código que usa a interface de mais baixo nível disponível. É o código que gasta complexidade onde o gargalo realmente está.

Todas as medições deste artigo foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H, com a entrada e a saída redirecionadas para arquivos, como em um juiz. Cada forma de leitura ou escrita rodou em um processo separado, porque as configurações dos fluxos valem para o processo inteiro, e os tempos são medianas de cinco execuções depois de uma de aquecimento. A maioria dos juízes online usa o GCC em Linux, e onde o comportamento do MSVC difere do comportamento do GCC, o texto diz.

1. As duas linhas obrigatórias

Toda solução comum que lê com std::cin deveria começar com duas linhas:

1
2

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

A primeira linha desliga a sincronização entre os fluxos do C++ e a biblioteca de entrada e saída do C. Por padrão, std::cin e std::cout ficam sincronizados com stdin e stdout, porque um programa pode misturar std::cin com scanf, ou std::cout com printf, e a ordem dos caracteres precisa sair certa. Essa compatibilidade tem um custo em cada leitura e em cada escrita: sincronizados, os fluxos do C++ não podem manter um buffer próprio e passam cada caractere pela biblioteca do C.