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!

Anúncios