[comp.arch] Ackermann on M/500 and Sun-4

firth@sei.cmu.edu (Robert Firth) (11/13/87)

This is a brief followup to John Mashey's comparisons between
the Mips machines and the Sun-4.

We tried the traditional Ackermann function benchmark on both
machines:

	function acker (m,n : integer) return integer is
	begin
	  if m=0 then
	    return n+1;
	  elsif n=0 then
	    return acker(m-1,1);
	  else
	    return acker(m-1, acker(m,n-1));
	  end if;
	end acker;

In all cases, the function was hand coded for maximum performance,
with tail recursion elimination, call protocol simplification, and
hand reorganisation to get rid of no-ops.

The execution time for the call acker(3,8) is:

	M/500:	3.8"
	Sun-4: 15.8" (A)
	Sun-4:  2.3" (B)

The Sun-4 (A) result is obtained by using the save and restore protocols,
ie the register windows.  The (B) result is obtained by using a fixed set
of registers and saving locals in memory, on a software stack.  In fact,
this result could probably be improved still further if we had not used sp
as the stack pointer, which forced us to allocate 64 bytes in each local
frame for Unix kernel interrupts to dump registers into (!).

Of course, Ackermann's function is noted for very deep recursion, so across
each call the register window saves and restores 64 bytes, whereas doing
it by hand you need save and restore only 8 bytes.

I have lots of other reasons for believing register windows are a basically
bad isea, but I'm sure you'd rather just have the numbers.