Preparando para copiar blocos de bytes das superfícies

Acredito que eu já tenha falado disso por aqui (só não encontrei onde), mas precisaremos fazer cópias de blocos de dados, para cada scanline, da superfície fonte para a superfície destino, se formos usar a abstração das “superfícies” que citei no artigo anterior… Obviamente, queremos fazer isso da maneira mais rápida possível… Podemos, por exemplo, determinar se o bloco tem tamanho maior que 128 bits (16 bytes) e usarmos instruções SSE que não lidam com ponto flutuante para mover tantos bytes quanto possíveis numa só tacada e deixar os bytes restantes para serem copiados por outros métodos…

A primeira tentativa de criar uma rotina memcpy customizada poderia ser essa:

#include <x86intrin.h>

void _memcpy_sse(void *dest, void *src, size_t size)
{
  __m128i *xdest, *xsrc;
  size_t xmm_blocks;
  size_t remaining;

  xmm_blocks = size / 16;
  remaining = size % 16;

  // Copia blocos de 16 em 16 bytes.
  xdest = dest; xsrc = src;
  while (xmm_blocks--)
    *xdest++ = *xsrc++;

  // Copia os bytes que restaram.
  dest = xdest; src = xsrc;
  while (remaining--)
    *(char *)dest++ = *(char *)src++;
}

A rotina tem o potencial de ser 16 vezes mais rápida que um simples memcpy que, supostamente, copia dados byte por byte. Mesmo que memcpy leve em consideração que você tem um processador capaz de lidar com 32 bits por vez, a rotina acima tem o potencial de ser, pelo menos, 4 vezes mais rápida… Considere agora a aproximação “ingênua”:

void _memcpy_asm(void *dest, void *src, size_t size)
{
  __asm__ __volatile__ (
    "rep; movsb"
    :: "D" (dest), "S" (src), "c" (size)
}

Ahhh… isso deve ser muito ruim, não? Afinal, mesmo usando uma única instrução em assembly (MOVSB) com o prefixo REP, estamos copiando bytes individuais de um buffer para outro! Algo parecido com _memcpy_sse poderia ser mais útil e rápido…

O problema é quando medimos a performance (usando minhas macros):

void main(void)
{
  static char buff1[65535], buff2[65535];
  uint64_t clocks1, clocks2;

  BEGIN_TSC;
  _memcpy_sse(buff1, buff2, sizeof buff1);
  END_TSC(clocks1);

  BEGIN_TSC;
  _memcpy_asm(buff1, buff2, sizeof buff1);
  END_TSC(clocks2);

  printf("_memcpy_sse: %" PRIu64 " cycles\n"
         "_memcpy_asm: %" PRIu64 " cycles\n",
         clocks1, clocks2);
}

Eis o resultado que obtenho num i5-3570 de 3.40 GHz:

$ ./test
_memcpy_sse: 90404 cycles
_memcpy_asm: 6296 cycles

Ou seja, _memcpy_asm, usando uma simples instrução prefixada é cerca de 14 vezes mais rápida que a função que copia de 16 em 16 bytes! Como isso é possível?

Alinhamento e caches

O primeiro motivo da lentidão de _memcpy_sse são os caches. Copiar blocos de 16 bytes via instruções SSE exigem que os dados estejam alinhados de 16 em 16 bytes para que não existam acessos entre duas linhas de cache simultaneamente. A rotina não pode lidar com isso porque os endereços contidos nos ponteiros dest e src podem, de fato, estar desalinhados (considere o caso de um formato de pixel PELFMT_RGB, onde cada pixel tem 3 bytes de tamanho). De fato, o compilador cria o loop de cópia via SSE assim:

; R8 = xsrc
; RCX = xdest
; RAX = xmm_blocks
...
.loop:
  add r8, 16
  movdqa  xmm0, XMMWORD PTR [r8-16]
  add rcx, 16
  sub rax, 1
  movaps  XMMWORD PTR [rcx-16], xmm0
  cmp rax, -1
  jne .loop
...

Repare nas instruções MOVDQA e MOVAPS. Esse A em ambos os mnemônicos significa Aligned, ou seja, é assumido que os ponteiros tenham alinhamento com 16 bytes (ou seja, que o endereço contenha os 4 bits inferiores zerados)… Se não tiver, 1 ciclo de clock adicional pode ser gasto… Usar as instruções “desalinhadas” como MOVDQU e MOVAPU (U de Unaligned) não ajuda, porque essas instruções são, de fato, sempre mais lerdas que as que assumem alinhamento.

Você pode estar pensando que existirão casos onde o alinhamento será obedecido e _memcpy_sse será de fato mais rápida… Infelizmente não… Acontece que, pelo que sei, desde a arquitetura Sandy Bridge a instrução MOVSB prefixada por REP tem um tratamento especial. Ela automaticamente copiará os maiores blocos possíveis e, internamente, leva em conta os problemas de alinhamento! Acho que ela lida diretamente com o tamanho de uma linha de cache (64 bytes). Se o bloco tiver mais que 64 bytes de tamanho, ela copiará uma linha inteira do cache, de um lugar para o outro… Em essência, ela funciona como _memcpy_sse, porém não lida com SSE e sempre lidará com blocos de tamanho tal onde a cópia seja mais eficiente… Os detalhes, são obscuros.

E quanto a memcpy?

Claro, podemos usar a função da libc, declarada em string.h: memcpy ou até mesmo a memmove. Infelizmente elas são mais lentas. A função memcpy é cerca de 60% mais lenta (cerca de 10000 ciclos) que um simples REP MOVSB e memmove é cerca de 160% mais lenta (cerca de 16300 ciclos)! Ambas ainda ganham de nossa _memcpy_sse e, neste caso, memcpy deve ser a nossa escolha preferida se o processador não tiver a otimização de REP MOVSB. Isso porque é injusto comparar a performance de memmove, que é projetada para lidar com blocos sobrepostos.

Para detectar se essa otimização do REP MOVSB existe, nada mais simples:

// Retorna 0 se não suporta, caso contrário, suporta!
int supports_enhanced_repmovsb(void)
{
  int result;

  __asm__ __volatile__ (
    "cpuid\n"
    : "=b" (result) : "a" (7) :
#ifdef __x86_64
      "%rcx", "%rdx"
#else
      "%ecx", "%edx"
#endif
  );

  return result & (1U << 9);
}

Mesmo assim, recomendo que use a função __builtin_memcpy do GCC, já que o compilador pode resolver substituí-la por REP MOVSB por si mesmo… Geralmente ele usa a libc (talvez não no modo freestanding)…

Então, a melhor maneira de lidamos com as rotinas é essa:

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

extern int supports_enhanced_repmovsb(void);
extern void _memcpy_asm(void *, void *, size_t);

// Ponteiro para a nossa "memcpy".
// retorna void * para manter a chamada compatível
// com a memcpy original!
void *(*_memcpy)(void *, void *, size_t);

// Essa rotina será chamada antes mesmo de main!
__attribute__((constructor))
void __init_memcpy(void)
{
  if (supports_enhanced_repmovsb())
    // Ignoro o "retorno" para manter a rotina "compatível"
    // com memcpy original!
    _memcpy =
      (void *(*)(void *, void *, size_t))_memcpy_asm;
  else
    _memcpy = memcpy; // ou __builtin_memcpy.
}

E, voilà, possivelmente você a rotina de cópia de blocos mais rápida para a máquina onde o código será executado! A única diferença é que, ao invés de usar memcpy ou _memcpy_asm, você chamará a função através do ponteiro _memcpy, que, efetivamente, criará uma chamada no estilo call [_memcpy], que “gasta” apenas 2 ciclos de clock adicionais, em comparação à chamada direta e poderá gastar mais, se o ponteiro não estiver no cache L1d. Mais ainda, se a própria função apontada não estiver no cache L1i, mas isso também acontece com as chamadas diretas.

De qualquer maneira, essa chamada indireta é sempre mais rápida que a rotina original, usando SSE. Mas, caso você ainda esteja cético com relação às performances, experimente modifica o loop final de _memcpy_sse que, se o último bloco a ser copiado tiver menos que 16 bytes, ele será executado… Poderíamos substituí-lo por:

  // Copia os bytes que restaram.
  //dest = xdest; src = xsrc;
  //while (remaining--)
  //  *(char *)dest++ = *(char *)src++;
  memcpy(xdest, xsrc, remaining);

Meça a performance e verá que não faz muita diferença se usarmos esse loop ou a a chamada a memcpy. Também não fará diferença se usarmos _memcpy_asm no lugar desse memset porque temos, no máximo, 15 bytes para mover, ou seja, menos que uma linha de cache.

Anúncios