Entendendo a coerência de cache

Antes de você começar a ler a coisa boa desse artigo deixe-me te dizer que a primeira coisa que deve ser pensada para garantir que uma função seja rápida não está relacionada ao comportamento do cache, com o sistema de paginação, com a contagem de ciclos de clock… O que importa, inicialmente, é o algoritmo usado. Refiná-lo até o ponto onde você acha que não pode melhorar é o primeiro passo. A partir dai você descobre que ainda tem muito a percorrer. O cache e os outros detalhes entram na jogada… Este artigo descreve, com algum detalhe, mas sem a profundidade que eu gostaria, o comportamento do cache…

Tanto aqui quanto no meu inacabado livro faço questão de ressaltar a importância dos caches quando estou falando de performance absoluta de rotinas. Já deve ser de conhecimento geral que o processador jamais acessa memória diretamente. Que ela é “cacheada” (se é que esse verbo existe) sempre! E o cache é uma memória RAM de alta velocidade, bem mais rápida que a memória RAM, dinâmica, instalada na sua placa-mãe. Nos processadores x86 modernos existem, pelo menos, três níveis de cache: L1, L2 e L3.

Para efeitos de explicação, considerarei, na maioria das vezes, que o cache L1 é o único que existe. Na prática, o cache L1 recebe seus dados do cache L2 e este do cache L3, se houver. O último nível de cache recebe/envia dados para a memória física…

Os níveis de cache:

O primeiro nível de “cacheamento” é dividido em dois: “dados” e “instruções”. Tanto dados quanto instruções têm de ser lidos da memória, certo? Desses dois, o que nos interessa mais é o cache de dados, chamado de L1D e ele  é excepcionalmente importante porque trata-se do acesso direto das unidades de execução às cópias de dados da memória física. A palavra importante aqui é “cópia”. Quando falamos de cache falamos de cópias de blocos de dados que se encontram na memória RAM do seu sistema.

A memória física está bem longe do primeiro nível de cache. O cache L1D está mais perto dos processadores lógicos. Entre ele e a memória temos os caches L2 e, possivelmente, o cache L3. Só então a memória física pode ser encontrada.. O cache L1D é pequeno, tendo apenas cerca de 32 KiB de tamanho. O cache L2 costuma ter uns 256 KiB e o cache L3, se houver, alguns MiB de tamanho (no meu sistema, 8 MiB). Os caches L1 e L2 costumam estar localizados no interior do processador. O cache L3 pode ser interno ou estar localizado numa memória estática, de alta velocidade, externa.

Estrutura dos caches:

Caches funcionam com unidades fundamentais de uma “linha”. Na arquitetura Intel (i386 ou x86-64), especialmente em processadores mais modernos, o tamanho dessa linha é de 64 bytes (ou 512 bits). O cache L1D é dividido em 512 linhas (para 32 KiB). É fácil calcular a quantidade de linhas dos outros caches, mas essas linhas sempre terão o mesmo tamanho.

Uma linha sofre outras divisões chamadas de “caminhos” (ways). Essencialmente, é uma divisão igualitária dos 64 bytes em blocos menores. Num processador com “associatividade” de 4 caminhos (4 ways associativity), temos 4 blocos de 16 bytes cada, o que é conveniente para conter o conteúdo de registradores para Streaming SIMD Extension (SSE). Aliás, este é o motivo pelo qual a Intel e a AMD recomendam que os pontos de entrada de funções e pontos de entrada de loops sejam alinhados de 16 em 16 bytes, para evitar duas leituras (do cache L1I), necessárias quando uma instrução cruza a fronteira de um caminho…

A associatividade só é importante se houver particionamento de informações dentro de uma linha. Se tentarmos ler/escrever dados que cruzem a fronteira de um caminho, alguma penalidade pode ser adicionada na execução de uma instrução. Para fazer um tuning fino do acesso ao cache, devemos evitar coisas como:

struct {
  int a[3]; /* a, b e parte de c cabem numa associação. */
  char b;
  int c;    /* Os byte final cabe em outra associação! */
} data;

Essa estrutura tem 17 bytes de tamanho e portanto cabe numa única linha, mas a variável c não cabe dentro de um único caminho. Para alterar o conteúdo de c devemos acessá-lo, no cache, duas vezes…

Outra informação importante é que cada “núcleo” do seu processador tem o próprio cache L1D. Note que falei cada “núcleo”, que tem tipicamente dois processadores lógicos. Assim, um cache é compartilhado por dois processadores lógicos o tempo todo. Isso causará penalidades se tivermos duas threads executando em dois processadores do mesmo núcleo…

