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=1.3 required=5.0 tests=AWL,SPF_SOFTFAIL 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 F1637BC0A for ; Fri, 15 Jun 2007 17:45:07 +0200 (CEST) Received: from smtp.janestcapital.com (janestcapital.com [66.155.124.107]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5FFj78e023281 for ; Fri, 15 Jun 2007 17:45:07 +0200 Received: from [172.25.131.105] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id A33801E8; Fri, 15 Jun 2007 11:41:44 -0400 Message-ID: <4672B328.4030504@gnu.org> Date: Fri, 15 Jun 2007 11:41:28 -0400 From: Sam Steingold User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: Jacques Garrigue Cc: caml-list@inria.fr Subject: Re: compiling large file hogs RAM and takes a long time. References: <4666E11F.6000308@podval.org> <466829A3.2090508@gnu.org> <20070608.100255.84973407.garrigue@math.nagoya-u.ac.jp> <20070608.213010.99453104.garrigue@math.nagoya-u.ac.jp> In-Reply-To: <20070608.213010.99453104.garrigue@math.nagoya-u.ac.jp> X-Enigmail-Version: 0.95.1 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4672B403.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; hash:01 60%:98 cvs:01 constants:01 constants:01 polymorphic:01 wrote:01 compile:01 variant:02 caml:02 compiling:02 quadratic:02 quadratic:02 garrigue:03 jacques:03 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Jacques Garrigue wrote: >>> 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. > > I found the reason, and this is now fixed in CVS 3.10. > I can now compile a pattern matching with 3000 cases in 10s and just > 10MB, which is better than 40s and 250MB before :-) I observe a time reduction of 40% (from 10 minutes down to 6 minutes) and RAM usage reduction of 60% (from 450MB down to 160MB) for my (generated) file. Very nice, thanks! > This doesn't change the quadratic time complexity, but as other > mentioned, constants do matter. Indeed, but it appears that in this case improving constants does not solve the problem completely. Sam. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGcrMoPp1Qsf2qnMcRAu6EAJ449kDgvpfKPSRoI1vlIiLqjNcILwCeMvi9 6EWbtykwW5kD62QvxW/hU6Y= =XRSH -----END PGP SIGNATURE-----