Rolling back: O medidor de ciclos que uso atualmente…

Quem estiver procurando neste blog vai encontrar diversas atualizações no “medidor de ciclos de clock” que uso para medir a performance de rotinas, usando o timestamp mantido pelo processador desde o Pentium… O fato é que ele não é preciso (e mostro porquê disso em alguns artigos por aqui), mas é melhor que nada…

Eis a versão mais atual, onde obtenho melhores resultados:

#ifndef __CYCLE_COUNTING_INCLUDED__
#define __CYCLE_COUNTING_INCLUDED__

/* ==========================================
    Quick & Dirty cycle counting...

    begin_tsc() e end_tsc()

    são usadas para contar a quantidade de ciclos
    de máquina gastos num bloco de código.

    Exemplo de uso:

      uint64_t t;

      BEGIN_TSC;      
      f();
      END_TSC(t);

    É conveniente compilar o código sob teste com a
    opção -O0, já que o compilador poderá 'sumir' com
    o código, por causa da otimização. Melhor ainda
    seria compilar a função f() num módulo separado com
    a opção -O2 para obter o código otimizado.

    As macros, em si, não são "otimizáveis", por assim dizer.
   ========================================== */

#include <stdint.h>

// Mantém o timestamp inicial.
uint64_t __local_tsc;

#ifdef __x86_64__
#define REGS1 "rbx","rcx"
#define REGS2 "rcx"
#else
#ifdef __i386__
#define REGS1 "ebx","ecx"
#define REGS2 "ecx"
#else
#error cycle counting will work only on x86-64 or i386 platforms!
#endif
#endif

// Macro: Inicia a medição.
// Uso CPUID para serializar o processador aqui.
#define BEGIN_TSC do { \
  uint32_t a, d; \
\
  __asm__ __volatile__ ( \
    "xorl %%eax,%%eax\n" \
    "cpuid\n" \
    "rdtsc\n" \
    : "=a" (a), "=d" (d) :: REGS1 \
  ); \
\
  __local_tsc = ((uint64_t)d << 32) | a; \
} while (0)

// Macro: Finaliza a medição.
// NOTA: A rotina anterior usava armazenamento temporário
//       para guardar a contagem vinda de rdtscp. Ainda,
//       CPUID era usado para serialização (que parece ser inóquo!).
//       Obtive resultados melhores retirando a serialização e
//       devolvendo os constraints para EAX e EDX, salvando apenas ECX.
// PS:   rdtscp também serializa, deixando o CPUID supérfluo!
#define END_TSC(c) do { \
  uint32_t a, d; \
\
  __asm__ __volatile__ ( \
    "rdtscp\n" \
    : "=a" (a), "=d" (d) :: REGS2 \
  ); \
\
  (c) = (((uint64_t)d << 32) | a) - __local_tsc; \
} while (0)

#endif

Façam bom proveito!

Anúncios

Ponteiro para um array…

Eu evito algumas construções mais “esotéricas” da linguagem C, não porque não saiba o que elas signifiquem, mas em virtude da legibilidade… Recentemente me perguntaram o que significa a declaração:

int (*p)[4];

Bem… isso ai é um ponteiro para um array de 4 inteiros. O que é bem diferente de:

int *p[4];

Que é um array de 4 ponteiros para o tipo int.

O detalhe é que deixei meio de lado a utilidade da primeira declaração. Considere isso:

int a[4][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 } };

void showarray(int a[][4])
{
  int i, j;

  for (i = 0; i < 4; i++)
  {
    for (j = 0; j < 4; j++)
      printf("%d ", a[i][j];
    putchar('\n');
  }
  putchar('\n');
}

A rotina showarray, como declarada acima, é um jeito de mostrar todos os itens de um array. Podemos chamá-la com showarray(a); e tudo funcionará perfeitamente bem… Mas, e se quiséssemos usar ponteiros ao invés de 2 índices (i e j)?

Note que, se você tem um array simples, pode usar um ponteiro para apontar para o primeiro item e incrementar o endereço contido no ponteiro para obter o próximo item, como em:

int a[] = { 1, 2, 3, 4, 5, 0 };

void showarray(int *p)
{
  for (; *p; p++)
    printf("%d ", *p);
  putchar('\n');
}

Aqui, o compilador criará código para somar 4 ao conteúdo de p a cada vez que ele for incrementado. O valor 4 é adicionado porque sizeof(int)==4. A pergunta original é: “Dá pra fazer algo semelhante com arrays bidimensionais?”. A resposta, obviamente, é: SIM!

Ao declarar um ponteiro p como int (*p)[4];, toda vez que você incrementar o ponteiro, a ele será adicionado o valor 16 (4*sizeof(int)) e podemos escrever a rotina showarray original, assim:

void showarray(int (*p)[4])
{
  int i;

  // Não é bem a rotina original, aqui considero que
  // se o primeiro item da "linha" for zero, devemos
  // encerrar o loop.
  //
  // p++ fará o ponteiro p apontar para o início da
  // próxima linha...
  for (; (*p)[0]; p++)
  {
    for (i = 0; i < 4; i++)
      printf("%d ", (*p)[i]);
    putchar('\n');
  }
  putchar('\n');
}

O array original, é claro, deverá ser definido assim, para a rotina funcionar:

int a[][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 },
    {} };  // note: 4 zeros aqui!

Estatisticamente insignificante…

Well… só para escrever um cadinho a respeito de alguma coisa, recentemente alguém em um grupo de Facebook que participo teve a brilhante ideia de “elaborar um algoritmo” para ganhar na MEGA SENA. Como se ninguém tivesse pensado (e ainda pensando) nisso antes, né?

Muito bem… saibam que todos os jogos já sorteados estão disponíveis para download no site da Caixa Econômica Federal neste, link, em formato ZIP que contém um arquivo HTML, mal formatado, por sinal… Baixado os resultados por ordem de sorteio (aqui) e depois de alguma filtragem, podemos obter algo assim:

04 05 30 33 41 52
09 37 39 41 43 49
10 11 29 30 36 47
01 05 06 27 42 59
01 02 06 16 19 46
07 13 19 22 40 47
...

Essa é a lista de 1960 jogos já sorteados até o último jogo antes que eu tivesse criado esse texto. E, agora, podemos brincar, não é? Infelizmente, não…

O problema é que a quantidade de sorteios feita é insignificante em relação à quantidade de jogos possíveis. Só para dar uma ideia, a quantidade de combinações possíveis é de C(n,r)=\frac{n!}{r!(n-r)!}\Rightarrow\frac{60!}{6!(60-6)!}\approx50063860. Sabendo que temos apenas 1960 jogos disponíveis para fazer alguma avaliação, isso significa que temos apenas 0,003915% de todas as amostras possíveis! Tentar divisar algum padrão nessa base é como dizer que só existem cavalos marrons porque você nunca viu um com pelagem de outra cor…

Com base nas amostras que temos, podemos chegar as mais variadas conclusões falsas. Por exemplo, se traçarmos um gráfico com o número de ocorrências de cada um dos valores, em todos os 1960 jogos, teremos:

Distribuição dos valores em todos os sorteios

Olhando para isso podemos concluir (errado!) que deveríamos ignorar os valores 26 e 55, já que eles aconteceram bem menos do que os demais. Ou, quem sabe, deveríamos prestar mais atenção justamente neles, já que eles tendem a acontecer mais, para manter o “sistema” equilibrado (errado! errado!).

Ainda, existem 6 valores que aconteceram mais que os demais (5, 10, 23, 33, 51 e 53), então, essa deve ser uma sequência mais “apostável” que as demais, não é? E os números 5 e 53 aconteceram 225 vezes nesses 1960 jogos (11% de todos os jogos, pena que não ao mesmo tempo! — de fato, ao mesmo tempo, eles aconteceram apenas 17 vezes!).

De novo, esses dados são estatisticamente insignificantes para que qualquer tipo de análise, no sentido de obtenção de padrões, seja possível e uma outra demonstração disso é uma animaçãozinha que mostra a distribuição dos valores no tempo, onde cada linha contém uma dezena de valores (a linha 1 vai de 1 até 10, a linha 2, de 11 até 20… até a 6ª linha, de 51 até 60):

1/10º de segundo por sorteio