Em uma linha, além dos 64 bytes de dados, temos duas outras informações: Uma “tag” ou “etiqueta”, que informa ao processador a qual região da “memória linear” a linha pertence. É importante ressaltar “memória linear” ao invés de “física” aqui, já que os sistemas operacionais modernos usam o recurso de “memória virtual” através de paginação.

Essa “etiqueta” contém apenas os bits superiores do “endereço linear”, já que os 6 bits inferiores serão usados para obter o offset do dado contido na linha (2^{6}=64). De fato, os quatro bits inferiores contém o offset e os dois bits seguintes o “caminho”.

Sempre que o processador queira acessar memória ele vai procurar nas linhas do cache L1D se existe uma etiqueta correspondente ao endereço solicitado. Se não houver temos um cache miss (dá pra ouvir a voz do Faustão dizendo “Errou!”) e o processador copiará a linha da memória e colocará no cache, para que as outras referências a esse bloco sejam feitas pelo cache, não pela memória do sistema, que é mais lenta.

Mas, se ao tentar acessar a memória uma etiqueta correspondente for encontrada no cache, temos um cache hit. Daí, o processador decide como acessar essa linha, de acordo com o “estado” em que ela se encontra.

Os estados das linhas de cache:

Além da “etiqueta” temos um campo de “estado” da linha. Existem 4 estados possíveis: Modified, Exclusive, Shared e Invalid (daí o nome do protocolo MESI). Esses estados são mutuamente exclusivos. Quero dizer, somente um deles pode estar sendo usado numa linha de cache a qualquer momento.

O estado mais óbvio é o I. Uma linha de cache inválida é uma linha “vazia”, que não contém uma cópia válida. Existem casos em que o processador decide “invalidar” uma linha, como veremos adiante.

O estado M ocorre quando há uma escrita numa linha válida. Indica que a linha sofreu alguma modificação e encontra-se num estado diferente do bloco de dados original, lido da memória. Outra designação para esse estado é “sujo” (Dirty). Ao escrever no cache o processador “sujou” a linha.

O estado E diz que a linha contém uma cópia válida e exclusiva. Ou seja, essa é a única cópia e não existem outras nos outros caches L1D associados aos outros processadores lógicos. O estado S é o contrário de E: ele diz que a linha é compartilhada (shared) em, pelo menos, dois caches L1D.

O protocolo MESI:

O diagrama abaixo mostra o protocolo MESI em algum detalhe (clique na imagem para ver de forma mais clara):

1024px-MESI_protocol_activity_diagram_1024

A cópia de blocos depende tanto do tipo de acesso (leitura ou escrita), quanto da capacidade de encontrar uma linha válida (cache hit, ou seja, “encontrei”, ou miss, “não encontrei”) e seu estado. O algoritmo acima explica muito bem o protocolo… Existe uma complicação quando temos um cache hit para escrita em linhas no estado S e em cache misses, quando tivermos outras linhas já modificadas. Linhas contidas em outros caches L1D podem ser invalidadas para manter a integridade dos dados, fazendo com que o processador lógico associados aos outros caches tenham que recarregar as linhas a partir do próprio cache. Para evitar isso, a Intel e a AMD resolvem implementar o protocolo MESI modificado.

No caso da Intel, ela usa o protocolo MESIF, com a adição de um estado Forward. Esse novo estado é um substituto para o estado S nos outros caches. Diz ao processador que a linha contendo os dados modificados está “adiante”, numa linha marcada com o estado M, em outro cache. Já a AMD usa o protocolo MOESI, onde o estado Owned (“proprietário” ou “dono”) faz praticamente a mesma coisa que o F, só que no sentido contrário: Ele substitui o estado M para linhas compartilhadas, indicando quem é o dono real da linha, deixando as demais, marcadas com S, intactas.

Não vou debulhar os protocolos MESIF ou MOESI aqui, basta saber que eles tentam acelerar um pouco a coerência dos caches, em ambientes multi threaded, evitando a invalidação de linhas e sua posterior recarga.

Por que o conceito do protocolo MESI é importante?

Se você realmente pretende lidar com multi threading terá que saber que um bloco de dados, que pode ser maior que uma simples variável, pode estar sendo compartilhada entre processadores lógicos e escritas podem causar penalidades na performance. Por isso, podemos querer evitar que linhas de cache adquiram estado S, mantendo-as exclusivas no ato da leitura. O problema de linhas em estado S é que eventualmente precisarão ser sincronizadas, como citei acima, e o processador vai gastar algum tempo para fazer isso.

Claro que alguma penalidade também pode ser percebida em escritas… Lembre-se que o que temos nos caches é uma cópia da memória física e, em algum momento, esses dados terão que ser “despejados” do cache. Da mesma forma que o processador deu uma “paradinha” para carregar uma linha, eventualmente ele terá que dar outra “paradinha” para copiá-la de volta para a memória.

Tipos diferentes de escrita:

O comportamento do processador com relação à escrita depende de como o bloco de memória física é configurado no power on (via MTRR – Memory Type Range Registers): Se a região da memória sendo cacheada é marcada como write through (“escrever através” [do cache]) o processador manterá o estado M por pouco tempo, fazendo a escrita o mais rapidamente possível. Este é o caso de I/O mapeada em memória, já que a maioria dos dispositivos de I/O é sensível à temporização de escrita…

Se a região é marcada como write back (“escrever por trás”), a linha em estado M pode ser mantida tanto tempo quanto for necessário neste estado até que precise ser usada para conter um bloco de dados de outra região. Neste caso, o processador copiará a linha atual e lerá outra, mudando o estado de M para E ou S, dependendo apenas se já existe ou não uma linha com a mesma etiqueta em outro cache. Ou seja, o processador só vai transferir a linha quando for absolutamente necessário…

Dicas de codificação para aproveitar o cache L1D:

O que se pode esperar de toda essa lenga-lenga?

  1. Evite compartilhar linhas de cache entre threads! Isso pode ser feito alinhando-se blocos de dados usados por threads diferentes de 64 em 64 bytes. Em C isso não costuma ser muito problemático, já que variáveis locais às threads costumam ser alocadas na pilha e cada thread tem sua própria pilha… O problema é o uso de variáveis globais por várias threads, que deve ser minimizado, mesmo porque, vale à pena evitar o sincronismo de threads;
  2. Evite usar blocos de dados muito grandes. Blocos de dados grandes geram dois problemas: Aumentam a pressão nos caches (muitas linhas terão que ser descartadas e outras, lidas) e pode colocar pressão no sistema de paginação se usarmos blocos maiores que 4 KiB. Se você tiver que trabalhar com blocos grandes, tente traduzi-lo em “pedaços”;
  3. De preferência, faça prefetches para garantir que os “pedaços” que você precisa que estejam no cache realmente sejam colocados lá de antemão.

Busca antecipada ou prefetches:

Para finalizar minha explicação sobre os efeitos do cache, devo falar sobre prefetches.

Prefetch pode ser traduzido livremente como “pré busca” ou “pré carga”, em inglês. É o ato de pré carregar um bloco de dados antes de manipulá-lo. O processador faz isso sozinho, quase sempre, mas é interessante fornecer “dicas” informando-o que, em certos pontos, ele deve fazer uma pré carga… Essas dicas são enviadas ao processador através de instruções PREFETCH e existem algumas delas.

Existe um outro campo escondido nas linhas de cache que especificam uma prioridade “temporal” para elas. As instruções PREFETCHTn (note o “Tn“) pedem ao processador para pré carregar uma linha de cache e atribuir uma prioridade entre 0 e 2, onde 0 é menos prioritária e 2, mais. Quando menor o valor, mais facilmente o processador pode “esquecer” a linha do cache.

Essas instruções são essencialmente inóquas em relação ao cache L1D e altamente dependentes de arquitetura. No Pentium III, por exemplo, a instrução PREFETCHT0 tendia a pré carregar uma linha no cache L1D, sempre. Do Pentium 4 em diante, o prefetch de leitura temporal é feito automaticamente pelo processador. Se for  realizar prefetch para leitura, prefira PREFETCHT0, mas saiba que o processador pode não respeitar seu pedido.

Já a instrução PREFETCHW é um pouco mais útil. Ela pede ao processador a pré carga no cache L1D e prepara o processador para uma escrita na linha. Isso não muda o estado da linha para M, mas literalmente faz o processador ficar com “orelha em pé”, esperando que em qualquer momento haja uma escrita.

