1

Estou estudando uma linguagem de assembly de aprendizado. Nela tenho duas implementações de função fatorial que gostaria de saber se podem ser consideradas basicamente equivalentes.

TL;DR

No final da postagem há a verdadeira pergunta, na qual tento sintetizar as minhas dúvidas. As duas implementações estão um pouco abaixo.

Contexto das implementações

A linguagem é para uma máquina simples de dezesseis registros (r0 a r15).

As duas implementações que vou mostrar usando essa linguagem não empilham dados (isto é, não usam stack). (Obs.: qual palavra estou querendo usar no lugar de dados? Seria estado de execução, contexto de execução?)

Em vez disso usam o registro r1 para o parâmetro de entrada e r2 para a saída (resultado do fatorial).

Por simplicidade ela não faz nenhum tipo de tratamento de exceções, como por exemplo argumentos negativos.

Também, exceto pela comparação com zero (jeqzn), não existe opcode para comparação de igualdade.

O registro de retorno das funções fica em r14.

As duas implementações

A implementação-exemplo é assim (junto com um "pseudo-C" que fiz nos comentários para auxiliar a compreensão):

0 read r1
1 calln r14, 4
2 write r2
3 halt

# Função fatorial
4 setn r2, 1      # 4: r2 = 1;
5 jeqzn r1, 9     # 5: if (r1 == 0) goto 9;
6 mul r2, r1, r2  # 6: r2 = r1 * r2;
7 addn r1, -1     # 7: r1--;
8 jumpn 5         # 8: goto 5;
9 jumpr r14       # 9: return r2;

Esta é minha implementação:

0 read r1
1 calln r14, 4
2 write r2
3 halt

# Função fatorial
4 copy r2, r1     # 3: r2 = r1;
5 addn r1, -1     # 4: r1--;
6 jeqzn r1, 9     # 5: if (r1 == 0) goto 9;
7 mul r2, r1, r2  # 6: r2 = r1 * r2;
8 jumpn 5         # 7: goto 5;
9 jumpr r14       # 8: return r2;

A princípio são bem parecidas

O princípio das duas é quase igual: se N = 3, multiplica-se 3 * 2 * 1 (isto é, vai-se decrementando o N) e quando este chega a 0 retorna o resultado sem fazer nova multiplicação. Não deveria haver grande diferença entre elas, em princípio.

Elas podem ser consideradas equivalentes em princípio, do ponto de vista de implementarem ideias de algoritmo parecidas e terem desempenho aproximadamente equivalente?

Obs.: Essa pergunta é feita com uma certa ingenuidade, no sentido que não estou pensando em uma situação em que a performance da implementação seja crítica e precise ser "espremida" ao máximo causando um impacto significativo, digamos em um laço com muitas repetições.

Instrução por instrução parece que sim, com uma (supostamente) negligível diferença entre setn r2, 1 e copy r2, r1.

A diferença entre elas é que uma começa com um resultado 1 e vai multiplicando por N e decrementando este N até ele chegar a zero, quando então o resultado é retornado.

Na outra começa com um valor N que é multiplicado por N - 1, decrementa-se N, multiplica-se o resultado por N - 2, e assim por diante, também até chegar a zero, momento em que o resultado é retornado.

Guiando as respostas, 1-3

Como elas se comparam? Eu testei os algoritmos e ambos dão o mesmo resultado. Se isso fosse em assembly normal, seria possível dizer que são basicamente equivalentes (descontando diferenças como a que foi citada entre os semelhantes setn e copy)?

O segundo algoritmo foi uma implementação que fiz que me pareceu mais intuitiva que o primeiro (no sentido de partir de um algoritmo imaginado e seguir com sua implentação conforme vai pensando nas instruções). A implementação mais eficiente tende a ser intuitiva ou contra-intuitiva? Ou não há uma regra?

Quando você busca uma ou outra, a diferença em eficiência pode ser significativa? Ou, dado meu conhecimento precário em assembly, estou perguntando isso cedo demais para ter ideia de como isso funciona na prática?

Guiando as respostas, 2-3

Outra forma de perguntar: a dúvida é sobre uma ser melhor que a outra em termos de desempenho e outros aspectos não citados (preferência de qual adotar), sobre equivalência, sobre diferenças entre as instruções.

Teste de mesa, 1-2

Para N = 3, isso é o que o primeiro código faz (obs.: estou ignorando o custo dos jumps, deveria?):

r1 = 3;
r2 = 1;

r2 = (r1 * r2) = (3 * 1) = 3;
r1 = 2;

