Jargão técnico: Metáforas, alusões e siglas

A motivação pela escrita desse artigo surgiu de uma pergunta que me foi feita a respeito de “referências”, um conceito ou alusão a um “tipo” (outra alusão) de variável… Me perguntaram se a linguagem C tem, ou não, “referências”. Espero responder a isso no final.

Jargão

Uma das principais coisas a serem dominadas por estudantes e profissionais de quaisquer áreas é o jargão técnico específico. Qualquer profissional na área de engenharia elétrica que diga “neste fio circulam 127 V de corrente” vai ser zoado, e com razão! O mesmo aplica-se ao profissional de desenvolvimento de software que diga que use “megagem” ou “gigagem” de memória, querendo expressar ordem de grandeza de certa quantidade de recursos (obs: Um amigo mineiro me disse, uma vez, que era comum ouvir isso nos lugares onde trabalhou!).

Além de tomar cuidado para não passar vergonha em público, é imprescindível que usemos as analogias e alusões, próprias do jargão, de forma correta para que possamos ser compreendidos e evitemos confusões. Isso é especialmente necessário se você, como eu, pretende escrever material de consumo público que objetive “ensinar” alguma coisa a alguém (jeito bonitinho de falar “livros”!)… Neste artigo tendo mostrar a origem e usos de alguns termos.

Alusões literárias

Quando lidamos com unidades de armazenamento de dados e agrupamentos dessas unidades é comum o uso de analogias relacionadas com “livros”. Os primeiro termo, que especifica a menor quantidade de informação possível, não é uma alusão a algum objeto físico, mas um acrônimo: bit vem de “digito binário” (binary digit). A referência aqui é aos “digitos decimais” e, especificamente, “digito” porque temos a propensão de contar nos “dedos”… O termo correto seria “algarismo binário” (bismo?), mas “bit” expressa duas coisas: Um termo bem simples de ser lembrado e uma quantidade, na língua inglesa.

À partir de byte começa-se a usar alusões menos explícitas. A palavra faz alusão a um conjunto de bits, a um “bocado” de bits… ou a uma “mordida” (bite). Dos termos que lidam com quantidade de bits esse é o menos “literário” deles… Hoje, um byte equivale a um conjunto de 8 bits, mas o termo não especifica essa quantidade! Originalmente, um byte pode conter quantidades arbitrárias de bits. Em computadores mais antigos, um byte continha 9 bits, por exemplo (se não me engano, o antigo PDP-7 era assim!).

Definido o byte alguém desejou que alguma analogia similar fosse usada para pedaços menores, mas maiores que um único bit. Se byte é definido (hoje) como 8 bits, define-se a metade dessa “mordida” como uma “beliscada” (nibble)… Um nibble tem 4 bits de tamanho, metade de um byte.

Já o termo palavra (word) surge para explicitar um conjunto de bits que é usado nativamente pelo processador em questão. Nos antigos processadores de 8 bits (Z-80, 6502, 8080…) uma word tinha um byte de tamanho. Nos antigos 8086, uma word tinha 2 bytes (16 bits) de tamanho e essa designação “pegou”, tornando-se corriqueira, hoje em dia.

Para especificar tamanhos maiores que uma word outras alusões apareceram: 32 bits tornou-se double word ou dword, 64 bits é uma quadruple word ou quad word (qword) e, menos usara, 128 bits é uma octuple word ou octa word… Outra designação menos usada, hoje em dia, para 128 bits é um parágrafo. Essa alusão é ainda usada em assembly, particularmente no Microsoft Macro Assembler para especificar o alinhamento de um segmento (outra alusão literária):

_TEXT segment para public 'CODE'
...
_TEXT ends

Esse para ai da especificação do alinhamento de um segmento significa parágrafo (ou paragraph) que diz ao compilador que o início desse segmento deve começar num offset múltiplo de 16 (16 bytes = 128 bits).

Não tenho conhecimento sobre outras designações literárias para tamanhos maiores de 16 bytes a não ser a página. Por causa do uso de “memória virtual”, um bloco de 4 KiB (nos processadores Intel) têm essa designação.

Note que um parágrafo é maior que uma palavra e uma página é maior que um parágrafo, isso também é intencional na analogia.

Um exemplo de alusão literária de nível mais alto

Já falei dessa alusão antes: Little Endian e Big Endian é uma alusão aos versos de “Humpty Dumpty“, que é tão famoso em países de lingua inglêsa quanto alguns personagens do folclore brasileiro são, por aqui (Saci Pererê, Mula Sem-cabeça, Curupira)… Nos versos há uma discussão onde tenta-se decidir se um ovo deve ser quebrado pelo seu lado mais pontudo ou “menor” (little endian – o “final” menor) ou pelo lado mais “rombudo” ou “maior” (big endian).

Esses termos entraram no jargão porque houve mesmo uma discussão acirrada em relação ao posicionamento dos bytes de uma word, nos anos 50: Deve colocar o byte menos significativo no menor endereço de memória ou vice-versa? Note que a turma que lida com “redes” optou por escrever uma word, ou tipos que tenham tamanho maior que 1 byte, na ordem em que a lemos, ou seja, big endian: Se quisermos escrever a word 0x1234 o byte 0x12 é escrito antes (no endereço menor) do que 0x34. Já os processadores atuais (os mais usados, pelo menos) preferem escrever o byte de mais baixa ordem no menor endereço (0x1234 aparece na memória na sequência 0x34, 0x12) ou little endian.

Ai está: Quando falamos de endianess estamos falando de um ovo!

Linguagens de programação e suas alusões

Existem diversos termos usados em linguagens de programação que são alusões a objetos ou conceitos que nada têm a ver com “programação”. Muitos deles são relacionados à matemática porque, ora bolas, afinal de contas, um algoritmo é uma construção matemática! Programas são conjuntos de expressões matemáticas e um conjunto de expressões coerente que serve como instruções ou informações é, no mundo “real” conhecido como linguagem. Uma “linguagem” também é uma referência literária, se você pensar bem…

Acontece que existe uma Torre de Babel nessa área. Termos como “variáveis” e “objetos”, “estruturas” e “classes” são intercambiáveis e todos são alusões… Não existem “variáveis”, mas “containers” que podem assumir vários valores.. Não existem “objetos”, mas containers de valores (que são chamados também de “variáveis” – confuso, não?)… Não existem “classes”, nem no sentido de “agrupamento social” (sociologia?) ou “categoria taxionômica” (biologia), mas estruturas que agrupam “variáveis” (ou seriam “objetos”?).

Embora muitas das analogias sejam similares, elas são usadas para diferenciar conceitos ligeiramente diferentes. Ao falarmos de “classe”, hoje, queremos dizer “estrutura”, mas com um plus: Junto com os dados, as “funções” que manipulam esses dados podem estar encapsulados junto com eles e damos a isso o nome de “classe”. Note que, mesmo nessa explicação usei duas alusões (função e encapsular) que, para o purista, estudante de “orientação a objetos”, é uma heresia. Para esses os termos corretos seriam “comportamento” e “agregar” (talvez “compor”, mas acho que “encapsular” pode ser perdoado!)… Assim como dizer que classes têm “dados” também me condenaria à fogueira. O termo certo seria “estados”.

É interessante notar que, assim como no mundo real, alguns conceitos surgem em oposição a outros. Por exemplo, o termo “variável” surge em oposição ao termo “constante”… Matematicamente, “variável” não é tradicionalmente usado, mas “contante” o é… Então, provavelmente quando as primeiras linguagens de programação estavam sendo estudadas (ALGOL, por exemplo), o termo “variável” apareceu no jargão.

Linguagem C: Referências e Ponteiros

Ponteiro é uma alusão a um método indireto de acesso a uma variável. Ao invés de lermos ou escrevermos (outras alusão à literatura!) o dado diretamente, “apontamos” para ele e usamos esse “ponteiro” para manipular o dado, indiretamente.

Ora… Uma “referência” é uma “método indireto de acesso a uma variável” (ou objeto… puts!). Uma referência é um ponteiro! Assim, C possui referências! Simples assim.

O estudante pode ficar confuso e tentar argumentar: “mas não é desse ‘tipo’ de referência que estou falando!”. Acontece que esse “tipo” de referência é apenas uma construção sintática. Por exemplo. Isaac Newton, em seu Principia Matematica define suas leis de forma puramente textual. Se você ler o livro verá que não existe uma só equação matemática por lá, no máximo, figuras geométricas. Por quê? Tradição! No século XVII a aritmética já era conhecida, mas o “atalho” da “prova matemática” era considerado algo que só alguém “não educado” faria.

No entanto, se Newton dissesse algo como “Ao sofrer variação de velocidade, um corpo qualquer com massa conhecida sofre a influência de uma força proporcional” ou escrevesse simplesmente “F=m\cdot a“, estaria dizendo, essencialmente a mesma coisa, não? E essa é a diferença entre dizer que um ponteiro é uma referência e uma referência é um ponteiro, ou seja, essencialmente nenhuma!

Mais problemas com inlining

No último texto mostro que usar funções inline nem sempre é uma boa ideia e também nem sempre o compilador respeitará a “dica” do “inline”. Mas, existe uma condição em que o compilador tende a transformar suas rotinas em “inline”: Quando elas têm tamanho que atendem o critério do próprio compilador e são definidas no próprio módulo (arquivo com extensão .c), ele a transforma em “inline” mesmo sem a dica. Um exemplo:

unsigned int sum(char *bufptr, size_t size)
{
  unsigned int s = 0;

  while ( size-- )
    s += *bufptr++;

  return s;
}

unsigned int f(unsigned int scale, 
               char *bufptr, size_t size)
{
  return scale * sum( bufptr, size );
}

Aqui a função sum() provavelmente será compilada inline deontro da função f() mas, como temos duas funções “extern”, por default, tanto a versão inline da chamada quanto a função original são passadas para o linker.

Terminamos com duas versões da mesma função… E o linker não tem a menor ideia disso. Não é tarefa do linker saber se uma função está ou não sendo usada já que ela pode ser chamada de forma indireta, por exemplo, através de um ponteiro:

unsigned int (*fp)(char *, size_t);
...
fp = sum;
x = fp(buffer, sizeof buffer);

Esse fragmento chamará sum(), mais ou menos assim:

  ...
  mov  rax,sum
  mov  rdi,buffer
  mov  rsi,N      ; N é o tamanho do buffer.
  call rax
  mov  [x],eax
  ...

