BT

Disseminando conhecimento e inovação em desenvolvimento de software corporativo.

Contribuir

Tópicos

Escolha a região

Início Artigos Tornando o código mais rápido domando ramificações

Tornando o código mais rápido domando ramificações

Pontos Principais

  • Para melhorar o desempenho, os processadores modernos antecipam as ramificações e executam as instruções seguintes de forma especulativa. Isso é uma otimização poderosa;

  • Os desenvolvedores podem ser induzidos a subestimar o custo das previsões incorretas das ramificações ao comparar códigos utilizando dados sintéticos, muito pequenos ou muito previsíveis. O impacto de uma previsão errada pode ser grande. Felizmente, muitas vezes é possível evitar ramificações inteiras;

  • Reescrever código com menos ramificações torna o código mais rápido e consistente;

  • Pode ser necessário manipular as ramificações imprevisíveis de forma apropriada para atingir o desempenho ideal.

Boa parte dos softwares possuem códigos com ramificações condicionais. No código, as ramificações aparecem como cláusulas if-then-else, loops e comandos switch-case. Quando as ramificações condicionais são encontradas, o processador verifica a condição e pode continuar seguir as instruções dentro da ramificação ou continuar o fluxo do código. Infelizmente, o processador só saberá, se será necessário ir para um novo caminho, depois de executar todas as instruções antes da condição. Para melhorar o desempenho, os processadores modernos prevê o resultado da ramificação e executam as instruções de forma especulativa. Esta é uma poderosa otimização.

No entanto, existem algumas limitações nas execuções especulativas como, por exemplo, o processador deve descartar o trabalho feito após um erro na previsão e recomeçar. Os processadores são bons em reconhecer padrões e, sempre que possível, evitar falhas nas previsões, mas mesmo assim, algumas ramificações são intrinsecamente difíceis de prever e podem criar gargalos de desempenho.

1. Não é fácil enganar os preditores das ramificações

Comparar o código com dados sintéticos muito pequenos ou muito previsíveis podem levar os desenvolvedores a subestimar o custo dos erros nas previsões das ramificações. Os processadores modernos podem aprender a prever milhares de ramificações, portanto, um pequeno teste pode falhar em expor o verdadeiro custo das previsões errôneas, mesmo que os dados pareçam aleatórios.

O exemplo a seguir, fará a decodificação dos dígitos hexadecimais composto de decimais (0-9) ou letras (A-F, a-f). O objetivo é encontrar o valor inteiro correspondente entre 0 e 16. Uma função escrita em C para esta tarefa seria:

int decode_hex(char c) {
  if(c >= '0' && c <= '9') return c - '0';
  if(c >= 'A' && c <= 'F') return c - 'A' + 10;
  if(c >= 'a' && c <= 'f') return c - 'a' + 10;
  return -1;
}

O desenvolvedor pode fazer um benchmark desta função, gerando primeiro uma string aleatória. Por exemplo, em C, pode-se chamar repetidamente, a função rand para selecionar um dos 22 dígitos hexadecimais possíveis.

char hex_table[] = { '0', '1', '2', '3', '4',
   '5', '6', '7', '8', '9',
   'a', 'b', 'c', 'd', 'e', 'f',
   'A', 'B', 'C', 'D', 'E', 'F' };

void build_random_string(size_t length,
  char *answer) {
  for (size_t i = 0; i < length; i++) {
    answer[i] = hex_table[rand() % sizeof(hex_table)];
  }
  return answer;
}

Então, pode-se registrar o tempo necessário para decodificar todos os dígitos hexadecimais na nova string. Para uma boa medição, um programador deve executar os testes diversas vezes e calcular a média das execuções. Vamos criar um gráfico para visualizar a quantidade de ramificações com erro na previsão das ramificações, com diferentes tamanhos de strings (1.000, 2.000, ...) ao longo das muitas execuções. É importante reutilizar a mesma string de entrada em todas as execuções.

Usando um processador padrão de servidores (AMD Rome), foi possível encontrar que, com uma string contendo 3.000 dígitos, o número de erros na previsão das ramificações por valor reduziu para 0,015 (ou 1,5%) após menos de 20 execuções. Para uma string menor (1.000 dígitos), o número de erros na previsão nas ramificações reduziu ainda mais, sendo 0,0005 após 8 tentativas. Em outras palavras, um processador padrão pode aprender a prever todas as ramificações geradas por uma sequência aleatória hexadecimal de 1kB após menos de 10 passagens de decodificação.

Nas linguagens de programação que possuem suporte a um compilador just-in-time (como Java ou JavaScript), é comum repetir as comparações até que o compilador tenha otimizado o código. Se o teste for muito pequeno, mesmo que a entrada seja aleatória, existe o risco de subestimar o custo dos erros nas previsões das ramificações.

De forma similar, a execução dos testes utilizando dados sintéticos como entrada, mesmo com um grande volume dos dados, pode ser possível para o processador predizer as ramificações com alta assertividade. Supondo que, ao invés de usar uma string de dígitos aleatórios, use-se dígitos gerados contando de 0 a 65536: 0X00, 0X01, ...

O preditor das ramificações deve essencialmente prever onde os dígitos decimais e alfabéticos aparecem. A string que resulta (000100021003100421052106310731084219421a521b521c631d631e731f7310842 ... 8ce18ce29ce39ce4ade5ade6bde7bde8cef9cef …) não é aleatória, mas pode precisar de um esforço para predizer os padrões seguidos dos dígitos decimais e dígitos alfabéticos. Ainda usando o mesmo processador AMD Rome, verificamos que a quantidade de erros na predição das ramificações de uma string com 131.072, é praticamente zero no primeiro teste: erro de 0,002 por byte.

2. Os erros nas previsões das ramificações podem ser custosos

O efeito de prever errado uma ramificação pode ser grande. Ao usar os dados coletados em sequências hexadecimais aleatórias de vários tamanhos e plotar um gráfico com o número de ciclos da CPU por dígito de entrada, em relação ao número de ramificações imprevisíveis, descobrimos que o número de ciclos da CPU varia entre pouco mais de 5 ciclos por dígito hexadecimal até 20 ciclos por dígito, dependendo da quantidade de ramificações previstas erroneamente.

Não podemos concluir que a presença de uma grande quantidade de erros nas previsões é necessariamente algo a se preocupar, pois podem haver preocupações mais urgentes. Por exemplo, considerando uma busca binária em uma grande matriz, a limitação é a latência do acesso a memória principal, que é muito mais custosa que um erro na previsão de uma ramificação.

3. Evitando ramificações

Ferramentas de análise de desempenho, como perf (Linux), xperf (Windows) e Instruments (macOS), podem medir a quantidade de erros nas previsões de ramos. O que aconteceria se em uma determinada situação, as ramificações fossem um problema?

Felizmente é possível evitar ramificações inteiras. Por exemplo, para decodificar dígitos hexadecimais, podemos usar uma pesquisa simples no array:

int digittoval[256] = {
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, 0,  1,
    2,  3,  4,  5,  6,  7,  8,  9,  -1, -1,
    -1, -1, -1, -1, -1, 10, 11, 12, 13, 14,
    15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, 10, 11, 12,
    13, 14, 15, -1,...};
int hex(unsigned char c) {
  return digittoval[c];
}

Esta função pode ser compilada com uma única instrução e ainda pode ser utilizada para validar entradas impróprias verificando inteiros negativos.

Assim, geralmente pode-se substituir ramificações por memorização: com isso, as ramificações são pré-computadas e armazenadas em uma estrutura de dados simples como um array.

Outra estratégia para evitar ramificações é fazer um trabalho especulativo para posteriormente descartá-lo. Por exemplo, supondo que os números inteiros negativos do array de entrada precisam ser apagados. Em C, podemos fazer com um laço e uma ramificação:

