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 28347BB84 for ; Thu, 18 May 2006 22:07:37 +0200 (CEST) Received: from mail.davidb.org (mail.davidb.org [66.93.32.219]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k4IK7ZxI014338 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 18 May 2006 22:07:36 +0200 Received: from davidb by mail.davidb.org with local (Exim 4.60 #1 (Debian)) id 1FgomS-0008PA-E1; Thu, 18 May 2006 13:07:32 -0700 Date: Thu, 18 May 2006 13:07:32 -0700 From: David Brown To: Jacques Carette Cc: Xavier Leroy , caml-list@yquem.inria.fr Subject: Re: [Caml-list] compiler bug? Message-ID: <20060518200732.GA31619@old.davidb.org> References: <20060517231426.30289.qmail@web32203.mail.mud.yahoo.com> <446CABCA.8000906@inria.fr> <446CB021.6000009@mcmaster.ca> <446CB2EE.1080102@inria.fr> <446CCB8E.8080601@mcmaster.ca> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <446CCB8E.8080601@mcmaster.ca> User-Agent: Mutt/1.5.11 X-Miltered: at nez-perce with ID 446CD407.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; compiler:01 bug:01 algebra:01 worst-case:01 worst-case:01 compiler:01 2006:98 wrote:01 caml-list:01 caml-list:01 jacques:01 generally:03 thu:05 rather:07 rather:07 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=SPF_SOFTFAIL autolearn=disabled version=3.0.3 On Thu, May 18, 2006 at 03:31:26PM -0400, Jacques Carette wrote: > In Computer Algebra, people use Groebner bases all the time. They have > doubly-exponential worst-case complexity -- but seem to work rather well > in practice. So I have stopped paying attention to worst-case; average > case, when available, does matter a lot more. Except when someone made a decision like this, in say a revision control system, and suddenly you discover that you've provoked a worst case scenario, and it suddenly takes hundreds of cpu hours to check in a file rather than a few seconds. For something like a compiler, worse case behavior is very important. It is not generally acceptable for a build to just hang in the compiler. Dave