Yep… a referência ao símbolo sum está ali e pode ser um fator de decisão para o linker, mas existem outras formas de inicializar um ponteiro, não é? Além disso, o linker tende a ser agnóstico em relação à linguagem de programação usada para gerar os arquivos objeto e, por isso, não sabe das capacidades de cada linguagem. Sua tarefa é resolver nos identificadores (nomes de símbolos) e dar-lhes endereços…

Bem… Nem tudo está perdido… Uma das maneiras de evitar o inlining é codificar as funções em módulos separados. A função sum() poderia ficar num arquivo sum.c e a função f() em func.c, por exemplo. Compilamos ambos separadamente e o linker resolverá os nomes dos símbolos… Como são arquivos objetos diferentes, não há inlining automático.

A outra maneira é modificando o atributo da função, contida no mesmo módulo, que pode ser feito num protótipo, antes da definição da mesma:

__attribute__((noinline))
unsigned int sum(char *, size_t);

Ou então logo antes da definição. Nesses casos o compilador respeitará o atributo…

Uma terceira maneira, se a função não for usada por nenhuma outra função “extern”, é declará-la como static e também usar o atributo acima… Uma função marcada como static só é visível pelo próprio módulo e o compilador tende a torná-la inline, mas com o atributo ela passa a ser “offline” e invisível para os demais módulos (e, provavelmente, para o próprio linker – o nome será resolvido, em teoria, pelo próprio compilador).

Este é um método interessante se a sua função for usada apenas no módulo em que está contida e você não quer acabar com múltiplas cópias (uma “global” e várias “inline”). É ainda mais interessante porque, como ela não é perceptível pelo linker, vários módulos podem reusar o nome da função sem problemas de conflitos.

Dica pouco óbvia sobre otimização de código (funções inline)

Vou tentar aqui desfazer um conceito que é amplamente divulgados a respeito de organização de código para atingir “a melhor performance possível”. Trata-se da afirmação de que “códigos inline são mais rápidos porque não incorrem em chamadas e retorno”…

Embora seja verdade de códigos inline pequenos possam ser mais eficientes que códigos pequenos chamados, isso não é verdade para códigos com algum nível de complexidade. Sim, as instruções CALL e RET tomam tempo porque:

  1. Têm que manipular a pilha;
  2. Têm que verificar o nível de privilégio;
  3. Têm que verificar o nível de “proteção”.

Basta dar uma olhada na rotina equivalente das instruções CALL e RET no manual de desenvolvimento de software da Intel (2º volume) para ficar com certo receio de usá-las. No entanto, o processador é esperto o suficiente para não realizar as verificações 2 e 3, acima, se estamos lidando somente com o userspace ou o kernelspace. Essas verificações só acontecem no caso de mudança de privilégio ou características diferentes dos descritores de segmento selecionados (no modo i386) – ou dos descritores de páginas (ambos os modos).

Já o primeiro item tende a ser otimizado, graças ao cache e, ainda, a perda não é assim tão grande… CALL gasta cerca de 5 ciclos de clock e RET, 8. Mas, o detalhe é que essas instruções podem ser paralelizadas nas várias “portas” da unidade de execução. Claro, funções inline tendem a não usarem essas instruções e, quando digo “tendem” é porque marcar uma função como inline significa apenas oferecer uma dica ao compilador, que pode ou não ser obedecida.

De fato, funções com alguma complexidade podem ser bem mais lentas se forem usadas inline. O motivo? O cache L1! Já falei muito do cache aqui. O problema é que temos uma quantidade bem limitada de espaço nele e as funções inline tendem a fazer com que as rotinas chamadoras fiquem bem grandes que podem não caber no cache L1. Assim, ao tentar ler uma instrução que não está no cache o processador tem que “parar tudo”, trazer 64 bytes para o cache (uma linha) e continuar com a leitura das instruções. Esse “parar tudo” pode gastar centenas de ciclos, dependendo do caso.

Além da instrução RET e, talvez, prólogo e epílogo para manipular o stack frame, a rotina que não seja inline tende a ter o MESMO tamanho da rotina inline, mas ocupará apenas o seu próprio espaço, não sendo replicada por todo o código, diminuindo a pressão no cache L1 e, como consequência, aumentando a velocidade… Vale lembrar que não é apenas o seu código que está sendo executado, mas o código do sistema operacional, drivers, interrupções, etc. O cache L1 não é apenas do seu processo!

Neste ponto, é interessante tentar definir a fronteira do que seria a “alguma complexidade” que citei acima. Usei essa maneira genérica para tentar definir qualquer coisa que exija algum processamento mais ativo (loops, múltiplos testes etc). Por exemplo, as funções abaixo podem ser candidatas para serem inline:

int f(int x, int y)
{ return 3*x+y; }

int g(int x)
{ 
  if (x)
    return 3;
  return 0;
}

Mas, considero rotinas como essa outra indignas da promoção à inline:

unsigned int sum(char *bufptr, size_t size)
{
  unsigned int s = 0;

  while ( size-- )
    s += *bufptr++;

  return s;
}

O motivo é simples… Funções de baixa complexidade costumam usar poucas instruções. As funções f() e g() acima provavelmente serão compiladas como:

f:
  lea eax,[rsi+rdi*2]
  add eax,edi
  ret

g:
  xor  eax,eax
  mov  ecx,3
  test edi,edi
  cmovnz eax,ecx
  ret

Ou algo semelhante… A primeira rotina, ignorando o RET, tem 5 bytes de tamanho, a segunda, 12 e, em minha opinião, qualquer coisa com menos de 16 bytes pode (mas, não necessariamente deve) ser promovido a inline. Comparemos agora o código da terceira rotina “simples”, acima:

sum:
  test rsi, rsi
  je   .L9
  add  rsi, rdi
  xor  eax, eax
.L8:
  add	rdi, 1
  movsx edx, BYTE [rdi-1]
  add  eax, edx
  cmp  rsi, rdi
  jne  .L8
  ret
.L9:
  xor  eax, eax
  ret

Ignorando os RETs a rotina gasta 32 bytes do cache L1. Metade de uma linha e 2 nívels de associatividade… Não é lá grandes coisas, mas considere que múltiplas “chamadas” colocam \frac{1}{4} de linha de pressão no cache por chamada. Como uma única função CALL gastará apenas 5 bytes (0xE8 seguido do deslocamento relativo de 32 bits), gastar 32 bytes por “chamada” é claramente um exagero desnecessário.

Neste aspecto a função f() é uma séria candidata para inlining, afinal 5 bytes do CALL contra 5 bytes sem CALL não é algo difícil de decidir. A função g() por outro lado é mais complicada… Minha escolha por 16 bytes é devido ao alinhamento automático que o compilador faz com relação ao início de cada função, mas, é claro, você pode decidir por um tamanho maior “mínimo”, desde que ele não ultrapasse os 64 bytes e/ou cruze várias linhas do cache.

Você, provavelmente, não quer ficar medindo o tamanho das suas funções em bytes (e nem precisa fazer isso, basta pedir pro linker gerar um mapa), mas é mais prático usar um critério de “complexidade” subjetiva, como fiz acima…

“Receitas de bolo” não costumam ser boas ideias…

Existem algumas regras de otimização que são aplicáveis a arquiteturas específicas em condições específicas e em ambientes específicos. Recentemente um de meus leitores me perguntou sobre algumas “regrinhas” de otimização para serem usadas em C que, infelizmente, tive que refutar (de maneira rasteira e, aqui, apresento mais detalhes).

Arqumentos de funções “por referência” versus “por valor”

A ideia aqui é que passar uma estrutura por valor para uma função é bem mais lento do que passá-la por referência, ou seja, via um ponteiro… Geralmente isso é verdade, mas, nem sempre… Considere os códigos abaixo:

#include <math.h>

struct vec3_T { double x, y, z; };

double vec3_length( struct vec3_T v )
{
  return sqrt( v.x * v.x + 
               v.y * v.y + 
               v.z * v.z );
}

double vec3_length2( struct vec3_T *pv )
{
  return sqrt( pv->x * pv->x + 
               pv->y * pv->y + 
               pv->z * pv->z );
}

No primeiro caso os 24 bytes da estrutura vec3_T terão que ser copiados para a pilha antes da chamada da função vec3_length(). No segundo caso, a função supõe que dos dados já estejam em algum lugar na memória e apenas a referência pv é usada para localizá-los. Mas, olhando para o código em assembly para a arquitetura x86-64 com boa otimização, temos:

vec3_length:                 vec3_length2:
  sub rsp, 24                         
                                      
  movsd xmm1, [rsp+32]         movsd xmm1, [rdi]
  movsd xmm2, [rsp+40]         movsd xmm2, [rdi+8]
  mulsd xmm1, xmm1             mulsd xmm1, xmm1
  movsd xmm0, [rsp+48]         movsd xmm0, [rdi+16]
  mulsd xmm2, xmm2             mulsd xmm2, xmm2
  mulsd xmm0, xmm0             mulsd xmm0, xmm0
  addsd xmm1, xmm2             addsd xmm1, xmm2
  pxor  xmm2, xmm2             pxor  xmm2, xmm2
  addsd xmm0, xmm1             addsd xmm0, xmm1

  ucomisd xmm2, xmm0           ucomisd xmm2, xmm0
  sqrtsd  xmm1, xmm0           sqrtsd  xmm1, xmm0
  ja  .L5                      ja  .L12
.L1:                                  
  movapd  xmm0, xmm1           movapd  xmm0, xmm1
  add rsp, 24                           
  ret                          ret 

.L5:                         .L12:
  movsd [rsp+8], xmm1          sub rsp, 24
  call  sqrt@PLT               movsd [rsp+8], xmm1
  movsd xmm1, [rsp+8]          call  sqrt@PLT
  jmp .L1                      movsd xmm1, [rsp+8]
                               add rsp, 24
                               movapd  xmm0, xmm1
                               ret

Exceto pelo ajuste do stack frame e pela verificação da precisão de sqrtsd, as rotinas são essencialmente as mesmas. E a cópia da estrutura só será feita se esta não estiver já na pilha.

O que quero mostrar que essa afirmação categórica de que “por referência” é sempre melhor é falsa. Bem como afirmações que “passagem por referência” tendem a usar registradores quando “por valor” não também são falsas. Isso depende da convenção de chamada em uso e do escopo da função (funções estáticas tendem a ser “otimizadas” de forma diferente e muitas vezes são promovidas para “inline”).

Funções inline são mais “rápidas”

