Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize minor_gc emphemeron handling #719

Open
ctk21 opened this issue Oct 26, 2021 · 2 comments
Open

Optimize minor_gc emphemeron handling #719

ctk21 opened this issue Oct 26, 2021 · 2 comments
Labels
post 5.00 Items to be worked on after OCaml 5.0 release

Comments

@ctk21
Copy link
Collaborator

ctk21 commented Oct 26, 2021

In the minor GC as it stands, we promote all ephemeron keys and let the major GC handle the complexities of knowing if a key is alive in any domain. The rational was to avoid introducing extra synchronisation barriers into the minor GC. This is a divergence from upstream, where ephemeron keys are scanned after reachable promotions have complected to allow collection of the ephemerons.

There are some optimizations that can be implemented:

  • single domain: if we know we only have one domain, then use the trunk algorithm to collect ephemerons in the minor gc
  • multi-domain: if there are no ephemerons with keys in the minor heap, then we do not need a barrier. This can be naive (determined before the minor_gc starts) or more advanced where we keep count of the number of ephemerons with keys that might be promoted but need to wait for the promotion step to end across all domains.
@ctk21
Copy link
Collaborator Author

ctk21 commented Oct 26, 2021

Beware trying to do clever things in the "multi-domain" case. Things can get really complicated. Consider two domains:

  • Domain A contains an ephemeron E1 where the key is alive in Domain B's minor heap, and the values keep the ephemeron E2 in Domain C's minor heap alive.

At the end E1 needs to be alive and E2 (and the values off E2). However E2 can not be collected easily, we need to wait until E1 has kept all the values off it alive.

(Also see the lengths the major GC goes to with multiple cycles to determine ephemerons are dead here)

@kayceesrk kayceesrk added the post 5.00 Items to be worked on after OCaml 5.0 release label Oct 27, 2021
@kayceesrk
Copy link
Contributor

Another possible improvement is to blit functions. Currently, when blitting ephemeron keys and data, we force the fields to be darkened. This is to handle the case that the target ephemeron may be on the ephe_live list of a domain, whose invariant is that there are no unmarked keys or data, which may be violated by copying in an unmarked key. One possible way of fixing this is to ensure that ephemeron sweep phase ephe_sweep also sweeps the live list.

This solution needs further thought to ensure that it is compatible with the ephemeron marking and sweeping in the major GC, which is already quite complicated. The current strategy punts the problem by taking a safe but conservative approach.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
post 5.00 Items to be worked on after OCaml 5.0 release
Projects
None yet
Development

No branches or pull requests

2 participants