prefetch primops are not currently useful
I wanted to use GHC's new prefetch primops to speed up a cover tree data structure I've been working on. The current implementation, however, is insufficient. The pure primops do not work at all. I propose an alternative using a seq-like syntax.
- *The problem**
Consider the function:
prefetchAddr3# :: Addr# -> Int# -> Addr#
It is used like:
-- addr# :: Addr# let prefetchAddr# = prefetchAddr3# addr# 0 ... do some stuff not involving addr# doRealWork prefetchAddr#
The problem is that we want the prefetch operation to get inserted at the let statement before "do some stuff...", but it doesn't get inserted there. It gets inserted directly before the call to doRealWork. This doesn't give the prefetch enough time to actually put the memory in cache, and so we still get a cache miss. I made several attempts to get around this, but they all failed due to dead code elimination.
prefetchMutableByteArray# functions solve this problem by incorporating an explicit state parameter. This forces the compiler to insert the prefetch operation at the location it is actually called in the code. This function, however, can only be used within the ST and IO monads, so it is of limited use.
- * The solution**
The solution is to restructure the pure primops to use a seq-like format. For example, the prefetchAddr3# function above would become:
prefetchAddr3# :: Addr# -> Int# -> a -> a
Then we would call the function like:
prefetchAddr3# addr# someOtherOp ... do some stuff not involving addr# doRealWork prefetchAddr#
This would correctly insert the prefetch instruction at the location it appears in the haskell code. In particular, the prefetch will occur whenever the second parameter is evaluated.
This format has the advantage that it can work in non-monadic code. In my cover tree structure, I've implemented searching the tree as a
fold operation. Every time the fold branches, only one of the branches is guaranteed to be in the cache. So I get a cache miss when I go down the other branches. I want to use the prefetch primop to prefetch the next branch the fold will go down. The fold function is pure, and I don't want to have to wedge it into the ST monad just for prefetching.