Performance of Data.Graph.{preorderF, postorderF}
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?
Trac metadata
Trac field | Value |
---|---|
Version | 7.0.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries (other) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |