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@gnu.org>
> Hi,
> continuing the saga started in
> http://permalink.gmane.org/gmane.comp.lang.caml.inria/37496
> I have 3 files: f1.ml, f2.ml, and f.ml:
[...]
> === f.ml ===
> type ('a,'b,'c) t3 = [
> | ('a,'b) F1.t1
> | ('a,'b,'c) F2.t2
> ]
> 
> let f ~fa ~fb ~fc = function
>   | # F1.t1 as x -> F1.f ~fa ~fb x
>   | # F2.t2 as x -> F2.f ~fa ~fb ~fc x
> === f.ml ===
> 
> except that the number of variants is not 2-3 but 800 for f1 and 3000
> for f2 (the number of parameter types ('a,'b,'c) is 3).
> compiling f1.ml and f1.ml takes 10-30 minutes (of 40% less if I use 3.10).
> compiling f.ml takes forever. literally. it has been running for 5+
> hours now and there is no sign of hope (all it has produces so far is an
> empty f.cmo):
> 27820 sds       25   0 1343m 1.3g 1576 R   98 37.2 306:01.80 ocamlc.opt
> (the 3 sample files above compile reasonably fast, but my files are larger).
> the command line is
> ocamlfind ocamlc -dtypes -thread -w Ae -warn-error Ae -for-pack
> Tickslots -g -I . -c generic_tick.ml
> 
> Is this a known problem?

Are you using the CVS 3.10 version?
Performance has been been improved, but as I already answerred you,
complexity for polymorphic variant pattern-matching is still O(n*n),
which is going to create problems with huge variant types.
In particular, you may not be aware that #F1.t1 and #F2.t2 are
actually expanded internally into huge or-patterns, which have to be
type-checked. This could be improved, at least at the type-check
level, but again polymorphic variants were not implemented with
thousands of constructors in mind.

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

Jacques