Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Sam Steingold <sds@podval.org>

> actually these horrors are observed with 3.09.3.
> we are planning to upgrade to 3.10 soon.

Note that it should be the 3.10 CVS version, not 3.10.0.
Or you can wait for 3.10.1 (but I have no idea when it will be.)

> > This could be improved, at least at the type-check
> > level, but again polymorphic variants were not implemented with
> > thousands of constructors in mind.
> 
> too bad. any chance this could be fixed?

That the original implementation hadn't huge types in mind?
Too late: it would require a very different approach.
Also, as Christophe Raffalli pointed out, there are some features of
pattern-matching that are NP-complete by design.
But we can try to remove flagrant innefficiencies when we understand
them.

> > Could you send me your real code, so that I can see whether something
> > unexpected is happening?
> 
> attached

Seems you're lucky. The fix I did yesterday after reading your first
mail, combined with the fixes following the previous discussion,
solved the problem. Compilation times are now about 7s using less than
7MB, for all of the 3 files, using ocamlc (bytecode). Of course, you
can still expect quadratic behaviour if your types grow more...

By the way, you're also lucky for the generated code: due to the
naming of your constructors, the code for small0.ml is very compact
and efficient. Of course, this is not going to be true in general.
(You can see the result of pattern-matching compilation with
'ocamlc -c -dlambda')

Jacques Garrigue