Simple: Lazy Sweeping Optimization #7
Labels
enhancement
impl-simple
The simple mark/sweep collector (our first one :D)
performance
Performance issues
Milestone
Comments
Techcable
added
enhancement
performance
|
Note to self (based on some playing around and reading): |
Techcable
added a commit
that referenced
this issue
May 28, 2020
The avoids explicitly setting the mark bits in the sweep phase. It implicitly resets reachable (black) objects to white and dead (white) objects to black. This is nessicarry for lazy sweeping #7
|
NOTE: Once again losing interest in this 😆 |
Techcable
added a commit
that referenced
this issue
Jun 21, 2020
I'd say this pretty much fixes #9 This was causing use after free. The parallel binary_trees example now produces the correct output (usually)! We're well on our way to #8 It appears we're still getting some segfaults since GcHandleList doesn't appear to be properly tracing -_- We should definitely look into lazy sweeping (#7). The parallel example is wasting a lot of time sweeping (mostly free) areans! However, it's output in the wrong order. Also for some reason it doesn't terminate if we enable the "small-object-arenas" feature. It looks like the sweep phase is taking way too long..... Should we work on lazy free?
|
I'm going to defer this to a later release. I want to get a working prototype in DuckLogic ASAP 😉 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This would remove the sweep phase of the collection and implicitly mark the arenas as dead instead of adding them to the free list. Instead of searching the free list, allocations would search for a free slot in the dead memory. This would amortize the sweeping cost across future allocations.
As of to 9a9634d, the binary_trees benchmark spent 30% of total time compacting (I accidentally said tracing). This would actually make the mark/sweep collector noticeably faster than the old copying collector.
This actually reduces the theoretical complexity of the algorithm 😮 Normally, the collection is proportional to total objects (live + dead), while now it's only proportional to live objects.
This is discussed in Section 2.5 of The Garbage Collection Handbook (Jones, 2012). In addition to the obvious reduction in collection time, it improves the locality of sweeping. They state that it offers good throughput, especially when there are many dead objects (the same workloads copying collectors are best at).
This threatens to increase complexity, so I'm not quite sure about whether it's a great idea... It should probably be optional, although I'd put it on by default (eager sweeping could return memory to the operating system: #6).
If issues ever arise with the simple collector's pause times, this is definitely the most obvious optimization opportunity...
However, this is currently not a very high priority for me.
The text was updated successfully, but these errors were encountered: