C: Performance: percorrendo vetores de bytes

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.

This entry was posted in C. Bookmark the permalink.

8 Responses to C: Performance: percorrendo vetores de bytes

  1. aristeu says:

    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.

  2. Adenilson Cavalcanti says:

    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?

  3. Fyy says:

    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

  4. Fyy says:

    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.

  5. Marcus says:

    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…

  6. Renato says:

    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.

  7. Renato says:

    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.

Comments are closed.