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.4 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 4BF1FBC0A for ; Fri, 8 Jun 2007 15:39:14 +0200 (CEST) Received: from smtp.janestcapital.com (www.janestcapital.com [66.155.124.107]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l58DdCkE029094 for ; Fri, 8 Jun 2007 15:39:13 +0200 Received: from [172.25.131.105] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id AC0B020C; Fri, 08 Jun 2007 09:39:23 -0400 Message-ID: <46695BFE.4050107@gnu.org> Date: Fri, 08 Jun 2007 09:39:10 -0400 From: Sam Steingold User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: skaller Cc: Jacques Garrigue , 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> <1181267500.15201.144.camel@rosella.wigram> In-Reply-To: <1181267500.15201.144.camel@rosella.wigram> X-Enigmail-Version: 0.95.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 46695C00.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; hash:01 compiler:01 polymorphic:01 wrote:01 wrote:01 binary:01 variant:02 caml:02 compiling:02 quadratic:02 garrigue:03 seems:03 jacques:03 gnu:03 gnu:03 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 skaller wrote: > On Fri, 2007-06-08 at 10:02 +0900, 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. > > You mention in the ticket there is a hard way out .. using > binary trees; hard because it would require changes everywhere > in the compiler. Is this actually enough? Seems to reduce > > O(n * n * log n) > > to > > O( n * log n * log n) > > which is still pretty bad.. is that right? for n=16,000 you have log n~14, i.e., a factor of 1,000. even allowing for an unfavorable constant, the factor of 100 would be a huge win. I think going from n*n*log to n*log*log would be a worthy project. Sam. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGaVv+Pp1Qsf2qnMcRAkKzAJ4lWTSha/aF/3Uhr9+2E6C3nIGwpACgio0q Z0Yb0Aru1bbV0vzwt/1eMXM= =8UNH -----END PGP SIGNATURE-----