also try replacing that (foldl' intersect') with (foldr (flip intersect'))!
OK, next question: Given that I'm using all the results from
intersect', why is the lazy version better than the strict one? Is ghc
managing to do some loop fusion?
haskell tends to prefer foldr where mls prefer foldl, be it for
lazyness and short-circuiting operators, or because a tail-recursive
function with a lazy accumulator is only an efficient way to construct
inefficient expressions.
so, the very first thing i tend to look for when someone ports a
program from ml to haskell are tail recursions with non-strict
accumulators. even using foldl', when constructing pairs in the
accumulator, there's no guarantee that the pair components will
be evaluated early even if the pairs themselves are forced. so
replacing foldl with foldr when porting from ml to haskell tends
to be a useful habit, unless there are good reasons for foldl.
however, things seem to be a little bit more involved in this
example: intersect' forces the first component, and ignores
the second, never building nasty delayed combinations of old
accumulator and list head in the new accumulator. but if you
compare the outputs of -ddump-simpl, or if you export all
definitions from main and compare the outputs of --show-iface,
you'll find differences related to the the result of intersect':
whether or not that result can be passed unboxed.
Constructed Product Result Analysis for Haskell (2000)
http://citeseer.ist.psu.edu/baker-finch00constructed.html
i don't know the details, but in the foldr case, the result of
intersect' seems to be passed unboxed, in the foldl' case, it
isn't. i'll leave it to the experts to explain whether that has to
be the case or whether it is an omission in the optimizer.
claus
using a recent ghc head instead of ghc-6.6.1 also seems to
make a drastic difference
$ uname -a
CYGWIN_NT-5.1 cr3-lt 1.5.19(0.150/4/2) 2006-01-20 13:28 i686 Cygwin
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.6.1
$ gcc --version
gcc.exe (GCC) 3.4.2 (mingw-special)
Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ ghc --make Ray1.hs
[1 of 1] Compiling Main ( Ray1.hs, Ray1.o )
Linking Ray1.exe ...
$ time ./Ray1.exe >out
real 0m55.705s
user 0m0.015s
sys 0m0.031s
$ /cygdrive/c/fptools/ghc/ghc-6.7.20070613/bin/ghc --make Ray1.hs -o
Ray1head.exe
[1 of 1] Compiling Main ( Ray1.hs, Ray1.o )
Linking Ray1head.exe ...
$ time ./Ray1head.exe >out.head
real 0m24.989s
user 0m0.031s
sys 0m0.015s
$ diff -q --binary out out.head
$
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
