[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
@hvr's version is basically just a more concise way to write @parcs'
#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]: 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
#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