for(size_t i = 0; i < length; i++) {
    if(values[i] >= 0) {
        values[pos++] = values[i];
    }
}

Vamos chamar esta função de "branchy". Este código verifica o sinal da entrada e cópia condicionalmente para um novo local. Esperamos que seja difícil prever quais inteiros são negativos, então este código pode ser ineficiente. Em vez disso, seria possível escrever a entrada de maneira otimista, e apenas incrementar o índice se o número inteiro for negativo.

Podemos determinar o sinal de um inteiro sem a necessidade de ramificações. Muitos compiladores vão compilar a função C a seguir em uma negação seguido por um deslocamento lógico a direita:

size_t sign(int v) {
    return (v >= 0 ? 1 : 0);
}

A função a seguir omite os valores negativos do array. Na maioria dos compiladores, esta função irá conter uma única ramificação que executa um loop, porém este é uma ramificação previsível para grandes arrays.

for(size_t i = 0; i < length; i++) {
  values[pos] = values[i];
  pos += sign(values[i]);
}

Vamos chamar esta função de "branchless". Observe que ambas as funções não são estritamente equivalentes. A versão "branchy" pode nunca escrever no array de entrada, enquanto a versão "branchless" sempre escreverá cada número inteiro uma vez. Assim, pode ser difícil para o compilador substituir uma pela outra, contudo, as funções podem ser logicamente equivalentes para fins práticos - uma mudança bem feita pelo desenvolvedor.

Mesmo quando é impossível remover todos as ramificações, podemos reduzir a quantidade de ramificações "quase sempre tomado" ou "quase nunca tomado"[a] pode ajudar o processador a prever melhor as ramificações restantes. Por exemplo, se decodificamos cada dígito usando um laço, então haverá uma ramificação previsível resultando em um loop por dígito.

for (i = 0; i < length; i++) {
  int code = decode_hex(input[i]);
  …

Para entradas de grandes strings, podemos reduzir pela metade o número de ramificações previsíveis ao "desenrolar" o loop, processam dois caracteres de entrada em cada iteração do loop.

for (; i + 1 < length; i += 2) {:
  int code1 = decode_hex(input[i]);
  int code2 = decode_hex(input[i + 1]);
  …

Se contarmos o número de erros na previsão das ramificações por dígito de entrada, será possível encontrar que a versão "desenrolada" pode ter menos erros de previsão. No processador AMD Rome usando como entrada uma string de 5.000 dígitos, foi possível notar que, depois de muitas tentativas, o número de erros na previstos erroneamente por dígito de entrada foi 0,230 para o laço simples e de apenas 0,165 para o laço "desenrolado" - uma redução de 30%.

Uma explicação possível para este fenômeno é que os processadores usam a história dos ramos recentes para prever ramos futuros. As ramificações não informativas podem reduzir a habilidade dos processadores fazerem boas previsões.

Quando não é possível evitar as "ramificações difíceis de prever", pode-se frequentemente reduzir seu uso. Por exemplo, quando compara-se duas datas, é conveniente colocá-las no formato YYYYMMDD, e comparar com o resultado de strings de 8 bytes como se fossem inteiros de 64 bits, usando uma única instrução.

Conclusão

O código de benchmarking que contém "ramificações difíceis de prever" é difícil e os programadores às vezes podem subestimar o preço das ramificações. Refatorar o código, deixando-o com poucas ramificações leva a um código com mais velocidade e desempenho. Pode ser necessário o manuseio adequado dos erros nas previsões das ramificações previstas erroneamente para obter o desempenho ideal.

Sobre o autor

Daniel Lemire é professor de ciência da computação da Universidade Québec (TELUQ). Ele escreveu mais de 70 publicações revisadas por pares, incluindo mais de 40 artigos. Atua nos comitês de programa das principais conferências de ciência da computação.

 

Avalie esse artigo

Relevância
Estilo/Redação

Conteúdo educacional

BT