De novo: Por que programar diretamente em assembly geralmente não é uma boa ideia…

Sim… de novo estou advogando contra mim mesmo. Eu uso assembly sempre que posso e quando isso não implica em códigos dependentes de arquitetura. Mas, para o novato, que está aprendendo assembly agora, programar nessa linguagem quase sempre é sinônimo de desastre. Eis o porquê:

Convenções de chamadas existem por um bom motivo

Quando estamos aprendendo é sugerido que manter o contexto da função chamadora é importante. Por contexto quero dizer os registradores que estavam sendo usados pela função que chamou a sua… Isso parece razoável, mas não é assim que compiladores de nível mais alto fazem… Um exemplo simples é a implementação padrão da função strcpy, em C:

char *strcpy(char *d, char *s)
{
  char *p = d;
  while (*p++ = *s++);
  return d;
}

Note que a função não verifica o conteúdo dos ponteiros (eles PODEM ser NULL e causarem segmentation fault) e o código gerado também não se preocupa em preservar o conteúdo dos registradores. No x86-64 isso é mais evidente:

strcpy:
  mov   rax,rdi
  mov   rdx,rdi
.loop:
  add   rsi,1
  movzx ecx,byte [rsi-1]
  add   rdx,1
  test  cl,cl
  mov   [rdx-1],cl
  jne   .loop
  ret

Aqui a função alterou, sem escrúpulos, o conteúdo de RAX, RCX, RDX, RSI e RDI. Isso acontece porque, no modo x86-64, o GCC só se preocupa em manter os registradores RBX, RBP, RSP e de R12 até R15. Já no modo i386, os mantidos devem ser EBX, EBP e ESP apenas. Todos os demais podem ser modificados.

Há uma vantagem escondida nessa aproximação: Se você sabe que o compilador C vai manter, à todo custo, esses registradores inalterados entre chamadas, tanto ele quanto você pode usá-los como “variáveis temporárias” (desde que preserve os seus conteúdos vindos da função chamadora!)… Quanto aos demais, se sua função chama outra e você precisa preservar o conteúdo de EAX, por exemplo, então é obrigá-lo a salvá-lo você mesmo (na pilha, por exemplo!).

Ahhh, sim… nas convenções de chamada usadas por C, pelo menos no modo i386, EAX é usado para retornar um valor e o par EDX:EAX, se esse valor for maior que 32 bits. Se sua função não retorna valores, pode mexer com EAX e EDX à vontade e deixá-los “bagunçados”. Eles não precisam ser preservados, neste caso.

Usando a pilha para manter variáveis locais entre chamadas

O GCC tenta manter todas as variáveis locais em registradores, mas, eventualmente, precisa guardá-los para uso futuro (depois do retorno da chamada de alguma função). Geralmente ele faz algo assim:

f:
  sub esp,4
  ...
  mov [esp],eax
  call some_function
  mov eax,[esp]
  ...
  add esp,4
  ret

ESP, quando sua função é chamada, aponta para o endereço de retorno da função chamadora. Como a pilha cresce para baixo, nossa função resolveu alocar 4 bytes (no modo i386 a pilha deve estar sempre alinhada por DWORD) adicionando 4 ao ESP. Antes de retornar (RET) o conteúdo de ESP deve voltar ao valor original que estava (lembra-se que ele é um dos que têm que ser preservados?).

É claro que você poderia guardar o conteúdo dessa variável “local” dentro de algum endereço no segmento de dados ou, até mesmo, no segmento de código, mas ai ela deixaria de ser “local”, não é?

Por que não usar PUSH e POP?

Depois que você aprende o conceito de pilha, parece muito mais simples usar as instruções PUSH e POP do que usar o esquema que mostrei acima. O mesmo fragmento de código em poderia fazer, retirando aqueles SUB e ADD e codificando como:

f:
  ...
  push eax
  call some_function
  pop  eax
  ...
  ret

A função fica menor? Fica! Parece mais simples? Parece! Mas ela tem um problema… As instruções PUSH e POP são ligeiramente mais lentas que MOV porque cada PUSH e cada POP, além de lerem/gravarem na pilha os valores dos registradores têm que adicionar 4 ou retirar 4 de ESP. O código acima, sem usar PUSH e POP, é equivalente a:

f:
  ...
  sub  esp,4
  mov  [esp],eax
  call some_function
  mov  eax,[esp]
  add  esp,4
  ...
  ret

Essa sequência de SUB/MOV e MOV/ADD acontece em cada um dos PUSHes e POPs, respectivamente. O que o compilador C faz é, já que ele sabe quantos bytes vai precisar usar da pilha, ele os aloca de antemão e usa apenas MOVs para guardar os valores!

Ainda não se convenceu que usar a pilha é melhor?

Se você ainda acha que guardar estados no segmento de dados ou código é uma boa ideia, existe mais um motivo para não fazê-lo. Um acesso à memória depende do cálculo do “endereço efetivo”, que pode ser dado por uma expressão. Por exemplo:

mov eax,[esp]
mov eax,[esp+4]
mov eax,[ebx+esi+8]
mov eax,[ebx+esi*8+8]
mov eax,[0x7ffffff0]

Nos primeiros 4 casos o “endereço” de onde um DWORD será lido é dado pelas expressões envolvendo registradores. No primeiro e no segundo caso não há gasto de ciclos de clock adicionais e o acesso é muito parecido com quando você acessa um registrador qualquer, em termos de performance. Os outros casos envolvem cálculos mais complicados e, no caso do último, um deslocamento maior que 2047. Qualquer deslocamento maior que 2047 causa o consumo de 1 ciclo de clock extra (além do cálculo)… Por exemplo, se usássemos [esp+4096] teríamos o consumo de 1 ciclo a mais na instrução… Se usássemos [ebx+esi+4096], teríamos o consumo de 1 ciclo a mais, graças ao cálculo de EBX+ESI e ainda mais 1 porque o offset é maior que 2047.

Ao usar a pilha e manter as variáveis locais próximas de onde ESP aponta, digamos, menos de 2 KiB perto, não há consumo de ciclo extra. É como se o processador estivesse lendo/gravando num registrador.

É claro que existem outras penalidades: Cache Misses, TLB misses e Page Faults, por exemplo… Mas, isso poderia ocorrer nos outros casos também…

 

Adote uma convenção de chamadas ao estilo de C…

Deixar para as funções chamadoras manterem seus próprios contextos e evitar fazer testes desnecessários em funções de baixo nível são sempre boas ideias… Suas funções de baixo nível devem fazer apenas o que elas precisam fazer. Verificar se ponteiros são nulos, se valores estão dentro da faixa desejada etc, são tarefas para funções de níveis mais altos, mais “inteligentes”. Essa estratégia leva a códigos menores e mais rápidos, sempre!

Anúncios

Para quem está criando o próprio “toy OS”…

Conheço algumas pessoas que estão experimentando a criação do próprio sistema operacional de brinquedo. Já vi alguns projetos interessantes, a maioria voltada para o modo protegido i386 (32 bits). Aqui vai uma dica para quem está usando o GCC para gerar código freestanding

A convenção de chamada padrão da linguagem C é chamada de cdecl, onde os argumentos de uma função são sempre empilhadas, na ordem do último argumento para o primeiro; e a função chamadora é a responsável por “limpar” a pilha dos argumentos. Acontece que ficar usando pilha para passagem de argumentos é um jeito bem lento de se fazer as coisas. Será que não tem alguma forma de usar registradores? Felizmente, tem! Antes, vamos dar uma olhada nas funções abaixo:

__attribute__((noinline))
int f(int a, int b, int c) 
{ return a * b + c; }

__attribute__((noinline))
int g(int a, int b, int c, int d, int e) 
{ return ( f(a, b, c) - d) / e; }

Se você compilar com as opções tradicionais, obterá algo assim:

; Código equivalente, para NASM, compilado com
; o GCC via:
;
; $ cc -O2 -S -masm=intel -ffreestanding -m32 test.c
;
  bits 32
  section .text

; A estrutura da pilha após a chamada de f é:

;   ESP+0:  Endereço de retorno colocado pelo CALL.
;   ESP+4:  Valor de 'a';
;   ESP+8:  Valor de 'b':
;   ESP+12: Valor de 'c';
;
  global f
f:
  mov  eax,[esp+8]
  imul eax,[esp+4]
  add  eax,[esp+12]
  ret

; A estrutura da pilha após a chamada de g é:
;
; ESP+0:  Endereço de retorno colocado pelo CALL;
; ESP+4:  Valor de 'a';
; ESP+8:  Valor de 'b';
; ESP+12: Valor de 'c';
; ESP+16: Valor de 'd';
; ESP+20: Valor de 'e';
;
  global g
g:
  ; Aqui tem um "macete"... Como cada PUSH
  ; decrementará ESP em 4, para acessar a próxima referência
  ; à pilha, temos que usar o mesmo offset "ESP+12".
  push	dword [esp+12]  ; Empilha 'c'.
  push	dword [esp+12]  ; Empilha 'b'.
  push	dword [esp+12]  ; Empilha 'a'.
  call	f
  add   esp, 12         ; Livra-se dos 12 bytes empilhados.

  sub   eax, [esp+16]
  cdq
  idiv  dword [esp+20]
  ret

Cada referência à memória consome, pelo menos, 1 ciclo de clock adicional para a instrução e, ainda, aumenta um bocado o tamanho do código. Eis o micro código das duas funções, obtida com o objdump:

f:
   0: 8b 44 24 08      mov  eax,[esp+0x8]
   4: 0f af 44 24 04   imul eax,[esp+0x4]
   9: 03 44 24 0c      add  eax,[esp+0xc]
   d: c3               ret

g:
  10: ff 74 24 0c      push DWORD PTR [esp+0xc]
  14: ff 74 24 0c      push DWORD PTR [esp+0xc]
  18: ff 74 24 0c      push DWORD PTR [esp+0xc]
  1c: e8 fc ff ff ff   call f
  21: 83 c4 0c         add  esp,0xc
  24: 2b 44 24 10      sub  eax,[esp+0x10]
  28: 99               cdq  
  29: f7 7c 24 14      idiv DWORD PTR [esp+0x14]
  2d: c3               ret

Agora, vejamos como fica o mesmo código, compilado com o GCC, mas incluindo a opção -mregparm=3:

f:
   0:	0f af d0         imul edx,eax
   3:	8d 04 0a         lea  eax,[edx+ecx*1]
   6:	c3               ret  

g:
  10:	e8 fc ff ff ff   call f
  15:	2b 44 24 04      sub  eax,[esp+0x4]
  19:	99               cdq  
  1a:	f7 7c 24 08      idiv DWORD PTR [esp+0x8]
  1e:	c3               ret    

O que aconteceu aqui é que o atributo regparm faz com que os 3 primeiros argumentos, se forem inteiros, são passados sempre pelos registradores EAX, EDX e ECX, nessa ordem. Os demais argumentos são empilhados, de acordo com a convenção de chamada cdecl. Na função g, apenas os argumentos d e e estarão empilhados e, como e é empilhado primeiro, ele estará em [ESP+8], deixando d em [ESP+4].

Note que, como EAX, EDX e ECX já contém os argumentos que serão passados para f, na função g, nenhum empilhamento é necessário, retirando os 3 PUSHs que existiam antes, bem como a limpeza da pilha. Do lado da função f, já que os argumentos estão todos em registradores, podemos usar LEA para fazer a adição final…

Bem… o resultado final é que as duas funções ficarão bem mais rápidas e com a metade do tamanho das originais!

SDCC: Algumas considerações sobre o Z80…

Escrevendo o artigo nostálgico sobre Z80 e 6502 testei o SDCC (Small Devices C Compiler) criando pequenos códigos. Eu pretendia mostrar como um código simples (checksum ou obter o maior valor contido num array) ficariam, para esses processadores. Minha surpresa é que o SDCC cria código ineficiente.

A primeira coisa a fazer aqui é determinar qual é a convenção de chamada usada pelo SDCC. Para isso vou compilar funções simples:

char f(void)   { return '0'; }
char g(char c) { return c + '0'; }
int  h(void)   { return -1; }
int  i(int x)  { return x - 1; }

Isso cria código como mostrado abaixo:

_f:
  ld  l,#0x30       ; L = '0'.
  ret

_g:
  ld  hl, #2
  add hl, sp        ; HL = SP+2
  ld  a, (hl)       ; A = c
  add a, #0x30      ; A += '0'
  ld  l,a
  ret

_h:
  ld  hl,#0xFFFF    ; HL = -1
  ret

_i:
  ld  hl, #2
  add hl, sp        ; HL aponta para x, na pilha.

  ld  e, (hl)       ; DE = (HL).
  inc hl
  ld  d, (hl)

  dec de            ; HL = DE - 1
  ex  de,hl
  ret

Ao que parece, os valores de retorno são sempre feito em L ou no par HL e o acumulador, bem como o par DE, podem ser modificados à vontade (não precisam ser preservados entre chamadas). E, também, os argumentos da função são sempre passados pela pilha.

Para determinar melhor a convenção de chamadas, devemos lidar com rotinas mais complexas, para observar a alocação dos registradores e, se necessário, como as variáveis locais são alocadas na própria pilha. Por exemplo, uma rotina mais elaborada, checksum, poderia ser útil:

#include <stdint.h>
#include <stdlib.h>

uint16_t cksum(uint8_t *p, size_t size)
{
  uint16_t sum;

  for (sum = 0; size--; )
    sum += *p++;

  return sum;
}

E, eis o código que o SDCC cria:

_cksum:
  push  ix        ; Salva IX para usá-lo como
  ld    ix,#0     ; ponteiro auxiliar para a pilha.
  add   ix,sp

  push  af        ; Cria espaço para cópia do ponteiro p.

  ld    de,#0     ; DE é 'sum'.

  ; Copia 'p' para variável local, na pilha.
  ld    a,(ix+4)
  ld    (ix-2),a
  ld    a,(ix+5)
  ld    (ix-1),a

  ; BC contém 'size'
  ld    c,(ix+6)
  ld    b,(ix+7)

00103$:
  ld    h,c       ; HL <- BC
  ld    l,b
  dec   bc        ; size--;

  ; size == 0?
  ld    a,l
  or    a,h
  jr    Z,00101$   ; Se 'size==0', sai da rotina.

  pop   hl        ; Recupera 'p' da pilha.
  push  hl

  ld    l,(hl)    ; L <- *p

  ; Incrementa p (na pilha)
  inc   (ix-2)
  jr    NZ,00116$
  inc   (ix-1)

  ; sum += *p;
00116$:
  ld    h,#0x00
  add   hl,de
  ex    de,hl
  jr    00103$

  ; Coloca DE em HL, recupera SP, limpa a pilha e sai.
00101$:
  ex    de,hl
  ld    sp, ix
  pop   ix
  ret

Aqui podemos extrapolar que AF e BC também não são preservados. Aliás, ao que parece, apenas os registradores de índice IX e IY (se usado) e o SP (por motivos óbvios) devem ser preservados… Lembrando que os retornos são feitos em L ou HL. E, mesmo no caso de retornos de tipos de 8 bits, o registrador H não precisa ser preservado (como pode ser visto na função g, lá em cima).

Uma coisa estranha no código criado pelo SDCC é que ele preferiu manter uma cópia do ponteiro ‘p’ na pilha, ao invés da variável local ‘sum’… E a rotina ficou maior do que poderia ser, respeitando os critérios do compilador. Eis como eu a implementaria, se fosse o compilador:

_cksum:
  push ix
  ld   ix,#0
  add  ix,sp

  ld   h,(ix+4)   ; HL <- p
  ld   l,(ix+5)
  ld   b,(ix+6)   ; BC <- size
  ld   c,(ix+7)

  ld   de,#0      ; DE <- 0

.loop:
  ld   a,b        ; if (BC == 0) goto .exit;
  or   c
  jr   z,.exit

  dec  bc         ; BC--;

  ld   a,e        ; DE += *p;
  add  a,(hl)
  ld   e,a
  ld   a,d
  adc  a,#0
  ld   d,a

  inc  hl         ; p++;

  jr   .loop

.exit:
  ex   de,hl      ; HL <- DE.
  pop  ix
  ret

Não há necessidade de variáveis locais alocadas na pilha e a rotina acima é 6 instruções menor que a anterior. Ainda, o loop principal é mais curto!

Claro que o SDCC foi esperto ao usar o par HL, com H zerado, para acumular, em DE, o checksum, mas não foi muito esperto ao usar uma variável local, na pilha, para manter a cópia do ponteiro p. Outro fato interessante é que eu não confio que (IX-2) será calculado corretamente, já que as instruções que usam IX dessa maneira indireta adicionam um byte ao registrador de 16 bits. Ou seja, -2 é 0xFE e não 0xFFFE… Isso é uma desconfiança minha e é bem possível que essa adição seja feita considerando o sinal do offset (é provável que seja assim).

Deixe-me lembrá-lo que o processador Z80, assim como outros de 8 bits, não possuem cache (nem de dados, nem de código). Não possuem “reordenador” de instruções, não possuem arquitetura superescalar, não possuem “branch prediction”, etc… Cada instrução e cada acesso à memória adicional conta. A regra para otimização de código para esses processadores é: Menos instruções e menos acessos à memória, além, é claro, de bons algoritmos.

Mais um exemplo: Nem sempre assembly é a resposta!

Já escrevi sobre isso aqui: Criar suas próprias rotinas em assembly não é uma panaceia para a obtenção de alta performance. É possível acabar com uma rotina pior do que a gerada pela linguagem de alto nível. Especialmente se estivermos falando de compiladores que oferecem recursos de otimização.

Para demonstrar, consideremos a simples rotina de selection sort, abaixo:

#define swap(a,b) \
    { int _t; _t = (a); (a) = (b); (b) = _t; }

// Para ser justo, não vou permitir inlining...
__attribute__((noinline))
static void selection_sort(int *p, unsigned int size)
{
  unsigned int i, j;

  for (i = 0; i < size - 1; i++)
    for (j = i+1; j < size; j++)
      if (p[i] > p[j])
        swap(p[i], p[j]);
}

É legítimo pensar que essa rotina seja menos que ótima, já que usa o macro swap(), que lança mão de uma variável temporária que talvez seja alocada em memória. Assim, o programador pode criar uma rotina equivalente, em assembly, assim:

bits 64

section .text

; void selection_sort_asm(int *, unsigned int);
; -- Para ser justo, alinho em DWORD o ponto de entrada
;    da rotina!
  global selection_sort_asm
  align 4
selection_sort_asm:
  lea r8d,[rsi-1] ; r8d == size - 1;

  xor ecx,ecx     ; i = 0;

.loop2:
  lea edx,[rcx+1] ; j = i + 1;

.loop1:
  mov eax,[rdi+rcx*4]   ; if (ptr[i] > ptr[j]) ...
  cmp eax,[rdi+rdx*4]
  jle .skip

  xchg eax,[rdi+rdx*4]  ; ... swap(p[i], p[j]);
  mov [rdi+rcx*4],eax

.skip:
  add edx,1     ; j++
  cmp edx,esi   ; if (j < size) goto loop1;
  jb  .loop1

  add ecx,1     ; i++;
  cmp ecx,r8d   ; if (i < size - 1) goto loop2;
  jb  .loop2

  ret

Claro que essa rotina pode ser melhorada, especialmente entre os labels .loop1 e .skip, mas, em arquiteturas mais modernas (Ivy Bridge, SandyBridge e Haswell, sem contar com as mais recentes Broadwell e Skylake) os cálculo de endereços efetivos podem ser cacheados, numa espécie de common subexpression elimination, ou seja, isso não tem grande influência… Além do que, quero mostrar como uma abordagem “ingênua” se parece…

Bem… a rotina acima não é tão “ingênua” assim porque levei em conta algumas possíveis otimizações: Note que usei a instrução XCHG, usada para aproveitar o conteúdo de EAX na “troca” e evitar o uso de um outro registrador temporário. Repare também que não uso a instrução INC para evitar a penalidade de 1 ciclo de clock pelo fato dessa instrução não afetar o flag de carry (e precisar preservá-lo). É preferível usar ADD, mesmo tendo tamanho maior, em seu microcódigo… Ainda, os saltos condicionais são feitos “para trás”, para aproveitar o algoritmo estático de branch prediction (exceto para o label .skip). Uso também as instruções LEA para adições rápidas, carryless

Mas, se você medir a performance de ambas as rotinas contra um array de 10 elementos aleatórios obterá (num i5-3570 @ 3.4 GHz, arquitetura Ivy Bridge) algo em torno de 1800 ciclos para a rotina em C e 2200 ciclos para a rotina em assembly! Ou seja, a rotina em C é 18% mais rápida!!! Num i7, com arquitetura Haswell poderá obter menos ciclos…

A rotina em Assembly equivalente para o selection sort, gerada pelo GCC com as opções de compilação “-O2 -mtune=native“, é esta:

bits 64

section .text

  global selection_sort
  align 4
selection_sort:
  cmp esi, 1
  jbe .exit
  lea r11d, [rsi-1]
  mov r9, rdi
  xor r10d, r10d

  align 4
.loop2:
  add r10d, 1
  mov eax, r10d
  cmp esi, r10d
  jbe .skip2

  align 4
.loop1:
  mov edx, eax
  mov ecx, [r9]
  lea rdx, [rdi+rdx*4]
  mov r8d, [rdx]
  cmp ecx, r8d
  jle .skip1
  mov [r9], r8d
  mov [rdx], ecx

.skip1:
  add eax, 1
  cmp esi, eax
  jne .loop1

.skip2:
  add r9, 4
  cmp r10d, r11d
  jne .loop2
  ret

.exit:
  ret

Essencialmente, ela é a mesma coisa da rotina em assembly que mostrei acima. A diferença está na organização das instruções e no aproveitamento do paralelismo das unidades de execução do processador (não confundir com os “cores” ou “núcleos”!).

O GCC também evita instruções problemáticas como XCHG (que, quando faz acesso à memória, “trava” [lock] o barramento de dados). O compilador também entende que pontos de retorno de loops podem precisar estar alinhados para que eles não cruzem a fronteira de uma linha do cache L1I e, por isso, coloca aquele “align 4” lá… Ele também tenta evitar problemas de “interlocking” de registradores (quando modificamos um registrador e tentamos usá-lo, na instrução seguinte, como operando fonte. Isso evita que duas instruções sejam executadas em paralelo).

Ou seja, o compilador tenta levar em conta a grande quantidade de regras de otimização (que podem ser estudadas no manual de otimização de software da Intel [baixe aqui] – prepare-se: são quase 700 páginas!) que você, ou eu, poderíamos deixar “passar batido”. Isso não significa que não seja possível para você ou eu elaborarmos uma rotina que seja melhor da gerada pelo compilador. Isso significa, porém, que na maioria das vezes, o compilador faz um trabalho melhor do que faríamos!

strlen_sse42() usando função “intrínseca”.

Pode parecer que a instrução PCMPISTRI seja meio complicada de usar em C, já que ela oferece dois resultados diferentes: ECX, contendo um índice de acordo com a comparação, e os flags. Mas, felizmente, o valor de ECX será 16 se InRes2 estiver totalmente zerado! Assim, a função anterior, escrita em assembly, pode ser reescrita em C assim:

/* test.c

  Compilar com:
    gcc -Ofast -msse4.2 -o test test.c
*/
#include <stddef.h>
#include <x86intrin.h>

size_t strlen_sse42_c(const char *s)
{
  unsigned int index;
  size_t result;
  static const char ranges[16] = { 1, 255 };

  result = 0;
  do
  {
    index = _mm_cmpistri(*(__m128i *)ranges, 
                         *(__m128i *)s,
                         _SIDD_UBYTE_OPS         | 
                         _SIDD_CMP_RANGES        | 
                         _SIDD_NEGATIVE_POLARITY |
                         _SIDD_LEAST_SIGNIFICANT);

    result += index;
    s += sizeof(__m128i);
  } while (count == 16);

  return result;
}

O código final ficará semelhante, mas menos performático, ao anterior:

bits 64

section .rodata

  align 16
_ranges:  db 1, 255
          times 14 db 0

section .text

global strlen_sse42:
  align 16
strlen_sse42:
  movdqa xmm0,[_ranges]
  xor    eax,eax

.loop:
  pcmpistri xmm0, [rdi], 0x0_01_01_0_0  
  mov    edx,ecx
  add    rdi,16
  add    rax,rdx
  cmp    ecx,16
  jz     .loop
  
  ret

Algumas diferenças óbvias: a instrução MOVDQA é mais rápida que MOVDQU e exige que o array _ranges esteja alinhado. Eu deveria ter previsto isso no código em assembly no artigo anterior… O compilador escolheu fazer DUAS comparações, como instruído. Como não temos como verificar o flag ZF à partir da função intrínseca _mm_cmpistri, só nos restava comparar o valor retornado com 16.

Agora… é evidente que PCMPISTRI só está disponível se seu processador suportar SSE 4.2. Um método bem simples de usar essa função OU a função padrão do compilador é este:

#include <stddef.h>
#include <string.h>
#include <x86intrin.h>

// Daqui para frente, strlen será chamada por esse ponteiro!
size_t (*__strlen)(const char *);

static size_t strlen_sse42_c(const char *s)
{ ... }

// Esse atributo faz com que a função seja executada
// ANTES de main(). É interessante ter apenas uma dessas
// funções em seu programa, embora o atributo permita definir
// a ordem de execução...
static __attribute__((constructor)) void ctor(void)
{
  if (__builtin_cpu_supports("sse4.2"))
    __strlen = strlen_sse42_c;
  else
    __strlen = strlen;
}

As chamadas a __stlen, evidentemente, serão sempre indiretas, mas assim você garante a compatibilidade entre processadores ao usar a rotina. Além do mais, a quase totalidade das funções da libc são chamadas de forma indireta, já que localizam-se em libc6.so.

strlen() usando SSE 4.2

Há uns meses atrás (ou será que já faz um ano?) topei com uma dica do amigo Cooler, em seu blog, mostrando como comparar duas strings usando SSE 4.2. A rotina é realmente rápida porque compara 16 bytes de cada vez, ao invés de byte por byte ou, até mesmo, dword por dword (ou qword, se otimizarmos para o modo x86-64). Confesso que não tinha nenhuma intimidade com a instrução PCMPISTRI, disponibilizada pelo SSE 4.2 e fiquei maravilhado com o achado.

A rotina que ele publicou foi essa (publico aqui apenas a versão x86-64):

; Original code by Cooler_  c00f3r[at]gmail[dot]com
bits 64
section .text

global strcmp_sse42

