From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id 2A0C7BC6D
	for <caml-list@yquem.inria.fr>; Tue, 10 Jul 2007 01:38:08 +0200 (CEST)
Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l69Nc6qV020839
	for <caml-list@inria.fr>; Tue, 10 Jul 2007 01:38:07 +0200
Received: from localhost (orion [130.54.16.5])
	by kurims.kurims.kyoto-u.ac.jp (8.13.7/8.13.7) with ESMTP id l69Nbnbt005481;
	Tue, 10 Jul 2007 08:37:49 +0900 (JST)
Date: Tue, 10 Jul 2007 08:37:33 +0900 (JST)
Message-Id: <20070710.083733.116353766.garrigue@math.nagoya-u.ac.jp>
To: sds@gnu.org
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] large parametrized polymorphic variant type
 combinations take forever to compile
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <4692991E.8040205@gnu.org>
References: <4666E11F.6000308@podval.org>
	<4692991E.8040205@gnu.org>
X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Miltered: at discorde with ID 4692C6DE.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; parametrized:01 gmane:01 gmane:01 variants:01 cmo:01 ocamlc:01 ocamlfind:01 ocamlc:01 -thread:01 -warn-error:01 -for-pack:01 type-checked:01 variants:01 constructors:01 1.3:98 

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