[Mono-list] mono performance on highly recursive functions

[Paolo Molaro]

On 02/16/03 Marcus wrote:
> Yesterday Jeroen Frijters posted an array creation test, where mono did 
> particularly badly. I am wondering if mono's uncharacteristically poor 
> performance on that test is caused by a more general problem with highly 
> recursive functions.

As I told you on IRC, the arraytest slowness (that has been fixed in
cvs) has nothing to do with the code generated by the JIT.

> One well-known test that features a great deal of recursion is Ackermann test. 
> I've noticed for a while that mono runs the Ackermann test very slowly in 
> comparison to other VMs. On most tests, mono does very well, frequently 
> faster than Blackdown's JVM but slower than IBM's. In this case, mono takes 
> 25 times as long as IBM's JVM and 6 times as long as Blackdown's. Perhaps 
> this is an area that merits some investigation.

With the ackermann function, the number of calls increases exponentially
as you increase the initial starting values, so saying that it's 25
times slower doesn't mean much unless you also specify what values you
used for the test.
On my system, for example, running Ack(3, 9), mono is just 30-40% slower
than the IBM jdk 1.1.8. Using values bigger than 9 makes the IBM JVM
hang, so I couldn't test more than that with it. Since the number of
calls increases exponentially, I have no issue believing that if you got
a version of the JVM that completes the test, you'll get a factor even
more than 25 as you increase the initial values.
gcc will turn the recursion into a loop, I guess the IBM jvm does the
same and that is what gives the most speed benefit, so the issue is not
with recursion per-se, but just with recognizing when recursion can be
turned into a loop (tail-recursion elimination).
As an example, using recursive fibonacci of 41, mono is just 35% slower than
gcc -O3 -fomit-frame-pointer -march=pentium3 (and the new JIT, mini, is
23 % slower than gcc at the same test).
Detecting tail-recursion is easy and performing tail recursion
elimination should not be difficult in the new JIT, maybe one of these
days I'll have a look at doing it, but it's not an high priority
for me right now.

lupus

-- 
-----------------------------------------------------------------
lupus@debian.org                                     debian/rules
lupus@ximian.com                             Monkeys do it better