MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Re: interfacing odd usb device to mathematica
  • Next by Date: Re: Re: interfacing odd usb device to mathematica
  • Previous by thread: Re: Documentation Methods and Efficiencies
  • Next by thread: Re: Why is recursion so slow in Mathematica?