Essa é outra receita de bolo que pode ser perigosa para a boa performance. Em primeiro lugar, o modificador “inline” é apenas uma dica dada ao compilador. Este pode respeitá-la ou não. Ou seja, não há garantia de que sua função “inline” seja, de fato, “inline”… Em segundo lugar há o problema do cache L1.

Tanto seus dados quanto as instruções devem estar no cache L1 para que possam ser rapidamente acessados pelo circuito de decodificação e execução do processador. O cache L1 é limitado e dividido em dois grandes blocos: L1D e L1I. Cada um com 32 KiB divididos em 512 linhas de 64 bytes. Se tivermos muitas “funções inline”, é evidente que o tamanho de nossos códigos ficarão maiores e isso poderá, para uma única função, extrapolar os 32 KiB do cache L1I e fazer com que linhas do cache LII precisem ser carregadas com mais frequência do que o necessário.

A regra a ser seguida deveria ser: Funções estratégicas e pequenas merecem o estudo para que sejam promovidas para “inline”, desde que não poluam em demasia o cache L1I.

Arrays unidimensionais e de múltiplas dimensões

Outro ponto errado é a crença que, ao lidar com arrays unidimensionais teremos performance melhor que lidarmos com arrays multidimensionais. Qualquer leitura de livros sobre algoritmos vai te mostrar que as dimensões superiores são apenas deslocamentos num array unidimensional equivalente. Por exemplo, se tivermos um array definido como:

int a[3][3];

E fizermos:

a[1][2]=0;

Isso é equivalente a declararmos um array unidimensional de 9 elementos e efetuarmos um pequeno cálculo para localizar a posição correta:

int a[9];
a[1*3+2]=0;

O compilador sabe que tem que multiplicar a dimensão mais alta pela quantidade de itens na dimensão mais baixa para obter o deslocamento inicial correto para ser adicionado ao offset da dimensão mais baixa… Um exemplo esclarece: Suponha que tenhamos um array de dimensões 3\times7:

int a[3][7];

Obviamente que um array unidimensional do mesmo tamanho terá 21 elementos (3\times7). A primeira linha do array bidimensional terá 7 elementos e teremos 3 linhas deste tamanho… Assim, para locarlizar um elemento no array unidimensional equivalente teremos pos=l\cdot7+c, onde l é a linha e c a coluna da “matriz”. A posição pos é a do array unidimennsional equivalente… Num código do tipo:

int a[3][7];

void zero(int l, int c) { a[l][c] = 0; }

O compilador gera um código parecido com esse:

zero:
  lea   rdx, [a]
  movsx rdi, edi
  movsx rsi, esi
  lea   rax, [rsi+rdi*8] ; pos = l*8+c
  sub   rax, rdi         ; pos -= l
  mov   DWORD [rdx+rax*4], 0
  ret

Aqui o compilador escolheu não usar a instrução de multiplicação para poupar ciclos (era de se supor que fizesse, já que 7 não é fatorável em 2^n). Esse tipo de otimização será feita sempre que possível pelo compilaor, gerando um código bem eficiente.

Outro ponto é notar que a construção abaixo é diferente de um array multidimensional:

int *a[3];

Aqui temos um array de 3 ponteiros para int e, como cada ponteiro pode apontar para um array, teremos um array de 3 posições, unidimensional, cujos itens podem apontar para outros arrays unidimensionais de inteiros… Essa construção pode ser até melhor que a de arrays multidimensionais simples, em termos de performance, em muitos casos, já que a multiplicação do índice da dimensão mais alta pela quantidade de itens da dimensão mais baixa é, sempre que possível, evitada.

Loops “de trás para frente” são mais rápidos do que os “da frente para trás”

Essa crença é falsa no sentido de que o compilador tenta encontrar o melhor arranjo possível de instruções para atender a instrução do loop. Por exemplo, os loops abaixo podem resultar no mesmo conjunto de instruções em assembly:

for (i = 0; i < N; i++)
  a[i] = 0;

for (i = N - 1; i >= 0; i--)
  a[i] = 0;

O compilador saberá, por análise, que ambos os loops fazem a mesma coisa e criará o melhor código possível para ambos os casos. Isso é especialmente verdadeiro se algum nível de otimização estiver sendo usado (-O2 em diante no GCC, por exemplo).

O que é verdadeiro nessa “receita” é que, em assembly, em alguns casos, loops “para trás” podem ser melhores pelo fato de que a comparação estar sendo feita contra o valor zero. Mesmo assim, como já mostrei por aqui, a posição onde a comparação é feita também é importante para aproveitar os efeitos do branch prediction.

Aliás, em alguns compiladores, o código acima poderia muito bem não conter loop algum, sendo substituído por:

  mov ecx,N
  xor eax,eax
  lea rdi,[a]
  rep stosd

Pode-se argumentar que rep stosb é uma forma de loop, mas note que ele preenche o buffer apontado por RDI “da frente para trás”, o que quebra a “receita”…

Variáveis locais tendem a serem alocadas em registradores

Essa receita também deve ser avaliada cuidadosamente. Ela tende a ser verdadeira em duas condições:

  1. Se houverem registradores em número suficiente para essa “alocação”;
  2. Se estivermos compilando o código com algum nível de otimização.

O primeiro ponto é óbvio, se nossa rotina já estiver usando os registradores “alocáveis” disponíveis, na convenção de chamada, então não será possível alocar algum outro e a pilha será usada… Já o segundo ponto, a rotina abaixo pode ilustrá-lo:

int sum( int *a, unsigned size )
{
  int s;

  s = 0;
  while ( size-- )
    s += *a++;

  return s;
}

Compilando o código sem e com otimização (-O2), temos:

sum:                        sum:
  push  rbp                   test  esi, esi
  mov   rbp, rsp              lea   eax, [rsi-1]
  mov   [rbp-24], rdi         je    .L4
  mov   [rbp-28], esi         lea   rdx, [rdi+rax*4+4]
  mov   DWORD [rbp-4], 0      xor   eax, eax
  jmp   .L2                 .L3:
.L3:                          add   eax, [rdi]
  mov   rax, [rbp-24]         add   rdi, 4
  lea   rdx, [rax+4]          cmp   rdi, rdx
  mov   [rbp-24], rdx         jne   .L3
  mov   eax, [rax]            ret
  add   [rbp-4], eax        .L4:
.L2:                          xor   eax, eax
  mov   eax, [rbp-28]         ret
  lea   edx, [rax-1]
  mov   [rbp-28], edx
  test  eax, eax
  jne   .L3
  mov   eax, [rbp-4]
  pop   rbp
  ret

O código da esquerda (compilado sem otimizações) mantém na pilha a variável sum, bem como o ponteiro a e o argumento size que, por definição, são “variáveis locais”… Já a rotina da direita, os mantém em registradores (sum é mantido em EAX e o ponteiro final é mantido em RDX enquanto a é mantido em RDI.

Existem outros fatores em jogo aqui… variáveis locais de tipos primitivos e ponteiros tendem a serem colocados em registradores, se as otimizações estiverem sendo usadas, mas arrays não, especialmente se estes ultrapassarem certa quantidade de elementos.

“Eu uso o JDK da Oracle porque é free!”… ã-hã! tá… sei…

Já leu o acordo de licenciamento, figura? Tá aqui, ó. Pontos altos:

You may not:
- use the Programs for any data processing or any commercial,
  production or internal business purposes other than developing,
  testing, prototyping and demonstrating your Application;
- create, modify, or change the behavior of, classes, interfaces,
  or subpackages that are in any way identified as "java", "javax",
  "sun", “oracle” or similar convention as specified by Oracle in
  any naming convention designation.

A primeira é importante porque diz, claramente, que para usar O JDK (ou JRE) da Oracle você tem que dar uma grana para a Oracle…

Detalhes importantes sobre aritmética inteira

Em uns artigos eu falei pra vocês sobre algumas armadilhas relativas ao uso de ponto flutuante. A ideia de que você lida com valores no domínio dos números “reais”, por exemplo, deve ser compreendida com muito cuidado… Bem… e não é que existem erros de interpretação por ai a respeito da aritmética inteira também?

Vejamos uma otimização muito comum:

#include <stdio.h>

void main( void )
{
  int a = -1;
  int b = a >> 1;
  int c = a / 2;

  printf("%d, %d\n", b, c );
}

Olhando para o código acima o leitor pode supor que ambos os valores impressos serão iguais. Afinal, parece que estamos apenas dividindo por 2 o valor de a, em ambas as expressões. No entanto, em arquiteturas onde existe a distinção entre shifts lógicos e shifts aritméticos, o resultado em b será -1, enquanto o resultado em c será, necessariamente, zero!

Ambas as expressões continuam usando shifts, por debaixo dos panos. Uma implementação possível, por parte do compilador, poderia ser essa:

main:
  ...
  mov  edx,-1   ; EAX = a = -1

  mov  ecx,edx
  sar  ecx,1    ; ECX = b = (a >> 1)

  mov  eax,edx  ; EDX = c (EAX é um temporário aqui).
  shr  eax,31
  add  edx,eax  ; if (b < 0) c++
  sar  edx,1    ; c >>= 1
  ...

Esse pequeno shift lógico e a adição “condicional” corrigem o problema do shift aritmético com relação ao valor -1. Note que todos os outros valores inteiros negativos continuarão funcionando corretamente.

Isso quer dizer que devemos tomar muito cuidado com deslocamentos para a direita. Afinal, a própria especificação da linguagem C (leia a ISO 9989:1999 em diante) afirma que deslocamentos para a direita de objetos integrais sinalizados é “dependente de implementação”.

Outro problema que é vastamente ignorado é o calculo de valores absolutos de um valor inteiro. A libc implementa a função abs() que deveria ser usada para esse propósito, mas é bem comum ver fragmentos de código como o abaixo:

int _abs( int x )
{
  if ( x < 0 )
    x = -x;

  return x;
}

Isso parece correto, mas considere o seguinte: Se tentarmos inverter o sinal do valor 0 (zero), obteremos o mesmo zero. Isso pode ser interpretado de duas maneiras. Ou o valor zero é “especial” e não tem sinal, ou existem dois zeros diferentes (um +0 e um -0). No caso dos valores inteiros sinalizados o msb define o sinal do valor… Assim, -0 não existe e, de fato, zero é um valor com características especiais. Mas, vamos assumir que ele possa ser interpretado como valor sinalizado, de acordo com a função acima… Existe outro valor com a mesma característica (ou seja, que possa ser negativo e positivo ao mesmo tempo)?

No caso do tipo int, o msb é o bit 31 e, como aprendemos sobre “complemento 2”, para obter o valor representado temos que inverter todos os bits e somar 1… 0xffffffff, por exemplo, representa -1. Mas, em 32 bits, existe um valor diferente de zero especial: 0x80000000 (o bit 31 setado e os demais zerados). Ao invertê-lo e somar um obtemos o mesmo valor, ou seja, existe um -2^{31} e um +2^{31}. Mas, como o msb é quem define o sinal, ao informar o argumento 0x80000000 para x, na chamada da função acima, obteremos o mesmíssimo valor.

A rotina acima, obviamente está errada! Já que o valor absoluto de -2147483648 não pode ser o mesmo valor! Infelizmente isso não tem uma solução fácil porque, com 32 bits, usando um objeto integral sinalizado, não há como obter o valor positivo oposto a -2147483648, dada a assimetria dos valores extremos dessa representação.

Minhas tentativas de otimizar o checksum16

Existe uma recomendação (RFC) que mostra como o checksum de 16 bits deve ser calculado para pacotes IP (por exemplo). No projeto T50 já fiz várias tentativas malsucedidas de otimizar a rotina, tentando usar uma métrica simples: Quantos ciclos de clock estão sendo gastos para “somar” cada byte do buffer? Aqui vou mostrar como o cálculo funciona, como otimizá-lo, erros de cometi e, depois de acertá-los, porque não o fiz…

A referida RFC é a 1071 (que pode ser obtida aqui). Essencialmente, o algoritmo deve agrupar os bytes em words (16 bits) e somá-los, juntamente com os carry-outs resultantes das somas parciais (o que é chamado de soma em complemento um). No contexto dos protocolos de rede a soma final têm todos os 16 bits invertidos e armazenados no pacote, de forma que, se um novo cálculo de checksum for feito com esse novo pacote, o resultado final será exatamente zero. A rotina original (desconsiderando o endianess) pode ser vista na RFC. A apresento com ligeira modificação abaixo…

Para efeitos de teste, da mesma maneira que citada na RFC, consideremos um buffer contendo os seguintes bytes:

uint8_t buffer[] = {
  0x00, 0x01, 0xf2, 0x03, 0xf4, 0xf5, 0xf6, 0xf7
};

Ao somar cada par de valores, temos:

  0001
  f203
  f4f5
+ f6f7
───────
 2ddf0

O ‘2’, além dos 16 bits inciais veio dos carry-outs das somas parciais e, portanto, deve ser somado aos 16 bits infereiores. O checksum resultante é 0xddf2. Note que essa soma ai em cima foi feita usando o modelo big endian. Em little endian a única coisa que muda é que devemos trocar os bytes de posição no final das contas:

  0100
  03f2
  f5f4
+ f7f6
───────
 1f2dc

O resultado, depois de adicionado os carry-outs do resultado, é 0xf2dd que, depois do swap, dá exatamente 0xddf2.

O buffer tem exatamente o tamanho de 4 words, mas se retirarmos 0xf7 do buffer teremos um tamanho impar, em bytes. Neste caso, note que em big endian o valor da última word deverá ser 0xf600, não 0x00f6. Assim, esse último byte já estará na posição correta em processadores Intel (por exemplo), mas deverá ser colocada no MSB em arquiteturas que lidam com big endian.

A rotina final fica assim:

uint16_t cksum16( void *buffer, size_t size )
{
  uint16_t *ptr;
  uint32_t sum;

  sum = 0;
  for ( ptr = buffer; length > 1; length -= 2 )
    sum += *ptr++;

  if ( length > 0 )
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    sum += *( uint8_t *)ptr;
#else
    sum += ( ( uint16_t ) *( uint8_t *)ptr ) << 8;
#endif

  while ( sum >> 16 )
    sum = ( sum & 0xffffU ) + ( sum >> 16 );

  return ~htons(sum);
}

A rotina acima consegue calcular o checksum16 com a performance aproximada de 1,8 ciclos de clock para cada byte do buffer (para buffers grandes, como veremos mais adiante). Isso parece ser muito bom, mas, e se pudéssemos realizar o cálculo a cada 32 ou 64 bits por vez (ou até 128 ou 256, no caso de usarmos SSE ou AVX)? Isso pode ser feito facilmente, desde que os sub blocos de 16 bits do resultado final sejam somados de acordo com as mesmas regras que vimos até agora. Vejamos como a mesma sequência, em little endian, se comporta (isso também está na RFC):

  03f20100
+ f7f6f5f4
───────────
  fbe8f6f4   ⇒  fbe8 + f6f4 = 1F2DC

O valor final é o mesmo resultado que obtivemos, antes do swap, no exemplo para little endian anterior… O mesmo princípio da soma dos carry-outs nas somas parciais do buffer (em 32 bits) aplica-se aqui. No exemplo acima não houve carries na primeira soma ou, temos carry-outs igual a zero.

Em teoria, realizar a soma com grupos maiores pode ser uma boa ideia, mas há mais cuidados a serem levados em conta:

  1. Se o buffer não contiver uma quantidade de bytes múltipla do tamanho do bloco inicial, restarão de 1 a n-1 bytes finais (onde n é a quantidade de bytes do bloco parcial). Exemplo: Se tivermos um buffer de 9 bytes e usando somas parciais por dword (32 bits), sobrará 1 bytes final. Mas, se tivermos um buffer com 11 bytes, teremos 3;
  2. A mesma preocupação com padding que tivemos com 16 bits teremos que ter com mais bits, e graças a consideração acima, isso fica um pouquinho mais difícil;
  3. A variável de acumulação deve ser, necessariamente duas vezes maior, em tamanho, do que as somas parciais. Se usarmos somas parciais de 32 bits teremos que acumulá-las em uma variável de 64 para podermos separar os carry-outs.

Somente essas considerações tornam difícil melhorar a performance da rotina original, especialmente no que concerne à segunda e terceira… Mas, é claro, não é “impossível”… Vamos tentar…

Se formos usar dwords como limite superior de tamnho, temos que contar quantas existem no buffer. Isso é fácil, basta desconsiderar os 2 bits inferiores de size. Da mesma maneira, os 2 bits inferiores de size nos dizem se temos bytes extras no final do buffer:

A rotina para little endian fica assim:

uint16_t cksum16( void *buffer, uint32_t size )
{
  uint32_t *ptr;
  uint64_t sum;
  uint32_t dwcount;
  int wextra, bextra;

  // Quantas DWORDs temos?
  dwcount = size >> 2;

  // Temos uma WORD e/ou um BYTE extra?
  size &= 3;
  bextra = size & 1;  // byte?
  wextra = size >> 1; // word?

  // Soma as dwords.
  sum = 0;
  ptr = buffer;
  while ( dwcount-- )
    sum += *ptr++; 
  
  // Se temos uma word extra...
  if ( wextra )
  {
    sum += *( uint16_t *)ptr;

    buffer = ptr;   // Atualiza ptr.
    buffer += 2;
    ptr = buffer; 
  }

  // Se temos um byte extra...
  if ( bextra )
    sum += *( uint8_t *)ptr;

  // Interpreta tudo acima dos 16 bits inferiores
  // como carry-outs.
  while ( sum >> 16 )
    sum = ( sum & 0xffffU ) + ( sum >> 16 );

  return ~htons(sum);
}

Obviamente dá para melhorar a rotina, mas supostamente temos agora um avanço de performance. Se medirmos com o “medidor de ciclos do homem pobre” observamos que a coisa não é tão significativo assim.

Num dos PCs que tenho acesso, consegui aumento de 38% na performance (238 ciclos, contra 388 da rotina original), no modo x86-64… 38% não é lá grandes coisas, considerando que a rotina original já é bem rápida (388 ciclos num processador de 3.4 GHz nos dá cerca de 114 μs, contra os cerca de 70 μs da nova rotina). Implementar a rotina para obter uma qword de cada vez também não melhora lá muito. Obtive 306 ciclos, uma melhora de 20% em relação à rotina original, mas uma piora de 28% em relação à segunda! O motivo da piora da terceira rotina (que não vou nem colocar aqui) é que a acumulação exige 128 bits e não estamos lidando, necessariamente, com SSE aqui. Mesmo que usássemos, até onde sei, não existem instruções para adição de dois valores inteiros de 128 bits disponível…

Repare também que a afirmação que fiz anteriormente sobre a métrica de 1.8 ciclos por byte “não bate”, não é? Acontece que isso só é válido para buffers grandes. Com buffers pequenos o gasto de tempo das instruções fora dos loops têm peso no tempo gasto.

Como regra geral, se não consigo aumentar a performance em, pelo menos, 100%, não vale a pena a otimização. Especialmente porque existem outros fatores não considerados aqui:

  1. Cache misses
  2. Alinhamento do buffer
  3. Overrun da maneira como acumulamos os carry-outs

No caso do T50, a rotina do módulo que chama cksum() já colocou os dados do buffer no cache L1 (muito provavelmente) e, por isso, cache misses não é uma preocupação. Mas o alinhamento do buffer pode consumir alguns ciclos (pouco provável). O problema real é o terceiro item.

Seria mais “fácil” acumular os carry-outs em cada iteração do loop inicial, via o par de instruções ADD/ADC que, em teoria, eliminaria o loop final… Mas isso só pode ser conseguido em assembly, já que, em C, as operações aritméticas integrais são, em essência, carryless

Existe também o problema das arquiteturas. Na plataforma Intel posso realizar algumas otimizações que não estejam disponíveis em outras e vice-versa. A ideia do T50 é compilá-lo para qualquer uma das 24 (tem mais?) plataformas em que o Linux foi adaptado, de Intel x86 até Intel IA-64, MIPS, ARM, Atmel AVR, Motorola 68000, Power PC, SPARC etc… Para isso a segunda rotina pode até ser usada, mas aumentar a granulidade do loop inicial para além de 32 bits pode ser problemático para a performance nessas outras plataformas…

O erro de cometi…

Achou que eu ia deixar isso de fora? Na minha tentativa de otimizar a rotina original cometi o erro de pensar que a ordem dos bytes somados não interessava (de fato não interessa, se estivéssemos somando bytes!), mas a rotina é feita para somar words. O erro que cometi antes foi obter o byte do início do buffer caso tivéssemos um tamanho ímpar, em bytes e só depois acumular words. Isso simplificava a rotina, mas ao mesmo tempo a tornava errada… That’s it!