Mifu…

Sabem aqueles grupos onde o pessoal costuma fazer perguntas de “problemas” de cursos de graduação de computação? Do tipo “faça um programa que some 5 números…”? Well… Eu acho isso enfadonho! Mas, recentemente, topei com um que, onde “me fudi” com uma resposta irônica de minha parte (e peço desculpas, porque a solução é mesmo interessante para o aprendiz!)…

O problema era esse ai mesmo que citei acima:

“Faça um programa que leia 5 valores inteiros e apresente a soma desses valores usando apenas uma variável

A parte em negrito é a que torna o problema interessante… Normalmente o estudante usa uma variável para ler os valores e outra para acumulá-los:

/* test1.c */
#include <stdio.h>

void main ( void )
{
  int sum, n;

  scanf ( "%d", &sum );
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;}

  printf( "%d\n", sum );
}

Claro, isso usa duas variáveis, o que invalida a solução. Poderíamos usar um array:

/* test2.c */
#include <stdio.h>

void main ( void )
{
  int n[2];

  scanf ( "%d", &n[0] );
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];

  printf( "%d\n", n[0] );
}

O programa acima é, essencialmente, a mesma coisa que o anterior e o estudante pode pensar que está usando apenas uma “variável”. No entanto, um arry é uma “sequência” de variáveis (a tradução direta da palavra “array” significa “sequência”), ou seja, está usando duas variáveis. Isso invalida a parte “usar apenas uma variável” do problema. Eis a solução engenhosa:

/* test3.c */
#include <stdio.h>

void main ( void )
{
  long long n;  // n tem 64 bits de tamanho!

  scanf ( "%d", ( int * )&n );

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  printf( "%d\n", *( int * )&n );
}

Ao fazer o casting ( int * ) usamos a aritmética de ponteiros envolvendo o tipo int, que tem 32 bits de tamanho. Assim, ( int * )&n + 1 é uma expressão que é resolvida para os 32 bits superiores de n, enquanto ( int * )&n aponta para os 32 bits inferiores. Ao derreferenciar esse ponteiro, acessamos o seu valor, na pilha.

Em essência, estamos mexendo com um array, mas usando apenas uma variável!!! Isso atende a ambas os requisitos do problema, mas causa um problema de performance… Quando declaramos uma variável local qualquer o compilador, se tiver sido chamado com opções de otimização, tenta usar os registradores da CPU ao invés da pilha. Ao usar o operador & (endereço-de) forçamos o compilador a manter a variável na pilha. Como os scanf precisam do endereço da variável lida, os três programas, acima, geral praticamente o mesmíssimo código… Assim, cada chamda a scanf e cada acumulação usará um ou mais acessos à memória que, mesmo estando no cache L1d, poderá adicionar 1 ciclo de clock adicional às instruções (resolução do endereço efetivo).

A rotina abaixo, mais tradicional, tem o potencial de ser bem mais rápida e gastar menos espaço no cache L1i:

/* test4.c 
   Compile com: 
     gcc -O2 -fno-stack-protector -w -o test4 test4.c 
*/
#include <stdio.h>

void main ( void )
{
  int sum, n, count;

  count = 5;
  sum = 0;
  while (count--)
  {
    scanf ( "%d", &n );
    sum += n;
  }

  printf( "%d\n", sum );
}

Posso mostrar que count e sum não são mantidos na memória, mas em registradores. Apenas n não é otimizado dessa forma por causa do operador &:

; test4.asm - equivale a test4.c.
bits 64
section .rodata
scanf_fmt:  db `%d`
printf_fmt: db `%d\n`

section .text
global main
main:
  push rbp
  push rbx

  xor  ebp,ebp  ; sum=0
  mov  ebx,5    ; count=5

  sub  rsp,24   ; reserva espaço na pilha, alinhando-a

.loop:
  lea  rsi,[rsp+12]  ; n está alocado na pilha em rsp+12.
  xor  eax,eax       ; scanf() precisa disso (porquê?)
                     ; EAX, aqui, NÃO é stdin!
  mov  edi,scanf_fmt
  call __isoc99_scanf

  add  ebp,[rsp+12]  ; sum += n;
  sub  ebx,1         ; --count;
  jne  .loop         ; if (count != 0) goto loop.

  mov  edx,ebp
  mov  esi,printf_fmt
  mov  edi,1         ; stdout
  xor  eax,eax       ; printf() precisa disso (porquê?)
  call __printf_chk

  add  rsp,24   ; dealoca espaço previamente alocado na pilha.

  pop  rbx
  pop  rbp
  ret

Se não fosse pela necessidade do scanf, n também seria mantido em um registrador (R12D, por exemplo). Mas, note que temos apenas UM acesso à memória por iteração do loop (em add ebp,[rsp+12], mas, é claro, scanf também acessa memória!). No caso de test3.c temos 9 indireções, além das causadas pelo scanf, no caso de test4.c, 5.

Ahhh… lea rsi,[rsp+12] não é uma indireção, mas somente o cálculo do endereço efetivo…

Embora o exercício seja interessante, não passa de curiosidade acadêmica…

Anúncios

O bom, o mal e o feio

Neste artigo vou tentar mostrar 3 coisas: O algoritmo mais óbvio raramente é o melhor possível, um bom algoritmo pode ser sempre melhorado e que essa melhoria nem sempre vem sem custos. A ideia é usar um algoritmo custoso, em termos de processamento e, para isso, aqui vão os famosos testes para determinação se um valor inteiro positivo é ou não um número primo.

Nesses testes usarei o tipo unsigned int porque ele tem 32 bits de tamanho em ambas as plataformas Linux (e na SysV ABI) e Windows, tanto para o modo de operação do processador, x86-64 e i386. É bom reparar nisso, porque a determinação desse tipo de parentesco (se é primo!) em valores inteiros com mais bits pode ser muito demorada. Por exemplo, quando lidamos com o esquema de criptografia assimétrica, é comum o uso de chaves de 2048 bits de tamanho, o que torna uma das otimizações inviável (veremos adiante).

O feio

O algoritmo clássico é varrer toda a faixa de valores menores que o valor sob teste e verificar se existe algum divisor exato. Algo assim:

// Método tradicional: Tenta dividir todos os valores 
// inferiores a 'n' e conta quantos o dividem...
NOINLINE
int ugly_is_prime ( unsigned int n )
{
  unsigned int count, i;

  // caso especial.
  if ( !n ) 
    return 0;

  count = 1;
  for ( i = 2; i < n; i++ )
    if ( ! ( n % i ) )
      count++;

  return (count == 1);
}

Por que chamei essa rotina de “o feio”? Ela testa por todos os valores inferiores a n, começando por 2, se n for diferente de zero! Suponha que n=4294967291. Esse valor é primo, mas para a rotina determinar isso terá que percorrer todos os valores entre 2 e 4294967290. Veremos que, para isso, a rotina gasta cerca de 47 bilhões de ciclos de clock!

O mau

É claro que não precisamos verificar todos os valores! Por exemplo, 2 é o único valor par que também é primo. De cara podemos testar se n é par e diferente de 2. Se for, com certeza não é primo. Isso nos deixa os valores ímpares para teste, o que diminui pela metade o esforço computacional.

Outra melhoria que podemos fazer é a de que, de acordo com o Princípio fundamental da aritmética, todo número pode ser fatorado em números primos… Por exemplo, 9=3\cdot3, 10=2\cdot5, 76=2\cdot\cdot2\cdot19 e assim por diante (voltaremos a isso no algoritmo “bom”). Ainda, “lembre-se que a ordem dos fatores não altera o produto”. Tome 10 como exemplo… Ele pode ser escrito como 10=2\cdot5=5\cdot2.

Não é evidente, mas graças a isso só precisamos testar por divisores ímpares menores ou iguais a raiz quadrada de n:

// Método "ruim" (mas, melhor que o acima).
// Faz a mesma coisa, mas só verifica os valores inferiores a 'n' 
// que sejam ímpares e menores ou iquais a raiz quadrada de 'n'.
int bad_is_prime ( unsigned int n )
{
  unsigned int sr;
  unsigned int i;

  // casos especiais.
  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  };

  // O único par primo é 2.
  if ( ! ( n & 1 ) )
    return 0;

  // Obtém o valor ímpar menor ou igual
  // à raíz quadrada de n.
  sr = sqrt(n);
  if ( ! ( sr & 1 ) ) 
    sr--;

  // Só precisamos testar os valores ímpares
  for ( i = 3; i <= sr; i += 2 )
    if ( ! ( n % i ) )
      return 0;

  return 1;
}

Aqui tomo um atalho para os 2 primeiros primos (1 e 2) para simplificar a rotina.

Mas, porque essa rotina é ? O problema aqui é que, mesmo eliminando testes, estamos testando muitos valores mais de uma vez… Por exemplo, se n não for divisível por 3 ele também não será para nenhum múltiplo de 3, como 9, 12, 15, 18, 21, 24, 27… No entanto, estamos testando esses valores também, se n for grande!

O bom

A solução, é claro, é eliminar todos os valores múltiplos dos anteriores, ou seja, usar apenas divisores primos. O problema é óbvio: Ora, bolas! Como é que eu vou fazer uma rotina que testa se um valor é primo usando como critério o teste se um divisor também o é?!

O método de Erastótenes (276 AEC ~ 194 AEC) mantém uma sequência onde marcamos os valores primos, percorrendo a lista do início ao fim, e verificando se os próximos valores são múltiplos. Se forem, marcamos como “não primo”. Na próxima interação, o próximo valor é, com certeza, primo e repetimos o processo, até que todo o array contenha apenas os primos “não marcados”. Isso exige que toda a faixa de valores seja colocada no array, mas os valores usados como base de testes podem ser limitados à valores menores ou iguais a raíz quadrada de n, como fizemos anteriormente.

O ponto negativo desse método, é claro, é o consumo excessivo de memória para conter todo o array, mas, e se mantivéssemos apenas um array com os valores primos ímpares inferiores ou iguais à raiz quadrada da faixa do tipo unsigned int? Isso não consumirá tanta memória quanto você pode imaginar: Em primeiro lugar, no pior caso, teríamos um array com \frac{\sqrt{2^{32}-1}}{2}\approx32767 itens. Se cada item tem 4 bytes de tamanho, aproximadamente 128 KiB serão usados para o array. No caso mais prático, vários valores desses 32767 são eliminados, porque não serão primos.

O programinha abaixo, que usa o bad_is_prime(), acima, monta esse array:

// gentable.c
//
// Cria tabela contendo os inteiros, primos, menores ou iguais ao
// valor ímpar mais pŕoximo (porém menor) que a raiz quadrada de 2³²-1.
//
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

extern int bad_is_prime ( unsigned int );

#define ITEMS_PER_LINE 16

void main ( int argc, char *argv[] )
{
  FILE *f;
  unsigned int i, sr;
  unsigned int count = 0, cnt2 = 0;

  if ( ! *++argv )
  {
    fputs ( "Usage: gentable <cfile>\n", stderr );
    exit ( 1 );
  }

  if ( ! ( f = fopen ( *argv, "wt" ) ) )
  {
    fprintf ( stderr, 
              "ERROR opening file %s for writing.\n", 
              *argv );
    exit ( 1 );
  }

  fputs ( "// *** criado por gentable.c ***\n\n"
          "// tabela começa de 3...\n"
          "const unsigned int primes_table[] = {\n", f );

  // ~0U é o máximo valor de unsigned int.
  // Obtém a raiz quadrada ímpar...
  sr = sqrt(~0U);
  if (!(sr & 1)) 
    sr--;

  // Só precisamos dos inteiros ímpares e primos.
  for ( i = 3; i <= sr; i += 2 )
    if ( bad_is_prime ( i ) )
    {
      if ( count ) 
      {
        fputc( ',', f );

        if (++cnt2 == ITEMS_PER_LINE)
        {
          fputc ( '\n', f );
          cnt2 = 0;
        }
        else
          fputc ( ' ', f );
      }

      fprintf ( f, "%uU", i );
      count++;
    }

  fprintf ( f, "\n};\n\n"
            "// tabela ocupa %zu bytes.\n"
            "const unsigned int primes_table_items = %u;\n",
            sizeof ( unsigned int ) * count, 
            count );

  fclose ( f );
}

Basta compilar e executar o programinha para gerar um arquivo texto contendo o código fonte de uma tabela com apenas as raízes quadradas desejadas! No caso, gerarei table.c que, como pode ser observado, contém 6541 valores, ocupando apenas 25.5 KiB:

// *** criado por gentable.c ***

// tabela começa de 3...
const unsigned int primes_table[] = {
3U, 5U, 7U, 11U, 13U, 17U, 19U, 23U,
29U, 31U, 37U, 41U, 43U, 47U, 53U, 59U, 
61U, 67U, 71U, 73U, 79U, 83U, 89U, 97U,
...
... 65447U, 65449U, 65479U, 65497U, 65519U, 65521U
}; 

// tabela ocupa 26164 bytes.
const unsigned int primes_table_items = 6541;

Para essa tabela de raízes o processamento é rápido. Considere o caso de valores de 64 bits. A máxima raiz quadrada é 4294967295. Como verificar se um valor é primo é relativamente lento, pré-calcular toda a tabela pode demorar um bocado… Existe ainda o fator espaço, que explico abaixo.

Usando essa tabela, a nossa rotina de teste good_is_prime fica assim:

extern const unsigned int primes_table[];
extern const unsigned int primes_table_items;

// Método "melhor": Faz quase a mesma coisa que acima, mas
// usa uma tabela pré calculada.
int good_is_prime ( unsigned int n )
{
  unsigned int i, sr, *p;

  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  }

  if ( ! ( n & 1 ) )
    return 0;

  sr = sqrt(n);

  for ( i = 0, p = (unsigned int *)primes_table; 
        i < primes_table_items && *p <= sr; 
        i++, p++ )
  {
    if ( ! ( n % *p ) )
      return 0;
  }

  return 1;
}

Ela é bem parecida com bad_is_prime, mas usa uma tabela contendo apenas valores primos para os testes!

Nem sempre usar tabelas pré-calculadas é uma boa ideia

Em primeiro lugar, poderíamos usar uma tabela pré-calculada com todos os valores primos na faixa e a rotina final poderia ser uma simples busca binária, daí a performance da rotina seria proporcional a \log_2{n}, mas é claro que a tabela final seria enorme. Daí, escolhi armazenar apenas os valores que serão usados para verificar o divisor, eliminando os múltiplos…

A quantidade de valores primos, dado um valor máximo, pode ser aproximado (de longe!) por:

\displaystyle \Pi(x)\sim\frac{x}{\log{x}-1}

Assim, se quisermos montar uma tabela com todos os primos inferiores ou iguais à raiz quadrada do maior valor possível para um tipo, como no exemplo de unsigned int (que assume o valor máximo de 2^{32}-1), temos que o maior valor para a tabela é r_{max}=\lfloor\sqrt{2^{32}-1}\rfloor e, portanto, usando a aproximação acima, teríamos uma tabela com cerca de 17171 itens. Cada item cabe em 2 bytes (unsigned short), já que r_{max}=65535. O que nos daria um array de, no máximo, 33.5 KiB. Se usarmos unsigned int (como fiz) o array estimado ficaria com 67 KiB.

Observe o contraste com o que encontramos através de gentable.c… Temos menos da metade dessa quantidade! Mas isso não é garantido! Temos que assumir que a aproximação acima é uma quantidade média e usarmos como critério para estimar o custo da rotina.

Considere agora, 64 bits. Usando o mesmo critério, r_{max}=\lfloor\sqrt{2^{64}-1}\rfloor=4294967295, que cabe num unsigned int. Daí \Pi(r_{max})\approx497508081 itens com 4 bytes cada, ou seja, quase 2 GiB de array. Repare que dobramos o número de bits da faixa sob teste, mas o tamanho da tabela aumentou quase de 29 mil vezes.

Isso é esperado porque a estimativa é exponencial (proporcional a \frac{1}{\log{x}-1})… Então, não recomendo o método good_is_prime para valores com mais de 32 bits.

O quão bom é o “bom”?

No pior caso bad_is_prime é 10 milhões de vezes mais rápida que ugly_is_prime e good_is_prime é quase 4 vezes mais rápida que bad_is_prime (o que faz dela quase 40 milhões de vezes mais rápida que ugle_is_prime).

Estou informando esses valores, mas os medi, usando meu “contador de ciclos do homem pobre” em alguns casos:

  • Melhor caso: Um valor não primo pequeno;
  • Pior caso: Um valor primo muito grande: 4294967291
  • Um valor não primo grande cujos fatores sejam primos grandes: 144795733, por exemplo, pode ser fatorado em 12343 e 11731.

Em alguns casos, no “melhor caso” e somente às vezes, bad_is_prime ganha de good_is_prime, mas isso ocorre, provavelmente, por causa dos efeitos do cache L1 (que só tem 32 KiB!). Isso, talvez, possa ser compensado fazendo um prefetch da tabela antes de executar a rotina… Esse é especialmente o problema quando o valor não é primo! Quando a rotina precisa varrer grande parte do o array os efeitos do cache L1 entram em ação e ela fica um pouco mais lenta que a “má” rotina…

Prática horrível: Uso de MAX_PATH

Eis algumas coisas que considero muito erradas quando alguém tenta criar alguns tipos corriqueiros de rotinas: usar a pilha inescrupulosamente, e achar que o tamanho máximo de um pathname é de 260 caracteres. Ambas costumam levar a problemas sérios… Eis um exemplo:

void faz_algo(void)
{
  char fname[MAX_PATH+1];
  char *p;

  getcwd(fname, MAX_PATH);
  p = fname + strlen(fname) - 1;
  if (*p == '//') *p = '\0';
  strcat(fname, "/o-nome-maluco-de-algum-arquivo.txt");
  ...
}

Aqui, além do buffer apontado por fname ser alocado na pilha, gastando mais que 260 bytes, já que a pilha tem que estar, necessariamente, alinhada e ainda existe a red-zone, esse buffer tem tamanho máximo que parece bom… O que acontece se o diretório corrente for algo assim: /home/frederico/files/br/com/xpto/alpha/beta/theta/caralhos-me-levem/abobora/? Well… Ainda é provável que isso caiba num buffer de 260 caracteres, mas saiba que em certos ambientes o path máximo pode ter de 32 KiB! É o caso, por exemplo, do Windows (veja aqui).

A ideia do esquema acima pressupõe que tenhamos espaço suficiente e evita alocação dinâmica e, de bandeja, livra-se do buffer quando a função terminar. É interessante, mas não é assim que as linguagens que possuem o tipo primitivo para strings funciona. Eis uma maneira de fazer, com alocação, que não fica tão estranha assim:

char *fname, *cwd;

// get_current_directory() é uma extensão da glibc que
// aloca espaço da string pra você!
cwd = get_current_directory();

// asprintf() aloca espaço suficiente para todos os
// caracteres da string resultante!
asprintf(&fname,
         "%s/o-nome-maluco-de-algum-arquivo.txt",
         cwd);

// Não precisamos mais do bloco alocado em cwd.
free(cwd);
...
// Livra-se do buffer apontado por fname...
free(fname);

Ficou mais complicado? Que nada! O único detalhe é que você terá que se livrar dos buffers manualmente.

Os mais atentos verão que não faço nenhuma checagem de falha. Isso porque a alocação de pedaços pequenos de memória quase nunca falham. E free não liga se o ponteiro contém NULL… Mas, mesmo que isso seja importante pra você, alguns simples if‘s resolvem tudo.

Para lidar com strings dinâmicamente você pode, até mesmo, usar realocação, como, por exemplo:

char *_str_concat(char **pp, const char * const *s)
{
  char *tmp;
  size_t size;

  size = strlen(s);
  if (*pp) size += strlen(*pp);

  if (tmp = realloc(*pp, size+1))
  {
    *pp = tmp;
    strcat(*pp, s);
  }
  return *pp;
}

Neste caso, se o ponteiro para sua string for NULL, realloc alocará o espaço desejado (do mesmo tamanho da string apontada por s), caso contrário, os dois tamanhos são adicionados, o espaço da string original é aumentado e depois a concatenação é feita. O uso da dupla indireção pode te confundir, mas o uso é bem simples:

char *s = NULL;

_str_concat(&s, "Fred");
_str_concat(&s, " é ");
_str_concat(&s, "bom nisso!");
...
// Não se esqueça de livrar-se da string
free(s);

No fim das contas, o ponteiro s apontará para um buffer dinamicamente alocado contendo apenas a string “Fred é bom nisso\0“.

Você pode até mesmo garantir que sua string seja declarada corretamente usando uma macro:

#define DECLARE_STRING(name) char *name = NULL

Para usar, é claro, basta fazer DECLARE_STRING(s);, ao invés de escrever char *s = NULL;. E no caso do free, você pode fazer:

// Chame da mesma forma que chamou _str_concat.
void DELETE_STRING(char **pp)
{ if (*pp) free(*pp); *pp = NULL; }

Uma operação de assinalamento numa string já alocada não poderia ser mais simples:

char *_str_assign(char **pp, char *s)
{
  DELETE_STRING(pp);
  _str_concat(pp, s);
}

Todas as outras funções de string.h continuam funcionando do mesmo jeito e, ao contrário da crença “popular”, alocações de pequenos blocos são realmente rápidas. Você ainda pode criar rotinas de housekeeping, assim:

void alguma_funcao(void)
{
  jmp_buf jb;
  DECLARE_STRING(s);

  if (setjmp(jb))
  {
    // Coloque aqui seus DELETE_STRING()...
    DELETE_STRING(&s);
    return;
  }

  ...

  // Antes de sair chame longjmp()! :)
  // Não esqueça de fazer isso tb se tiver algum "return"
  // no código, fora daquele bloco de setjmp(), ai em cima...
  longjmp(jb, 1);
}

É claro, você pode criar MACROS para simplificar a coisa, tipo: DECLARE_HOUSEKEEPING, que declarará jb, HOUSEKEEPING que declarará o if (setjmp(jb)) e EXIT_FUNCTION, que chamará o longjmp(jb, 1):

// Coloque essas 3 num header!
#define DECLARE_HOUSEKEEPING jmp_buf _jb
#define HOUSEKEEPING if (setjmp(_jb))
#define EXIT_FUNCTION longjmp(_jb,1)

void alguma_funcao(void)
{
  DECLARE_HOUSEKEEPING;
  DECLARE_STRING(s);

  HOUSEKEEPING
  {
    // Coloque aqui seus DELETE_STRING()...
    DELETE_STRING(&s);
    return;
  }

  ...

  // Antes de sair chame EXIT_FUNCTION :)
  // Não esqueça de fazer isso tb se tiver algum "return"
  // no código, fora daquele bloco de setjmp(), ai em cima...
  EXIT_FUNCTION;
}

Ficou mais fácil de ler?

Meu problema com “inovações” e “coisas modernas” (ou “o que diabos é OOP”?)

Que estou ficando “velho” não é novidade nenhuma, faço questão de lembrar meus leitores (especialmente no Facebook) o tempo todo desse fato. Aliás, só para levantar uma pequena lebre, é bom que você entenda isso: Todos nós estamos ficando velhos! Não é óbvio?

Em grupos que criei, no interesse de compartilhar conhecimento (assim como esse blog, que foi criado pelo meu amigo Marcio Rezende), tenho recebido algumas “críticas” a respeito de minhas preferências por “bare metal programming” ou, simplesmente, de ser um “dinossauro”. Isso parte, geralmente, de pessoas que estão cursando faculdade e dando ouvidos para seus professores “moderninhos” que, provavelmente, nunca fizeram nada mais complexo do que um “hello world” em C e não têm nenhuma compreensão do que um compilador realmente faz.

Entendam, não há nada intrinsecamente errado em aprender uma nova linguagem de programação ou aproveitar abstrações interessantes em projetos, onde você não quer ter o trabalho de pensar muito. Para isso existem scripts, frameworks e “ambientes gerenciados”, como JVMs e .NET. E, não bastasse as abstrações oferecidas pela “linguagem”, desde os anos 80, a moda ainda corrente é “programação orientada a objetos” como forma de abstração de implementação (pra quê, por exemplo, eu preciso saber o que é um descritor de arquivos se eu posso simplesmente “instanciar” uma classe num “objeto” e usar seus métodos?)… Abstrações são, precisamente, como uma barreira entre como uma coisa realmente funciona e como você pode usá-la. Você não tem que saber como a gasolina é bombeada, queimada e descartada no motor do seu carro para ir do ponto A para o ponto B, certo?

Meu problema é quando se leva isso à sério demais. Pessoas que enchem o meu já velho (dinossaurico?) saco dizendo coisas do tipo “C é obsoleto” ou “Assembly é arcaico” me deixam nervoso (bem… nem tanto, me deixam mais é rindo da ignorância!). O pensamento aqui é que essas “linguagens” não são “orientadas a objeto” e, portanto, devem ser desconsideradas, enterradas junto com o Latim, o Grego Antigo e o Esperanto… Agora, peça para essas pessoas definirem o que significa “orientação a objetos” e vejam-nas listar o que ela faz, mas não o que ela é e nem mesmo qual problema real ela tenta resolver…

O que, diabos, é um objeto?

Se você fizer essa pergunta para uma criança de 5 anos de idade, garanto que vai ver no rostinho dela aquela expressão de “Esse sujeito só pode ser um idiota!”… Em termos gerais um objeto é uma manifestação física de alguma coisa. Simples assim.

Pense numa xícara… Essa xícara que você evocou a imagem na sua cabeça é uma entidade hipotética, possivelmente uma generalização de uma xícara real que você já viu, alguma vez (daí o termo “imagem”: o que você vê num espelho não é o objeto em si, mas um reflexo impreciso dele [no sentido que essa “imagem” não é tridimensional, por exemplo]), ou seja, é uma estrutura que ainda não existe no mundo real (porque está só na sua cabeça!). A partir do momento que você tem uma xícara real na sua frente, de preferência com café dentro, você tem um “objeto”.

Você só pode chamar o objeto real de xícara porque a estrutura, ou forma, da xícara que você pensou é uma “classe” de objetos possíveis, com atributos mais ou menos bem definidos do que deve ser uma xícara. Em termos de programação, uma “classe” é um monte de atributos que serão manipulados por um monte de funções (ou “procedimentos”). Mas, não só isso: Essa “classe” pressupõe que você possa criar “instâncias” com atributos isolados. Você pode pensar numa xícara, mas pode construir várias xícaras com base nesse “gabarito” mental, certo?

Neste aspecto, o simples código abaixo implementa uma “classe”:

struct myclass {
  int x;
};

// Função que "cria" uma instância da classe.
void myclass_create(struct myclass *this) 
  { this->x = 0; }

// Função que "destrói" um objeto.
void myclass_destroy(struct myclass *this) {}

// "setter" e "getter" do atributo x.
void myclass_setX(struct myclass *this, int x) 
  { this->x = x; }
int  myclass_getX(struct myclass *this) 
  { return this->x; }

Para os puristas, a implementação acima é exatamente o que algo que uma linguagem como C++ implementaria (note que o destrutor myclass_destroy é irrelevante aqui!). É claro, C++ esconde alguns desses detalhes de implementação, fazendo que pareça que o que acontece, por baixo dos panos seja quase mágica. Por exemplo, o ponteiro this passado para todas as funções é implícito, em C++.

O fato é que, até mesmo um tipo primitivo como int é uma classe. De fato, esses tipos são chamados, também, de “classes de armazenamento” (não é interessante isso?). E uma variável desses tipos são objetos ou instâncias da classe (do tipo)… Felizmente o compilador sabe como lidar com eles: a forma como uma operação aritmética é feita com um int não é a mesma que o compilador usará para lidar com o tipo (classe) float, por exemplo.

Então, um objeto é tão somente a manifestação física de uma forma. Mas e aquela história toda de encapsulamento e polimorfismo? Bem… isso são “coisinhas a mais” que alguém criou para parecer que objetos são coisas mais especiais que “estruturas”. São benefícios, mas não fazem parte da definição.

Qual a diferença entre os modelos “orientados a objetos” e “estruturados”?

Dizem, por ai, que o modelo “estruturado” é ultrapassado e deveria deixar de ser usado. Mas, como? Um objeto não é uma manifestação de uma “estrutura”? Se tirarmos o conceito de estrutura do assunto, um objeto obviamente jamais poderá existir! Só que não é disso que estão falando…

A questão da obsolescência do modelo “estruturado” em relação ao “orientado a objetos” refere-se à análise de sistemas, não sendo aplicável às linguagens de programação! Aqui vale entender o que significam as palavras “análise” e “sistema” (suponho que você saiba o que significa a preposição “de”!). Por “análise”, podemos contrastar com o conceito antagônico de “síntese”. Enquanto síntese é o processo de juntar partes num todo, análise é obter, do todo, suas partes… Quando alguém diz que vai “analisar o problema”, quer dizer que vai tentar “desmembrá-lo” em partes menores para poder entendê-las e, depois, “sintetizar” tudo, de alguma forma, para poder entender o referido problema… Já “sistema” significa somente um conjunto de peças ou coisas separadas que interagem com um objetivo comum… Repare que “análise de sistemas” é um termo baseado em redundância, uma vez que um “sistema” é, de fato, uma síntese de coisas e só é possível “analisar” alguma coisa se ela puder ser desmembradas em pedaços menores (“desintetizado”, por assim dizer).

As analogias com um veículo motorizado ou uma equipamento eletrodoméstico qualquer são bons exemplos do que um sistema é: Você, provavelmente, não sabe como uma geladeira funciona por dentro, mas sabe pra quê ela serve! Alguém que ganhe a vida consertando geladeiras precisa saber como ela funciona, em cada um de seus detalhes, separadamente… Acontece que geladeiras e carros são construídos de forma padronizada, “sistemas” do mundo real são, mais ou menos, caóticos… Para analisar um sistema desse tipo existem diversos métodos diferentes, formas de descobrir e criar especificações de como o troço todo funciona ou como criaremos alguma ferramenta que nos permita “padronizar” esse caos. É ai que entra a “análise de sistemas”.

Em qualquer “análise de sistemas” o objetivo é descobrir as estruturas que manipularemos e os procedimentos que as manipularão. No modelo “estruturado” a ênfase é separar estruturas e procedimentos. Já no modelo de “[estruturação] orientada a objetos” a ênfase continua sendo nas estruturas e procedimentos (só pode!), mas a ideia é agregá-los, de alguma forma.

A análise “orientada a objetos” surgiu por causa de um problema no modelo “estruturado”: Existe a tendência de haver um espalhamento de dados por todo o sistema. Na aproximação orientada a objetos tenta-se “aglutinar” os dados e os procedimentos que os manipulam numa única estrutura, que chamamos de “classe”, fazendo com que esses dados sejam acessíveis de apenas um lugar (na instância do objeto).

OO (orientação a objetos) é, então, apenas um meio de “não espalhar” dados, mas também precisa oferecer um meio de comunicação ou “relacionamento” entre os objetos (generalizações, associações, agregações, composições), já que não é mais possível acessar dados diretamente, senão voltaríamos ao modelo estruturado. Isso também existe na análise estruturada, mas de uma forma mais solta, menos “padronizada”…

Programação “orientada a objetos” não tem relação direta com análise!

É nesse ponto que surge uma confusão dos diabos: As ditas “linguagens orientadas a objetos” oferecem meios de “encapsulamento” (assim como na análise) e “generalizações” (normalmente chamada de “herança”), mas deixa de lado todo o resto, ficando a cargo do programador como agregações e composições, bem como a troca de mensagens, sejam organizadas. Daí a dificuldade em mapear, diretamente, esses últimos conceitos numa linguagem de programação (no diagrama de classes, em UML, uma agregação é aquele losago branco, mas uma composição é um losango preto – ambas são “a mesma coisa” com semânticas ligeiramente diferentes: Uma agregação é “opcional”, já a composição é “obrigatória”, por assim dizer)…

Acontece que esses conceitos podem ser implementados facilmente em qualquer linguagem. No exemplo em C que dei lá em cima, a estrutura myclass encapsula um objeto inteiro e poderia ter uma lista de outros objetos. Também, as funções que manipulam as “instâncias” do objeto da “classe” myclass além de serem nomeados com o nome da classe (prefixo “myclass_”), tomam como primeiro argumento um ponteiro para um objeto dessa mesma classe (e, para ficar claro, nomeia-o de this). Essa técnica meio que garante o encapsulamento (obviamente) e a aglutinação de métodos relacionados à instância de uma classe (objetos). Mas, é claro, poderia ser feito de forma diferente:

struct myclass {
  int x;

  // Destrutor
  void (*destroy)(struct myclass *);

  // setter e getter.
  void (*setX)(struct myclass *);
  int  (*getX)(struct myclass *);
};

// Ninguém precisa acessar diretamente essas funções!
static void myclass_destroy(struct myclass *);
static void myclass_setX(struct myclass *, int);
static int  myclass_getX(struct myclass *);

// O construtor continua sendo externo à "classe"...
void myclass_create(struct myclass *this) 
{ 
  // Inicialize os ponteiros para as "funções-membro".
  this->dtor = myclass_destroy;
  this->setX = myclass_setX;
  this->getX = myclass_getX;

  // Inicializa o objeto encapsulado.
  this->x = 0; 
}

void myclass_destroy(struct myclass *this) { }

void myclass_setX(struct myclass *this, int x) 
  { this->x = x; }
int  myclass_getX(struct myclass *this) 
  { return this->x; }

Agora, para criar um objeto da classe myclass e manipulá-la, o que tenho que fazer é:

struct myclass obj;

myclass_create(&obj);  // constrói o objeto.

obj->setX(&obj, 10);
printf("%d\n", obj->getX(&obj));

obj->destroy(&obj);      // destrói o objeto.

O que uma linguagem como C++ faz é esconder esses ponteiros this e fazer de conta que o construtor seja parte da classe, entre outras coisas:

struct myclass {
  int x;

  myclass();
  ~myclass();

  void setX(int);
  int getX(void);
};

myclass::myclass() { x = 0; }
myclass::~myclass() {}

void myclass::setX(int x) { this->x = x; }
int myclass::getX(void) { return this->x; }

Herança e polimorfismo em C

Notem que “herança” e “polimorfismo” podem ser implementados através de “promoções de tipos” sem problemas. Um exemplo é a estrutura de lista encadeada com batentes (já falei delas aqui) que poderiam ser implementadas com nós “genéricos”, assim:

struct node { struct node *next; };

Para criar um nó com dados reais poderíamos especificar:

struct data_node { struct data_node *next; int data; };

Do ponto de vista do código gerado pelo compilador, um ponteiro é apenas um endereço para alguma coisa na memória, o tipo associado existe para facilitar a avaliação de expressões envolvendo ponteiros (se incrementar um ponteiro para a estrutura data_node a este endereço será somado 8 [no modo i386] ou 12 [no modo x86-64]), porque o tipo int tem 4 bytes e o ponteiro tem tamanho diferente, de acordo com a arquitetura em uso. Mas um endereço contido em qualquer ponteiro é um valor inteiro de tamanho fixo, sempre… Assim, tudo o que você tem que fazer nas rotinas de manipulação de lista é fazer um casting para o ponteiro correto, já que ambas as estruturas começam com um endereço:

void list_insert_after(void *this_node, void *new_node)
{
  struct node *this, *next, *new;

  // pointer aliasing...
  this = (struct node *)this_node;
  new = (struct node *)new_node;
  next = this->next;
  this->next = new;
  new->next = next;
}

Ponteiros para void ajudam bastante aqui porque podem receber, ou serem usados, como um tipo “coringa”. Note que tanto faz passarmos ponteiros para node ou data_node ou qualquer outro tipo, desde que na estrutura apontada o primeiro atributo seja um ponteiro e que a estrutura tenha a mesma semântica (que seja um nó de uma lista). De fato, podemos até mesmo fazer a “herança” assim:

struct data_node { struct node _base; int data; };

Isso, é claro, é uma “composição”… A vantagem é que essa estrutura, sob o ponto de vista das funções de manipulação de lista como list_insert_after, acima, continuará funcionando igualzinho, mas agora temos um membro _base de onde podemos obter um atributo da classe “base”…

Deu para notar que já temos encapsulamento, generalizações (herança) e polimorfismo… o que mais falta para você perceber que OOP não tem nada a ver com OO (análise)?

Mas, encapsulamento não é só definir uma estrutura!

Esse é o argumento que alguns podem externar, afinal, existem níveis de proteção de membros de classe, certo? Um membro pode ser dito “privado” ao objeto ou “público”, para uso dos usuários dele… Acontece que isso não é parte do que é um objeto, é um “recurso extra” implementado pelo conceito de objeto… Se você pensar bem, pra que serve isso, de fato?

Considere que você definiu uma classe com um membro de dados privado porque ele só deve ser usado pelas funções membro da própria classe. É como se, conceitualmente, esse fosse um “estado intero”… depois de codificar umas 523 funções de um sistema, você percebe que, em algum ponto, precisa ter acesso a aquele estado privado. Você pode fazer três coisas para remediar isso:

  1. Mudar o privilégio de privado para publico para o estado em questão;
  2. Adicionar umas funções-membro públicas getter e setter na classe base;
  3. Herdar a classe base e adicionar getter e setter na nova generalização.

Em todas as três possibilidades você violou o princípio da acessibilidade que tanto preza. Seu membro “privado” acabou de se tornar “público”, mas de forma indireta (itens 2 e 3) ou diretamente (item 1). Na prática a privacidade ou “publicidade” de um membro de um objeto é apenas conceitual.

Tá certo que alguns design patterns usam o recurso do privilégio de acesso à membros para implementar coisas interessantes (como o padrão singleton, por exemplo), mas nada que não possa ser feito conceituando um membro como privado…

Mas, Fred, não é você quem diz que OOP é uma droga?

Sou eu mesmo! Mas, por favor, entenda o contexto… Como já deve ter ficado claro para quem tem algum bom senso, OOP é um modelo de abstração que, por definição, esconde um monte de implementações do programador. Se você ainda duvida disso, recomendo que estude as especificações mais recentes das linguagens C++ e Java e compare-as com a especificação, também mais recente, de C… Em resumo, a quantidade de regras de uso de alguma abstração chega a ser impossível de manter na cabeça de alguém (exemplos disso são as diferenças entre os diversos tipos de construtores [default, de cópia, de movimentação, de conversão, etc] e estilos de codificação de sobrecarga de operadores [qual é a diferença entre ++ pós e pré?]), templates, etc…

Quando falo mal de OOP eu me refiro à qualidade do código criado por compiladores que lidam com essas abstrações… Se a perda de velocidade de execução e o espaço usado para conter as funções compiladas não forem fatores decisivos no seu projeto e se você sabe exatamente o que está fazendo ao usar uma abstração, não há nada errado em preferir C++, Rust, Go, e até mesmo Java ou C# (“até mesmo”… well, não é novidade o meu despreso por ambas!)… O contexto ao qual me refiro não é somente a qualidade do código gerado mas, também, alguns artifícios usados pelo compilador para garantir que a coisa toda funcione (name mangling, em C++, e a famigerada virtual methods table, usada por todas as linguagens OOP)…

A qualidade do código só pode ser avaliada objetivamente se obtivermos uma listagem em Assembly e/ou se passarmos pelo crivo de um bom profiler, como o V-Tune, IDA, radare ou até mesmo o perf. Ou seja, se medirmos o continuum (espaço e tempo). Como medida didática só posso oferecer um exemplo bem simples: O famoso “hello, world”, implementado em ambos C e C++ da forma didática padrão.

Em C:

/* helloc.c */
#include <stdio.h>

void main(void) { puts("hello, world"); }

E em C++:

// hellocc.cc
#include <iostream>

int main() { std::cout << "hello,world" << std::endl; }

Estou usando std::endl aqui, mas prefiro não usá-lo normalmente pelo motivo que ficará claro, logo. Este é apenas o método mais usual… Agora, vejam as listagens da função main dos dois programas, compilados com a máxima otimização (-O2), para x86-64:

; helloc.c
; Código equivalente NASM, compilado com
;   cc -O2 -o helloc helloc.c
  bits 64
  default rel

  section .rodata
msg:
  db  `hello, world\0`

  section .text

  extern puts

  global main
main:
  lea  rdi,[msg]
  jmp  puts

Compare, agora, o mesmo código gerado para C++ e me responda sinceramente: Isso é “melhor”?

; hellocc.cc
; Código equivalente NASM, compilado com
;   c++ -O2 -o hellocc hellocc.cc
  bits 64
  default rel

  section .rodata

msg:
  db  `hello, world\0`

  section .text

  extern _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
  extern _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_

  global main
main:
  sub  rsp,8
  mov  edx,12
  lea  rsi,[msg]
  lea  rdi,[_ZSt4cout]
  call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
  lea  rdi,[_ZSt4cout]
  call _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
  xor  eax,eax
  add  rsp,8
  ret

  section .text.startup

  extern _ZStL8__ioinit
  extern _ZNSt8ios_base4InitC1Ev
  extern __dso_handle
  extern __cxa_atexit

  global _GLOBAL__sub_I_main
_GLOBAL__sub_I_main:
  sub rsp, 8
  lea rdi, [_ZStL8__ioinit]
  call  _ZNSt8ios_base4InitC1Ev
  lea edx, [__dso_handle]
  lea esi, [_ZStL8__ioinit]
  lea edi, [_ZNSt8ios_base4InitD1Ev]
  add rsp, 8
  jmp __cxa_atexit

O esquema de name mangling de C++ é tão esquisito que os nomes dos símbolos têm que incorporar os tipos de retorno, as referências à classe e a lista de argumentos, fazendo com que o nome da função chamada tenha 78 caracteres de tamanho e seja ilegível! Parece até que um gato de estimação andou no teclado pra dar o nome a esses símbolos, não é? E esse, obviamente, não é o pior problema de C++!

Repare que, para cada objeto global o compilador é obrigado a incorporar uma função que será atribuída ao tratador de saída (atexit e que a referência a std::endl é, na verdade, uma chamada de função… Bastava incorporar um ‘\n’ no final da string para evitar essa chamada (e este é o motivo pelo qual prefiro não usar std::endl, se tiver que lidar com C++ num terminal).

Velho dá trabalho, mas geralmente vale a pena…

Seja no sentido familiar, seja sobre coisas velhas, geralmente o que é antigo funciona “melhor” porque foi experimentado e testado tantas vezes e por tanta gente (“coisas velhas”, não estou falando de sua avó!) que não incorrem em problemas imprevistos de aproximações mais “modernas”. Ou seja, “tradições” existem por motivos práticos…

Se você ainda duvida disso, um exemplo tecnológico são as GUIs (Graphical User Interfaces) que não mudaram de estrutura nos últimos 40 anos: As janelas continuam sendo retangulares (mesmo que com bordas e “decorações”), o mouse conntinua sendo representado por uma “setinha”, o texto que você digita continua sendo sucedido por uma “barrinha vertical” ou “cursor” (piscando ou não)… É claro que houveram pequenas melhorias na “experiência” (no sentido da satisfação) gráfica, como quando você arrasta uma janela, todo o conteúdo visível vem junto (antes vinha apenas um “frame”), etc… mas, em essência, GUIs são como são desde que foram criadas, lá nos anos 70 dos idos do século XX.

Como vimos sobre “análise”, tanto a estruturada quando OO surgiram pela necessidade de esmiuçar um “sistema” e descobrir suas partes. Pressupõe-se que OO “facilitaria” o trabalho, mas ela apresenta diversos problemas piores que a aproximação estruturada: Os objetos precisam estabelecer algum tipo de relacionamento entre si, já que o objetivo é conter os estados no interior de estruturas, isolando os estados compartilhados, mesmo assim, outros objetos podem querer saber em estado essses “objetos interos” se encontram… Isso é feito, na OO, por “troca de mensagens” (onde o “como” não é definido! pode ser de qualquer forma, sendo que a preferida é a chamada de métodos)… Isso pressupoe, também, que essa troca de mensagens seja feita de forma organizada, no mínimo, hierarquica (o funcionário de baixo-nível pergunta pro gerente, que pergunta pro CEO… esse tipo de coisa). Como essa estruturação de comunicação entre objetos deve ser bem definida, é comum que tenhamos que quebrar as regras para obter acesso “direto” a algum estado encapsulado, fazendo com que, na prática, o estado isolado torne-se compartilhado de novo – dai a “solução” OO para os estados compatilhados espalhafatosos cai por terra… Em outros termos, seu grafo de relacionamentos torna-se tão complexo que fica inviável mantê-lo (levando embora o argumento da “estensibilidade” facilitada!).

Junte isso aos ambientes gerenciados (JVM e .NET)… A ideia é que, já que os estados são segregados, não precisaríamos mais nos preocupar com os estados compartilhados e, por isso, podemos ter um meio de nos livrarmos de objetos que tenham sido usados e, agora, estejam fora de uso… e de forma automática! Isso pressupoe que seu grafo de comunicação entre objetos seja previsível… mas, acontece que as regras de hierarquia previstas em OO são facilmente quebradas criando estados compartilhados, fazendo com que essa “gerência” não seja tão boa assim, causando leakages (vazamentos) ou deadlocks (inter-travamentos?). Sem contar que, mesmo que funcionem, os garbage collectors (GCs) vêm em diversos sabores… Python, por exemplo, implementa via reference counting, o que cria alguns problemas com referências circulares (a mesma coisa acontece com a implementação da Microsoft Common Object Model)… Java e .NET implementam os GCs geracionais (o que tende a deixar um monte de objetos “no limbo”)… Esses problemas podem ser resolvidos com a aproximação “estruturada” com algum cuidado, mas na OOP são muito difíceis de lidar graças a própria abstração, tão amada por todos.

O jeito velho é sempre melhor, nesses casos… mas, de novo, dá mais trabalho.

Teimosia…

Tem gente teimosa que insiste em fazer as coisas da forma errada… Neste artigo eu informei a meus leitores, explicitamente, que a string que deve ser passada para a função setlocale segue os padrões ISO 639 e ISO 3166. Alguns acreditam que isso só vale para ambientes Unix e que no Windows a coisa é “mais fácil”… A insistência, é claro, é pela passagem de strings como “Portuguese” ou “Portugues”, como em:

// Isto está ERRADO!!!
setlocale(LC_ALL, "Portuguese");

A função setlocale(), como descrita na MSDN Library (aqui), diz claramente: “The set of locale names supported by setlocale are described in Locale Names, Languages, and Country/Region Strings.” e o tópico em questão nos diz: “The locale name form—for example, en-US for English (United States) or bs-Cyrl-BA for Bosnian (Cyrillic, Bosnia and Herzegovina)—is preferred“.

Mais um exemplo para comprovar que, mesmo o Windows, usa o padrão para locale, é usar uma função da Win32 API para obter o locale padrão do sistema:

#include <stdio.h>
#include <wchar.h>
#include <windows.h>

void main(void)
{
  wchar_t locale[LOCALE_NAME_MAX_LENGTH+1];

  // Usando Win32 API para obter o locale padrão!
  // GetSystemDefaultLocaleName() exige um ponteiro
  // para wide string.
  GetSystemDefaultLocaleName(locale, 
                             LOCALE_NAME_MAX_LENGTH);
  wprintf(L"%ls\n", locale);
}

Ao compilar e executar o programinha acima, usando o MinGW64, obtemos:

$ x86_64-w64-mingw32-gcc -O2 -o locale.exe locale.c
locales.c: In function ‘main’:
locales.c:8:3: warning: implicit declaration of function ‘GetSystemDefaultLocaleName’ [-Wimplicit-function-declaration]
   GetSystemDefaultLocaleName(locale, LOCALE_NAME_MAX_LENGTH);
   ^
... Copiando o locale.exe para o Windows e executando:
C:\Work> locale
pt_BR

Yep… tem esse aviso ai (provavelmente estou esquecendo de definir algum símbolo para compilar código para versão do Windows superior ao Vista), mas o linker não reclamou, então ele conseguiu resolver a referência corretamente…

Note que a própria Win32 API prefere o padrão ISO!

Mais uma vez: Nem sempre é bom desenvolver diretamente em assembly!!!

Sim… de fato, a máxima “Não existe melhor otimizador do que o está entre suas orelhas” continua sendo verdadeira, só que essa massa de carne nem sempre realiza o melhor trabalho. Eis um caso onde uma rotina simples deveria ser mais rápida se feita em ASM:

uint16_t cksum(void *data, size_t length)
{
  uint32_t sum;
  uint16_t *p = data;
  _Bool rem;

  sum = 0;
  rem = length & 1;
  length >>= 1;

  while (length--)
    sum += *p++;

  if (rem)
    sum += *(uint8_t *)p;

  while (sum >> 16)
    sum = (sum & 0xffff) + (sum >> 16);

  return ~sum;
}

Essa é a implementação do cálculo de CHECKSUM de 16 bits, de acordo com a RFC 1071 (aqui). O código é bem simples e deveria gerar uma listagem em assembly tão simples quanto, mas quando você compila com a máxima otimização consegue ums listagem enorme que, inclusive, na plataforma x86-64, usa até SSE!

A minha implementação da rotina acima, em puro assembly e “otimizada”, para a plataforma x86-64, seria essa:

  bits 64

  section .text

  global cksum2

; uint16_t cksum2(void *data, size_t length);
  align 16
cksum2:
  xor   eax,eax   ; sum = 0;
  xor   ecx,ecx   ; RCX será usado como índice...
  shr   rsi,1     ; # de words!
  jnc   .even     ; Se CF=0, RSI era par!

  ; Ao invés de adicionar o byte extra no final,
  ; optei pelo início.
  movzx dx,byte [rdi]
  add   ax,dx
  inc   rdi
  jmp   .even

  ; Loops geralmente são críticos. Note que optei
  ; por colocar o teste no final, deixando o salto
  ; conticional para trás para não ferir o
  ; algoritmo estático do "branch prediction".
  ; Também, o ponto de entrada alinhado aos 16 bytes
  ; ajuda com possíveis efeitos negativos com o 
  ; cache L1i...
  align 16
.loop:
  add   ax,[rdi+rcx*2]
  adc   ax,0
  dec   rsi        ; length--;
  inc   rcx        ; próxima word...
.even:
  test  rsi,rsi    ; length == 0?
  jnz   .loop      ; não! continua no loop.
  
  not   ax         ; sum = ~sum;
  ret

Compare essa minha rotina com a gerada pelo compilador:

cksum:
  mov   r11,rsi
  shr   rsi
  push  rbp
  and   r11d,1
  test  rsi,rsi
  push  rbx
  je    .L2
  mov   rdx,rdi
  lea   r10,[rsi-1]
  and   edx,15
  shr   rdx
  neg   rdx
  and   edx,7
  cmp   rdx,rsi
  cmova rdx,rsi
  cmp   rsi,10
  ja    .L74
  mov   rdx,rsi
.L3:
  cmp   rdx,1
  lea   rcx,[rdi+2]
  movzx eax,WORD PTR [rdi]
  lea   r8,[rsi-2]
  je    .L5
  movzx r8d,WORD PTR [rdi+2]
  lea   rcx,[rdi+4]
  add   eax,r8d
  cmp   rdx,2
  lea   r8,[rsi-3]
  je    .L5
  movzx r8d,WORD PTR [rdi+4]
  lea   rcx,[rdi+6]
  add   eax,r8d
  cmp   rdx,3
  lea   r8,[rsi-4]
  je    .L5
  movzx r8d,WORD PTR [rdi+6]
  lea   rcx,[rdi+8]
  add   eax,r8d
  cmp   rdx,4
  lea   r8,[rsi-5]
  je    .L5
  movzx r8d,WORD PTR [rdi+8]
  lea   rcx,[rdi+10]
  add   eax,r8d
  cmp   rdx,5
  lea   r8,[rsi-6]
  je    .L5
  movzx r8d,WORD PTR [rdi+10]
  lea   rcx,[rdi+12]
  add   eax,r8d
  cmp   rdx,6
  lea   r8,[rsi-7]
  je    .L5
  movzx r8d,WORD PTR [rdi+12]
  lea   rcx,[rdi+14]
  add   eax,r8d
  cmp   rdx,7
  lea   r8,[rsi-8]
  je    .L5
  movzx r8d,WORD PTR [rdi+14]
  lea   rcx,[rdi+16]
  add   eax,r8d
  cmp   rdx,8
  lea   r8,[rsi-9]
  je    .L5
  movzx r8d,WORD PTR [rdi+16]
  lea   rcx,[rdi+18]
  add   eax,r8d
  cmp   rdx,10
  lea   r8,[rsi-10]
  jne   .L5
  movzx r8d,WORD PTR [rdi+18]
  lea   rcx,[rdi+20]
  add   eax,r8d
  lea   r8,[rsi-11]
.L5:
  cmp   rsi,rdx
  je    .L6
.L4:
  mov   rbx,rsi
  sub   r10,rdx
  sub   rbx,rdx
  lea   r9,[rbx-8]
  shr   r9,3
  add   r9,1
  cmp   r10,6
  lea   rbp,[0+r9*8]
  jbe   .L7
  pxor  xmm0,xmm0
  lea   r10,[rdi+rdx*2]
  xor   edx,edx
  pxor  xmm2,xmm2
.L8:
  movdqa  xmm1,XMMWORD PTR [r10]
  add   rdx,1
  add   r10,16
  cmp   r9,rdx
  movdqa  xmm3,xmm1
  punpckhwd xmm1,xmm2
  punpcklwd xmm3,xmm2
  paddd xmm0,xmm3
  paddd xmm0,xmm1
  ja    .L8
  movdqa  xmm1,xmm0
  sub   r8,rbp
  lea   rcx,[rcx+rbp*2]
  psrldq  xmm1,8
  paddd xmm0,xmm1
  movdqa  xmm1,xmm0
  psrldq  xmm1,4
  paddd xmm0,xmm1
  movd  edx,xmm0
  add   eax,edx
  cmp   rbx,rbp
  je    .L6
.L7:
  movzx edx,WORD PTR [rcx]
  add   eax,edx
  test  r8,r8
  je    .L6
  movzx edx,WORD PTR [rcx+2]
  add   eax,edx
  cmp   r8,1
  je    .L6
  movzx edx,WORD PTR [rcx+4]
  add   eax,edx
  cmp   r8,2
  je    .L6
  movzx edx,WORD PTR [rcx+6]
  add   eax,edx
  cmp   r8,3
  je    .L6
  movzx edx,WORD PTR [rcx+8]
  add   eax,edx
  cmp   r8,4
  je    .L6
  movzx edx,WORD PTR [rcx+10]
  add   eax,edx
  cmp   r8,5
  je    .L6
  movzx edx,WORD PTR [rcx+12]
  add   eax,edx
.L6:
  test  r11,r11
  lea   rdi,[rdi+rsi*2]
  je    .L71
.L17:
  movzx edx,BYTE PTR [rdi]
  add   eax,edx
  mov   edx,eax
  shr   edx,16
  test  edx,edx
  je    .L75
.L49:
  movzx eax,ax
  add   eax,edx
.L71:
  mov   edx,eax
  shr   edx,16
  test  edx,edx
  jne   .L49
.L75:
  not   eax
.L67:
  pop   rbx
  pop   rbp
  ret
.L74:
  test  rdx,rdx
  jne   .L3
  mov   r8,r10
  mov   rcx,rdi
  xor   eax,eax
  jmp   .L4
.L2:
  test  r11,r11
  je    .L76
  xor   eax,eax
  jmp   .L17
.L76:
  mov   eax,-1
  jmp   .L67

UAU! Obviamente a minha rotina é mais rápida que esse caminhão de instruções, certo? (aliás, repare nas instruções entre os labels .L8 e .L7! hehe)

Infelizmente os testes mostram que não! Comparando o cálculo do checksum de um buffer de 2 KiB (menos 1 byte para termos um buffer de tamanho impar, ou seja, o pior caso), a minha rotina é 5 vezes mais lenta que a gerada pelo compilador! Num de minhas máquinas de teste obtive, para cksum(), 3432 ciclos e para cksum2(), 16872!

É interessante notar que se mudarmos o código em C para efetuar a adição do byte isolado, se houver um, a performance vai ser semelhante à obtida em cksum2():

uint16_t cksum3(void *data, size_t length)
{
  uint32_t sum;
  uint16_t *p = data;

  sum = 0;
  if (length & 1)
    sum += *(uint8_t *)p++;
  length >>= 1;

  while (length--)
    sum += *p++;

  while (sum >> 16)
    sum = (sum & 0xffff) + (sum >> 16);

  return ~sum;
}

E, também, se mudar o meu código para efetuar a soma do byte adicional no final, se houver um, como na rotina original, a performance continuará tão ruim quanto:

  align 16
cksum4:
  xor   eax,eax
  xor   ecx,ecx
  mov   edx,esi
  and   edx,1
  shr   rsi,1
  jmp   .even

  align 16
.loop:
  add   ax,[rdi+rcx*2]
  adc   ax,0
  dec   rsi
  inc   rcx
.even:
  jnz   .loop
  test  edx,edx
  jz    .exit
  add   ax,[rdi+rcx*2]
  adc   ax,0
.exit:
  not   ax
  ret

Ou seja, o compilador está tomando conta dos possíveis efeitos no cache e desenrolando os loops para que atinja a melhor performance possível, mesmo que, para isso, gere um código bem maluco. Coisa que apenas com muita experiência eu ou você poderíamos fazer…

Novamente, sempre meça a performance de seus códigos e não pense que só porque está em “assembly” é que você conseguirá a melhor performance!

Arredondamento. Qual é o “correto”?

O último artigo gerou alguma controvérsia… Alguns leitores perguntam: “Qual é o jeito certo?” e não se satisfazem com a resposta de que ambos os métodos, de truncamento e de arredondamento para baixo, estão certos, dependendo da aplicação. Aqui quero provocá-los mostrando algo similar…

Já mostrei antes que operações em ponto flutuante dependem de algum método de arredondamento bem definido. O padrão IEEE 754 define quatro deles:

  • No sentido de +\infty;
  • No sentido de -\infty;
  • No sentido de 0;
  • O valor “mais próximo”;

Ao calcular f=1.0/10.0, o valor 0.1, que não pode ser representado numa variável do tipo ponto flutuante, já que, em binário, será uma dízima periódica:

\displaystyle (0.1)_{10} = (0.0110011001100110011001100...)_{2}

Portanto, precisa ser arredondado. Se estivermos lidando com o tipo float esse valor será (1.1001100110011001100110?)_{2}\cdot 2^{-2}, onde ‘?’ é o algarismo impreciso… Ou seja, se ele for zero, termos um valor levemente inferior a 0.1, se ele for 1, teremos um valor levemente superior a 0.1. Qual deles devemos escolher?

Por default, o padrão IEEE 754 escolhe o método do “mais próximo”. Repare:

/* test.c */
#include <stdio.h>

extern float _mydiv(float, float);

void main(void)
{
  float f;
  unsigned int d = 0x3dcccccc;
  float *g = (float *)&d;
  unsigned int *p = (unsigned int *)&f;

  f = _mydiv(1.0f, 10.0f);

  printf("O valor '%.2f' é codificado como '0x%08X'.\n\n", 
    f, *p);

  printf("Mas, na verdade:\n"
         "0x%08X -> %.18f\n"
         "0x%08X -> %.18f\n",
    *p, f,
    d, *g);
}

O motivo de criar a função _mydiv é para evitar que o compilador otimize a operação de divisão entre duas constantes e não faça divisão alguma. Neste caso, o arredondamento será feito pelo compilador, não pelo nosso programa. A função _mydiv é, simplesmente:

/* mydiv.c */
float _mydiv(float a, float b) 
{ return a/b; }

Compilando e linkando tudo e depois executando, temos:

$ gcc -o test test.c mydiv.c
$ ./test
O valor '0.10' é codificado como '0x3DCCCCCD'.

Mas, na verdade:
0x3DCCCCCD -> 0.100000001490116119
0x3DCCCCCC -> 0.099999994039535522

É fácil perceber que o primeiro caso está mais próximo de 0.1 do que o segundo e é este que o processador escolherá (como isso é feito não interessa agora!). Mas, isso não significa que os outros métodos de arredondamento não sejam “corretos”. De fato, se mandarmos o processador arredondar de outra maneira ele o fará, Eis um exemplo:

/* test.c */
#include <stdio.h>
#include <fenv.h>

extern float _mydiv(float, float);

void main(void)
{
  float f;
  int oldround;

  oldround = fegetround();
  fesetround(FE_TOWARDZERO);
  f = _mydiv(1.0f, 10.0f);
  fesetround(oldround);

  printf("%.18f\n", f);
}

Ao compilar e executar esse código (será preciso especificar a libm com -lm, no gcc) você verá que a divisão de 1 por 10 será arredondada para o MENOR valor, ou melhor, em direção ao zero. Esse será o valor mais distante do verdadeiro, neste caso. Troque 1.0f por -1.0f e veja o que acontece…

Depois, modifique o método para FE_DOWNWARD (arredondamenteo no sentido de -\infty) e teste os dois casos (com 1.0f e -1.0f)… Note que o truncamento citado no artigo anterior é equivalente a FE_TOWARDZERO…

O que quero dizer aqui é que, tanto na programação quanto na matemática, às vezes existe mais de um jeito “correto” de fazer alguma coisa. Depende apenas da aplicação.