A instrução de prefetch com maior prioridade é PREFETCHNTA. Ela marca a linha como “não temporal” (NT) em todos os níveis de caches (A, de “All”). O processador tenta manter a linha que tenha essa marca o maior tempo possível no cache L1D. Assim, ela será a última linha escolhida para substituição se o processador precisar de espaço. Claro que se você usar PREFETCHNTA para todo e qualquer acesso de seus dados, o sistema de prioridades não será de nenhuma valia… E o uso dessa instrução não significa que a linha nunca será liberada para outro uso. Ela só estará presente por mais tempo.

Uso de recursos

Há quanto tempo!!! Estive sumido daqui porque não encontrei assuntos relevantes para postar e também porque tenho estudado algumas coisas interessantes. Eis-me aqui, digníssimos…

Quero falar sobre o problema do uso de recursos (memória, I/O, etc) e citar um exemplo simples que vi, recentemente… Hoje em dia os amigos “desenvolvedores” costumam pensar em termos de ambientes ideais (recursos virtualmente ilimitados). Aqueles que não o fazem pensam que o uso irrestrito de recursos é justificável graças ao preço do hardware (que caiu muito nas últimas décadas). É minha opinião que o pensamento deveria ser o contrário.

O “preço” alto que deve ser pago é o da baixa performance. Especialmente quando estamos falando de aplicações que serão usadas por centenas ou milhares de usuários simultaneamente. O cálculo é bem simples: Se sua aplicação usa dezenas de megabytes de memória, multiplicando isso pelo pior caso — suponha: uns 1000 usuários simultâneos — acabamos com o problema de uso de dezenas de gigabytes de recurso… Ao mesmo tempo, para cada usuário (ou um pequeno conjunto deles) uma thread é alocada para atendẽ-lo. No pior caso teríamos milhares de threads em execução em uma única CPU.

Isso demonstra o quão preciosos são os recursos. Minha aproximação ao problema é limitar a quantidade de memória física usada por thread e, na medida do possível, limitar a quantidade de threads em execução por core. Parece lógico, né? Mas não é o que se observa por ai. Em meu trabalho já topei com servidores rodando mais de 1000 threads simultâneas e, de maneira alguma, limitando o uso de memória. Sem contar com o consumo de handles para sockets! Não vou mostrar estatísticas ou códigos desses sistemas (já que, provavelmente eu iria pro olho-da-rua se o fizesse, mesmo que pudesse). Vou mostrar um exemplo aparentemente inofensivo que topei num código ‘livre’. Olhe só:

#define MAX_IP_ADDRS 16777216

int main(int argc, char **argv)
{
  //...
  static uint32_t addresses[MAX_IP_ADDRS];

  //...
  for (i = 0; i < MAX_IP_ADDRS; i++)
    addresses[i] = base + i;

  //...
  rand_addr = rand() % MAX_IP_ADDRS;
  use_addr(addresses[rand_addr]);

  //...
}

Repararam que o desenvolvedor alocou um buffer de 64 MB para armazenar valores sequenciais? A idéia aqui é “acelerar” a aplicação através do método conhecido como table lookup. Só que, declarar um vetor como static dentro de uma função faz com que o compilador gere código escondido para alocação dinâmica do vetor e o preenchimento do mesmo com zeros.

Isso pode te parecer exagero, afinal, o que são 64 MB hoje em dia? Acontece que o código original usa forking para duplicar o processo e, no processo, duplicar os recursos em uso. Usaríamos então 128 MB de memória do sistema com dois processos rodando (e se realizássemos mais forks, teríamos 64 MB/fork!).

Eis um código que faz a mesma coisa (e mais rápido) sem criar um grande array de 64 MB:

#define MAX_IP_ADDRS 16777216

int main(int argc, char **argv)
{
  //...
  rand_addr = rand() % MAX_IP_ADDRS;
  use_addr(base + rand_addr);

  //...
}

O conselho aqui é poupar, ao máximo, o uso de recursos e sempre revisar o seu código, porque sempre tem uma maneira mais eficiente e econômica de fazer alguma coisa.

Estatística, Cache e a confiabilidade do RDTSC

Já acabei com o minha auto-flagelação (é assim que se escreve?!) e resolvi fazer umas medidas com relação ao uso da função rdtsc(). Como só faz sentido fazer testes com uma função destinada a testes do ponto de vista estatístico, então aqui vamos nós usar médias, modas e desvios-padrão. Aliás, por este último, entenda como sendo a média dos desvios da média (huh! ou seja: a maioria das amostras desviam-se de uma certa quantidade da média simples das mesmas amostras, ok?).

O desvio padrão nos dará uma idéia da precisão das medidas via rdtsc(). Vou usar o coeficiente de variação para expressar isso. Esse coeficiente é o a relação entre a o desvio-padrão (expressado pela letra grega σ) e a média (expresada pela letrea grega μ). A relação é dada em porcentagem. A interpretação é que a maioria das amostras desviam-se x porcento da média…

Antes de começarmos quero que você tenha em mente algumas informações sobre o seu hardware:

  • Sua memória é particionada em blocos de 4 kB chamados páginas. Essas páginas podem ou não existir fisicamente. No caso de elas ainda não existirem o sistema operacional vai criá-la e, para isso, pode simplesmente alocar o bloco de memória e colocá-lo num diretório de páginas ou, se este diretório estiver cheio ou prestes a encher, pode decidir guardar uma ou mais das páginas pré-existentes em disco e atribuí-las ao seu processo (ou seja, fazer swap). Esses processos são demorados e implicam numa parada total do seu processo (tempo dedicado 100% para o kernel);
  • Todos os processadores modernos possuem caches. Hoje é muito comum termos 2 caches. Um deles é o chamado cache L1 e localiza-se no interior do processador. Também hoje é comum termos caches L1 com 64 kB de tamanho. O outro cache é o L2 e também é muito comum que este cache esteja dentro do processador também. Em bons processadores o cache L2 pode ter 4 MB de tamanho. Caches aumentam a velocidade do acesso à memória porque, com eles, a quantidade de acessos à memória é diminuída. O problema é quando uma linha (64 bytes), correspondente a um bloco da memória do sistema, não se encontra no cache L1. Neste caso o processador pára tudo e tenta ler a linha do cache L2. Se a linha também não está no cache L2 então este tentará ler um bloco de linhas da memória do sistema e depois repassa a linha lida para o cache L1;
  • Existem muitas coisas feitas pelo kernel do seu sistema operacional que o seu processo não tem controle. A maioria deles interrompe a execução de seu processo.

Esses três fatores afetam muito a medição dos ciclos de máquina de um fragmento do seu processo. E estes são os motivos que causam imprecisão no uso da função rdtsc().

O processo que usei para colher dados estatísticos do uso de rdtsc() compreende a leitura de n diferenças de tempo entre chamadas à rdtsc() e o armazenamento dessas diferenças em um buffer com n “quad words” (ou seja, cada entrada é do tipo “uint64_t”). Este tamanho n vai ser de 8 elementos (64 bytes), 32 elementos (256 bytes), 256 elementos (4 kB) e 1024 elementos (8 kB). Em essência, o fragmento de código que armazena as diferenças é assim:

int i;
uint64_t buffer[BUFFER_SIZE], *p;

for (p = buffer, i = 0; i < BUFFER_SIZE; i++, p++)
{
  *p = rdtsc();
  *p = rdtsc() - *p;
}

Eis as estatísticas para 8 e 32 elementos:

$ ./test8
Tamanho do buffer: 64 bytes.
Média: 314.12
Desvio padrão: 9.49
Coeficiente de variação: 3.02%
Valor mínimo: 308
Valor máximo: 336

$ ./test32
Tamanho do buffer: 256 bytes.
Média: 308.22
Desvio padrão: 1.24
Coeficiente de variação: 0.40%
Valor mínimo: 308
Valor máximo: 315
Dentro do Cache e da Página não há muitos problemas!

Uma vez que o buffer está dentro do cache L1, a variação na medição de tempo não é lá grandes coisas. Chega a ser menor o igual a 5%. O problema é quando cruzamos a fronteira de uma página:

$ # Ainda não cruzamos a fronteira de 4096 bytes aqui!
$ ./test256
Tamanho do buffer: 2048 bytes.
Média: 309.94
Desvio padrão: 3.49
Coeficiente de variação: 1.13%
Valor mínimo: 308
Valor máximo: 336

$ # Agora sim, cruzamos a fronteira!
$ ./test1024
Tamanho do buffer: 8192 bytes.
Média: 322.03
Desvio padrão: 290.35
Coeficiente de variação: 90.16%
Valor mínimo: 308
Valor máximo: 7434
Continuamos dentro de uma página!
Os picos provavelmente são devidos à paginação e aos efeitos do cache.

É interessante observar que, no último gráfico, os picos ocorrem aproximadamente aos 4 kB e aos 8 kB, justamente a fronteira de uma página!

Observem que, no geral, mesmo com os efeitos da paginação e do cache, RDTSC não foge muito de seu valor esperado, exceto em alguns pontos. Se fizermos os mesmos testes com um buffer de 1 milhão de elementos, obteríamos um gráfico mais ou menos como o último, com mais picos graças ao número quase 1000 vezes maior de amostras.

