[GHC] #8345: A more efficient atomicModifyIORef'
#8345: A more efficient atomicModifyIORef' ------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: task | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 7.6.3 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: None/Unknown Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- `atomicModifyIORef'` is currently defined as: {{{ #!haskell atomicModifyIORef' ref f = do b <- atomicModifyIORef ref (\x -> let (a, b) = f x in (a, a `seq` b)) b `seq` return b }}} This doesn't seem to be the best we can do, though. The following implementation exhibits a speedup of 1.7x (vanilla RTS) / 1.4x (threaded RTS) over the current implementation: {{{ #!haskell atomicModifyIORef' ref f = do b <- atomicModifyIORef ref $ \a -> case f a of v@(a',_) -> a' `seq` v b `seq` return b }}} The differences between this version and the current version are: 1. the lambda is now strict in `f a`, and 2. a new result tuple is no longer being allocated. Is there a good reason why `atomicModifyIORef'` is not already defined this way? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------ Reporter: parcs | Owner: Type: task | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by simonmar): * cc: hvr (added) Comment: It looks plausible, but before committing someone should check that it doesn't regress any of the issues that the original version was designed to avoid, see #5926. Ideally we should have tests for these. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries/base | Version: 7.6.3 Resolution: | Keywords: IORef Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Runtime | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: #5926 -------------------------------------+------------------------------------- Changes (by hvr): * failure: None/Unknown => Runtime performance bug * related: => #5926 * difficulty: Unknown => Moderate (less than a day) * milestone: => 7.10.1 * keywords: => IORef * type: task => bug -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: libraries/base | Version: 7.6.3 Resolution: | Keywords: IORef Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Runtime | Difficulty: Moderate (less performance bug | than a day) Test Case: | Blocked By: Blocking: | Related Tickets: #5926 -------------------------------------+------------------------------------- Comment (by carter): huh, i'll try to find some cycles to think about the semantics of this -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by hvr): * cc: ekmett (added) Comment: Just a thought, what about: {{{#!hs atomicModifyIORef' ref f = evaluate =<< atomicModifyIORef ref (\a -> case f a of v@(!a',_) -> v) }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by ekmett): This looks sensible to me based on a quick sanity check and smoke test, but I don't have a good sense of how to test it for correctness robustly. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): The big difference I see between the original and hvr's version is that the original installs a thunk in the `IORef` and then immediately forces it, whereas hvr's version forces it, and then installs it in the `IORef`. I don't think this difference can be observed, but I'm no expert. I think parcs's modification is just a milder step on the way to hvr's, which looks likely to be the simplest/best, but that would take benchmarking. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Actually, one possible complication (maybe): the current version guarantees allocation (and therefore an opportunity to switch threads). I don't think the proposed one does this. I also don't know if that's a problem. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by carter): a version that doesn't (in general) trigger the heap check would probably be better, at least in some cases I can probably manufacture. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by carter): Reason being that the definition of atomicModify does a CAS retry loop internally. (though maybe yielding to the scheduler could be a good thing! ) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:10 carter]:
Reason being that the definition of atomicModify does a CAS retry loop internally. (though maybe yielding to the scheduler could be a good thing! )
If it's CAS, then yeah, it's probably reasonably safe to avoid the heap check, since CAS can't be interrupted by anything else on the same OS thread. The only exception is if a program (knowingly or unknowingly) uses `atomicModifyIORef'` to allow a thread switch. But I want to emphasize that I don't know enough about these inner workings to know if this change could actually cause this sort of problem. I just raised the issue so better-informed people like you can come up with a good answer. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): It looks like my fears were unjustified. If I run this: {{{#!hs silly = \current -> (True, True) {-# INLINE flipper #-} stupid = newIORef False >>= \r -> let flop = atomicModifyIORef' r silly in forever flop main = do flippy <- forkIO stupid mapM_ print [x | x <- [1..], x `rem` 10000000 == 0] }}} with just one thread, and try either of the above implementations, it prints things just fine. I don't see any obvious signs of allocation anywhere in the `stupid` thread, so I would speculate that maybe `atomicModifyMutVar#` always gives the scheduler a go. This looks like a real good catch by parcs. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by carter): ok, my remarks about the heapcheck stuff were wrong and such. please ignore them :) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonmar): @hvr's version is basically just a more concise way to write @parcs' proposed version. I'm happy with either. Someone want to put up a diff? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:14 simonmar]:
@hvr's version is basically just a more concise way to write @parcs' proposed version. I'm happy with either. Someone want to put up a diff?
I'll be happy to do that. I realized today that if I replace `evaluate` with its specification, I do indeed get the same Core for parcs's and hvr's versions, which of course (conditionally) proves that what you say is true. But using `evaluate` itself gives somewhat different core, because it uses `seq#` to order things properly instead of `case`. I haven't inspected the Cmm or asm output, so I don't know if this makes any difference. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: patch Priority: normal | Milestone: 7.10.1 Component: | Version: 7.6.3 libraries/base | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => patch Comment: Phab:D793 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:16> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: patch Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.6.3 Libraries | Keywords: IORef Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"9e2cb00e5af9d86546f82a74c3d0382e65704d56/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="9e2cb00e5af9d86546f82a74c3d0382e65704d56" Optimise atomicModifyIORef' implementation (#8345) This forces the new value before installing it in the IORef. This optimisation was originally suggested by Patrick Palka and "exhibits a speedup of 1.7x (vanilla RTS) / 1.4x (threaded RTS)" according to #8345 Reviewed By: austin, simonmar Differential Revision: https://phabricator.haskell.org/D315 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:18> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#8345: A more efficient atomicModifyIORef' -------------------------------------+------------------------------------- Reporter: parcs | Owner: Type: bug | Status: closed Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.6.1 Libraries | Keywords: IORef Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #5926 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by hvr): * cc: core-libraries-committee@… (added) * status: patch => closed * version: 7.6.3 => 7.6.1 * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8345#comment:19> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC