New primops for indexing: index*OffAddrUsing# etc
Here's an email from Roman, and response from Simon. Making a ticket so it's kept as an idea.
In package vector, primitive vectors (the ones that Data.Vector.Unboxed
is built on top of) are represented as follows (ByteArray
and friends are wrappers for various GHC primitives provided by package primitive):
data Vector a = Vector Int -- offset into the ByteArray
Int -- length
ByteArray -- data
This representation supports cheap slicing which is quite crucial. However, indexing into such vectors is a bit more expensive than necessary:
index (Vector i _ arr) j = indexByteArray arr (i+j)
Ultimately, this requires 2 additions to get the element's address:
<base address off the ByteArray> + ((i + j) * <size of element>)
I'd like to always allocate pinned ByteArrays
and store the starting address of the vector instead of the offset:
data Vector a = Vector Addr
Int
ByteArray
This would make indexing cheaper as it would require only one addition:
index (Vector addr i _) = indexOffAddr addr i
This is quite a big deal if indexing happens in an inner loop (some algorithms become up to 20% faster). Of course, the backend could optimise the offset-based version by performing partial redundancy elimination but it doesn't and it probably wouldn't get all interesting cases even if it did. So the second version is better.
The problem is that I can't implement it because I must touch the ByteArray
after accessing the memory. This results in code like this which hides the constructor, breaking various optimisations:
case indexIntOffAddr# addr# i# of { n# ->
case touch# arr# realWorld# of { _ -> I# n# }}
After thinking about this for a while, I came up with two possible solutions. One is to provide a "pure" version of touch#:
use# :: o -> o' -> o'
such that use# x y = y. This would change the code above to:
I# (use# arr# (indexIntOffAddr# addr# i#))
I don't know how to implement this, though, because use# would have to be able to return arbitrary (unboxed) types and the code generator doesn't really seem to support this.
A perhaps simpler solution is to add a new set of primitives:
indexIntOffAddrUsing# :: o -> Addr# -> Int# -> Int#
...
These would take an additional argument which they'd touch and otherwise ignore. The code would then become:
I# (indexIntOffAddrUsing# arr# addr# i#)
Incidentally, the index*OffAddr#
primitives don't seem to be used anywhere. [Not true: there are a handful of uses of index*OffAddr#
in libraries/base, mainly GHC.Base.]
Simon replies:
indexIntOffAddrUsing#
seems like the way to go, I can't think of a better alternative.
Trac metadata
Trac field | Value |
---|---|
Version | 6.12.2 |
Type | FeatureRequest |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |