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