Comments (16)
… which is weird, because the test execute accumE, issue #261: specifically tests a very similar network and doesn't detect any growth in network size.
Fixed it: The issue was an accumulation of finalizers, which was due to a short-cut that I took when implementing insertEdge
. As of commit 0044039, the program mentioned in #261 (comment) now runs in constant space, as indicated by the heap profile obtained through cabal run space -- +RTS -hT -RTS && hp2pretty space.hp
. 🥳
Unfortunately, the earlier program mentioned in #261 (comment) , involving observeE
and switchE
, does not run in constant space yet. 🤔
from reactive-banana.
Ok, I might have another fix:
connectChild parent child = do
w <- mkWeakNodeValue child child
modify' parent $ update childrenP (w:)
+
+ -- Add a finalizer to remove the child from the parent when the child dies.
+ case child of
+ P c@(Ref r _) -> addFinalizer r $ removeParents c
+ _ -> return ()
+
mkWeakNodeValue child (P parent) -- child keeps parent alive
The idea is pretty trivial - when a Pulse
is unreachable by the GC, then remove it from all parents. I think that the only thing we're actually leaking (in the examples here) is the Weak
value for the child and the cons cell in the parents list of children. I tested this with the following (even simpler) repro:
{-# language BlockArguments #-}
module Main where
import Control.Monad
import Control.Monad.IO.Class
import Data.Functor
import Reactive.Banana
import Reactive.Banana.Frameworks
import System.Mem
import System.Mem.Weak
import Control.Concurrent (threadDelay, yield)
withGhcDebug = id
main :: IO ()
main = withGhcDebug do
(ah1, fire1) <- newAddHandler
actuate =<< compile do
e <- fromAddHandler ah1
e2 <- execute $ e $> do
accumE () (id <$ e)
reactimate $ return () <$ e2
performGC
putStrLn "Running"
replicateM_ 10000 $ do
fire1 ()
performMajorGC
-- yield so finalizers can run.
yield
putStrLn "Done"
Ran with -hi
profile and analyzed in eventlog2html
, we see
Some noise, but that clear blue line is the signal - a clear leak.
With the fix above, we get:
But I also have to run 10x the amount of iterations otherwise it terminates too quickly!
So I think I've got a good handle on at least one fix. I think the way to proceed from here is to add a finalizer when we call newLatch
or newPulse
though - connectChild
is obviously the wrong place.
from reactive-banana.
I have fixed an additional space leak with switchP
, where old pulses would not be disconnected from the network. The cause is somewhat embarrassing: do
notation was picking up the reader monad instead of the IO
monad, and the function clearPredecessors
that disconnects the old pulses was just never called. 😳
But now, as of commit 29776bd , the heap profile for all programs mentioned in this thread is constant. 🥳 Here is the heap profile for @ocharles' initial example program:
cabal run space -- +RTS -hT -RTS && hp2pretty space.hp
In addition, several variants of the space leaks reported here are now part of the automated test suite — the tests will fail if the network grows unexpectedly.
I think that it's time to successfully close this issue. 💪 If you do find more space leaks, please don't hesitate to bring them to my attention!
from reactive-banana.
I'd watch it 🤷
from reactive-banana.
What a marathon effort! I've been reading these updates with bated breath, each one delivering a fraction but leaving me wanting more. Congratulations 🎉
from reactive-banana.
Nice, can you share how you made the pretty graph?
from reactive-banana.
Sure! I just used eventlog2html 😄
More specifically:
$ cabal run leak -- +RTS -l -hi
and build with -rtsopts -eventlog
.
I often also build with -finfo-table-map -fdistinct-constructor-tables
, as per https://well-typed.com/blog/2021/01/first-look-at-hi-profiling-mode/
from reactive-banana.
The same problem is present with just dynamic event switching - no need to bring Behavior
s in:
{-# language BlockArguments #-}
module Main where
import Control.Monad
import Data.Functor
import Reactive.Banana
import Reactive.Banana.Frameworks
import System.Mem
import System.Mem.Weak
withGhcDebug = id
main :: IO ()
main = withGhcDebug do
(ah1, fire1) <- newAddHandler
actuate =<< compile do
e <- fromAddHandler ah1
let e2 = observeE $ e $> do
accumE () (id <$ e)
e3 <- switchE never e2
reactimate $ return <$> e3
performGC
putStrLn "Running"
replicateM_ 10000 $ do
fire1 ()
performGC
I'll try and solve this leak first.
from reactive-banana.
Ok, the fix for both of these leaks isn't hard - we can just modify doAddChild
to cull any dead children:
doAddChild (P parent) (P child) = do
level1 <- _levelP <$> readRef child
level2 <- _levelP <$> readRef parent
let level = level1 `max` (level2 + 1)
w <- parent `connectChild` P child
-- Remove any dead children. These three lines are new.
let alive w = maybe False (const True) <$> deRefWeak w
children' <- filterM alive . _childrenP =<< readRef parent
modify' parent $ set childrenP children'
modify' child $ set levelP level . update parentsP (w:)
But I'm not particularly happy with this solution. When the switchE
fires I feel we should be able to propagate this information all the way up to e
. I'll have a think about how to do this.
from reactive-banana.
When implementing this, I was hoping to use finalizers to remove dead children — i.e. when switchE
switches to a new event, the old event may become garbage and the corresponding finalizer would remove it from the _childrenP
field.
Hm. Finalizers are run concurrently, but to keep our sanity, changes to the network need to be sequential and scheduled (e.g. using a writer part of Build
monad). Perhaps we should implement our own GC pass that is executed at the end of every step
, and the finalizers simply tell our GC more specific information about which weak pointers it should remove? 🤔
(One issue that I didn't think deeply enough about is the question of how fast we can remove transitive dependencies. I.e. event e3
may depend on e2
which depends on e1
. Now, if e3
is not used anymore, then both e2
and e1
can be garbage collected, but that should preferably happen in a single GC pass as opposed of two GC passes where we first discover that e2
is dead and only in the next pass that e1
is also dead because e2
is dead. The GHC GC does this alright, but any GC addendum that we implement might not.)
from reactive-banana.
@HeinrichApfelmus I've also thought about using finalizers, but the whole thing seems a lot more complex/action-at-a-distance than it needs to be. As far as I'm aware, we always have the entire graph right in front of us, through a Pulse
s parent/children lists. So if we dynamically switch away from something, we should - at that point - be able to find strongly connected components within this graph that are no longer reachable and nuke the whole lot.
I don't like finalizers partly because it's unclear when they will run, but more that it's unclear if they will run at all! I'd hate to be in a position where I accumulate just enough garbage to impact performance, but not enough to trigger the right generation GC to solve the problem.
from reactive-banana.
So if we dynamically switch away from something, we should - at that point - be able to find strongly connected components within this graph that are no longer reachable and nuke the whole lot.
Yes and no. The trouble is twofold:
- The program may reference a
Pulse
(e.g. through anEvent
) even though thatPulse
is currently not an active part of the network — but it may become part of the network again later. For example, aswitchE
periodically switching between two eventse1
ande2
, has this property — both events need to be kept alive (especially if they involve state), but only one of them is in the transitive closure of the current list ofreactimate
. This implies that we do need help from the garbage collector. - Conversely, the garbage collector may still think that a
Pulse
is alive during aswitchE
, even though thatPulse
becomes dead through the switch. Hence, the garbage collector may have some delay, and tell us that aPulse
can be removed only some time after the moment of switching. This implies that we need to expect help from the garbage collector in an asynchronous manner.
I don't like finalizers partly because it's unclear when they will run, but more that it's unclear if they will run at all!
I do agree that the documentation on finalizers is rather pessimistic. However, I feel that we may not have a choice, and in practice, it does not seem too bad (well, if it is bad, then we can report this as a bug in GHC. 😄)
from reactive-banana.
Yea, I was thinking over 1 yesterday! Thanks for sharing. Something I also want to do is try modelling our graph in Alloy and to use a model checker to work out the complexities here!
from reactive-banana.
A note to myself as to why we can't just use Ref
:
- Assume we have some chain of
Pulse
sp1, p2, ... pn
, where each pulse is a child of the previous (sop1
is the parent ofp2
, etc). - We have some top-level pulse
p
which is the parent ofp1
. - Now, introduce
pX
, which is derived by dynamically switching between some otherPulse
andpn
. - If we clean up the graph the instant
pX
switches out ofpn
, then we'll end up detachingp1
fromp
. - However, if we switch back to
pn
, then we'll never get any events, becausepn
is disconnected fromp
!
This is why we think we need help from the GC. When pX
switches out of pn
then yes, pX
should reparent. But we do still need to keep pushing p
through pn
because the dynamic event switch will keep pn
alive. I agree that it's going to be very hard to do this without letting the GC inform us.
Note that if we used dynamic event switching and switched out of pn
and don't have the possibility of switching back (e.g., something uses never
or some other mechanism that makes it impossible), then we'd lose any strong pointer to pn
allowing it to be GCed.
I need to think about promptly cleaning up a whole sequence of Pulse
s, but otherwise this is taking shape
from reactive-banana.
Thank you @ocharles !
I have revisited this problem and decided to redesign the low-level implementation entirely in order to separate concerns better. I have created a Graph
data structure without garbage collection and a GraphGC
data structure with garbage collection; this allows us to automatically test that garbage collection indeed behaves as desired. #268
The following program now runs in constant space:
{-# language BlockArguments #-}
module Main where
import Control.Monad
import Control.Monad.IO.Class
import Data.Functor
import Reactive.Banana
import Reactive.Banana.Frameworks
import System.Mem
import System.Mem.Weak
import Control.Concurrent (threadDelay, yield)
withGhcDebug = id
main :: IO ()
main = withGhcDebug do
(ah1, fire1) <- newAddHandler
actuate =<< compile do
e <- fromAddHandler ah1
e2 <- execute $ e $> do
accumE () never -- previously: accumE () (id <$ e)
reactimate $ return () <$ e2
performGC
putStrLn "Running"
replicateM_ 10000 $ do
fire1 ()
performMajorGC
-- yield so finalizers can run.
yield
putStrLn "Done"
… but the program with accumE () (id <$ e)
instead of accumE () never
does not. 🤔 … which is weird, because the test execute accumE, issue #261:
specifically tests a very similar network and doesn't detect any growth in network size.
from reactive-banana.
What a marathon effort! I've been reading these updates with bated breath, each one delivering a fraction but leaving me wanting more. Congratulations 🎉
Thanks! 😊 What do you think — maybe I could pitch the story of these update to Netflix? 🤔
from reactive-banana.
Related Issues (20)
- `reactive-banana` can't be compiled on GHC 9.2 HOT 2
- I created a Matrix channel HOT 8
- An interesting `Applicative`-ish way of combining `Event`s HOT 4
- Add `MonadMoment` instances for all monad transformers in `transformers` HOT 1
- Release 1.3.0.0 HOT 3
- Join Stackage HOT 4
- `Behavior` constantly re-evaluating when caching is expected HOT 4
- Unexpected memory growth HOT 6
- Event handler not seeing early events. HOT 12
- `Behavior`s can hold onto more memory than they need to HOT 2
- Gloss GUI events not responding HOT 5
- Idea: add a combinator to track when a behavior is a different value HOT 14
- Call `unregister` for garbage collected events made by `AddHandler`. HOT 9
- Discrepancy in model and implementation HOT 15
- Optimize representation of Latch HOT 1
- Not compatible with these-1.2 (disallowed) HOT 2
- Simultaneous events can have undefined behavior within execute HOT 2
- source-code formatter? HOT 2
- Accept deepseq-1.5 HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from reactive-banana.