From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 3FB28BC6B for ; Wed, 11 Jul 2007 02:10:37 +0200 (CEST) Received: from rabbit.math.nagoya-u.ac.jp (rabbit.math.nagoya-u.ac.jp [133.6.130.5]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6B0AX00031685 for ; Wed, 11 Jul 2007 02:10:36 +0200 Received: from localhost (rabbit-172 [172.16.254.254]) by rabbit.math.nagoya-u.ac.jp (8.12.11/3.7W) with ESMTP id l6B0AWFG008209; Wed, 11 Jul 2007 09:10:32 +0900 (JST) Date: Wed, 11 Jul 2007 09:10:02 +0900 (JST) Message-Id: <20070711.091002.39162301.garrigue@math.nagoya-u.ac.jp> To: sds@podval.org Cc: caml-list@inria.fr Subject: Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile From: Jacques Garrigue In-Reply-To: <46938BDA.1090605@podval.org> References: <4692991E.8040205@gnu.org> <20070710.083733.116353766.garrigue@math.nagoya-u.ac.jp> <46938BDA.1090605@podval.org> X-Mailer: Mew version 5.1 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 46941FF9.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; parametrized:01 variants:01 constructors:01 christophe:01 raffalli:01 compilation:01 ocamlc:01 bytecode:01 constructors:01 compilation:01 'ocamlc:01 cvs:01 polymorphic:01 polymorphic:01 compile:01 From: Sam Steingold > 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