On Friday 08 February 2002 22:14, you wrote:
define
test1 l = let s1 = foldr (+) 1 l s2 = foldr (-) 1 l in (s1, s2)
test2 l = let s = foldr (\x (a,b) -> (x+a,x-b)) (1,1) l in s
why is test1 so much faster than test2 for long lists l (eg [1..1000000])? replacing foldr with foldl makes it faster (of course), but test2 is still much slower.
i *expected* test2 to be much faster because you're only traversing the list once. presumably the two elements "a" and "b" in test2 could be put in registers and i'd imagine test2 should be faster (it certainly would be if written in c).
I'd say that's because in the second case you also got to apply the (,), besides the (+)/(-) constructor during the transversing... Am I right?
J.A.
My guess is that it is due to the laziness of the addition/subtraction in (,)
I've tried using a strict fold: foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs but that has no effect (or minimal effect). -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Fri, 8 Feb 2002, Konst Sushenko wrote:
On Friday 08 February 2002 22:14, you wrote:
define
test1 l = let s1 = foldr (+) 1 l s2 = foldr (-) 1 l in (s1, s2)
test2 l = let s = foldr (\x (a,b) -> (x+a,x-b)) (1,1) l in s
why is test1 so much faster than test2 for long lists l (eg [1..1000000])? replacing foldr with foldl makes it faster (of course), but test2 is still much slower.
i *expected* test2 to be much faster because you're only traversing the list once. presumably the two elements "a" and "b" in test2 could be put in registers and i'd imagine test2 should be faster (it certainly would be if written in c).
I'd say that's because in the second case you also got to apply the (,), besides the (+)/(-) constructor during the transversing... Am I right?
J.A.
My guess is that it is due to the laziness of the addition/subtraction in (,) _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Friday 08 February 2002 23:52, Hal Daume III wrote:
I've tried using a strict fold:
foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs
but that has no effect (or minimal effect).
That wouldn't work even if if laziness is the problem because that would only cause the elements of the list to be evaluated to head normal form, the elements of the pair would not be evaluated so you'd have a 'suspension of (minus and plus) operations'. instead of
(\x (a,b) -> (x+a,x-b)) try (\x (a,b) -> (((,) $! x-a)$! x-b) )
I just noticed that you were the one who sent me the DeepSeq module. This is the kind of place where I want to use it. Instead of $!, try $!!. And Konst Sushenko wrote:
My guess is that it is due to the laziness of the addition/subtraction in (,)
Seems to me like lazyness is not the right guess because both functions Hall first posted were lazy. So I think it's just the overhead of applying (,) besides (+) and (-) in each step. Do I make sense or am I missing something? J.A.
I agree that it's the overhead of (,), but I don't see why there would be any overhead for doing this. -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Sat, 9 Feb 2002, Jorge Adriano wrote:
On Friday 08 February 2002 23:52, Hal Daume III wrote:
I've tried using a strict fold:
foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs
but that has no effect (or minimal effect).
That wouldn't work even if if laziness is the problem because that would only cause the elements of the list to be evaluated to head normal form, the elements of the pair would not be evaluated so you'd have a 'suspension of (minus and plus) operations'.
instead of
(\x (a,b) -> (x+a,x-b)) try (\x (a,b) -> (((,) $! x-a)$! x-b) )
I just noticed that you were the one who sent me the DeepSeq module. This is the kind of place where I want to use it. Instead of $!, try $!!.
And Konst Sushenko wrote:
My guess is that it is due to the laziness of the addition/subtraction in (,)
Seems to me like lazyness is not the right guess because both functions Hall first posted were lazy. So I think it's just the overhead of applying (,) besides (+) and (-) in each step. Do I make sense or am I missing something?
J.A.
participants (3)
-
Hal Daume III -
Jorge Adriano -
Konst Sushenko