r2 = (r1 * r2) = (2 * 3) = 6;
r1 = 1;

r2 = (r1 * r2) = (1 * 6) = 6;
r1 = 0;

return 6;

E isso é o que o segundo código faz:

r1 = 3;
r2 = 3;

r1 = 2;
r2 = (r1 * r2) = (2 * 3) = 6;

r1 = 1;
r2 = (r1 * r2) = (1 * 6) = 6;

r1 = 0;

return 6;

Teste de mesa, 2-2

Para N = 4, isso é o que o primeiro código faz (também ignorando os jumps):

r1 = 4;
r2 = 1;

r2 = (r1 * r2) = (4 * 1) = 4;
r1 = 3;

r2 = (r1 * r2) = (3 * 4) = 12;
r1 = 2;

r2 = (r1 * r2) = (2 * 12) = 24;
r1 = 1;

r2 = (r1 * r2) = (1 * 24) = 24;
r1 = 0;

return 24;

E isso é o que o segundo código faz:

r1 = 4;
r2 = 3;

r1 = 3;
r2 = (r1 * r2) = (3 * 4) = 12;

r1 = 2;
r2 = (r1 * r2) = (2 * 12) = 24;

r1 = 1;
r2 = (r1 * r2) = (1 * 24) = 24;

return 24;

Guiando as respostas, 3-3

Com o primeiro teste de mesa reparei que somente há diferença entre as três primeiras linhas da primeira implementação e as duas primeiras linhas da segunda, isto é, depois dessas linhas é tudo idêntico.

Isso fica mais evidente no segundo teste.

Porém, não ficou muito clara para mim a diferença real. Fiquei em dúvida sobre qual é mais performático, qual é mais didático, qual é mais intuitivo, e o que esperar da eficiência quando se opta por uma dessas últimas duas qualidades.

Resumindo de uma vez: Pode-se (ou deve-se) esperar grandes diferenças mesmo se o "algoritmo" idealizado é basicamente muito parecido?

6
  • Você quer a analise comparativa da complexidade desses algoritimos? Commented 4/01/2022 às 17:17
  • @AugustoVasques Nada tão sofisticado. Só estou achando que são equivalentes em termos de lógica, e gostaria de saber se minha percepção faz sentido ou não.
    – Piovezan
    Commented 4/01/2022 às 17:18
  • Faz sentido sim, mas então eu acho que você já se respondeu ao identificar que um algoritmo calcula o produto dos termos de 1...N-1e o outro calcula o produto dos termos N-1 ...1. Commented 4/01/2022 às 17:21
  • 1
    Na verdade um faz resultado = 1; while N > 0 { resultado *= N; N--; }; return resultado; e o outro faz resultado = N; while N > 0 { N--; resultado *= N}; return resultado; então em ambos ocorre o decremento de N. Acho que vou esclarecer um pouco mais na pergunta o que espero comparar.
    – Piovezan
    Commented 4/01/2022 às 17:26
  • Exato. Desculpe se estou sendo superficial, mas estou com dificuldade em perceber em que podemos contribuir? PS: Não fui eu quem votou Commented 4/01/2022 às 17:29

1 Resposta 1

2

Tirei umas conclusões e vou arriscar uma auto-resposta, mas não sou entendido de assembly, são só observações.

O segundo teste de mesa deixa claro que somente a condição inicial muda entre as implementações, o restante tende a ficar cada vez mais parecido quanto maior for o valor do parâmetro passado para elas.

Essa semelhança mostra que nesse caso não é importante levar os jumps em consideração, mas acredito que isso pode variar a cada situação.

Então os códigos podem ser considerados basicamente equivalentes e usarem algoritmos muito parecidos, em que apenas é trocada a ordem das operações, conforme evidenciado no meu comentário em resposta ao @AugustoVasques.

Porém percebo que somente a equivalência de instruções no assembly não é garantia de equivalência da execução/desempenho, pois um trecho de instruções pode se repetir e "explodir" em termos de processamento, mesmo que dois trechos sejam a princípio bem parecidos, talvez com mudanças na ordem das operações.

Parece-me que a segunda implementação (a minha) eliminou uma redundância da primeira implementação em sua parte inicial, economizando ciclos e sendo portanto mais performática.

Sobre intuitividade e didaticidade não sei dizer bem. A minha, para mim, é mais intuitiva, porém menos didática. Não sei qual implementação seria a mais interessante de se adotar na prática (apesar que na prática não se faz nada disso, usa-se o stack, validam-se os parâmetros, e tratam-se exceções).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .