From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jon@ffconsultancy.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 30CACBC6B
	for <caml-list@yquem.inria.fr>; Wed, 11 Jul 2007 03:25:12 +0200 (CEST)
Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6B1PBwL015330
	(version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO)
	for <caml-list@yquem.inria.fr>; Wed, 11 Jul 2007 03:25:12 +0200
Received: from [80.229.56.224] (helo=beast.local)
	 by ptb-relay02.plus.net with esmtp (Exim) id 1I8Qx0-0003M5-7c
	for caml-list@yquem.inria.fr; Wed, 11 Jul 2007 02:25:06 +0100
From: Jon Harrop <jon@ffconsultancy.com>
Organization: Flying Frog Consultancy Ltd.
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile
Date: Wed, 11 Jul 2007 02:19:35 +0100
User-Agent: KMail/1.9.7
References: <4692991E.8040205@gnu.org> <46938BDA.1090605@podval.org> <20070711.091002.39162301.garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <20070711.091002.39162301.garrigue@math.nagoya-u.ac.jp>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200707110219.35727.jon@ffconsultancy.com>
X-Miltered: at concorde with ID 46943177.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; parametrized:01 compilation:01 ocamlc:01 bytecode:01 constructors:01 hash:01 trivial:01 printf:01 printf:01 compilation:01 ocaml:01 ocaml:01 0.09:98 frog:98 polymorphic:01 

On Wednesday 11 July 2007 01:10:02 Jacques Garrigue wrote:
> 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...

Isn't it a really bad idea to autogenerate polymorphic variant type 
constructors anyway because, sooner or later, you'll get a hash clash? In 
fact, wouldn't that be platform specific?

I would recommend factoring the sum type by the argument types of the 
contructors in this case. Looking at Sam's files, this is trivial. Just 
replace this:

type ('a,'b) t1 = [
| `t1_a of 'a option
| `t1_b of 'b list
| `t1_a0 of 'a option
...
| `t1_a9 of 'a option
| `t1_a10 of 'a option
...
| `t1_a1000 of 'a option

with this:

type t1 = [
| `t1_int of [
  | `a
  | `a0
  | `a10000 ] * int
| `t1_float of [`b] * float
]

and this:

let f ~fa ~fb = function
  | `t1_a a -> fa a
  | `t1_b b -> fb b
  | `t1_a0 a -> fa a
...
  | `t1_a1000 a -> fa a

with this:

let f ~fa ~fb = function
| `t1_int(_, a) -> fa a
| `t1_float(_, b) -> fb b

The following code autogenerates an equivalent to small1.ml and it compiles 
100x faster:

open Printf

let () =
  printf "type t1 = [\n";
  printf "| `t1_int of [\n| `a\n";
  for i=0 to 1000 do
    printf "  | `a%d\n" i
  done;
  printf "] * int\n";
  printf "| `t1_float of [`b] * float\n";
  printf "]\n";
  printf "let f ~fa ~fb = function\n";
  printf "| `t1_int(_, a) -> fa a\n";
  printf "| `t1_float(_, b) -> fb b\n";

Doing the same for small2.ml and small.ml, the final compilation time is 
0.09s.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e