trivial list foldings require quadratic time?
Hi, Recently I noticed that evaluating minimum [1 .. 10000] in Hugs takes much more time than evaluating minimum [10000, 9999 .. 1] . This seems weird because evaluating min always needs evaluation of both its arguments, so the computation schema should be the same. I think this is a bug. Making experiments with the length varying leads to the suggestion that minimum [1 .. n] runs in quadratic time on n while minimum [n, n - 1 .. 1] runs in linear time. But it would be normal to assume minimum working in linear time in both cases. By the way, both the number of reductions and the number of cells reported by Hugs grow linearly in both cases, the corresponding numbers remain close to each other. Somehow the reductions of minimum [1 .. 10000] take much more time on an average then the reductions of minimum [10000, 9999 .. 1] . The difference is that, in the first case, comparisions are performed with the same element 1 all the time while, in the second case, the numbers being compared continuously change. I made yet more experiments. From the expressions foldl (\ x y -> if x < y then x else y) (maxBound :: Int) [1 .. 10000] foldl (\ x y -> if x < y then x else y) (maxBound :: Int) [10000, 9999 .. 1] foldr (\ x y -> if x < y then x else y) (maxBound :: Int) [1 .. 10000] foldr (\ x y -> if x < y then x else y) (maxBound :: Int) [10000, 9999 .. 1] the first and the last evaluate slowly while the others evaluate fast, although evaluation of the last needs by ~20% less reductions and cells than the third. The phenomenon occurs even when using foldl' instead of foldl . The punch-line is that if I modify the expressions as follows: foldl (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [1 .. 10000] foldl (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [10000, 9999 .. 1] foldr (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [1 .. 10000] foldr (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [10000, 9999 .. 1] then all are fast! The conditional in the operator is not essential: foldl (\ x y -> x) 0 [1 .. 10000] evaluates fast, foldl (\ x y -> ($!) const x y) 0 [1 .. 10000] evaluates slowly, foldl (\ x y -> ($!) const (x + 0) y) 0 [1 .. 10000] evaluates fast again. All this occurs with both Nov-2003 and Mar-2005 release of Hugs, on both Linux and Solaris. I have not tested in Windows. With ghci, this anomaly does not appear. Härmel
On Mon, Feb 13, 2006 at 08:21:04PM +0200, Härmel Nestra wrote:
Making experiments with the length varying leads to the suggestion that minimum [1 .. n] runs in quadratic time on n while minimum [n, n - 1 .. 1] runs in linear time.
Great stuff! More experiments, expanding the arithmetic sequences: slow: foldr min 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int foldr max 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int foldl min 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int fast: foldl max 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int and even if we share the input to the folds. It seems that a shared redex isn't being updated by max/min and similar functions.
On Mon, Feb 13, 2006 at 08:21:04PM +0200, Härmel Nestra wrote:
Making experiments with the length varying leads to the suggestion that minimum [1 .. n] runs in quadratic time on n while minimum [n, n - 1 .. 1] runs in linear time.
OK, what's happening is that in Hugs, functions that return one of their arguments, like min x y = if x <= y then x else y return an indirection to the argument (to avoid copying it), so these examples traverse a chain of indirections that gets longer for each new min, hence the quadratic behaviour. This is now fixed in CVS (no need to create an indirection pointing at an indirection). Thanks for the analysis.
participants (2)
-
Härmel Nestra -
Ross Paterson