Meu veredito? rdtsc() possui problemas de precisão, mas é muito confiável. Mas, acho que eu já havia dito isso aqui, não?

Medir a performance, SEMPRE! (floats versus doubles)

Eu sou uma besta quadrada… admito… Em um post anterior afirmei (pelo menos acho que fiz isso) que usar floats ao invés de doubles é mais performático, em se tratando de operações em ponto flutuante. Sempre tive essa crença por dois motivos:

  • float é um tipo menor do que double. O primeiro tem exatamente 32 bits de tamanho. O segundo, 64. É lógico pensar que as inicializações e atribuições sejam feitas de forma mais veloz com floats do que com doubles, já que apenas um registrador genérico estará envolvido;
  • Pelo fato de float ser menor e ter menos precisão do que doubles, assumi que as operações (adição, subtração, multiplicação, divisão, funções trigonométricas, etc) fossem também mais rápidas
A minha crença, no primeiro caso, é justificada: Atribuições e cópias são, de fato, mais rápidas na arquitetura x86. Mas a segunda crença é falsa. Vejam isso:
#include <stdint.h>
#include "rdtsc.h"

int main(int argc, char **argv)
{
  float fa, fb, fc;
  double da, db, dc;
  long double lda, ldb, ldc;
  uint64_t t;
  int cnt;

  fb = fc = 0.1f;
  BEGIN_RDTSC(t);
  for (cnt = 0; cnt < 1000; cnt++)
    fa = fb + fc;
  END_RDTSC(t);
  printf_rdtsc_results("1000 float adds", t);  

  db = dc = 0.1;
  BEGIN_RDTSC(t);
  for (cnt = 0; cnt < 1000; cnt++)
    da = db + dc;
  END_RDTSC(t);
  printf_rdtsc_results("1000 double adds", t);

  ldb = ldc = 0.1;
  BEGIN_RDTSC(t);
  for (cnt = 0; cnt < 1000; cnt++)
    lda = ldb + ldc;
  END_RDTSC(t);
  printf_rdtsc_results("1000 long double adds", t);

  return 0;
}

Adicionei a função print_rdtsc_results() em rdtsc.c:

void printf_rdtsc_results(const char *sz, uint64_t t)
{
  printf("%s: %llu cycles\n", sz, t);
}

Ao compilar o código e executá-lo, eis o que obtive:

$ gcc -mtune=native -O0 -fomit-frame-pointer -o test test.c rdtsc.c
$ ./test
1000 float adds: 9849 cycles
1000 double adds: 5901 cycles
1000 long double adds: 8295 cycles

Ou seja, operações de adição com floats são cerca de 67% mais lentas do que as mesmas operações com doubles. São tão performáticas quanto o uso de long doubles (que tem 80 bits – 10 bytes de tamanho – e não podem ser copiadas de uma só vez pelo processador!).

A explicação para essas discrepâncias é a seguinte: Todas as operações em ponto flutuante são feitas como long doubles na arquitetura Intel. Quando usamos float, o processador tem o trabalho de convertê-lo para o tipo long double. Essa conversão toma tempo desnecessário… O mesmo acontece com o tipo double, mas a conversão é mais rápida. Quanto ao tipo long double, como expliquei, o problema não está na conversão, mas no ciclo adicional necessário para copiar os 10 bytes para a pilha do processador. Os 64 bits inferiores são copiados num ciclo e os 16 superiores no outro.

Ué?! Não estamos falando de arquitetura de 32 bits? Vale lembrar que o processador, desde o primeiro Pentium, realiza leituras e escritas usando um barramento de 64 bits de tamanho! Você até poderia pensar em forçar a barra e alinhar os tipos float de 8 em 8 bytes (64 bits boundary) assim:

typedef float __attribute__((aligned(8))) Float;

Basta trocar os tipos float por Float no código inicial. Mas, você observará que isso não mudará nada. A performance das adições em float permanecerá a mesma, corroborando a explicação sobre a conversão de tipos, pelo processador.

Outra fonte de confusão, pelo menos para mim, é a documentação do OpenGL que afirma:

We require simply that numbers’ floating-point parts contain enough bits and that their exponent fields are large enough so that individual results of floatingpoint operations are accurate to about 1 part in 105. The maximum representable magnitude of a floating-point number used to represent positional, normal, or texture coordinates must be at least 232. [p.7-8, OpenGL 4.1 Specification (Core Profile)]

Eu assumi que OpenGL fosse otimizado para atender esses requisitos e, por isso, o tipo float seria mais performático. Digo que sou uma besta quadrada porque não li a primeira frase do último parágrafo da página 7 do manual:

We do not specify how floating-point numbers are to be represented, or the details of how operations on them are performed. (o negrito é meu)

Estou batendo a cabeça na parede até agora, acreditem…

Num próximo artigo falo da comparação de performance entre SSE (que não permite o uso de doubles) e SSE2. Tenho a crença de que a discrepância mostrada ai em cima não vale para SSE, veremos…

Funções virtuais, C/C++ e outras linguagens

Aproveitando o artigo do MaRZ, abaixo, quero dizer que existe um “problema” (que é uma “feature”, na realidade!), em C++, com relação à herança e polimorfismo. Se você fizer isso:

#include <iostream>
class X
{
  public:
    void f(void) { std::cout << "X::f()" << std::endl; }
};

class Y : public X
{
  public:
    void f(void) { std::cout << "Y::f()" << std::endl; }
};

int main(void)
{
  X *p = new Y;
  p->f();
  delete p;
  return 0;
}

Você poderia esperar que a string “Y::f()” fosse impressa já que, por polimorfismo, um objeto da classe Y está sendo apontado pelo ponteiro do tipo da classe X, mas verá que aparecerá “X::f()” na tela. Isso acontece justamente porque o tipo do ponteiro p é a classe X, não a classe Y. Para resolver essa situação existe a palavra-chave virtual.

Colocando virtual antes da declaração da função f(), na classe X, dizemos ao compilador que esta e todas as funções de classes derivadas que tenham a mesma “assinatura”, serão virtuais. Isso significa que associada a toda classe que possui funções virtuais existe uma tabela que contém ponteiros para as funções declaradas como virtuais. O ponteiro para essa tabela faz parte do objeto instanciado. Assim, qualquer chamada a uma função declarada como virtual é feita de forma indireta. Se a função f() da classe X (e, por consequência a da classe Y também) for virtual, então o código que o compilador gerará para a função main(), no código acima, será mais ou menos assim:

_main:
  mov eax,sizeof Y
  call _new          /* Aloca espaço para o objeto */
  mov [p],eax

  call [eax+Y::ctor] /* Chama o construtor de Y */

  mov eax,[p]
  mov ebx,[eax]	    /* Pega o ponteiro da tabela VTBL */
  mov edx,[ebx]     /* Pega o ponteiro para a função f(), da VTBL */
  push eax          /* Empilha o ponteiro 'this' */
  call [edx]        /* Chama Y::f() */
  add esp,4         /* Joga 'this' fora */

  mov eax,[p]
  call _delete     /* Delete chamará o destrutor de Y */

  xor eax,eax
  ret

A chamada, num equivalente simplório, em C, seria:

  p->pVtbl->f();

Onde pVtbl é o ponteiro “escondido” para a tabela virtual.

No código em assembly, acima, viram como a manipulação de 3 ponteiros é necessária para lidar com a chamada? O primeiro ponteiro é o do próprio objeto (p, no nosso caso), dai pegamos o ponteiro da tabela virtual (que é a primeira coisa na estrutura do objeto — mas isso pode ser dependente de implementação!), depois pegamos o ponteiro da função f(), na tabela virtual e usamos esse ponteiro para fazer a chamada.

Isso é bem mais complicado do que um código equivalente em C, usando estruturas. Por isso (e outras “artimanhas”) o código em C++ é menos performático do que um código equivalente em C. Eu sinceramente prefiro abrir mão do uso de classes e ganhar em performance…

Se você é fã de outras linguagens como Java e C#, por exemplo, poderá observar que elas implementam um comportamento contrário ao de C++. Nelas as funções são virtuais por default. Ou seja, essas indireções de 3 níveis (no caso de Java e C# são 4 níveis. Explico daqui a pouco!) são a normalidade… Se você quiser “sobrescrever” funções deverá usar palavras-chave como “override”. Ao contrário de Java e C#, C++ é um pouco melhor (na minha opinião) porque permite que você escolha usar indireção como um caso especial.

Agora, para melhorar o seu conceito sobre C/C++ ainda mais, vamos à explicação sobre as 4 indireções do Java e do C#: Essas linguagens não fazem uso do conceito de ponteiros. Ponteiros não existem em Java. Existem em C#, mas o uso é limitado (e não recomendado). A idéia é que objetos são criados no heap e seu tempo de vida é controlado por uma thread de baixa prioridade, executando um sub-sistema conhecido como Garbage Collector. Quando criamos uma instância de um objeto fazemos algo assim:

X p = new X;

Note que p não é um ponteiro, é uma “referência”. Uma referência, nessas linguagens, é um ponteiro para um ponteiro. O compilador Java ou C# aloca um pedaço do heap que contém os endereços das estruturas alocadas em outro pedaço do heap controlado pelo Garbage Collector. Em Java esse pedaço “fixo” é conhecido como heap “permanente” (com o tamanho controlado pela opção -XX:PermSize).

Os objetos alocados no heap “normal” (não permanente) são movidos de tempos em tempos para outros lugares dentro do mesmo heap para evitar um fenômeno conhecido como fragmentação de memória. Se o Garbage Collector livra-se de objetos de tempos em tempos, é de se esperar que apareçam buracos no heap. Para aproveitar esses buracos, o GC move blocos de memória para o início do heap. Isso evita a fragmentação, mas também degrada a performance da aplicação já que a thread do GC tem que travar todas as threads da aplicação para poder mover os blocos de memória e reassinalar os novos endereços no heap permanente… Em java esse procedimento do GC chama-se stop-the-world.

Assim, os endereços dos objetos são constantemente alterados no heap “permanente” porque os objetos são constantemente movidos pelo GC. O ponteiro para o heap permanente  (usado como “referência” para o heap “normal” – entende agora o porque no nome?) não é alterado. No exemplo acima, a variável p é um ponteiro para o ponteiro no heap “permanente”.

Se lembrarmos que todas as funções de uma classe são, por default, virtuais — nessas linguagens — uma simples chamada lidará com 4 níveis de indireção: O primeiro é o ponteiro que aponta para o heap fixo (a referência). O segundo é o ponteiro do heap fixo que aponta para o objeto no heap “variável”, o terceiro é o ponteiro para a tabela virtual, associada ao objeto, e o quarto é o endereço da função obtido da tabela virtual.

Por isso não há comparação de performance entre C/C++ e C# e Java… Essas duas últimas (e outras linguagens interpretadas que usam Garbage Collectors) fazem tanto trabalho “preparatório” para realizar chamadas que a performance relativa pode ser mais que 200% pior do que o equivalente em C.

C rocks!

Uma prova de performance

Sempre está sendo dito e defendido que perfomance é fundamental. Esta performance depende de outros fatores além da otimização do código. Um deles é a escolha da tecnologia e da linguagem de programação.

Estou analisando o código do Cos – link que indiquei no último post, e ao compilar o primeiro dos programas fiquei espantado com a diferença de performance entre C e C++.

O C neste caso parece ser cerca de 5x (no meu teste) mais rápido do que C++.

/* Em C */
AB    : dynamic_cast<A*>(b) = 3218961676, iter = 62500000/sec
DCABBA: dynamic_cast<A*>(b) = 3218961600, iter = 21739130/sec
DCABBA: dynamic_cast<C*>(c) = 3218961556, iter = 21739130/sec

/* Em C++ */
AB    : dynamic_cast<A*>(b) = 3214284680, iter = 12048192/sec
DCABBA: dynamic_cast<A*>(b) = 3214284604, iter = 6622516/sec
DCABBA: dynamic_cast<C*>(b) = 3214284560, iter = 3267973/sec

O link dos fontes pode ser baixado daqui e faz uma demonstração de implementação de padrões orientados à objetos com o C.

Como dito pelo autor:

C++ Object Model is a long paper (see object_model.html) started years ago which I unfortunately never finished (about 25% achieved), but is enough to understand the overall. It comes with a complete example in C (see cmd_c.sh) and C++ (see cmd_cpp.sh) which describes one way to implement the C++ object model (i.e. the g++’s object model). It is addressed to advanced (and motivated ;-) C and C++ programmers who have some interest in the C++ object model, so I put it here for curiosity. It may give you some hints about the implementation complexity corresponding to the management of dynamic types within constructors and destructors (i.e. intermediate vtbl) and covariant and contravariant types in the presence of multiple and virtual inheritance (i.e. thunks). I found interesting that my naive implementation of dynamic_cast is about x3 faster than the dynamic_cast provided by g++ ;-)

Nota adicional: o compilador utilizado é o gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5) e o programa foi rodado num Core 2/2.2 GHz/3Gb Ram