Reasoning about performance
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'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 <pakin@lanl.gov> 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>
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 <pakin@lanl.gov<javascript:_e({}, 'cvml', 'pakin@lanl.gov');>
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 <javascript:_e({}, 'cvml', 'Haskell-Cafe@haskell.org');> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
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
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
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
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 <pakin@lanl.gov> 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>
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.
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
participants (5)
-
Bob Ippolito -
Carter Schonwald -
Dan Burton -
Richard A. O'Keefe -
Scott Pakin