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.0 required=5.0 tests=none 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 DF19ABC0A for ; Fri, 8 Jun 2007 11:36:01 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l589ZxBr004634 for ; Fri, 8 Jun 2007 11:36:00 +0200 X-IronPort-AV: E=Sophos;i="4.16,399,1175437800"; d="scan'208";a="100717735" Received: from ppp2-129.lns1.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.2.129]) by ipmail03.adl2.internode.on.net with ESMTP; 08 Jun 2007 19:05:56 +0930 Subject: Re: [Caml-list] Re: compiling large file hogs RAM and takes a long time. From: skaller To: Thomas Fischbacher Cc: Jacques Garrigue , sds@gnu.org, caml-list@inria.fr In-Reply-To: <46691BE3.1050607@functionality.de> References: <4666E11F.6000308@podval.org> <466829A3.2090508@gnu.org> <20070608.100255.84973407.garrigue@math.nagoya-u.ac.jp> <1181267500.15201.144.camel@rosella.wigram> <46691BE3.1050607@functionality.de> Content-Type: text/plain Date: Fri, 08 Jun 2007 19:35:53 +1000 Message-Id: <1181295353.20252.26.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 466922FF.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0100,:01 compiler:01 parser:01 sourceforge:01 wrote:01 wrote:01 compile:01 compile:01 caml-list:01 binary:01 compiling:02 seems:03 perhaps:04 fri:05 computing:05 On Fri, 2007-06-08 at 10:05 +0100, Thomas Fischbacher wrote: > skaller wrote: > > > 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? > > What would be so bad about O(n log n log n)? > After all, in our relevant computing universe, there > always is an upper bound to log n which is quite > a small constant (like 25 or so). Perhaps you're right .. still, there's a big difference between a 5 minute compile (enough time to make a coffee!) and a 2 hour compile (enough time to have lunch!) I just went through this: Felix normal build time is about 20 minutes including all tests. With an early version of Dypgen parser, this was changed to around 4 hours... luckily, back to 20 minutes now. Even a small % increase in times can be quite significant. I usually illustrate this by asking if you'd be happy to give up your 2 / 52 week annual holiday .. that's under 4% of the year.. I'm sure you'd be horrified .. 4% is a LOT! -- John Skaller Felix, successor to C++: http://felix.sf.net