From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 60C4EBC32 for ; Wed, 16 Mar 2005 15:14:25 +0100 (CET) Received: from ryxa.irisa.fr (ryxa.irisa.fr [131.254.50.45]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2GEEPZJ026266 for ; Wed, 16 Mar 2005 15:14:25 +0100 Received: (from pad@localhost) by ryxa.irisa.fr (8.11.6/8.11.6) id j2GEEBx13735; Wed, 16 Mar 2005 15:14:11 +0100 X-Authentication-Warning: ryxa.irisa.fr: pad set sender to padiolea@irisa.fr using -f Sender: pad@ryxa.irisa.fr To: Jacques Garrigue Cc: padiolea@irisa.fr, caml-list@yquem.inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot References: <20050316001819.GB347@first.in-berlin.de> <200503160301.11138.jon@ffconsultancy.com> <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> From: Yoann Padioleau Date: 16 Mar 2005 15:14:11 +0100 In-Reply-To: <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Miltered: at nez-perce with ID 42383F41.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 irisa:01 irisa:01 ocaml's:01 hashtbl:01 hashtbl:01 hash:01 hash:01 ocaml:01 recursive:01 inputs:01 haskell:01 haskell:01 rennes:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: Jacques Garrigue writes: > From: Yoann Padioleau > > Jon Harrop writes: > > > Although Map is asymptotically faster than List.assoc for lookup (O(ln n) vs > > > O(n)), OCaml's Hashtbl and array-based equivalents are typically several > > > times faster than Map. > > > > I agree, I beleived that too but > > I switched from Map to Hashtbl in the "troll" code and Hashtbl sux. > > I don't know why. > > Because the default hash function doesn't work well on complex > data-structures, where it has lots of collisions, and results in > putting lots of values in the same bucket. It's a bad idea to directly > use complex data structures as key anyway, but particularly bad with > hash tables. > > > > In OCaml, non-tail-recursive functions are often faster than their tail > > > recursive equivalents for small inputs (e.g. short lists). > > > > really ? why ? > > Because tail-recursive versions do some extra work to ensure > tail-recursiveness. For instance building a list in reverse order, and > converting it back with List.rev at the end. This only pays off for > huge lists. I am happy. I have learned (or re-learned) a few stuff from this thread so in a way from this "troll" :) Perhaps it is not always a waste of time to post in the news :) It would be cool if some of those insights on optimization would be put somewhere via a wiki. http://haskell.org/hawiki/ThingsToAvoid is a good stard but it is for haskell (but many stuff said still apply to ocaml). I am sure that I am not the only one to ask for a wiki (and not the only one to do nothing about it :) ) It seems that this page is no more accessible from the new website http://caml.inria.fr/pub/old_caml_site/FAQ/FAQ_EXPERT-eng.html#efficacite > > Jacques Garrigue > -- Yoann Padioleau, INSA de Rennes, France www.irisa.fr/prive/padiolea/ Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**