; int strcmp_sse42(char *ptr1, char *ptr2);
strcmp_sse42:
  mov    rax,rdi
  sub    rax,rsi
  sub    rsi,16
   
strloop:
  add    rsi,16
  movdqu xmm0,[rsi]
  pcmpistri xmm0,[rsi+rax],0b0011000
  ja     strloop
  jc     blockmov
  xor    eax,eax
  ret
  
blockmov:
  add    rax,rsi    
  movzx  rax,byte [rax+rcx]
  movzx  rsi,byte [rsi+rcx]
  sub    rax,rsi    
  ret

O detalhe, é claro, está na instrução PCMPISTRI e no byte de controle… Ele torna a instrução bastante flexível e, ao mesmo tempo, difícil de entender… Eis uma outra rotina da libc que pode ser acelerada (de novo, para x86-64, mas, agora, com meus comentários):

bits 64

section .rodata
; Pares de bytes contendo faixas (ranges).
  align 16
_ranges:
  db 1, 0xff      ; Faixa entre (char)1 e (char)0xff.
  times 14 db 0   ; As demais "faixas" não são "usadas".

section .text

global strlen_sse42

; size_t strlen_sse42(const char* s1)
  align 16
strlen_sse42:
  xor ecx,ecx           ; Necessário. Garante que os bits
                        ; superiores, [63:5], de RCX 
                        ; estejam zerados.

  lea rax,[rdi-16]
  movdqu xmm0,[_ranges]

.loop:
  add rax,16

  ; Compara os 16 bytes do buffer apontado por RAX
  ; Com os pares de faixas em XMM0...
  ;
  ; PCMPISTRI é "Packed Compare Implicit-ending String 
  ; returning Index" ou algo assim... "implícito" 
  ; significa string terminada com '\0'.
  ;
  ; O byte de controle da instrução representa:
  ;
  ; +-+-+---+---+-+-+
  ; |0|0|0 1|1 0|0|0|-----------> 0 = char
  ; +-+-+---+---+---+             1 = short
  ;    |  |   |  |
  ;    |  |   |  +--------------> 0 = unsigned
  ;    |  |   |                   1 = signed
  ;    |  |   |
  ;    |  |   |                   00 = Equal any
  ;    |  |   |                   01 = "Ranges"
  ;    |  |   +-----------------> 10 = Equal each (string compare)
  ;    |  |                       11 = Equal ordered
  ;    |  |
  ;    |  |                       00 = Positive Polarity
  ;    |  +---------------------> 01 = Negative Polarity
  ;    |                          10 = Masked (+)
  ;    |                          11 = Masked (-)
  ;    |
  ;    +------------------------> 0 = Least significant index
  ;                               1 = Most significant index

  pcmpistri xmm0,[rax],0b0_01_01_0_0  ; LSB InRes2 offset; 
                                      ; InRes2=~InRes1; 
                                      ; Range compare; 
                                      ; unsigned char.

  jnz .loop   ; ZF=1 só se um dos bytes de [rax] for 0 
              ; (o 'i' do mnemônico pcmp(i)stri garante isso).
              ; ECX é índice (dos 16 bytes) onde achou o '\0'.
              ; (o 'i' de pcmpistr(i) garante isso).

  add rax,rcx

  lea rdx,[rdi]
  sub rax,rdx
  ret

Bem… Como é que PCMPISTRI funciona? Ela toma dois valores de 16 bytes (sim! bytes!) e os comparara de acordo com os bits de 0 a 3 do valor imediato, segundo o comentário que você pode ver acima. No caso de usarmos “unsigned char”, cada byte comparado setará ou zerará um bit de um registrador interno chamado InRes1. Depois que a comparação for feita, podemos inverter ou não o valor contido em InRes1 e colocá-lo em InRes2 – a isso é dado o nome de “polarização” (informada nos bits 4 e 5).

No caso da instrução PCMPISTRI, o bit 6 diz como o valor de ECX será calculado. Isso é feito fazendo uma varredura em InRes2 e, o primeiro bit setado, encontrado (do primeiro ao último ou vice-versa) é colocado em ECX. Se todos os bits estiverem zerados, ECX retornará 16 (será?), mas o flag ZF também estará zerado por causa do I no final do nome do mnemônico (ou seja, a instrução não achou um fim-de-string, um char ‘\0’).

Na rotina acima eu peço para PCMPISTRI comparar cada byte da string com uma faixa de bytes variando de 1 a 255. Os valores zerados na faixa nao contam porque PCMPISTRI irá parar a busca ao encontrar um ‘\0’, de qualquer maneira…

Só um aviso… existem instruções similares, como PCMPESTRI, onde o tamanho da string tem que ser informado no par EDX:EAX. Existem também PCMPISTRM e PCMPESTRM que retornam uma “máscara”, isto é, o próprio InRes2.

Outra dica importante: Essas instruções são feitas para lidar com strings e, por isso, a Intel não impõe a necessidade dos dados estarem alinhados em 16 bytes, como é comum com as instruções SSE. Alinhei _range acima só por vício mesmo… :)

Surpresa! Contar ciclos no ring0 não é tão bom assim!

Estive aqui testando um módulo para o kernel para medir os ciclos de clock gastos por uma função qualquer e comparando isso com a minha rotina para fazer o mesmo, no userspace. A rotina sob teste é simples:

/* test.c */

// Não vamos usar esse array fora daqui,
// por enquanto...
int a[100] = { 0 };

void f(void)
{
  for (int i = 1; i < 100; i++)
    a[i] = a[i-1] + 1;
}

No userspace basta usar as funções inline begin_tsc e end_tsc, como mostradas abaixo:

/* cycle_counting.h */

#ifdef __x86_64__
# define REGS1 "rbx", "rcx"
# define REGS2 "rax, "rbx", "rcx", "rdx"
#else
# ifdef __i386__
# define REGS1 "ebx", "ecx"
# define REGS2 "eax, "ebx", "ecx", "edx"
# else
#  error "Need x86-64 or i386 platforms to use cycle counting!"
# endif
#endif

unsigned long long __local_tsc;

inline void begin_tsc(void)
{
  unsigned int a, d;

  __asm__ __volatile__ ("xorl %%eax,%%eax\n"
                        "cpuid\n"
                        "rdtsc"
                        : "=a" (a), "=d" (d)
                        :: REGS1);

  __local_tsc = ((unsigned long long)d << 32) | a;
}

inline unsigned long long end_tsc(void)
{
  unsigned int a, d;

  __asm__ __volatile__ ("rdtscp\n"
                        "movl %%eax,%0\n"
                        "movl %%edx,%1\n"
                        "xorl %%eax,%%eax\n"
                        "cpuid"
                        : "=m" (a), "=m" (d)
                        :: REGS2);

  // Retorna a contagem de ciclos.
  return ((unsigned long long)d << 32) + a - __local_tsc;
}

Já para usá-las no kernelspace, temos que criar um módulo:

/* cyclemod.c */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/hardirq.h>
#include <linux/preempt.h>
#include "cycle_counting.h"

//extern int a[];
extern void f(void);

static int __init cyclecnt_start ( void )
{
  int i;
  unsigned long flags;
  unsigned long long c;

  printk ( KERN_INFO "Loading Cycle-Counting module...\n" );

  preempt_disable();
  raw_local_irq_save(flags);

  begin_tsc();
  f();
  c = end_tsc();

  raw_local_irq_restore(flags);
  preempt_enable();

  printk ( KERN_INFO "\tCycles: %llu\n", c);

  return 0;
}

static void __exit cyclecnt_end ( void )
{
  printk ( KERN_INFO "Goodbye Cycle-Counter.\n" );
}

module_init ( cyclecnt_start );
module_exit ( cyclecnt_end );

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Frederico L. Pissarra");
MODULE_DESCRIPTION("Cycle Counting Module");

Para compilar esse bicho, crie o makefile abaixo e simplesmente execute make. Você verá diversos arquivos, mas o módulo é o com extensão .ko (kernel object).

ccflags-y := -Ofast
obj-m := cyclescount.o
cyclescounter-objs := cyclemod.o test.o

KVERSION = $(shell uname -r)

all:
  make -C /lib/modules/$(KVERSION)/build M=$(PWD) modules

clean:
  make -C /lib/modules/$(KVERSION)/build M=$(PWD) clean

A diferença na rotina acima é que desabilitamos as interrupções para o processador local (provavelmente o kernel usa apenas a instrução CLI) e a preempção (não haverá chaveamento de tarefa para essa thread)… Isso deveria eliminar algum custo que existe no userspace e nos dar uma contagem mais “precisa”, mas veja só… Não é isso o que acontece:

$ ./cnttest    # userspace app
Cycles: 552
$ sudo insmod cyclecounter.ko
$ sudo rmmod cyclecounter
$ dmesg | sed -n '/Load.\+Cycle-Count/,+2p'
[17630.739459] Loading Cycle-Counting module...
[17630.739464] 	Cycles: 748
[17630.747001] Goodbye Cycle-Counter.

Como assim, no userspace obtive uma contagem menor de ciclos do que no kernspace?

E agora, Zé?!