Reasoning about performance

newer
GHC API question: Getting access...

older
Mistakes in documentation for weak...

Scott Pakin

3 Sep 2013 3 Sep '13

6:28 p.m.

I'm a Haskell beginner, and I'm baffled trying to reason about code performance, at least with GHC. For a program I'm writing I needed to find all pairs of elements of a list. That is, given the list "ABCD" I wanted to wind up with the list [('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')], where the order of elements in the resulting list is immaterial, but I don't want both ('A', 'B') and ('B', 'A'), for example. My first attempt looked like this: allPairs1 :: [a] -> [(a, a)] allPairs1 [] = [] allPairs1 (x:xs) = map (\a -> (x, a)) xs ++ allPairs1 xs Benchmarking with ghci's ":set +s" reveals the following performance (median of three runs shown): $ ghci GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o ) Prelude Control.DeepSeq AllPairs> :set +s Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True True (4.85 secs, 4004173984 bytes) A colleague suggested getting rid of the list append as follows: allPairs2 :: [a] -> [(a, a)] allPairs2 [] = [] allPairs2 (x:xs) = allPairs2' x xs xs where allPairs2' x [] [] = [] allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs allPairs2' x [] (z:zs) = allPairs2' z zs zs Not surprisingly, that runs faster: Prelude Control.DeepSeq AllPairs> deepseq (allPairs2 [1..10000]) True True (2.14 secs, 4403686376 bytes) I then figured I could do even better by rewriting the code tail-recursively: allPairs3 :: [a] -> [(a, a)] allPairs3 [] = [] allPairs3 (x:xs) = allPairs3' x xs xs [] where allPairs3' :: a -> [a] -> [a] -> [(a, a)] -> [(a, a)] allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h, x):result) allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result allPairs3' _ [] [] result = result This takes half the memory as the above (yay!) but runs substantially *slower* (and appears to be thrashing my computer's memory system): Prelude Control.DeepSeq AllPairs> deepseq (allPairs3 [1..10000]) True True (10.58 secs, 2403820152 bytes) What gives? Why does my tail-recursive implementation run even slower and presumably produce more garbage than my initial, naive implementation? Is there some optimization GHC is performing for allPairs1 and allPairs2 that it can't apply to allPairs3? Similarly, how should I, as a newcomer who wants to write efficient Haskell code, reason about whether a code change is likely to improve rather than degrade performance? Guidelines like "per-iteration appends = bad" and "tail recursion = good" are great, but the preceding data indicate that something subtler is taking precedence over those guidelines with respect to code performance. Thanks in advance, -- Scott

Show replies by date

Bob Ippolito

3 Sep 3 Sep

7:43 p.m.

Haskell's non-strict evaluation can often lead to unexpected results when doing tail recursion if you're used to strict functional programming languages. In order to get the desired behavior you will need to force the accumulator (with something like Data.List's foldl', $!, seq, BangPatterns, etc.). One issue with the tail recursive version is that you're basically sequencing it twice, forcing the result is going to force the whole spine of the list, and then you're walking it again with deepseq. The overhead of the deepseq call with that size list on my machine is 2.2 seconds, so you're basically paying that cost twice with a tail recursive version. allPairs2 only forces what is needed, so deepseq isn't traversing any data structures that are already forced. I think what's happening with allPairs2 is that GHC is throwing away the the list during the traversal since the result of the computation isn't used at all. I get very different timings (still fast, but no longer orders of magnitude difference) for allPairs2 if the result is still around. You could probably figure this out with the heap profiler. h> deepseq (allPairs2 [1..10000]) True True (2.47 secs, 4403724176 bytes) h> let x = allPairs2 [1..10000] (0.00 secs, 510488 bytes) h> deepseq x True True (10.47 secs, 4401625192 bytes) h> deepseq x True True (2.21 secs, 1031864 bytes) I'm no expert, but I think that allPairs2 is likely as good as you're going to get with straightforward Haskell using lists. It doesn't build up a lot of unevaluated computation, and if you only need to see the first n elements it's not going to have to process the entire input. allPairs1 has most of the good properties of allPairs2 but is a bit worse because of the concatenation, though concatenating in this way isn't a disaster like it would be in a strict functional programming language. -bob On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin wrote:

...

I'm a Haskell beginner, and I'm baffled trying to reason about code performance, at least with GHC. For a program I'm writing I needed to find all pairs of elements of a list. That is, given the list "ABCD" I wanted to wind up with the list [('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where the order of elements in the resulting list is immaterial, but I don't want both ('A', 'B') and ('B', 'A'), for example.

My first attempt looked like this:

allPairs1 :: [a] -> [(a, a)] allPairs1 [] = [] allPairs1 (x:xs) = map (\a -> (x, a)) xs ++ allPairs1 xs

Benchmarking with ghci's ":set +s" reveals the following performance (median of three runs shown):

$ ghci GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o ) Prelude Control.DeepSeq AllPairs> :set +s Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True True (4.85 secs, 4004173984 bytes)

A colleague suggested getting rid of the list append as follows:

allPairs2 :: [a] -> [(a, a)] allPairs2 [] = [] allPairs2 (x:xs) = allPairs2' x xs xs where allPairs2' x [] [] = [] allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs allPairs2' x [] (z:zs) = allPairs2' z zs zs

Not surprisingly, that runs faster:

Prelude Control.DeepSeq AllPairs> deepseq (allPairs2 [1..10000]) True True (2.14 secs, 4403686376 bytes)

I then figured I could do even better by rewriting the code tail-recursively:

allPairs3 :: [a] -> [(a, a)] allPairs3 [] = [] allPairs3 (x:xs) = allPairs3' x xs xs [] where allPairs3' :: a -> [a] -> [a] -> [(a, a)] -> [(a, a)] allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h, x):result) allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result allPairs3' _ [] [] result = result

This takes half the memory as the above (yay!) but runs substantially *slower* (and appears to be thrashing my computer's memory system):

Prelude Control.DeepSeq AllPairs> deepseq (allPairs3 [1..10000]) True True (10.58 secs, 2403820152 bytes)

What gives? Why does my tail-recursive implementation run even slower and presumably produce more garbage than my initial, naive implementation? Is there some optimization GHC is performing for allPairs1 and allPairs2 that it can't apply to allPairs3?

Similarly, how should I, as a newcomer who wants to write efficient Haskell code, reason about whether a code change is likely to improve rather than degrade performance? Guidelines like "per-iteration appends = bad" and "tail recursion = good" are great, but the preceding data indicate that something subtler is taking precedence over those guidelines with respect to code performance.

Thanks in advance, -- Scott

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafe

Carter Schonwald

8:02 p.m.

It's also worth adding that ghci does a lot less optimization than ghc. Likewise, the best tool for doing performance benchmarking is the excellent Criterion library. To repeat: use compiled code for benchmarking, and use criterion. Ghci is not as performance tuned as compiled code, except when ghci is linking in code that's already been compiled On Tuesday, September 3, 2013, Bob Ippolito wrote:

...

Haskell's non-strict evaluation can often lead to unexpected results when doing tail recursion if you're used to strict functional programming languages. In order to get the desired behavior you will need to force the accumulator (with something like Data.List's foldl', $!, seq, BangPatterns, etc.).

One issue with the tail recursive version is that you're basically sequencing it twice, forcing the result is going to force the whole spine of the list, and then you're walking it again with deepseq. The overhead of the deepseq call with that size list on my machine is 2.2 seconds, so you're basically paying that cost twice with a tail recursive version. allPairs2 only forces what is needed, so deepseq isn't traversing any data structures that are already forced.

I think what's happening with allPairs2 is that GHC is throwing away the the list during the traversal since the result of the computation isn't used at all. I get very different timings (still fast, but no longer orders of magnitude difference) for allPairs2 if the result is still around. You could probably figure this out with the heap profiler.

h> deepseq (allPairs2 [1..10000]) True True (2.47 secs, 4403724176 bytes) h> let x = allPairs2 [1..10000] (0.00 secs, 510488 bytes) h> deepseq x True True (10.47 secs, 4401625192 bytes) h> deepseq x True True (2.21 secs, 1031864 bytes)

I'm no expert, but I think that allPairs2 is likely as good as you're going to get with straightforward Haskell using lists. It doesn't build up a lot of unevaluated computation, and if you only need to see the first n elements it's not going to have to process the entire input. allPairs1 has most of the good properties of allPairs2 but is a bit worse because of the concatenation, though concatenating in this way isn't a disaster like it would be in a strict functional programming language.

-bob

On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin

...
wrote:

...
I'm a Haskell beginner, and I'm baffled trying to reason about code performance, at least with GHC. For a program I'm writing I needed to find all pairs of elements of a list. That is, given the list "ABCD" I wanted to wind up with the list [('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where the order of elements in the resulting list is immaterial, but I don't want both ('A', 'B') and ('B', 'A'), for example.

My first attempt looked like this:

allPairs1 :: [a] -> [(a, a)] allPairs1 [] = [] allPairs1 (x:xs) = map (\a -> (x, a)) xs ++ allPairs1 xs

Benchmarking with ghci's ":set +s" reveals the following performance (median of three runs shown):

$ ghci GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o ) Prelude Control.DeepSeq AllPairs> :set +s Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True True (4.85 secs, 4004173984 bytes)

