Opened 5 years ago

Last modified 4 years ago

#9353 new bug

prefetch primops are not currently useful

Reported by: MikeIzbicki Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.8.2
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): D350
Wiki Page:

Description (last modified by MikeIzbicki)

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.

Change History (20)

comment:1 Changed 5 years ago by MikeIzbicki

Description: modified (diff)

comment:2 Changed 5 years ago by carter

Milestone: 7.10.1
Owner: set to carter

thanks for taking the time to writeup the design we discussed and motivate the change.

I think this is a reasonable breaking change to make to the prefetch primops for the pure API, i'll get to it soon.

comment:3 Changed 5 years ago by carter

Differential Rev(s): D350

comment:4 Changed 5 years ago by carter

Status: newpatch

comment:5 Changed 5 years ago 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.

comment:6 Changed 5 years ago by carter

Owner: carter deleted

comment:7 Changed 5 years ago by carter

Status: patchinfoneeded

comment:8 Changed 5 years ago by carter

Status: infoneedednew

comment:9 Changed 5 years ago by carter

Owner: set to carter

I'll get the ball rolling on this new crazy candidate design and then try to collect some feedback

comment:10 Changed 5 years ago by carter

David pointed me to #5129 and #2273 which touch on related semantic concerns in the context of seq. I'm not sure if those same problems apply there though.

comment:11 Changed 5 years ago by carter

Status: newpatch

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

comment:12 Changed 5 years ago by carter

note that its not seq-like yet for this reelase, but rather doing the state token passing.

comment:13 Changed 5 years ago by Austin Seipp <austin@…>

In f44333eae7bc7dc7b6003b75874a02445f6b633b/ghc:

Changing prefetch primops to have a `seq`-like interface

Summary:
The current primops for prefetching do not properly work in pure code;
namely, the primops are not 'hoisted' into the correct call sites based
on when arguments are evaluated. Instead, they should use a `seq`-like
interface, which will cause it to be evaluated when the needed term is.

See #9353 for the full discussion.

Test Plan: updated tests for pure prefetch in T8256 to reflect the design changes in #9353

Reviewers: simonmar, hvr, ekmett, austin

Reviewed By: ekmett, austin

Subscribers: merijn, thomie, carter, simonmar

Differential Revision: https://phabricator.haskell.org/D350

GHC Trac Issues: #9353

comment:14 Changed 5 years ago by thoughtpolice

Owner: carter deleted
Status: patchnew

Well, I'm an idiot and used the totally wrong commit message for this; this doesn't reflect the seq-based interface, but the State# based interface. I am the dumb. Sorry :(

comment:15 Changed 5 years ago 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

comment:16 Changed 5 years ago by carter

to clarify: i think the seq style api is still the right path for the future, or at least should be explored eventually.

comment:17 Changed 5 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:18 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:19 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:20 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.