#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

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: carter MikeIzbicki | Status: new Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Changes (by carter): * differential: => D350 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: carter MikeIzbicki | Status: patch Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Comment (by carter): So one complication that came up is that to provide the refitted pure prefetch operations as a naive primop is that the types need to be of the shape ` Addr# -> Int# -> a -> (# a #)` For some reason, the more "obvious" type ` Addr# -> Int# -> a -> a` will make GHC panic! Looking at how seq is defined, another option to consider would be to take a page from seq and define the prefetch operations in the pseudo op style like seq, ie `prefetchSeq addr offset b = case prefetch# addr offset of _ -> b` This would allow giving it the type `Addr# -> Int# -> a -> a`, with the prefetch# operation itself then having a type like `Addr# -> Int# -> State#` and the `has_side_effects=True` attribute Luite has helped sketch out this new design, and has pointed out how the semantics of touch# and seq and seq# relate to this. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: MikeIzbicki | Status: infoneeded Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Changes (by carter): * status: patch => infoneeded -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: carter MikeIzbicki | Status: new Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Changes (by carter): * owner: => carter Comment: I'll get the ball rolling on this new crazy candidate design and then try to collect some feedback -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: carter MikeIzbicki | Status: patch Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Changes (by carter): * status: new => patch Comment: ok, i've fixed up the design into one thats a) simpler b) more general c) easier to use its not perfect, but should be decent for 7.10 purposes -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9353: prefetch primops are not currently useful -------------------------------------+------------------------------------- Reporter: | Owner: MikeIzbicki | Status: new Type: bug | Milestone: 7.10.1 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: D350 | -------------------------------------+------------------------------------- Comment (by carter): its my fault partly too, that PR was originally going to be for the seq like interface, but then I realized how much more complicated that would be and moved to the state# based one -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9353#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler