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?

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.

Pré processador e constantes

Um amigo me mostrou um problema interessante que, confesso, levei algum tempo para resolver. O fragmento de código abaixo simplesmente não compila, causando um erro de “invalid suffix ‘…’ on integer or constant“:

/* fragmento de keys.h */
...
#define OFFSET 0x1000
...
#define ALT_1  (0xf8+OFFSET)
#define ALT_2  (0xf9+OFFSET)
#define ALT_3  (0xfa+OFFSET)
#define ALT_4  (0xfb+OFFSET)
#define ALT_5  (0xfc+OFFSET)
#define ALT_6  (0xfd+OFFSET)
#define ALT_7  (0xfe+OFFSET)
#define ALT_8  (0xff+OFFSET)
#define ALT_9  (0x80+OFFSET)
#define ALT_0  (0x81+OFFSET)
...
/* fragmento de main.c */
...
int altconvert[] = {
  ALT_A,ALT_B,ALT_C,ALT_D,ALT_E,ALT_F,ALT_G,ALT_H,
  ALT_I,ALT_J,ALT_K,ALT_L,ALT_M,ALT_N,ALT_O,ALT_P,
  ALT_Q,ALT_R,ALT_S,ALT_T,ALT_U,ALT_V,ALT_W,ALT_X,
  ALT_Y,ALT_Z,ALT_0,ALT_1,ALT_2,ALT_3,ALT_4,ALT_5,
  ALT_6,ALT_7,ALT_8,ALT_9
};

O erro aparece na linha que define o símbolo ALT_7 para o pré processador:

keys.h:97:21: error: invalid suffix "+OFFSET" on integer constant
 #define ALT_7 (0xfe+OFFSET)
                ^
main.c:9:11: note: in expansion of macro ‘ALT_7’
  ALT_6,ALT_7,ALT_8,ALT_9
        ^

Meu amigo ficou se perguntando isso não seria um bug do compilador… E a pergunta que fiquei me fazendo é: Por que diabos as definições de ALT_1 até ALT-6 e de ALT_8 e ALT_9 não deram o mesmo problema?

A diferença entre ALT_6, ALT_7 e ALT_8 é apenas uma: ALT_7 é um valor em hexadecimal terminada em ‘e’ e as demais não… Qual é mesmo a maneira de declarar constantes que tenham um ‘e’? Ahhhhh… ponto flutuante:

float c = 1e+10;

Acontece que os valores associados a ponto flutuante têm que ser expressos em decimal. Não podem ser hexadecimais… A não ser que estejamos falando do padrão C99 e, neste caso, o caractere ‘e’ teria que ser trocado por ‘p’:

float c = 0xfp+10;

Note que o expoente continua tendo que ser decimal…

No caso apresentado, o símbolo ALT_7 é definido como a string ‘0xfe+0x1000’. O ‘e’, seguido do valor inteiro, indica uma constante em ponto flutuante, mas hexadecimal… dai o erro. Que faz parte da especificação da linguagem! Não se trata de um bug!

Existem duas soluções possíveis:

  1. Colocar os valores inteiros na definição dos símbolos entre colchetes;
  2. Colocar um espaço entre os valores e o operador + (ou -).

É bom lembrar que o pré processador faz apenas substituições léxicas. Quando definimos um macro, como em:

#define advance_ptr(p) { (p)++; }

O pré compilador não efetua a operação… em qualquer parte do código onde advance_ptr for encontrado ele apenas substituirá p pelo parâmetro passado no macro… É o compilador que avaliará a operação ++, mas apenas depois que o pré compilador terminar suas substituições!

Portanto, a dica aqui é simples: Não assuma que o pré compilador “compila” alguma coisa ou avalia expressões… Nope, ele nunca fará isso!… Apenas “substituirá”. E “compilador” só tem um… a ênfase no nome deve ser no “pré”…