Assembly vs. [coloque-sua-linguagem-de-programacao-favorita-aqui]

O termo versus dá uma idéia de briga. Parece que estou prestes a defender Assembly com unhas e dentes e dizer que é melhor do que qualquer outra coisa. Antes que você pense, isso não vai acontecer! =D O que vou mostrar aqui é apenas um comparativo que fiz há uns 4~5 anos atrás e que por algum motivo que eu ainda não sei qual, passou pela minha cabeça denovo recentemente.

Nessa época eu estava no quinto período e era monitor de Assembly na faculdade. Sim, eu fui monitor de assembly! E tem mais, nessa mesma época, empolgado com a monitoria, reescrevi o clássico snakeinteiramente em Assembly.

A idéia de fazer essa comparação (naquela época) veio porque eu estava aprendendo sobre linguagens compiladas e interpretadas. E todo mundo sabe que, na teoria um código implementado em uma linguagem interpretada não pode ser mais rápido do que esse mesmo código implementado em uma linguagem compilada.

Por mesmo código entenda: Implementação dos mesmos algoritmos.

Isso acontece pois para a linguagem interpretada existe uma camada a mais para que o código seja efetivamente executado, o que não acontece com a linguagem compilada já que essa é transformada diretamente em código de máquina.

O que faremos será bem simples. Vamos calcular o MMC para ~700.000 pares de números gerados aleatoriamente (na verdade eu gerei 10k e repliquei até o total) e marcar quanto tempo demoramos para terminar esses cálculos. Teremos duas versões da função int mmc(int a, int b). Uma escrita em assembly e outra escrita em uma linguagem interpretada. Para a versão em Assembly, a parte principal do programa, responsável por ler os dados e chamar a funcção mmc será escrita em C. A outra versão será escrita toda na linguagem interpretada escolhida.

Isso pode nos levar a pensar que o um dos programas estará em vantagem, pois por ter sua parte principal escrita em C, sua execução seria um pouro mais rápida. Isso não é verdade já que na contagem do tempo de cálculo levaremos em consideração apenas o tempo gasto executando a função mmc. Logo o tempo gasto para ler os dados será desconsiderado nas duas versões.

Descrição do algoritmo usado no cálculo do MMC

É importante descrever o algoritmo para que a contagem do tempo seja a mais justa possível. Como pseudo-código é para os fracos segue o código das  implementações.

mmc.py

class Mmc:
 def calcula(self, a, b):
   menor = a;
   if (b < a):
     menor = b

   if (menor == 1):
     return 1

   for i in range(2, menor+1):
     if ((a % i < 1) and (b % i < 1)):
       return i

   return a * b

mmc.S

global mmc

section .text
mmc: ;int mmc(int a, int b);

  ;precisamos salvar o que vamos usar
  push ebx
  push ecx
  push edx

  mov eax, [esp+16] ; primeiro parametro
  mov ebx, [esp+20] ; segundo parametro

  cmp eax, ebx
  jnc eax_maior
  push eax ; se der carry eax < ebx. Colocamos eax na pilha
  jmp eax_menor
eax_maior:
  push ebx
  mov ebx, eax ;guardamos o maior numero em ebx
eax_menor:

; no final, eax possui o menor parametro e ebx, o maior

  pop eax ;pegamos o valor do menor que estava da pilha
  cmp eax, 2h
  jnc comeca ; se der carry, eax tem valor < 0 (ou 0 ou 1), então o mmc será 1
  mov eax, 1h ;mmc entre qualquer coisa e 1 é 1! =D
  jmp retorna

comeca:
  push eax ;eax ainda possui o menor parametro
  mov ecx, 1h
proximo_candidato:
  pop eax
  push eax ; salva eax na pilha para as próximas iterações
  inc ecx
  xor edx, edx ;zera parte alta

  div ecx ;quociente em eax, resto em edx
  cmp edx, 0h
  jz testa_outro_parametro ;se o primeiro numero divide,
                           ;temos que ver se o segundo também divide
  jmp proximo_candidato ;se nao divide, já podemos testar o proximo cantidado a mmc

testa_outro_parametro:
  mov eax, ebx ; movemos o maior parametro para fazermos o teste da divisão
  xor edx, edx ; parte alta

  div ecx
  cmp edx, 0h
  jz achou_mmc ;se o segundo também não divide,
               ;temos que ver se já iteramos até o valor do menor parametro
  pop eax
  push eax
  cmp ecx, eax
  jc proximo_candidato ;se ainda *não* iteramos até o valor do menor parametro
                       ;temos que continuar
  jmp iteracao_completa
achou_mmc:
  ;Se chegamos até aqui é porque
  ;os dois parametros sao divisiveis por ecx, então achamos o mmc.
  ;É o valor que está em ecx
  pop eax ;precisamos desempilhar para deixar a _stack_ intacta.
  mov eax, ecx
  jmp retorna

iteracao_completa:
  ; Quando iteramos até o valor do menor numero
  ; temos duas possibilidades:
  ; 1 Ou o maior numero *não* é divisivel pelo menor, nesse caso mmc = menor * maior
  ; 2 Ou o maior *é* divisível pelo menor, nesee caso mmc = menor
  mov eax, ebx
  div ecx ;Como iteramos até o valor do menor, ecx está com esse valor ao final da iteração
  cmp edx, 0h
  jz mmc_em_ecx
  ;se nao divide, então mmc = maior * menor
  pop eax
  mul ebx
  jmp retorna
mmc_em_ecx:
  pop eax
retorna:
  pop edx
  pop ecx
  pop ebx
  ret

Primeiro vamos fazer uma comparação mais grosseira, vendo apenas quanto tempo cada programa demora pra rodar.

Comparação do tempo de cálculo, incluindo tempo de I/O

Comparação do tempo de cálculo, incluindo I/O

Veja que a diferença é absurda! Mas temos que lembrar que nesse tempo está incluído o tempo gasto para ler os dados! Sabemos que isso pode distorcer completamente o resultado dos testes. Para termos uma contagem mais próxima do real temos que dispensar o tempo gasto com leitura dos dados e contar apenas o tempo gasto no cálculo dos MMC’s.

Para isso usaremos uma ferramenta especializada nesse tipo de atividade, o GNU Prof. Com ele poderemos calcular o tempo exato gasto apenas na execução do cálculo do MMC. Não entrarei em detalhes em como usar o gprof pois não é a intenção desse post. Vou apenas usá-lo e mostrar os resultados.

Para que seja possível visualizar as informações de profiling temos apenas que compilar o código com a opção -pg que gera informações de profiling para o gprof poder analisar mais tarde.

Para gerar os dados de profiling, basta rodar o programa normalmente. Ele vai gerar o arquivo gmon.out que será usado pelo gprof.

Implementação em Assembly

Contagem do tempo de cálculo com gprof

Contagem do tempo de cálculo com gprof

A saída do gprof está cortada pois o que nos interessa é quanto tempo ficamos dentro da função mmc, que nesse caso foi 8.83s

Implementação em Python

Para fazer o profiling no código python vamos usar o modulo cProfile, distribuído junto com o próprio python.

Saída gerada pro profiler do python

Saída gerada pro profiler do python

Aqui, o que nos interessa é quando tempo ficamos dentro do método Mmc.calcula(), que nesse caso foi 390.134s (aprox. 6,5 min)

Veja que a diferença continua grande e que no final das contas, para esse caso, até que o tempo de leitura dos dados não alterou tanto os resultados.

Para termos uma outra idéia, vamos fazer a mesma comparação com um código escrito em C.

mmc.c

int mmc(int a, int b){
 int i;
 int mmc = 0;

 int menor = a;
 if (b < a){
   menor = b;
 }

 if (menor == 1) return 1;

 for (i = 2; i <= menor; i++){
   if ((a % i) == 0 && (b % i) ==0){
     return i;
   }
 }

 if (!mmc){
   mmc = a * b;
 }

 return mmc;
}

Contagem de tempo para código em C, incluindo I/O

Contagem de tempo para código em C, incluindo I/O

Agora usando o profiling para saber o tempo exato gasto na função mmc

Saída go gprof para o código em C

Saída go gprof para o código em C

Veja que a diferença se torna minima! Isso porque o programa em C é transformado em código de máquina, o que o faz rodar muito mais rapidamente.

Mas porque então todo mundo não escreve código sempre em assembly, já que ele é tão mais rápdo?

Resposta rápida:

Código em asembly é muito dificil de manter/escrever/debugar e isso torna o desenvolvimento muito caro. Se você fica muito pouco tempo sem programar em assembly já é suficiente para você esquecer algumas manhas. Não vejo C há uns 4 anos e mesmo assim não demorei mais que 40 minutos para escrever o mmc (e com testes unitários!), agora o código em assembly me tomou alguns fins de semana, inteiros!

Poucas são as pessoas que olham para um código assembly e dizem: “Ah, mas é claro que esse “xor eax, eax / div ecx / mul ebx / ret” está errado! Mas como eu não vi isso antes? Estava aqui o tempo todo!”. Se você é uma dessas pessoas, ok! Senão, continue com sua linguagem predileta! =D

Todo o código usado para escrever esse post está disponível. Não deixe de comentar se tiver observado algum erro nas comparações e/ou no cálculo dos tempos! Espero não ter cometido nenhuma injustiça nos cálculos!

, ,

  1. #1 por Eusyar em 01/06/2010 - 19:52

    Pô cara, post Top Foda… Muito bom msm, esse treco de assembly é faca na caveira. TENSO =D

  2. #2 por Neto em 06/10/2010 - 14:39

    Como sempre dizem e nem por isso deixa de ser verdade, toda linguagem compilada será mais rápida que as interpretaas por magnitude,salvo raras exceções, como JIT com loops acima de 10.000 laços.

    Mas eu sempre digo, um código BEM ESCRITO em c++ será sempre mais rápido que JAva ou C#, o mesmo serve para C, Pascal e Assembly.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: