[Mono-bugs] [Bug 557606] New: Compilation of polymorphic recursion is too eager
bugzilla_noreply at novell.com
bugzilla_noreply at novell.com
Sun Nov 22 11:55:27 EST 2009
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.
More information about the mono-bugs
mailing list