Repare como os quadrados vão ficando rosados, mais ou menos, ao mesmo tempo e mais ou menos terminam em tonalidades similares (e você, muitas vezes, nem percebe o degrau de variação nessa animação de 10 frames por segundo! Ou seja, 1 segundo = 10 sorteios). Isso significa que a distribuição é mais ou menos uniforme no decorrer do tempo, o que torna a “adivinhação” difícil!

Outra forma de ver a variação de cada valor, acima, é a simulação do gráfico inicial em timelapse (de novo, 10 frames por segundo):

Cada ponto é a contagem do valor em uso em cada sorteio

Ok… tem um pequeno bug no programinha que fiz para criar essa animação (a barra azul do lado direito), mas você pegou a ideia…

E, se você ainda acha, que dá para obter algum padrão, pense nisso: Será que o peso da tinta dos números pintados nas bolinhas sorteadas não têm alguma influência? E quanto à quantidade de plástico usado na fabricação delas? E a “qualidade” desse material? Todas as bolinhas vieram do mesmo fabricante? E aquela “cesta” giratória (se é que ainda usam isso!), de que material é feito? Ela parece ser metálica, existem soldas? Elas são uniformes? Tanto a cesta quanto as bolinhas são perfeitamente esféricas? E quanto ao atrito? E a temperatura ambiente? E o diferencial de temperatura entre a “cesta” (de metal) e as bolinhas (de plástico)? E quem está girando as cestas? Tá com fome? Tá cansado? Tá doente? etc…

Existem muitas variáveis e poucas amostras para dizer sequer se essas variáveis devem ou não serem consideradas!

MyToyOS: Cuidados com gcc e assembler entre modos de operação

No que concerne códigos “não hosted” (freestanding), se você é como eu, usa C para a maioria das funções mais complexas, deixando assembly para aquelas que seriam mais complicadas de implementar em C. Neste artigo quero mostrar alguns problema que pode enfrentar.

Em primeiro lugar, o GCC permite o desenvolvimento de funções que serão usadas no modo real, basta usar a opção -m16 na linha de comando. Nessa modalidade ele adiciona os prefixos 0x66 e 0x67 nas instruções, para que os offsets e operandos continuem sendo de 32 bits. Mas, isso pode ser problemático com saltos e retornos de funções. Tomemos como exemplo a seguinte função:

int f(int a, int b) { return a + b; }

O compilador gera algo assim, como pode ser observado via objdump:

00000000 <f>:
   0: 67 66 8b 44 24 08   mov  eax,DWORD PTR [esp+0x8]
   6: 67 66 03 44 24 04   add  eax,DWORD PTR [esp+0x4]
   c: 66 c3               ret    

Os prefixos 0x67 e 0x66 nas instruções mov e add estão ai porque, no modo real, os registradores default são as variantes de 16 bits (ax, no caso) e precisamos do prefixo 0x66 para usarmos EAX. O prefixo 0x67 está ai porque ESP está sendo usado como base no modo de endereçamento. Mas, o que diabos esse 0x66 está fazendo antes do RET?

Infelizmente o GCC continua pensando que está no modo protegido i386 e o empilhamento dos endereços de retorno continua sendo feito em 32 bits. Isso é evidente ao se olhar os offsets dos argumentos a e b da função. De acordo com o macete de usarmos uma estrutura para acesso ao stack frame, podemos escrever a rotina acima, em NASM, assim:

struc stkfrm
.retaddr  resw 1
.a        resd 1
.b        resd 1
endstruc

bits 16

global f
f:
  mov eax,[esp+stkfrm.a]
  add eax,[esp+stkfrm.b]
  ret

O NASM, por outro lado, vai gerar o código correto para o RET:

 1                           struc stkfrm
 2 00000000 <res 00000002>   .retaddr resw 1
 3 00000002 <res 00000004>   .a  resd 1
 4 00000006 <res 00000008>   .b  resd 2
 5                           endstruc
 6                           
 7                           bits 16
 8                           
 9                           f:
10 00000000 66678B442402       mov eax,[esp+stkfrm.a]
11 00000006 666703442406       add eax,[esp+stkfrm.b]
12 0000000C C3                 ret

Em primeiro lugar, o endereço de retorno empilhado, em modo real, é de 16 bits, para uma chamada near e isso é expresso pela reserva de uma WORD no topo da pilha. Assim, os acessos a pilha serão [esp+2] e [esp+6], respectivamente para a e b. E nada de 0x66 antes de RET!

