Eliminate zero_static_objects_list()
ClosedPublic

Authored by simonmar on Jul 17 2015, 3:26 AM.

Details

Summary

In a workload with a large amount of code, zero_static_objects_list()
takes a significant amount of time, and furthermore it is in the
single-threaded part of the GC.

This patch uses a slightly fiddly scheme for marking objects on the
static object lists, using a flag in the low 2 bits that flips between
two states to indicate whether an object has been visited during this
GC or not. We also have to take into account objects that have not
been visited yet, which might appear at any time due to runtime linking.

Test Plan

validate

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
simonmar retitled this revision from to Eliminate zero_static_objects_list().Jul 17 2015, 3:26 AM
simonmar updated this object.
simonmar edited the test plan for this revision. (Show Details)
simonmar added reviewers: bgamari, ezyang, rwbarton.
bgamari requested changes to this revision.Jul 17 2015, 4:41 AM

I think it wouldn't hurt to add more comments here. As you say this is rather fiddly and I would have quite some difficulty working out what is going on here without reconstructing the change by the looking at the patch itself. Even just pasting the commit message in a comment somewhere would be a substantial improvement in understandability (although ideally there would be more discussion that this even).

A quick comment associated with the reversible_caf_list, static_objects and scavenged_static_objects fields of gc_thread saying that these pointers may be tagged and should be untagged with UNTAG_STATIC_LIST_PTR before dereferencing would be nice.

rts/sm/Storage.h
152

It's not entirely clear from the above discussion what STATIC_FLAG_A and _B mean or in what contexts they might be used (e.g. the gc_thread.static_objects list)

This revision now requires changes to proceed.Jul 17 2015, 4:41 AM

Typo in commit message: zero_static_object_list not zero_static_objects_list

I didn't check if you put enough untags everywhere, but presumably things will break spectacularly if you missed one. Logic looks sound, but I'd mention that we only evacuate static objects on a major GC (so we will never "miss" flagging a live static object).

rts/RetainerProfile.c
1884

Any reason we can't use the END_OF_STATIC_OBJECT_LIST macro here?

rts/sm/Evac.c
335

// If the static object is not part of a static list, or it was placed in a static list the previous major GC, we need to add it to the static list of THIS GC.

(Also, there's an invariant that link_field is OF q. Obvious if you look at the call site but less obvious at the function definition.)

rts/sm/Storage.h
152

Well, A/B is meaningless; we just flip between them from one GC to another.

156

It took me a little bit of thinking to figure out why the end of the list needed to be based on static_flag too :)

ezyang accepted this revision.Jul 17 2015, 3:57 PM
simonmar updated this revision to Diff 3616.Jul 21 2015, 4:47 AM
  • Change the tagging scheme slightly to speed up the GC
  • Improve comments as suggested
simonmar updated this revision to Diff 3617.Jul 21 2015, 5:20 AM

more comments

bgamari accepted this revision.Jul 21 2015, 8:06 AM

This looks good to me. Thanks!

This revision is now accepted and ready to land.Jul 21 2015, 8:06 AM
This revision was automatically updated to reflect the committed changes.