#5034: Performance of Data.Graph.{preorderF, postorderF}
---------------------------------+------------------------------------------
Reporter: michalt | Owner:
Type: bug | Status: new
Priority: normal | Component: libraries (other)
Version: 7.0.2 | Keywords:
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Runtime performance bug
---------------------------------+------------------------------------------
The functions can be quite slow in some cases, but it's easy to improve
the performance. I've just used `Data.Sequence` instead of ordinary lists.
This makes especially large difference for `scc` (strongly connected
components). In one extreme case I found:
{{{
benchmarking extreme case, original: scc
collecting 100 samples, 1 iterations each, in estimated 1.521492 s
bootstrapping with 100000 resamples
mean: 15.38460 ms, lb 15.35417 ms, ub 15.41660 ms, ci 0.950
std dev: 160.7804 us, lb 144.4490 us, ub 184.5445 us, ci 0.950
variance introduced by outliers: 0.990%
variance is unaffected by outliers
benchmarking extreme case, new: scc
collecting 100 samples, 12 iterations each, in estimated 559.8664 ms
bootstrapping with 100000 resamples
mean: 480.0413 us, lb 477.9581 us, ub 483.2204 us, ci 0.950
std dev: 13.01511 us, lb 9.219410 us, ub 22.67802 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
3 (3.0%) low mild
1 (1.0%) high severe
variance introduced by outliers: 0.998%
variance is unaffected by outliers
}}}
The patch is attached. I've also written some example code to illustrate
the
performance differences and two small quickcheck tests.
What do you think about it?
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5034>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