A colleague suggested getting rid of the list append as follows:

allPairs2 :: [a] -> [(a, a)] allPairs2 [] = [] allPairs2 (x:xs) = allPairs2' x xs xs where allPairs2' x [] [] = [] allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs allPairs2' x [] (z:zs) = allPairs2' z zs zs

Not surprisingly, that runs faster:

Prelude Control.DeepSeq AllPairs> deepseq (allPairs2 [1..10000]) True True (2.14 secs, 4403686376 bytes)

I then figured I could do even better by rewriting the code tail-recursively:

allPairs3 :: [a] -> [(a, a)] allPairs3 [] = [] allPairs3 (x:xs) = allPairs3' x xs xs [] where allPairs3' :: a -> [a] -> [a] -> [(a, a)] -> [(a, a)] allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h, x):result) allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result allPairs3' _ [] [] result = result

This takes half the memory as the above (yay!) but runs substantially *slower* (and appears to be thrashing my computer's memory system):

Prelude Control.DeepSeq AllPairs> deepseq (allPairs3 [1..10000]) True True (10.58 secs, 2403820152 bytes)

What gives? Why does my tail-recursive implementation run even slower and presumably produce more garbage than my initial, naive implementation? Is there some optimization GHC is performing for allPairs1 and allPairs2 that it can't apply to allPairs3?

Similarly, how should I, as a newcomer who wants to write efficient Haskell code, reason about whether a code change is likely to improve rather than degrade performance? Guidelines like "per-iteration appends = bad" and "tail recursion = good" are great, but the preceding data indicate that something subtler is taking precedence over those guidelines with respect to code performance.

Thanks in advance, -- Scott

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafe

Scott Pakin

4 Sep 4 Sep

11:33 a.m.

On 09/03/2013 06:02 PM, Carter Schonwald wrote:

...

It's also worth adding that ghci does a lot less optimization than ghc.

Yes, I discovered that before I posted. Note from my initial message that I used ghc to compile, then loaded the compiled module into ghci: Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o )

...

Likewise, the best tool for doing performance benchmarking is the excellent Criterion library.

Ah, I didn't know about Criterion; that does look useful. For the record, here's what Criterion reports for my three all-pairs implementations: Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs1" $ nf allPairs1 [1..10000]] ... mean: 5.184160 s, lb 5.156169 s, ub 5.212516 s, ci 0.950 std dev: 144.4938 ms, lb 127.3414 ms, ub 164.8774 ms, ci 0.950 Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs2" $ nf allPairs2 [1..10000]] ... mean: 2.310527 s, lb 2.290451 s, ub 2.329349 s, ci 0.950 Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs3" $ nf allPairs3 [1..10000]] ... mean: 10.05609 s, lb 10.02453 s, ub 10.08866 s, ci 0.950 As before, allPairs2 is the fastest, followed by allPairs1, with allPairs3 in last place. -- Scott

Carter Schonwald

12:15 p.m.

Awesome/ thanks for sharing. It's worth noting that criterion is also pretty great for microbenchmarks too. On my machine I get pretty good timing accuracy on anything that takes more than 20 nanoseconds. On Wednesday, September 4, 2013, Scott Pakin wrote:

...

On 09/03/2013 06:02 PM, Carter Schonwald wrote:

...
It's also worth adding that ghci does a lot less optimization than ghc.

Yes, I discovered that before I posted. Note from my initial message that I used ghc to compile, then loaded the compiled module into ghci:

Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o )

Likewise, the best tool for doing performance benchmarking is the

...
excellent Criterion library.

Ah, I didn't know about Criterion; that does look useful. For the record, here's what Criterion reports for my three all-pairs implementations:

Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs1" $ nf allPairs1 [1..10000]] ... mean: 5.184160 s, lb 5.156169 s, ub 5.212516 s, ci 0.950 std dev: 144.4938 ms, lb 127.3414 ms, ub 164.8774 ms, ci 0.950

Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs2" $ nf allPairs2 [1..10000]] ... mean: 2.310527 s, lb 2.290451 s, ub 2.329349 s, ci 0.950

Prelude Criterion.Main AllPairs> defaultMain [bench "allPairs3" $ nf allPairs3 [1..10000]] ... mean: 10.05609 s, lb 10.02453 s, ub 10.08866 s, ci 0.950

As before, allPairs2 is the fastest, followed by allPairs1, with allPairs3 in last place.

-- Scott

Scott Pakin

8:56 p.m.

On 09/03/2013 05:43 PM, Bob Ippolito wrote:

...

Haskell's non-strict evaluation can often lead to unexpected results when doing tail recursion if you're used to strict functional programming languages. In order to get the desired behavior you will need to force the accumulator (with something like Data.List's foldl', $!, seq, BangPatterns, etc.).

I had previously tried BangPatterns and recall it not making any difference. However, this result now makes sense given what you described in terms of tail recursion thwarting some of the benefits of non-strict evaluation.

...

I think what's happening with allPairs2 is that GHC is throwing away the the list during the traversal since the result of the computation isn't used at all. I get very different timings (still fast, but no longer orders of magnitude difference) for allPairs2 if the result is still around. You could probably figure this out with the heap profiler.

h> deepseq (allPairs2 [1..10000]) True True (2.47 secs, 4403724176 bytes) h> let x = allPairs2 [1..10000] (0.00 secs, 510488 bytes) h> deepseq x True True (10.47 secs, 4401625192 bytes) h> deepseq x True True (2.21 secs, 1031864 bytes)

Ah, I hadn't thought about that. Even though deepseq is forcing the complete evaluation, it can discard evaluated results (and maybe even deforest) in the lazy allPairs1 and allPairs2 implementations but not in the tail-recursive-but-not-lazy allPairs3. Using your let trick to prevent the result from being discarded cases caused my memory subsystem to scream in pain in all three cases. I had to reduce the problem size quite a bit and still ended up spending hours of real time in GC. With this approach, allPairs1 and allPairs2 take an equal amount of time and roughly equal amounts of memory. allPairs3 takes twice as long and uses a bit more than half the memory: Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs1 [1..4000] (0.00 secs, 512968 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (1.31 secs, 1113528 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (0.74 secs, 641687568 bytes) Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs2 [1..4000] (0.00 secs, 510144 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (3.53 secs, 848312 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (0.74 secs, 705185688 bytes) Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs3 [1..4000] (0.01 secs, 510072 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (27.00 secs, 956096 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (1.54 secs, 385915160 bytes) Thanks for the explanation, -- Scott

Dan Burton

3 Sep 3 Sep

8:09 p.m.

Well for one thing, note that allPairs3 produces the result in reverse order:

...

...
...
allPairs1 "abc" [('a','b'),('a','c'),('b','c')] allPairs2 "abc" [('a','b'),('a','c'),('b','c')] allPairs3 "abc" [('b','c'),('a','c'),('a','b')]

allPairs2 uses "guarded recursion" which the optimizer probably likes, although I don't quite see why that version would use twice as much memory as allPairs3. See also: http://www.haskell.org/haskellwiki/Tail_recursion Here's a fun alternative for you to benchmark, using an old trick. I kind of doubt that this one will optimize as nicely as the others, but I am by no means an optimization guru: allPairsS :: [a] -> [(a, a)] allPairsS xs = go xs [] where go [] = id go (y:ys) = (map (\a -> (y, a)) ys ++) . go xs Further reading: http://www.haskell.org/haskellwiki/Difference_list -- Dan Burton On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin wrote:

...

I'm a Haskell beginner, and I'm baffled trying to reason about code performance, at least with GHC. For a program I'm writing I needed to find all pairs of elements of a list. That is, given the list "ABCD" I wanted to wind up with the list [('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where the order of elements in the resulting list is immaterial, but I don't want both ('A', 'B') and ('B', 'A'), for example.

My first attempt looked like this:

allPairs1 :: [a] -> [(a, a)] allPairs1 [] = [] allPairs1 (x:xs) = map (\a -> (x, a)) xs ++ allPairs1 xs

Benchmarking with ghci's ":set +s" reveals the following performance (median of three runs shown):

$ ghci GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :!ghc -c -O2 allpairs.hs Prelude> :load allpairs Ok, modules loaded: AllPairs. Prelude AllPairs> :m +Control.DeepSeq Prelude Control.DeepSeq AllPairs> :show modules AllPairs ( allpairs.hs, allpairs.o ) Prelude Control.DeepSeq AllPairs> :set +s Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True True (4.85 secs, 4004173984 bytes)

A colleague suggested getting rid of the list append as follows:

allPairs2 :: [a] -> [(a, a)] allPairs2 [] = [] allPairs2 (x:xs) = allPairs2' x xs xs where allPairs2' x [] [] = [] allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs allPairs2' x [] (z:zs) = allPairs2' z zs zs

Not surprisingly, that runs faster:

Prelude Control.DeepSeq AllPairs> deepseq (allPairs2 [1..10000]) True True (2.14 secs, 4403686376 bytes)

I then figured I could do even better by rewriting the code tail-recursively:

allPairs3 :: [a] -> [(a, a)] allPairs3 [] = [] allPairs3 (x:xs) = allPairs3' x xs xs [] where allPairs3' :: a -> [a] -> [a] -> [(a, a)] -> [(a, a)] allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h, x):result) allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result allPairs3' _ [] [] result = result

This takes half the memory as the above (yay!) but runs substantially *slower* (and appears to be thrashing my computer's memory system):

Prelude Control.DeepSeq AllPairs> deepseq (allPairs3 [1..10000]) True True (10.58 secs, 2403820152 bytes)

What gives? Why does my tail-recursive implementation run even slower and presumably produce more garbage than my initial, naive implementation? Is there some optimization GHC is performing for allPairs1 and allPairs2 that it can't apply to allPairs3?

Similarly, how should I, as a newcomer who wants to write efficient Haskell code, reason about whether a code change is likely to improve rather than degrade performance? Guidelines like "per-iteration appends = bad" and "tail recursion = good" are great, but the preceding data indicate that something subtler is taking precedence over those guidelines with respect to code performance.

Thanks in advance, -- Scott

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafe

Richard A. O'Keefe

9:48 p.m.

allPairs2 can be simplified using a trick I wouldn't dare use in any language but Haskell: triangle4 xs = fused undefined [] xs where fused x (y:ys) zs = (x,y) : fused x ys zs fused _ [] (z:zs) = fused z zs zs fused _ [] [] = [] I submit this just for grins; it happens to be a touch faster but not enough to bother about. While the result _isn't_ all possible pairs of elements, making the allPairs name a bit dodgy, it _does_ have O(|xs|**2) of them... I would be surprised if the relative performance of two approaches in ghci were always the same as their relative performance in ghc.

Scott Pakin

10 Sep 10 Sep

5:01 p.m.

On 09/03/2013 06:09 PM, Dan Burton wrote:

...

Here's a fun alternative for you to benchmark, using an old trick. I kind of doubt that this one will optimize as nicely as the others, but I am by no means an optimization guru:

allPairsS :: [a] -> [(a, a)] allPairsS xs = go xs [] where go [] = id go (y:ys) = (map (\a -> (y, a)) ys ++) . go xs

Ummm...it loops forever. Oh wait; I see it now: The final token should be "ys", not "xs". With this modification the code unfortunately uses both a lot of time and a lot of memory. For reference, here was my original, naive version (using what we now know to be a flawed way to measure execution time in a non-strict language): Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True True (4.85 secs, 4004173984 bytes) And here's the resource usage of the difference-list implementation: Prelude Control.DeepSeq AllPairs> deepseq (allPairs4 [1..10000]) True True (11.34 secs, 8404906432 bytes)

...

Further reading: http://www.haskell.org/haskellwiki/Difference_list

Thanks for the pointer. I don't see why it's called a "difference list", but I get the basic idea. -- Scott

4271

Age (days ago)

4278

Last active (days ago)

List overview

Download

8 comments

5 participants

participants (5)

Bob Ippolito
Carter Schonwald
Dan Burton
Richard A. O'Keefe
Scott Pakin

Reasoning about performance

tags

participants (5)