Hanoi towers as a pure recursion benchmark, part 1 – Introduction

· May 29, 2005

The final purpose of this will be analyzing the performance differences between native C++ and managed C++, with a focus on them coexisting in the same process.
Too often, whenever one mentions .NET technologies, he gets various comments on performance hits for his applications. Is this truth or myth ?

The first benchmark we’re going to use is a simple one. Simple doesn’t mean it isn’t effective as a measurement solution; however its result might not reflect real world situations. The example is a classic problem in recursion : Hanoi towers. You can get more information, as well as a running demo of the problem, here.

The code to solve Hanoi towers is (C, but easily portable to C# or Java – remove the printf !) :

int Hanoi(int from, int to, int use, int howmany)
{
if (howmany == 1)
{
printf("Moving a piece from %d to %d\n", from, to);
return 1;
}
else
{
int imovs = 0;
imovs += Hanoi(from, use, to, howmany - 1);
imovs += Hanoi(from, to, use, 1);
imovs += Hanoi(use, to, from, howmany - 1);
return imovs;
}
}

It prints the required moves, and returns the total number of moves done. The from and to parameters are the starting and destination pegs, the use parameter is the third peg (note that there is effectively no need to pass this parameter to each call, since it can be calculated with use=6-from-to; ). howmany is the number of disks (pieces) to be moved from the from peg to the to peg.

This algorithm takes 2^n-1 moves to move n pieces from the 1st peg to the 3rd peg, thus it has exponential complexity.

I’ve taken time to write this in VB.NET and x86 Assembly. The assembly solution uses only registers, except for a push/pop every call which I can’t figure a way to strip out. Both codes are without the print function which prints every move (which should be removed from performance tests, otherwise the execution becomes hogged from I/O).

VB.NET :

Public Shared Function Hanoi(ByVal from As Integer, ByVal _to As Integer, ByVal use As Integer, ByVal howmany As Integer) As Integer
If (howmany = 1) Then
Return 1
Else
Dim imovs As Integer

imovs += Hanoi(from, use, _to, howmany – 1)
imovs += Hanoi(from, _to, use, 1)
imovs += Hanoi(use, _to, from, howmany – 1)

Return imovs
End If
End Function
x86 Assembly :

mov ebx, from
mov ecx, to
mov edx, use
mov eax, howmany
xor esi, esi
call HanoiAsm
mov retcode, esi
jmp EndHanoiAsm
HanoiAsm:
dec eax
or eax, eax
jz NextLoop
push eax
xchg ecx, edx
call HanoiAsm
xor eax, eax
xchg ecx, edx
inc eax
call HanoiAsm
xchg edx, ebx
pop eax
call HanoiAsm
xchg edx, ebx
dec esi
NextLoop:
inc esi
ret
EndHanoiAsm:

All of this should make a good basis for our performance test on pure recursion.
As an interesting fact, take into account that I wrote the both the C and VB versions in less than a minute each. The assembly version costed me at least 30 minutes of coding, 1 hour of debugging and maybe it still has bugs.. and surely it’s not optimal!