Use eager indexing for !? #347
Conversation
* Make `(!?)` extract a value from the vector eagerly. * Make the range check for `(!?)` use one comparison instead of two.
Use `!?` for vector `ix` rather than manual range calculations. Once [this PR](haskell/vector#347) lands, that will also make the lookups eager, as they should be.
| v !? i | i < 0 || i >= length v = Nothing | ||
| | otherwise = Just $ unsafeIndex v i | ||
| -- Lengths are never negative, so we can check 0 <= i < length v | ||
| -- using one unsigned comparison. |
There was a problem hiding this comment.
I don't understand this comment and logic. Is the idea that
fromIntegral (minBound :: Int) :: Word
9223372036854775808
is always bigger than any realistic length Vector could be?
I think that should explained more clearly, this is "too clever" otherwise.
There was a problem hiding this comment.
@phadej, right; a vector of length over maxBound :: Int will break assumptions all over the place. I can add a comment to that effect.
There was a problem hiding this comment.
Existing definition has a benefit of short-circuiting in compile time when i is a statically known negative number. But I do not think that this is an important scenario.
There was a problem hiding this comment.
It's probably worth adding note that fromIntegral (i :: Int) :: Word > fromIntegral (maxBound :: Int) :: Word for all negative Ints. Such optimization is not entirely obvious
|
|
No idea. The benefits will be pretty sensitive to branch prediction load, I imagine. |
|
Even more importantly is to make sure that this change doesn't make things worse because GHC does something stupid with casts. Even more interesting target for such optimization is |
|
To be honest, I do not quite imagine As always, the smallest PRs catch the biggest scrutiny :) Could the range check optimization be moved to a separate PR? |
|
I looked at generated code for Word trick. Int->Word conversion is compiled to nothingness and less C-- code is generated. So I think it should be advantageous. I didn't try to run benchmarks yet |
(!?)extract a value from the vector eagerly.(!?)use one comparison instead of two.