index*OffAddr

[Roman Leshchinskiy]

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.

Any thoughts?

Roman