Para testar essa chamada, eis um programinha simples, em modo real, que implementa um simples setor de boot:

bits 16

global _start
_start:
  jmp   0x7c0:_main
_main:
  cld
  mov   ax,cs
  mov   ds,ax
  mov   es,ax

  ; apaga a tela:
  mov   ax,3
  int   0x10

  ; x = f(2,1);
  push  dword 1
  push  dword 2
  call  f

  ; printf("2 + 1 = %#08x\n", x);
  lea   di,[value];
  call  dword2hex
  lea   si,[msg]
  call  puts

  ;; while (1);
.L1:
  hlt
  jmp   .L1

msg:
  db    '2 + 1 = 0x'
value:
  db    '00000000 (?).',13,10,0

hextbl:
  db    '0123456789abcdef'

; Como implementada pelo GCC
f:
  mov   eax,[esp+2]
  add   eax,[esp+6]
;  mov   eax,[esp+4]    ;; GCC implementa assim...
;  add   eax,[esp+8]
;  db    0x66
  ret

; ES:DI = ptr onde armazenar os chars
; AL  = byte
; ---
; Destrói AX,BX e CX.
; Avança DI
byte2hex:
  mov   bx,ax
  shr   bx,4
  and   bx,0x0f
  mov   cl,[hextbl+bx]
  mov   bx,ax
  and   bx,0x0f
  mov   ch,[hextbl+bx]
  mov   ax,cx
  stosw
  ret

; DS:DI = ptr onde armazenar os chars.
; EAX = dword
; ---
; Destrói EAX,BX,CX e EDX.
; Avança DI
%macro cvt_upper_byte 0
  ror eax,8
  mov edx,eax
  and eax,0xff
  call byte2hex
  mov eax,edx
%endmacro

dword2hex:
  cvt_upper_byte
  cvt_upper_byte
  cvt_upper_byte
  cvt_upper_byte
  ret

puts:
  lodsb
  test  al,al
  jz    .puts_exit
  mov   ah,0x0e
  int   0x10
  jmp   puts
.puts_exit:
  ret

  times 510-($-$$) db 0
  dw    0xaa55

Compile e execute com:

$ nasm -f bin boot.asm -o boot.bin
$ qemu-system-i386 -drive file=boot.bin,index=0,media=disk,format=raw

O resultado será este:

Mude a função f para que ela fique exatamente como codificada pelo GCC e verá que isso ai não funcionará mais. A prefixação 0x66 para RET faz com que a instrução tente recuperar EIP da pilha, só que apenas IP foi empilhado… Ao mesmo tempo, GCC supõe que o ambiente ainda seja de 32 bits e, por isso, ESP+4 e ESP+8, ao invés de ESP+2 e ESP+6, são usados para obter os dados da pilha…

Outro detalhe são as chamadas. Vejamos:

int g(int a, int b) { return f(a,b)+7; }

Isso criará um código assim:

00000010 <g>:
  10: 67 66 ff 74 24 08   push  DWORD PTR [esp+0x8]
  16: 67 66 ff 74 24 08   push  DWORD PTR [esp+0x8]
  1c: 66 e8 fc ff ff ff   call  1e <g+0xe>
  22: 66 5a               pop   edx
  24: 66 83 c0 07         add   eax,0x7
  28: 66 59               pop   ecx
  2a: 66 c3               ret

Note que a instrução CALL usa um deslocamento de 32 bits ao invés de 16. Isso não é problemático, graças ao prefixo 0x66 e ao fato de que todo salto near usa endereçamento relativo do EIP (ou IP). O único problema aqui é mesmo o RET prefixado.

Rotina em ASM chamando função em C e vice-versa

Para corrigir esse problema podemos, num código para o modo real escrito em assembly, simplesmente empilhar uma WORD 0 antes de chamar a função em C:

; Chamando função f(), em asm:
  push word 0
  call f
  ...

Isso garante que, na pilha, teremos IP estendido com zeros, formando o offset de 16 bits dentro do segmento de código. Podemos até mesmo criar uma macro:

%macro pm_call 1
  push word 0
  call %1
%endmacro

Do outro lado, a chamada de uma função feita para o modo real à partir do código em C gerado pelo GCC, espera que uma DWORD seja desempilhada no RET, já que CALL, prefixado com 0x66, ira colocar EIP na pilha. Podemos copiar a WORD apontado por ESP para ESP+2 e adicionar 2 a ESP, na rotina em ASM… Lembre-se que EIP é a última coisa empilhada antes do salto:

%macro pm_ret 0
  push ax
  mov  ax,[esp+2]
  mov  [esp+4],ax
  pop  ax
  add  esp,2   ; Descarta a primeira WORD do topo da pilha.
  ret
%endmacro

Ok, é gambiarra, mas, infelizmente o GCC não gera código muito bom em 16 bits!

Uma outra forma de explicar ponto flutuante…

Já expliquei de várias formas aqui, ai vai mais uma: “Ponto flutuante é uma maneira de lidar com frações racionais”. Para entender isso, voltemos à equação que descreve um float:

\displaystyle v=(-1)^S+\left(1+\frac{F}{2^{23}} \right )\cdot2^e

Onde os valores S, F e e são os “pedaços” de um float e são inteiros e positivos:

Estrutura de um float

Note que S tem apenas 1 bit de tamanho (S de “sinal”), F (de “fração”) tem 23 bits e, portando, suporta valores entre 0 e 2^{23}-1. Assim, \frac{F}{2^{23}} sempre será menor que 1.0! Já e é expresso pela equação e=E-127. O E, maiúsculo, é o valor que consta na estrutura…

Sendo assim, 1+\frac{F}{2^{23}} sempre será uma fração racional. Isso é evidente se você pensar que, numa estrutura com quantidade limitada de bits, não dá para armazenar um valor como π (3.1415926… e não acaba nunca).

O importante aqui é lembrar que a fração racional deve ser racional em binário. O valor 0.1, em decimal, não é racional em binário. Aliás, qualquer valor que seja diferente de 0.0 que não termine, na parte fracionária, em 5, não é um valor racional em binário. Isso é fácil perceber quando você calcula cada “casa” binária “depois da vírgula”:

2^{-1}=0.5\quad2^{-2}=0.25\quad2^{-3}=0.125\quad\cdots

E se somarmos cada um desses bits “fracionários”, verá que o final sempre terá o algarismo 5, em decimal.

Regra geral: Se a parte fracionária de um valor decimal for diferente de zero e não terminar em 5, o valor em ponto flutuante não é exato! Exemplo: 454.76 não é exato com qualquer tipo de ponto flutuante (float, double, long double) porque a parte fracionária termina em 6.

TARDIS!

Time and Relative Dimensions In Space“! Yep! Tornei-me um “Whovian”! Mas, não vou falar da série britânica aqui, e sim dos CACHES e dois conceitos fundamentais: Localidade Temporal e Localidade Espacial.

Você pode achar estranho que o “Continuum” (espaço-tempo), conceito aplicável à Física e às séries de Ficção Científica, seja aplicável também à programação. Seu processador também usa conceito semelhante no que se refere aos CACHES. Lembre-se que CACHE é uma memória intermediária entre aquela endereçável nos seus pentes de memória (e na ROM) e a acessada, internamente, pelo processador, através de uma instrução. No meio do caminho temos algumas memórias RAM, rápidas, que são divididas em “linhas”, onde cada linha tem, hoje em dia, 64 bytes de tamanho.

Isso significa que o processador carregará, da memória principal, 64 bytes para dentro do CACHE e passará a lidar com esses 64 bytes, ao invés de, toda vez que quiser ler/escrever dados na memória, torrar ciclos de clock “esperando” que o circuito de sua RAM (por exemplo) esteja pronto para receber/enviar dados… Acontece que cada um dos CACHES disponíveis no interior do processador (e os disponíveis fora dele, como o cache L3, hoje em dia) tem capacidade limitada… Estamos interessados no cache L1 (sempre!), quando falamos de performance e este tem, no máximo 64 KiB de tamanho…

Sendo o cache L1 é o mais curto dos caches, tendo apenas 1024 linhas, precisamos nos certificar que todas as linhas disponíveis estejam sendo usadas pelo maior tempo possível. Isso significa que, se todas as linhas estiverem sendo usadas, para acessar memória que não consta do cache, uma linha terá que ser escrita na memória física, externa, e outro bloco de 64 bytes terá que ser lido e colocado no lugar. Isso também significa que os seus dados têm localidade temporal, ou seja, as linhas dos caches podem não estar presente nele por muito tempo.

O macete para obter alta performance é manter as linhas mais acessadas no cache o maior tempo possível, evitando poluí-lo com trocas ou “despejos” de linhas desnecessários… Nem sempre isso é possível, já que o kernel também usa o cache e não temos nenhum controle sobre o que o kernel faz, do ponto de vista de nossos códigos no userspace.

Existe também o conceito de localidade espacial. Se uma linha tem 64 bytes de tamanho, então, se mantivermos os dados mais acessíveis o mais próximos possível, poderíamos garantir que eles estejam na mesma linha, ou “no mesmo espaço”. Isso também vale para as instruções sendo executadas pelo processador… Se mantivermos um loop dentro de uma única linha, não corremos o risco de outra linha ser usada para conter as instruções do loop e ser “despejada”, precisar ser recarregada em cada iteração do loop, desperdiçando ciclos de clock! Por esse motivo, quanto menos instruções usarmos, melhor. A mesma coisa vale para o tamanho das instruções…

O mesmo raciocínio pode ser feito com dados. Se uma estrutura tiver 64 bytes ou menos de tamanho, podemos garantir que ela esteja dentro de uma única linha de cache desde que não ultrapasse a fronteira de uma linha. Como podemos fazer isso? Já que toda linha tem 64 bytes de tamanho, o endereço linear que marca o início de uma linha sempre terá os 6 bits inferiores zerados e a linha terminará com o endereço contendo os 6 bits inferiores setados… Note que um dado em um endereço linear não necessariamente está localizado no cache. Ele só estará lá quando for acessado (mostro outro jeito mais adiante).

Eis um exemplo de um array de 64 bytes alinhado com o início de uma linha de cache:

  section .data

  global array
  align 64  ; Alinha com o início de uma
            ; linha de cache.
array:
  times 64 db 0

Aqui, é garantido que o array inteiro, de 64 bytes, estará alocado em uma única linha do cache L1 quando for acessado. No entanto, isso não é lá muito prático… Em primeiro lugar, se ficarmos alinhando tudo quanto é estruturas no início de uma linha termos muitos “buracos” em nosso segmento de dados. De fato, poderemos até mesmo ter mais “buracos” do que dados efetivos. Garantiremos que uma estrutura estrutura individual qualquer esteja toda no menor número de linhas possível, mas nosso segmento de dados poderá ficar enorme!

Em segundo lugar, o principio da localidade espacial nos indica que devemos agrupar a maior quantidade de dados possível dentro de uma única linha… Ou seja, evitarmos que seus dados cruzem a fronteira de uma linha e passem a pertencer a duas linhas… Estatisticamente, se alinharmos nossos dados de 16 em 16 bytes (\frac{1}{4} de linha), podemos conseguir esse efeito com a maioria dos dados. No entanto, pode ser prudente o alinhamento de 8 ou 4 bytes, de acordo com o tipo de dado. No exemplo anterior, o array tem 64 bytes, então faz todo sentido alinhá-lo com o início de uma linha do cache se seu acesso for crítico para performance…

Mas, e quanto ao princípio de localidade temporal? Bem… para não poluir o cache, evitando “despejos”, podemos, às vezes, usar instruções especiais que lêem/escrevem direto na memória. MOVNTA, por exemplo, é uma instrução SSE que faz o MOV “Não temporal”, ou seja, não passa pelo cache… Às vezes é útil, mas não é prudente abusar… Acessar memória diretamente implica em esperar pela leitura/escrita e isso pode ser lento! Na prática queremos usar MOVNTA apenas para evitar despejos desnecessários de pequenos blocos de dados.

Para retardar a temporalidade de uma linha, podemos fazer um prefetch, ou seja, pedir ao processador que carregue uma linha antecipadamente, com os seus 64 bytes, se eles já não estiverem no cache. Para isso existe a instrução PREFETCH, que toma um endereço como argumento. Qualquer endereço no interior da linha fará com que a linha inteira seja carregada para o cache… Mas, note… Existem 3 caches diferentes no seu processador: O L1, L2 e L3… Existem 3 instruções PREFETCH também: PREFETCHT0, PREFETCHT1, PREFETCHT2 que, em teoria, pede para o processador transfira uma linha de um cache para outro ou da memória para um dos caches… Existe também PREFETCHW, que faz a mesma coisa que o PREFETCHT0, mas prepara a linha para a escrita (apenas as linhas que foram “modificadas” são reescritas num cache de nível superior ou na memória do sistema – PREFETCHW, suponho, marca a linha como “suja”, forçando a escrita quando ela for “despejada”).

As instruções de prefetching são uma “dica” para o processador. Usar essas instruções não garante que as linhas do cache sejam preenchidas. Mas, pelo menos, informa a intenção e pode melhorar a performance um bocado… Quando você precisar forçar um prefetching, recomendo o uso de PREFETCHT0, que tentará carregar todos os caches com a linha correspondente…

Essas instruções são úteis se você tem uma grande quantidade de dados e quer organizar quais porções deverão estar presentes no cache. Por exemplo, suponha que você tenha duas matrizes 4×4, onde cada item seja do tipo float. Temos 16 floats e, portanto 64 bytes que, é claro, cabe exatamente numa linha!… Você pode querer colocar cada uma das matrizes no cache L1d antes de começar a manipulá-los… Suponha que queira multiplicar uma matriz por outra e obter uma terceira… Suponha também que as três matrizes estejam alinhadas com o início de uma linha de cache (endereço com os 6 bits inferiores zerados)… Antes de multiplicá-las você poderia fazer:

; Estou assumindo que mat1, mat2 e
; mat_result estejam alinhados com o início 
; de uma linha.
  ...
  ; faz o prefetching...
  prefetcht0 [mat1]
  prefetcht0 [mat2]
  prefetcht0 [mat_result]

  ; chama a função matrix_mult.
  lea rdi,[mat_result]
  lea rsi,[mat1]
  lea rdx,[mat2]
  call matrix_mult
  ...

Com os 3 primeiros prefetches você dá a dica ao processador de que precisa dos 3 blocos de dados nos caches. Especialmente no cache L1! Claro, se matrix_mult “consumir muita memória”, esses prefetches serão “perdidos” (temporalidade!), mas aqui estamos usando apenas 192 bytes, ou 3 linhas do cache L1, que tem 1024…

Aí está! Espaço e Tempo são importantes quando lidamos com caches.

Quem tem medo de otimizações?

Já me disseram que eu não deveria usar as opções -O3 ou -Ofast em meus projetos. Bem… elas tendem a oferecer as melhores otimizações possíveis e, na tabela abaixo, mostro a diferença entre elas e a compilação sem opções de otimização (que chamei de “generic”) e a opção de “nenhuma” otimização (-O0). A opção -Os, em teoria, gera código pequeno (‘s’ de smaller), mas essencialmente, ele é a mesma coisa que -O2, exceto pela possível otimização de chamadas à strlen (que, na minha experiência, quase nunca o compilador consegue otimizar):

generic -Os -O0 -O1 -O2 -O3 -Ofast
-faggressive-loop-optimizations
-fasynchronous-unwind-tables
-fauto-inc-dec
-fchkp-check-incomplete-type
-fchkp-check-read
-fchkp-check-write
-fchkp-instrument-calls
-fchkp-narrow-bounds
-fchkp-optimize
-fchkp-store-bounds
-fchkp-use-static-bounds
-fchkp-use-static-const-bounds
-fchkp-use-wrappers
-fcommon
-fearly-inlining
-ffunction-cse
-fgcse-lm
-fira-hoist-pressure
-fira-share-save-slots
-fira-share-spill-slots
-fivopts
-fkeep-static-consts
-fleading-underscore
-flifetime-dse
-flto-odr-type-merging
-fpeephole
-fprefetch-loop-arrays
-freg-struct-return
-fsched-critical-path-heuristic
-fsched-dep-count-heuristic
-fsched-group-heuristic
-fsched-interblock
-fsched-last-insn-heuristic
-fsched-rank-heuristic
-fsched-spec
-fsched-spec-insn-heuristic
-fsched-stalled-insns-dep
-fschedule-fusion
-fsemantic-interposition
-fshow-column
-fsplit-ivs-in-unroller
-fstack-protector-strong
-fstdarg-opt
-fstrict-volatile-bitfields
-fsync-libcalls
-ftree-loop-if-convert
-ftree-loop-im
-ftree-loop-ivcanon
-ftree-loop-optimize
-ftree-parallelize-loops
-ftree-phiprop
-ftree-reassoc
-ftree-scev-cprop
-funit-at-a-time
-funwind-tables
-malign-stringops
-mavx256-split-unaligned-load
-mavx256-split-unaligned-store
-mfancy-math-387
-mfp-ret-in-387
-mfxsr
-mglibc
-mno-sse4
-mpush-args
-mred-zone
-msse
-msse2
-mtls-direct-seg-refs
-mvzeroupper
-fsigned-zeroes
-fdelete-null-pointer-checks
-fident
-finline-atomics
-ftrapping-math
-fbranch-count-reg
-fcombine-stack-adjustments
-fcompare_elim
-fcprop-registers
-fdefer-pop
-fforward-propagate
-fguess-branch-probability
-fhoist-adjacent-loads
-fif-conversion
-fif-conversion2
-finline
-finline-functions-called-once
-fipa-profile
-fipa-pure-const
-fipa-reference
-fmerge-constants
-fmove-loop-invariants
-fomit-frame-pointer
-fshrink-wrap
-fsplit-wide-types
-fssa-phiopt
-ftoplevel-reorder
-ftree-bit-ccp
-ftree-ccp
-ftree-ch
-ftree-coalesce-vars
-ftree-copy-prop
-ftree-copyrename
-ftree-cselim
-ftree-dce
-ftree-dominator-opts
-ftree-dse
-ftree-forwprop
-ftree-fre
-ftree-pta
-ftree-sink
-ftree-slsr
-ftree-sra
-ftree-ter
-falign-labels
-fcaller-saves
-fcrossjumping
-fcse-follow-jumps
-fdevirtualize
-fdevirtualize-speculatively
-fexpensive-optimizations
-fgcse
-findirect-inlining
-finline-small-functions
-fipa-cp
-fipa-cp-alignment
-fipa-icf
-fipa-icf-functions
-fipa-icf-variables
-fipa-ra
-fipa-sra
-fisolate-erroneous-paths-dereference
-flra-remat
-foptimize-sibling-calls
-fpartial-inlining
-fpeephole2
-free
-freorder-blocks
-freorder-blocks-and-partition
-freorder-functions
-frerun-cse-after-loop
-fschedule-insns2
-fstrict-aliasing
-fstrict-overflow
-fthread-jumps
-ftree-builtin-call-dce
-ftree-switch-conversion
-ftree-tail-merge
-ftree-vrp
-foptimize-strlen
-ftree-pre
-finline-functions
-fgcse-after-reload
-fipa-cp-clone
-fpredictive-commoning
-ftree-loop-distribute-patterns
-ftree-loop-vectorize
-ftree-partial-pre
-ftree-slp-vectorize
-funswitch-loops
-fassociative-math
-fcx-limited-range
-ffinite-math-only
-freciprocal-math
-funsafe-math-optimizations

Note que somente com as opções -O3 e -Ofast podemos ter o recurso de vetorização de um loop que, é claro, poderia ser “ligada” usando a chave -ftree-loop-vectorize, mas, de qualquer maneira, Essas duas opções oferencem muitas vantagens, tanto do ponto de vista da performance e do tamanho do código gerado pelo compilador.

Se você usa apenas a opção -O2, note que algumas coisas não são oferecidas, como o recurso de organizar funções de pouco uso como inline, algumas otimizações inter process também são são realizadas e além da vetorização, algumas eliminações de sub expressões globais e da previsão de loops (para auxiliar no branching predition) podem ficar seriamente comprometidas.

Tá certo que a opção -Ofast só é realmente útil em dois pontos: Quando não precisamos da conformidade estrita com IEEE 754 e quanto otimizações ainda mais agressivas (porém “unsafe”) sejam interessantes. Eu evitaria o -Ofast a não ser que você saiba o que faz. Mas adotaria -O3 como padrão.

UPDATE: Eu já tinha observado isso antes mas fiz questão de fazer alguns testes… Ao que parece, -O2 realmente gera código mais rápido que -O3 ou -Ofast!