From: Yoann Padioleau <padiolea@irisa.fr>
To: Jon Harrop <jon@ffconsultancy.com>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] OCaml troll on Slashdot
Date: 16 Mar 2005 14:10:09 +0100 [thread overview]
Message-ID: <m31xaf4tzi.fsf@ryxa.irisa.fr> (raw)
In-Reply-To: <200503160301.11138.jon@ffconsultancy.com>
Jon Harrop <jon@ffconsultancy.com> writes:
> Just for the record, I'd like to dispell a couple of myths:
>
> On Wednesday 16 March 2005 01:05, Yoann Padioleau wrote:
> > IMHO the reason it was slow is because it used associative list (instead of
> > Map) for associative access,
>
> 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.
> Also, I think that many people would consider the use of an imperative data
> structure, such as a hash table, for memoizing to be the remit of functional
> programming.
I do. As much as possible I try to have "persistent" (persistent in the okasaki sense)
data-structures.
>
> On Wednesday 16 March 2005 00:18, Oliver Bandel wrote:
> > which does not really looks tail recursive.
> > Called more than 2 * 10^6 times...
> > And many other examples...
>
> In OCaml, non-tail-recursive functions are often faster than their tail
> recursive equivalents for small inputs (e.g. short lists).
really ? why ?
> I expect that the
> functions you have identified fall into this category, so converting them to
> tail-recursive form is likely to slow the program down rather than speed it
> up.
--
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. ____**
next prev parent reply other threads:[~2005-03-16 13:10 UTC|newest]
Thread overview: 71+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-03-15 1:29 Karl Zilles
2005-03-15 8:32 ` [Caml-list] " Oliver Bandel
2005-03-15 8:45 ` Michael Vanier
2005-03-15 8:59 ` Jon Harrop
2005-03-15 20:17 ` Yoann Padioleau
2005-03-15 20:36 ` Jon Harrop
2005-03-15 21:03 ` padiolea
2005-03-15 21:40 ` William D.Neumann
2005-03-15 22:12 ` Yoann Padioleau
2005-03-15 23:07 ` William D.Neumann
2005-03-15 23:39 ` Jon Harrop
2005-03-15 23:54 ` Thomas Fischbacher
2005-03-16 0:03 ` Christopher Dutchyn
2005-03-16 0:18 ` Oliver Bandel
2005-03-16 1:05 ` Yoann Padioleau
2005-03-16 2:55 ` Oliver Bandel
2005-03-16 11:23 ` Thomas Fischbacher
2005-03-16 23:41 ` Oliver Bandel
2005-03-16 13:33 ` Yoann Padioleau
2005-03-16 23:59 ` Oliver Bandel
2005-03-16 3:01 ` Jon Harrop
2005-03-16 13:10 ` Yoann Padioleau [this message]
2005-03-16 13:41 ` Jacques Garrigue
2005-03-16 14:14 ` Yoann Padioleau
2005-03-17 0:27 ` Oliver Bandel
2005-03-16 17:43 ` brogoff
2005-03-16 19:51 ` Jon Harrop
2005-03-17 3:35 ` brogoff
2005-03-17 3:48 ` Yaron Minsky
2005-03-17 10:16 ` Jon Harrop
2005-03-17 10:47 ` Oliver Bandel
2005-03-17 18:06 ` brogoff
2005-03-17 19:15 ` Marcin 'Qrczak' Kowalczyk
2005-03-18 17:46 ` brogoff
2005-03-18 18:44 ` Marcin 'Qrczak' Kowalczyk
2005-03-17 21:31 ` Oliver Bandel
2005-03-17 9:45 ` Christian Szegedy
2005-03-17 10:31 ` Jon Harrop
2005-03-17 11:11 ` Ville-Pertti Keinonen
2005-03-17 11:31 ` tail-recursion vs. no tail-recursion in list functions sebastian.egner
2005-03-17 21:41 ` [Caml-list] " Oliver Bandel
2005-03-18 0:04 ` David Brown
2005-03-18 0:06 ` Karl Zilles
2005-03-18 1:13 ` Jacques Garrigue
2005-03-17 0:21 ` [Caml-list] OCaml troll on Slashdot Oliver Bandel
2005-03-17 1:05 ` Jacques Garrigue
2005-03-17 17:32 ` Jason Hickey
2005-03-17 19:06 ` Marcin 'Qrczak' Kowalczyk
2005-03-17 0:14 ` Oliver Bandel
2005-03-16 1:38 ` Jacques Garrigue
2005-03-31 11:42 ` Paul Argentoff
2005-03-31 11:41 ` Paul Argentoff
2005-03-15 20:06 ` Yoann Padioleau
2005-03-15 9:25 ` Richard Jones
2005-03-15 10:08 ` YANG Shouxun
2005-03-15 20:02 ` Yoann Padioleau
2005-03-15 22:33 ` Richard Jones
2005-03-16 1:33 ` YANG Shouxun
2005-03-15 10:34 ` padiolea
2005-03-15 10:52 ` Diego Olivier Fernandez Pons
2005-03-15 14:12 ` Eijiro Sumii
2005-03-15 15:25 ` Christophe TROESTLER
2005-03-15 18:05 ` Thomas Fischbacher
2005-03-15 18:26 ` Kip Macy
2005-03-16 0:32 ` Oliver Bandel
2005-03-16 11:26 ` David Fox
2005-03-15 18:55 ` Christopher A. Watford
2005-03-15 19:56 ` Jon Harrop
2005-03-16 0:35 ` Oliver Bandel
2005-03-16 0:34 ` Oliver Bandel
2005-03-18 6:04 Harrison, John R
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m31xaf4tzi.fsf@ryxa.irisa.fr \
--to=padiolea@irisa.fr \
--cc=caml-list@yquem.inria.fr \
--cc=jon@ffconsultancy.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).