Re: Why is recursion so slow in Mathematica?
- To: mathgroup at smc.vnet.net
- Subject: [mg100550] Re: Why is recursion so slow in Mathematica?
- From: David Bailey <dave at removedbailey.co.uk>
- Date: Mon, 8 Jun 2009 02:03:45 -0400 (EDT)
- References: <h0d6s8$spq$1@smc.vnet.net>
Daniel wrote:
> This post is about functional programming in Mathematica versus other
> functional languages such as OCaml, SML or Haskell. At least a naive
> use of functional constructs in Mathematica is horrendously slow. Am I
> doing something wrong? Or isn't Mathematica really suitable for
> functional programming beyond toy programs? Couldn't the Wolfram team
> make a more efficient implementation for recursion, as other
> functional languages has done? (Instead of the naive C-like behavior
> for recursively defined functions.)
>
> As grounds for my question/argument, I wrote my own version of select,
> as below
>
> myselect[{}, predicate_] = {}
> myselect[{head_, tail___}, predicate_] := If[predicate[head],
> Join[{head}, myselect[{tail}, predicate]],
> myselect[{tail}, predicate]
> ]
>
> Then I tried this function on a 20.000 element vector with machine
> size floats:
>
> data = Table[Random[], {20000}];
> $RecursionLimit = 100000;
> Timing[data2 = myselect[data, # > 0.5 &];]
>
> The result is {7.05644, Null}, and hundreds of MB of system memory are
> allocated. On 1.7 GHZ dual core Intel machine with 1 GB of RAM. For
> 20.000 floats! It's just a megabyte!
>
> The following OCaml program executes in apparently no-time. It is not
> compiled and does the same thing as the above Mathematica code. After
> increasing the list by a factor of ten to 200.000 elements, it still
> executes in a blink. (But with 2.000.000 elements my OCaml interpreter
> says Stack overflow.)
>
> let rec randlist n = if n=0 then [] else Random.float(1.0) :: randlist
> (n-1);;
>
> let rec myselect = function
> [],predicate -> []
> | x::xs,predicate -> if predicate(x) then x::myselect(xs,predicate)
> else myselect(xs,predicate);;
>
> let mypred x = x>0.5;;
>
> let l=randlist(20000);;
> let l2=myselect(l,mypred);; (* lightning-fast compared to Mathematica
> *)
>
You can't really take a programming style that is optimised for one
language and expect it to be optimal in another! Clearly, OCaml does
tail recursion optimisation, and represents lists in memory, in a way
that makes it easy to take the tail of a long list - perhaps lists in
OCaml are represented as linked lists.
However, representing a list as a linked list, has a downside.
Extracting the N'th element of a long list and large N, is an expensive
operation. Since lists in Mathematica are often used as vectors, a
representation using linked lists would have been a BAD choice overall.
David Bailey
http://www.dbaileyconsultancy.co.uk