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 75B45BC0A
	for <caml-list@yquem.inria.fr>; Fri,  8 Jun 2007 03:03:27 +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 l5813PWn019134
	for <caml-list@inria.fr>; Fri, 8 Jun 2007 03:03:26 +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 l58137cN008584;
	Fri, 8 Jun 2007 10:03:07 +0900 (JST)
Date: Fri, 08 Jun 2007 10:02:55 +0900 (JST)
Message-Id: <20070608.100255.84973407.garrigue@math.nagoya-u.ac.jp>
To: sds@gnu.org
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Re: compiling large file hogs RAM and takes a long
 time.
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <466829A3.2090508@gnu.org>
References: <4666E11F.6000308@podval.org>
	<466829A3.2090508@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 4668AADD.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; variants:01 foo:01 foo:01 variants:01 ocamlopt:01 3050:98 polymorphic:01 polymorphic:01 caml-list:01 variant:02 variant:02 caml:02 compiling:02 quadratic:02 garrigue:03 

From: Sam Steingold <sds@gnu.org>
> update: the main problem is a polymorphic variant type with 3050
> variants and a function that returns its instances.
> chunking the type, i.e., replacing
> type foo=[|`A|`B|`C|`D]
> with
> type foo_1=[|`A|`B]
> type foo_2=[|`C|`D]
> type foo=[|foo_1|foo_2]
> (but with ~55 variants in ~55 types) did not help.
> Removing the type definition did solve the RAM problem - according to
> top(1), ocamlopt.opt was taking ~80MB, and it compiled the file in about
> 10 minutes.
> 
> Any chance there is some quadratic code in polymorphic variant type
> processing?!

There is, and this is a known problem:
  http://caml.inria.fr/mantis/view.php?id=4053

I'm sorry, but I don't see any easy way out.
At least on the basic time complexity.
However, the space complexity could be improved, if I find what is
gobbling memory so fast.

         Jacques