From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 26687BB84 for ; Fri, 19 May 2006 05:11:55 +0200 (CEST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k4J3BrL7013852 for ; Fri, 19 May 2006 05:11:54 +0200 Received: from rosella (ppp28-237.lns1.syd6.internode.on.net [59.167.28.237]) by smtp3.adl2.internode.on.net (8.13.6/8.13.5) with ESMTP id k4J3BfQO048164; Fri, 19 May 2006 12:41:45 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] compiler bug? From: skaller To: Brian Hurt Cc: caml-list@yquem.inria.fr, Jacques Carette In-Reply-To: References: <20060517231426.30289.qmail@web32203.mail.mud.yahoo.com> <446CABCA.8000906@inria.fr> <446CB021.6000009@mcmaster.ca> <1147976357.25630.27.camel@rosella.wigram> <446CC2C1.5040801@mcmaster.ca> <1148003249.25630.29.camel@rosella.wigram> Content-Type: text/plain Date: Fri, 19 May 2006 13:11:40 +1000 Message-Id: <1148008300.25630.70.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 446D3779.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; compiler:01 bug:01 haskell:01 gcc:01 high-level:01 compiler:01 2006:98 compromising:98 wrote:01 sourceforge:01 caml-list:01 closures:01 compile:01 ghc:01 modules:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Thu, 2006-05-18 at 22:17 -0400, Brian Hurt wrote: > >>> reduce revrev[t] (x:list[t]): rev (rev x) => x; > I'm just wondering how often such optimizations are worthwhile. Me too. I don't know. However the above type of optimisation is only a hint at what can be done. It's what I could implement easily in a few hours, after noting in generated code there really were cases of double list reversals. > From what > I've read, basic register allocation and peephole optimizations gain you > 2x the performance- after that, it's a fight for percentage points. Most people seem to think eliminating array bounds checks is worthwhile. Haskell certainly thinks deforestation and closure elimination to be useful. These are high level optimisations which I expect to have much more impact in most cases than register fiddling. (They'd better .. GHC is still a snail solving some very simple problems) Indeed, the current Felix optimiser was obtained by noting the woeful code generated for things like the Shootout multiple loop test, and adding enough heuristics to eliminate closures so the code reduced to the same kind of basic C code a C programmer would write. Of course I hope gcc -O3 etc will do the low level optimisations for me, but it has to start with decent C code for that to work. > Especially considering that humans tend to be a lot better at recognizing > opportunities for high-level optimizations than computers are. For > example, a human would be much more likely to notice a double list > reversal when the two reversals are in seperate modules, or otherwise > obscured from the compiler. Even more so, the programmer may decide that > maybe a list isn't the right datastructure for this data- a decision I > wouldn't trust to a compiler. I agree. Also note applying even reductions of the form above is extremely expensive in compile time (matching every subexpression looking for double list reversals cannot be fast :) However, the point is that there is scope for much improvement with high level optimisations. In particular, one hopes they can be hinted at in a way that not only makes faster code .. but does so without compromising correctness or other safety features. -- John Skaller Felix, successor to C++: http://felix.sf.net