[clean-list] Optimising Recursive Functions Yielding Multiple Results in Tuples?

[Janis Voigtlaender]

Hi,

I read the following paper about a very interesting compiler
optimisation concerning tupled results:

  J.H.G. van Groningen. Optimising Recursive Functions Yielding
  Multiple Results in Tuples in a Lazy Functional Language. In
  Implementation of Functional Languages, Lochem, The Netherlands,
  Proceedings, volume 1868 of LNCS, pages 59-76. Springer-Verlag,
  September 1999. 

The paper states that the proposed optimisation has been implemented
in the Clean 1.3 compiler. However, I cannot reproduce the measurements
given there. For the running example:

  module split

  import StdEnv,MersenneTwister

  quick_sort1 [e:l] t = quick_sort1 small [e: quick_sort1 large t]
	where small = [v \\ v<-l | v<e]
 	      large = [v \\ v<-l | v>=e]
  quick_sort1 []    t = t
	
  split v [e:l]
	| e<v       = ([e:small],large)
	| otherwise = (small,[e:large])
	where (small,large) = split v l
  split v [] = ([],[])

  quick_sort2 [e:l] t = quick_sort2 small [e: quick_sort2 large t]
	where (small,large) = split e l
  quick_sort2 []    t = t
	
  n:==10000 
  m:==50    

  Start = map (\l -> sum (quick_sort1 l [])) 
              [take n (genRandInt i) \\ i<-[1..m]]

the author observes a speed-up of about 25% by using quick_sort2 instead
of quick_sort1 in Start.

But with my downloaded Clean version 1.3.3.2 for SUN Sparc Solaris, I
instead get the following times:

              Execution   Garbage collection   Total

quick_sort1:     4.35         0.87             5.22
quick_sort2:     7.10         2.03             9.13

They show that the program using quick_sort2 is *slower* than
quick_sort1 by a factor of 1.75! This coincides with the measurements in
the above mentioned paper for quick_sort2 *without* the new tuple
optimisation.
 
This leads me to believe that the Clean 1.3.3.2 compiler does *not*
implement the tuple optimisation proposed by van Groningen. I made
similar observations (quick_sort2 being less efficient than quick_sort1
by a factor of 1.85) for Clean 2.0 (and 1.3.3) under Win, so I suppose
the tuple optimisation is also not implemented there.

Hence, my question is:

  Which version of the compiler do I need to download in order to
  experiment with the optimisation from the above paper? Or is it just a
  matter of some compiler switch that I don't know?

Any hints would be highly appreciated.

Thanks and kind regards,
Janis Voigtlaender.


PS: If I can actually benefit from the tuple optimisation, this might
very well "convert" me from Haskell to Clean ;-)


--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de