[GHC] #9353: prefetch primops are not currently useful

[GHC]

#9353: prefetch primops are not currently useful
-------------------------------------+-------------------------------------
              Reporter:              |            Owner:
  MikeIzbicki                        |           Status:  new
                  Type:  bug         |        Milestone:
              Priority:  normal      |          Version:  7.8.2
             Component:  Compiler    |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Unknown
  Unknown/Multiple                   |       Blocked By:
       Type of failure:              |  Related Tickets:
  None/Unknown                       |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
Description changed by MikeIzbicki:

Old description:

> 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.
>
> The `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# -> 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.

New description:

 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.

 The `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.

--

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9353#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler