[Mono-bugs] [Bug 557606] New: Compilation of polymorphic recursion is too eager

[bugzilla_noreply at novell.com]

http://bugzilla.novell.com/show_bug.cgi?id=557606

http://bugzilla.novell.com/show_bug.cgi?id=557606#c0


           Summary: Compilation of polymorphic recursion is too eager
    Classification: Mono
           Product: Mono: Runtime
           Version: 2.4.x
          Platform: Other
        OS/Version: Ubuntu
            Status: NEW
          Severity: Critical
          Priority: P5 - None
         Component: JIT
        AssignedTo: lupus at novell.com
        ReportedBy: ekirpichov at gmail.com
         QAContact: mono-bugs at lists.ximian.com
          Found By: Community User
           Blocker: ---


Description of Problem:


Steps to reproduce the problem:
1. Create a file with the following source code:

using System;

namespace csharppolyrec
{
    struct S<T> {}

    class MainClass    {
        private static void f<T>(int i) {
            if(i==42) f<S<T>>(i);
        }
        public static void Main(string[] args) {
            f<int>(0);
            Console.WriteLine("Hello World!");
        }
    }
}

2. Compile it.
3. Run the result.


Actual Results:
The program hangs. Running under gdb yields a stacktrace full of
mono_metadata_type_hash, which is a clear sign that mono tries to eagerly
instantiate all the possible parameterizations of f(), of which there is
clearly an infinite number.

Expected Results:
The program should print "Hello world!" and terminate. This is what happens on
the Microsoft CLR virtual machine.

How often does this happen? 
This happens always, at least in version 2.4.2.3.

Additional Information:
If I replace the condition with "if(false)" then the compiler reports an
unreachable code warning but the program runs fine.

Generic instantiation should be done lazily in runtime (at the time of method
invocation), not during some data-flow analysis pass. Of course this is a lot
harder and may slow things down for polymorphically recursive stuff, but this
won't harm performance for monomorphically recursive methods (which are used
99% of the time) if they are detected statically.
I unfortunately do not have access to a Windows machine to check whether
polymorphic recursion gets compiled by MS CLR to slower code than monomorphic
recursion.

This compiler bug prevents one from implementing some polymorphically recursive
data structures, such as the ones described in Okasaki's "Purely functional
data structures, in the chapter on numeric representations, in a type-safe way.
So I think that marking the bug "critical" is fair.

-- 
Configure bugmail: http://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.