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?
resultado = 1; while N > 0 { resultado *= N; N--; }; return resultado;
e o outro fazresultado = 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.