Palavras-chave: C, memória, otimização, arrays, vetores, bitmap, pixmap
Ao se escrever código para manipulação de strings ou imagens, é comum percorrer grandes vetores de bytes. A maneira óbvia de fazer isto é algo no estilo de:
char *ptr= buffer;
for (i= 0; i < fim; i++)
*ptr++= 0;
Mas percorrer memória byte a byte é bastante lento, por questões de alinhamento de memória, o fato dela ser endereçada por palavra. Por exemplo, um int em i386 e long em x86_64.
O exemplo abaixo inclui código que percorre por byte e por int, mas pode ser facilmente modificado para percorrer por longs:
#include <sys/types.h>
int main()
{
char buffer[1000];
uint32_t *iptr;
char *ptr;
int i, j;
int max= 973;
for (j= 0; j < 100000; j++)
{
#ifdef lento
ptr= buffer;
for (i= max-1; i>=0; --i)
*ptr++= 0;
#else
iptr= (uint32_t*)buffer;
// processa o vetor de 4 em 4 bytes,
// arredondando o número de elementos
for (i= max>>2-1; i>=0; --i)
*iptr++= 0;
ptr= iptr;
// processa os últimos bytes restantes
switch (max&((1<<2)-1))
{
case 3: *ptr++= 0; // sem break
case 2: *ptr++= 0; // sem break
case 1: *ptr++= 0;
break;
}
#endif
}
return 0;
}
Os tempos de execução para o código com percorrimento por palavras de 8, 32 e 64bits em uma máquina x86_64, são de: 0.190s, 0.100s e 0.025s, uma melhora de até 800%(!).
Obviamente, neste caso, um memset() seria mais rápido mas o ponto é que este conceito pode ser estendido para casos em que o memset() não serve. Ainda há espaço para mais otimizações, mas isto é deixado como exercício ;)
Obs.: lembre-se que o comprimento de long varia de acordo com a arquitetura e é prudente colocar trechos que dependem disso dentro de #ifdefs.
Leia também um artigo relacionado, sobre o aproveitamento da memória cache nesta dica do Eduardo.
Lembrando que para programas que são escritos para serem portáveis (todos deveriam ser) que dependem do tamanho da variável, é recomendado usar os tipos definidos no stdint.h, como por exemplo int32_t, uint32_t: variáveis inteiras de 32 bits, com e sem sinal, respectivamente.
Bem lembrado!
Eu *provavelmente* devo estar fazendo alguma coisa errada, mas se tento executar este código dá:
//———————————————————————
adedasil@axon:~/prog$ ./a.out
*** stack smashing detected ***: terminated
Aborted (core dumped)
//———————————————————————
Loaded symbols for /lib/ld-linux.so.2
Core was generated by `./a.out’.
Program terminated with signal 6, Aborted.
#0 0xffffe410 in __kernel_vsyscall ()
(gdb) bt
#0 0xffffe410 in __kernel_vsyscall ()
#1 0xb7e03770 in raise () from /lib/tls/i686/cmov/libc.so.6
#2 0xb7e04ef3 in abort () from /lib/tls/i686/cmov/libc.so.6
#3 0xb7e38d0b in __fsetlocking () from /lib/tls/i686/cmov/libc.so.6
#4 0xb7ebce41 in __stack_chk_fail () from /lib/tls/i686/cmov/libc.so.6
#5 0x08048490 in main () at what_heck.c:34
(gdb)
//———————————————————————
Alguém confirma?
sim, esse programa esta bem errado.
Program received signal SIGSEGV, Segmentation fault.
0x08048411 in main () at 5.c:24
24 *iptr++ = 0;
(gdb) print *iptr
Cannot access memory at address 0x4
e porque tem um outro for? “for (i= max>>2-1; i>=0; –i)”? e que diabos de for é esse? :)
swap de 2 para a direita do valor de max.? realmente nao entendi o pq dele. alias…
voce ja esta apontando um ponteiro int para o buffer, e somando-o.. ou seja. voce ja esta percorrendo a array de 4 em 4 bytes. nao tem pq ter um for ai.
Esse for nao faz sentido se o objetivo é apenas zerar a variavel. um *iptr=0 ja seta todos os 4 bytes para 0.
e o *iptr++ ja aponta para os proximos 4 bytes.
Muito interessante! Dá um pouco mais de trabalho, mas é bom saber disso! Sempre acabo me esquecendo dessas técnicas, parece que elas não “grudam” na minha cabeça, hehehe.
Só não sei por que escrever ((1<<2)-1) quando dava pra escrever simplesmente 3! À primeira vista, pensei que fosse para parametrizar de acordo com o tamanho do int, mas não é o caso…
pode ser que eu seja louco mas
uint64_t *lptr;
lptr = buffer;
for (i=0; i<1000/sizeof(uint64_t); i++){
lptr[i] = (uint64_t)0;
}
for (i=(1000/sizeof(uint64_t))*sizeof(uint64_t); i<1000; i++){
buffer[i] = (char)0;
}
ja resolve. *os casts não são stritamente necessário. **utilizar um inteiro de 64 bits é melhor ainda.
além disso, você obviamente esta querendo complicar algo simples
max>>2 == max/2
switch (max&((1<<2)-1)) // <== resto da divisão
{
case 3: *ptr++= 0; // sem break
case 2: *ptr++= 0; // sem break
case 1: *ptr++= 0;
break;
}
e eu não consigo pensar em algum caso em que o memset não serve para inicializar um vetor.