🚀 go-pugleaf

Carl Laurence Gonsalves wrote:
> 
> In article <317173F1.5790@concentric.net>,
> Alan L. Lovejoy <alovejoy@concentric.net> wrote:
> >Mike Zorn wrote:
> >>
> >> In <4kbfn8$1bu@news1.is.net> mvantassel@teambca.com (Mark VanTassel) writes:
> >>
> >> >"Alan L. Lovejoy" <alovejoy@concentric.net> wrote:
> >> >>Bzzzt!  Not according to the benchmarks I've done.  Go benchmark the factorial or fibonacci
> >> >>functions (implemented recursively) in both C and a good Smalltalk.  You are in for a big
> >> >>surprise.
> >
> >> >I don't think this is a valid benchmark... (and I too fail to see how
> >> >Smalltalk can be faster than C++ except perhaps in bizarre special
> >> >cases)
> >>    True, the Fibonacci and factorial are not good candidates for a
> >> recursive algorithm.  (They're just taught that way because it's one
> >> of the few recursive problems that we can understand in first-year
> >> college courses.)
> >>    On the other hand, almost any interesting program, compiled & run
> >> in different languages, should be able to give a good idea of how the
> >> languages compare.  For my part, I'd also like to look at the source
> >> code, and know how long it took to write (and debug) the two programs.
> >>    So, Alan, I guess you'll have to come up with a program for
> >> Ackermann's Function in C++ and Smalltalk to satisfy the rest of us.
> >>
> >> Mike Zorn      ozma@kaiwan.com   |  Thought for the day:
> >>   http://www.kaiwan.com/~ozma/   |    Java is C--
> >
> >I did those benchmars to prove that Smalltalk message sends are faster
> >than c function calls.  To do that, I needed a benchmark that consisted
> >mostly of function calls/message sends--and involved as little other
> >code as possible.  The recursive factorial and fibonacci functions
> >meet those requirements better than anything else I could think of.
> 
> Both factorial and fibonacci are tail-recursive, which means that your
> translator may be doing tail recursion elimination, folding your n message
> sends (or function calls) down to one (plus a loop).
> 
> I don't know of any C compilers that do tail recursion elimination. I
> don't know enough about the workings of Smalltalk to say for sure, but it
> may be possible that your translator is doing tail recursion elimination,
> thereby making message sends seem to be a heck of a lot more efficient
> than they really are.
> 
> Try doing a similar test with functions that aren't tail-recursive. Or at
> least find out if your Smalltalk translator may be doing tail-recursion
> elimination.
> 
> --
>         Carl Laurence Gonsalves - clgonsal@undergrad.math.uwaterloo.ca
>                    Computer Science, University of Waterloo
>                http://www.undergrad.math.uwaterloo.ca/~clgonsal/
>                    http://www.csclub.uwaterloo.ca/~clgonsal/

Here's the Smalltalk method source code:

factorial
	"Answer the factorial of the receiver. Fail if the 
	receiver is less than 0."

	self < 2
		ifTrue: 
			[self < 0 ifTrue: [self error: 'Must not be negative'].
			^1].
	^(self - 1) factorial * self

Here's the bytecodes for the same method:

1 <44> push self
2 <4B> push 2
3 <A2> send <
4 <E8 0B> jump false 17
6 <44> push self
7 <49> push 0
8 <A2> send <
9 <C4> jump false 15
10 <44> push self
11 <1C> push 'Must not be negative'
12 <F0 20> send error:
14 <66> pop
15 <4A> push 1
16 <65> return
17 <44> push self
18 <4A> push 1
19 <A1> send -
20 <71> send factorial
21 <44> push self
22 <A8> send *
23 <65> return

I see no tail recursion elimination.  It's harder to do in Smalltalk, because 
any message send could theoretically add, recompile, or remove any method to, 
in or from any class. Message semantics (with some very specific exceptions that
have no bearing here) is NOT defined by the Smalltalk syntax. 

Also, note that the main logic sequence executes 4 message sends out of 11 
instructions--a rather high ratio for C-code (equating message sends with
function calls, of course), but typical for Smalltalk.

What speeds things up is that the bytecodes for each method executed are translated
once into native code, stored in a native method cache, and then directly executed
the next time the same method is executed.  And when the 'factorial' message is 
sent (for example), message selector to method lookup starts by checking whether the 
class of the message receiver is the same as the last time that message was sent to 
that receiver (where "same receiver" is determined lexically).  If so, it can jump 
straight to the correct method. And I do mean "JMP," not "JSR."  So on machines with 
high "JSR" overhead, such as the SPARC I did my benchmarks on, Smalltalk is actually 
faster than C.  This is a reproducible fact.

Because of 32-bit overflow (a problem for C, not Smalltalk), the benchmark consists of 
computing the factorial of 12 (=479,001,600) a large number of times (so that execution 
time is about 1 minute).  The time to simply execute an empty loop the same number of 
times is subtracted from the overall time, so that only the time actually spent computing 
the factorial is actually counted.

--Alan