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

[GC] Change the goal of the marking phase. #7303

Closed
vicuna opened this issue Jul 22, 2016 · 5 comments
Closed

[GC] Change the goal of the marking phase. #7303

vicuna opened this issue Jul 22, 2016 · 5 comments

Comments

@vicuna
Copy link

vicuna commented Jul 22, 2016

Original bug ID: 7303
Reporter: bobot
Status: closed (set by @mshinwell on 2016-12-09T11:38:28Z)
Resolution: not a bug
Priority: low
Severity: feature
Category: runtime system and C interface
Monitored by: braibant @ygrek

Bug description

In one sentence, currently the GC aims at marking at the end of the marking phase all the values reachable during any time of the marking phase, however the correctness of the GC ask only for the values reachable at the end of the marking phase.

The current behavior simplify the understanding of the marking phase, however it forces some useless value to be marked (eg. overwritten values and value obtained from weak pointer). In light of #7279, it can be interesting to accept to not mark them.

Currently the marking phase (simplified):

  • start: mark grey all the roots
  • during: mark grey overwritten values by caml_modify
  • during: mark grey created values in major heap
  • during: mark grey values looked up using Weak.get
  • in slice: mark grey values pointed by marked values
  • stop when there is no grey values

The idea would be to distinguish two kind of roots:

  • the gentle one that are modified only through caml_modify (global ocaml variable)
  • the hard one that are directly modified (C globals, C locals, stack)

And modify all the marking algorithm:

  • start: mark grey all the gentle roots
  • during: mark grey written values by caml_modify
  • during: mark grey created values in major heap (optional)
  • in slice: mark grey values pointed by marked values
  • stop when there is no grey values and marking grey hard roots doesn't mark any new values.

The advantage is that overwritten values and value obtained from weak pointer don't have to be marked. The function Weak.get_copy can be deprecated in favor of Weak.get, since there is no more advantage and contrary to the old Weak.get_copy the children of the value are not marked.

Do you think this algorithm is correct? Is it used in another GC?

@vicuna
Copy link
Author

vicuna commented Jul 23, 2016

Comment author: @lpw25

Do you think this algorithm is correct? Is it used in another GC?

Without reading the description too carefully, I think you are roughly describing a Dijkstra barrier, as opposed to the Yuasa barrier currently used by OCaml.

@vicuna
Copy link
Author

vicuna commented Jul 25, 2016

Comment author: bobot

Without reading the description too carefully, I think you are roughly describing a Dijkstra barrier, as opposed to the Yuasa barrier currently used by OCaml.

Thanks a lot! It seems exactly that. With these keywords, for the one interested, an article that describes different kinds of GC barrier and their respective cache locality https://www.cs.kent.ac.uk/pubs/2010/3012/content.pdf .

Interestingly there is an issue on ocaml-multicore for going in the other way: ocaml-multicore/ocaml-multicore#41

@vicuna
Copy link
Author

vicuna commented Dec 8, 2016

Comment author: @mshinwell

@bobot Does this issue need to remain open?
The multicore branch has a replacement major GC, for what it's worth.

@vicuna
Copy link
Author

vicuna commented Dec 9, 2016

Comment author: bobot

No it can be closed. I'm just going to paste the reason given by multicore:

This eliminates the small stop-the-world phase at the end of a major collection > to finish the marking work. Stop-the-world phase is only required to flip the
colors at the end of collection.

Changing the runtime for removing the need for Weak.get_copy seems a dead-end, perhaps a new feature in the compiler could help.

@vicuna vicuna closed this as completed Dec 9, 2016
@vicuna
Copy link
Author

vicuna commented Feb 21, 2017

Comment author: @damiendoligez

We might want to change the weak hash tables along the lines suggested by sawfish in #7279#c16109 but yes, changing the barrier means introducing a pause at the end of the major GC.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant