Estrutura com arrays ou Arrays de estruturas?

Me perguntaram isso, uma vez: “O que é melhor? Usar SOA ou AOS?”. O termo SOA é a abreviação de “Structure Of Arrays”. E AOS é “Array Of Structures”. Essecialmente, o sujeito pergunta qual das duas estruturas abaixo é melhor:

struct soa {
  int x[1000];
  int y[1000];
} soa;

stuct aos {
  int x;
  int y;
} aos[1000];

No primeiro caso, para obter o ponteiro do primeiro item de y temos que somar 4000 ao ponteiro do primeiro item de x. No segundo caso podemos manter um ponteiro para os itens do array de estruturas e usar os offsets 0 e +4 para obter os ponteiros de x e y.

Considere duas rotinas simples de preenchimento desses arrays:

void fill_soa(void)
{
  int i;

  for (i = 0; i < 1000; i++)
    soa.x[i] = soa.y[i] = 0;
}

void fill_aos(void)
{
  int i;

  for (i = 0; i < 1000; i++)
    aos[i].x = aos[i].y = 0;
}

Os códigos correspondentes, em assembly, para ambas as rotinas ficam:

fill_soa:
  xor esi,esi
  mov rdi,soa+4000
  mov edx,4000
  call memset
  xor esi,esi
  mov rdi,soa
  mov edx,4000
  call memset
  ret

fill_aos:
  mov eax,aos
  pxor xmm0,xmm0
.L1:
  movdqa [rax],xmm0
  add rax,16
  cmp rax,aos+8000
  jne .L1
  ret

A segunda rotina é claramente mais eficiente que a primeira. O compilador entendeu, nesse caso, que pode preencher x e y em uma tacada só (em fill_aos) e o faz. Na primeira rotina duas chamadas para memset são feitas!

Mas a coisa toda não está decidida ainda! Este é um exemplo simples, com “tipos” adjacentes na estrutura similares (que não faz muita diferença!) e assinalamento similares (zerando todos os itens). E se tivermos assinalamentos diferentes como em:

void fill_soa(void)
{
  int i;

  for (i = 0; i < 1000; i++)
  {
    soa.x[i] = rand();
    soa.y[i] = rand();
  }
}

void fill_aos(void)
{
  int i;

  for (i = 0; i < 1000; i++)
  {
    aos[i].x = rand();
    aos[i].y = rand();
  }
}

Neste caso, acabmos com ambas as rotinas muito similares:

; As rotinas usam RBP como ponteiro base para os
; arrays e RBX como índice. Isso parece violar a convenção
; de chamada, mas é uma alternativa interessante, já que a
; própria convenção de chamada garante que esses
; registradores sejam preservados entre chamadas.
;
; Outro fator interessante é o cálculo do endereço efetivo:
; O uso de [rbx+rbp] usa o seletor DS, já [rbp+rbx] usa SS.
; Como nossos arrays estão no segmento de dados (.bss ou
; .data) e não na pilha, usar [rbx+rbp] garante o acesso
; correto.

fill_soa:
  push rbp
  mov rbp,soa
  push rbx

  xor ebx,ebx
.L1:
  call rand
  mov [rbx+rbp],eax

  call rand
  mov [rbx+rbp+4000],eax ; Essa é a diferença!

  add rbx,4
  cmp ebx,4000
  jne .L1

  pop rbx
  pop rbp
  ret

fill_aos:
  push rbp
  mov rbp,soa
  push rbx

  xor ebx,ebx
.L1:
  call rand
  mov [rbx+rbp],eax

  call rand
  mov [rbx+rbp+4],eax ; Essa é a diferença!

  add rbx,8
  cmp ebx,8000
  jne .L1

  pop rbx
  pop rbp
  ret

Ambas as rotinas pecorrerão todo os arrays e farão duas chamadas a rand. Mas a segunda rotina (fill_aos) usará uma instrução MENOR que a primeira… Eis a diferença entre elas:

89 84 2B A0 0F 00 00   mov [rbx+rbp+4000],eax
89 44 2B 04            mov [rbx+rbp+4],eax

Esses 3 bytes a menos na segunda instrução corresponde a 1 ciclo de máquina a menos na execução. E, de novo, parece que a alternativa AOS é mais eficiente! Mas, ainda assim, isso não é definitivo.

Existem casos onde podemos querer agrupar os valores de x e y em blocos individuais dentro de estruturas para manipulá-los através de ponteiros individuais. A alternativa AOS cria um interleave entre os valores. Isso quer dizer que, na solução SOA teremos “XXXXXXXXXX….YYYYYYYY….” e na AOS teremos “XYXYXYXY…”. Dependendo do seu código a solução SOA pode ser melhor que a AOS e vice-versa.

Como regra geral, se você não vai manipular os itens em blocos individuais em suas rotinas, use AOS. O código tende a ficar um cadinho (mas, só um cadinho!) mais rápido!

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s