O trabalho mais rápido é o que você não faz. Três formas de fazer menos a cada mensagem, e uma de baratear as decisões pequenas:
- Tabelas de consulta. Se uma função de uma entrada pequena (um byte, um tipo de mensagem, uma faixa de preço) é lenta ou cheia de
if, calcule todas as respostas uma única vez em um array e indexe o array no caminho crítico.
- Busque melhor. Em dados ordenados,
std::lower_bound encontra uma posição em cerca de log2(n) comparações em vez de n.
- Tire do loop o trabalho invariante. Uma chamada cujo resultado é o mesmo a cada volta de um loop vai antes do loop.
- Menos desvios. Os processadores adivinham a direção de cada desvio e se adiantam; um palpite errado joga esse trabalho fora. Para decisões pequenas,
std::min e std::max costumam compilar em código sem nenhum desvio.
Não dá para ver previsões de desvio de um navegador, e aqui os tempos seriam só ruído, então estes exercícios contam o trabalho: quantas vezes uma função lenta roda e quantas comparações uma busca faz. Os testes fornecem as funções contadas.
Uma tabela leva o trabalho lento para a inicialização.