Mais um blog inútil.

Abril 29, 2009

Byte Swap com SSE2

Filed under: Assembly,Coding,Useless — dongs @ 0:32

Encontrava-me hoje na Internet descansado quando o raxx7 começou a falar de optimizar uma função simples, mas engraçada -- inverter a ordem dos bytes de um inteiro de 64 bits. Vou desde já assumir x86, visto que em amd64 existe uma instrução nativa que faz isto em apenas 4 ciclos (latência no core2) e é provavelmente rápido o suficiente. Mas em x86 precisamos de 2 instruções destas e 2+2 acessos à memória. Assim, peguei na identidade simples:

    BSWAP64(x) = BSWAP32(x>>32)|BSWAP32(x&0xFFFFFFFF)
    BSWAP32(x) = ((ROTL32((x), 8) & 0x00FF00FF) | (ROTL32((x), 24) & 0xFF00FF00))

,onde ROTL32 significa uma rotação de n bits à esquerda. Infelizmente, as extensões SSE2 da arquitectura x86 não possuem instruções específicas de rotação, forçando-nos a utilizar outra identidade bastante útil:

    ROTL32(x, n) = ((x< < n) | (x >> (32-n))) 

Neste momento, já temos tudo o que precisamos para efectuar a operação desejada em SSE2. No entanto, parece haver aqui um excesso de computação que torna este método demasiado ineficiente: 10 operações lógicas -- 5 booleanas, 4 shifts e 1 shuffle. Mas a pipeline do Core 2 é extremamente boa: conseguimos efectuar 3 operações booleanas por ciclo, 1 shift por ciclo e 1 shuffle por ciclo. Se conseguirmos esconder a latência dos shifts com as operações booleanas, vamos obter uma contagem de ciclos não muito superior à dos 2 bswap de 32 bits. Além do mais, efectuamos 2 inversões simultâneas, dado que os registos XMM têm 128 bits; seria um desperdício não o fazer. Os acessos à memória também são mais eficientes, com acessos contíguos de 16 bytes (com o unrolling correcto processamos uma cache line (64 bytes) inteira de uma só vez).

Fiz então uma função para completar o exercício:

BITS 32

%define UNROLL_COUNT (4)

section .data
mask1: dd 0x00ff00ff, 0x00ff00ff, 0x00ff00ff, 0x00ff00ff
mask2: dd 0xff00ff00, 0xff00ff00, 0xff00ff00, 0xff00ff00

section .text
global _sse2_bswap64
_sse2_bswap64:
  push ebp
  mov edx, [esp+8] ; buffer -- assumed aligned 16
  mov ecx, [esp+12] ; length in #words
  test   ecx, ecx
  jz     _end

  and    ecx, -(UNROLL_COUNT*2) ; make ecx even
  jz     _finalize
  
  movdqa xmm6, [mask1]
  movdqa xmm7, [mask2]

align 16
_loop:
  sub ecx, UNROLL_COUNT*2
  
%assign i 0  
%rep  UNROLL_COUNT
  
  movdqa xmm0, [edx] ; p2
  movdqa xmm1, xmm0  ; p0/p1/p5
  pslld  xmm0, 8     ; p0
  movdqa xmm2, xmm1  ; p0/p1/p5
  psrld  xmm1, 24;   ; p0
  movdqa xmm3, xmm2  ; p0/p1/p5
  pslld  xmm2, 24    ; p0
  por    xmm0, xmm1  ; p0/p1/p5
  psrld  xmm3, 8     ; p0
  por    xmm2, xmm3  ; p0/p1/p5
  pand   xmm0, xmm6  ; p0/p1/p5
  pand   xmm2, xmm7  ; p0/p1/p5
  por    xmm0, xmm2  ; p0/p1/p5
  pshufd xmm0, xmm0, 10110001b ; p5 + p0/p1
  movdqa [edx], xmm0 ; p2  
  lea    edx,  [edx+16] ; p0   
  
%assign i i + 1
%endrep

  jnz _loop ; no dependency, all flags were 
               ; computed in the beginning of the loop

_finalize:
  mov  ebp, [esp+8]
  and  ebp, (UNROLL_COUNT*2)-1 ; ebp = count mod UNROLL
  jz _end
  
_endloop:
  mov eax, [edx]
  bswap eax ; p0+p5
  mov ecx, [edx+4]
  bswap ecx
  mov [edx], ecx
  mov [edx+4], eax
  sub ebp, 1
  lea edx, [edx+8]
  jnz _endloop
  
_end:
  pop ebp
  ret

Este código pode ser usado com o yasm ou nasm (o yasm em win32 não acertava com os endereços das masks, não sei se era bug no exportador para COFF ou AIDS). Esta função, junto com código para testá-la encontra-se aqui.

A performance obtida não foi tão boa como esperado, mas mantém-se competitiva com a alternativa: no Core 2 (65 nm) onde testei, a versão SSE2 era ~2% mais rápida. A utilidade de todo este exercício é, assim, discutível.

Bem-haja.

Um comentário a “Byte Swap com SSE2”

  1. mirage diz:

    Adoro o ROTL32 ;-)

Comentar

widgeon
widgeon
widgeon
widgeon