[Haskell-cafe] Help moving a bounds check into a case branch

David Feuer david.feuer at gmail.com
Mon May 23 03:27:08 UTC 2016


Sorry for the terrible subject line, but I'm a but stuck here. A
couple days ago I overhauled Data.Sequence.splitAt, greatly improving
its performance. You can see the new implementation at
https://github.com/haskell/containers/blob/e8b1f664a631e3795dfd14f2d8c2b39c906284cf/Data/Sequence.hs#L2346
.

There's one spot where I'm still stuck, however. Much like the
original implementation, I check that the splitting index is before
the end of the sequence (to ensure correctness). I go further, in
fact, checking that the splitting index is positive, in order to avoid
allocating a new tree-top in a trivial split.

Logically, this check should be moved into the Deep case branch in
splitTreeE, to avoid pattern matching on the top of the tree twice and
performing redundant comparisons. However, when I make that move, the
split/append benchmark gets worse. When I looked at the Core, it
seemed that I confused GHC somehow. I ended up with a join point
taking an extra argument that it totally ignored. I can fix that
benchmark by marking the splitTreeMiddleE function INLINE, but then
the zipWith benchmark went screwy. Unless I can get non-fragile
results, I'm just going to accept the redundant case match.

If anyone has any ideas, please let me know.

Thanks,
David Feuer


More information about the Haskell-Cafe mailing list