Position of arguments in function definition and performance

Hal Daume III hdaume@ISI.EDU
Wed, 6 Feb 2002 23:51:00 -0800 (PST)


Actually, presumably you meant:
> reverse2 ys (x:xs) =3D reverse2 (x:ys) xs

(stupid cut & paste late at night).

with this fix (and now we actually are reversing the list with reverse2),
we get the following timings for reverse2:

11:49pm enescu:~/ time a.out
2000000
4.64u 0.31s 0:05.18 95.5%
11:49pm enescu:~/ time a.out
2000000
4.87u 0.25s 0:06.23 82.1%

which seems to say they perform comparably, as we would expect.  sorry for
freaking out earlier :)

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

On Wed, 6 Feb 2002, Hal Daume III wrote:

> Well, I assume you meant:
>=20
> reverse1 [] ys =3D ys
> reverse1 (x:xs) ys =3D reverse1 xs (x:ys)
>=20
> reverse2 ys [] =3D ys
> reverse2 ys (x:xs) =3D reverse1 (x:ys) xs
>=20
> If so, and you make two programs:
>=20
> main =3D print (length $! reverse1 [1..2000000] [])
>=20
> and
>=20
> main =3D print (length $! reverse2 [] [1..2000000])
>=20
> compile them with ghc -O2 -fvia-c, and time them we get:
>=20
> FOR REVERSE1:
>=20
> 11:42pm enescu:~/ time a.out
> 2000000
> 4.84u 0.28s 0:06.01 85.1%
> 11:42pm enescu:~/ time a.out
> 2000000
> 4.71u 0.24s 0:05.25 94.2%
>=20
> FOR REVERSE2:
>=20
> 11:43pm enescu:~/ time a.out
> 2000000
> 1.00u 0.03s 0:01.09 94.4%
> 11:43pm enescu:~/ time a.out
> 2000000
> 0.99u 0.01s 0:00.99 101.0%
>=20
> curiously, REVERSE2 did significantly better; I have no idea why.  Perhap=
s
> one of the Simons could comment on this.  Moreover, if this is a general
> phenomenon, why doesn't GHC simply permute the order of parameters to
> allow it to optimize best?
>=20
> Regards,
>=20
>   Hal
>=20
> --
> Hal Daume III
>=20
>  "Computer science is no more about computers    | hdaume@isi.edu
>   than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
>=20
> On Wed, 6 Feb 2002, [iso-8859-1] Jos=E9 Romildo Malaquias wrote:
>=20
> > Hello.
> >=20
> > Please, tell me which set of definitions below should I expected
> > to be more efficient: the reverse1 or the reverse2 functions.
> >=20
> > reverse1 []     ys =3D ys
> > reverse1 (x:xs) ys =3D reverse2 (x:ys) xs
> >=20
> > reverse2 ys []     =3D ys
> > reverse2 ys (x:xs) =3D reverse2 (x:ys) xs
> >=20
> > The difference rely on the position of the argument in which the
> > pattern matching is done in the function definition.
> >=20
> > Regards.
> >=20
> > Romildo
> > --=20
> > Prof. Jos=E9 Romildo Malaquias               Departamento de Computa=E7=
=E3o
> > http://iceb.ufop.br/~romildo       Universidade Federal de Ouro Preto
> > romildo@iceb.ufop.br                                           Brasil
> > romildo@uber.com.br
> > _______________________________________________
> > Haskell mailing list
> > Haskell@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell
> >=20
>=20
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>=20