let-floating

[Janis Voigtlaender]

Hello,

I've got a question regarding let-floating [1].=20
Consider the following two versions of the quicksort algorithm:

> qsort1 l =3D f l []
>     where f []     =3D (\y -> y)
>=09    f (x:xs) =3D let (xs_1,xs_2) =3D part (<x) xs=20
>=09=09       in  (\y -> f xs_1 (x:(f xs_2 y)))

> qsort2 l =3D f l []
>     where f []     =3D (\y -> y)
>           f (x:xs) =3D (\y -> let (xs_1,xs_2) =3D part (<x) xs
>=09                      in  f xs_1 (x:(f xs_2 y)))

where the following auxiliary function is used for partitioning a list acco=
rding=20
to some predicate p:

> part  p l =3D part' p l [] []
> part' p []     =3D (\y_1 y_2 -> (y_1,y_2))
> part' p (x:xs) =3D (\y_1 y_2 -> if p x then part' p xs (x:y_1) y_2
>                                      else part' p xs y_1 (x:y_2))

If compiled with "ghc -O", qsort1 runs considerably slower than qsort2=20
(profiling shows that the problem is garbage collection). However, qsort2 c=
an be=20
obtained from qsort1 by floating the let-binding into the lambda-abstractio=
n. Of=20
course, [1] states that this is no good idea unless we know that the=20
lambda-abstraction will be applied only once (as is the case here, right?).=
=20
There it is also stated that an analysis phase is added to GHC that spots s=
uch=20
"one-shot-lambdas". I use a fairly old GHC, so my question is:

Is there a compiler (which version?) that optimizes qsort1 to (essentially)=
=20
qsort2 ?

Any hints concerning the possibility/impossibility of this would be helpful=
.
Thanks and regards, Janis.


[1] Simon L. Peyton Jones, Will Partain, Andr=E9 Santos: "Let-floating: Mov=
ing=20
Bindings to Give Faster Programs", ICFP 1996.


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