Remove TransitiveClosure param from Space::trace_object and Scanning::scan_object

[wks]

TL;DR: The type parameter of XxxxxSpace::trace_object<T: TransitiveClosure> and the trace: &mut T parameter can be removed, and the information should be carried by return value.

TL;DR2: The trace: &mut T parameter of Scanning::scan_object should also be removed and replaced by a lambda. (See comment below)

TODO list:

• Remove the <T: TransitiveClosure> parameter from XxxxxSpace::trace_object
• Remove the <T: TransitiveClosure> parameter from Scanning::scan_object
• Remove the TransitiveClosure trait completely

What?

Each space (like this one) has a trace_object<T: TransitiveClosure> method that takes a trace: &mut T parameter.

We mentioned the removal of the <T: TransitiveClosure> type parameter in #110. In that issue, @qinsoon mentioned that once we remove plan-specific ProcessEdgesWork, we can remove it.

But I think we can remove it earlier than that, and plan-specific edge-processing is not even the core of the problem. The trace parameter is more like an "out parameter" in some languages.

What does trace: &mut T do?

It only serves one purpose for any Space: to enqueue the newly marked object.

Space::trace_object does two things:

1. Mark an object if it is not already marked. When an object is marked (in GC terms, when a "grey" object becomes "black"), its edges should be enqueued (i.e. adjacent object shall turn "grey").
2. Forward an object if it is not already forwarded. If the current object reference points to a tombstone, find the address of the forwarded object.

So the result of the function should also consist of two parts:

1. If the object is newly marked, and
2. if the object is forwarded and, if it is, what is the new address.

The current trace_object signature is

    pub fn trace_object<T: TransitiveClosure>(
        &self,
        trace: &mut T,
        object: ObjectReference,
        semantics: Option<CopySemantics>,
        worker: &mut GCWorker<VM>,
    ) -> ObjectReference {

With this signature, the return value ObjectReference only carries the information of part (2). Part (1) is done by calling trace.process_node(object) just before returning. See:

• MallocSpace: here, just before returning.
• CopySpace: here, just before returning.
• ImmixSpace: without copying and with copying, just before returning.
• MarkCompactSpace: marking and forwarding, almost just before returning.
• LargeObjectSpace: here, just before returning.

Currently, the T: TransitiveClosure type parameter can only be instances of ProcessEdgesWork, and the ProcessEdgesWork::process_node(object) has only one implementation. It simply adds object into ProcessEdgesBase::nodes. This makes the polymorphism against T: TransitiveClosure pointless, for it is not polymorphic at all.

What should it return?

trace_object should have returned this:

pub struct TraceObjectResult {
    pub is_newly_marked: bool,  // true if the object is newly marked
    pub forwarded: Option<ObjectReference>,  // If an object is forwarded, return Some(newobj), otherwise None.

MallocSpace::trace_object should return TraceObjectResult(true, None) if called on a "grey" object, and TraceObjectResult(false, None) if the object is "black".

If an object is in a from-space, CopySpace::trace_object should return TraceObjectResult(true, Some(newobj)) the first time it visits an object, but TraceObjectResult(false, Some(newobj)) for subsequent visits. For objects in to-spaces, the second part should be None.

The Immix space, depending on whether it is defragging, may either return TraceObjectResult(xxx, None) or TraceObjectResult(xxx, Some(newobj)).

How should it be used?

trace_object is called in ProcessEdgesWork::process_edge. The default implementation is:

    #[inline]
    fn process_edge(&mut self, slot: Address) {
        let object = unsafe { slot.load::<ObjectReference>() };
        let new_object = self.trace_object(object);
        if Self::OVERWRITE_REFERENCE {
            unsafe { slot.store(new_object) };
        }
    }

ImmixProcessEdges and GenNurseryProcessEdges override it, but the only difference is the way to decide whether to store back to the slot. With this change, it only needs to be implemented in one way:

    #[inline]
    fn process_edge(&mut self, slot: Address) {
        let object = unsafe { slot.load::<ObjectReference>() };
        let TraceObjectResult(newly_marked, forwarded) = self.trace_object(object);
        if newly_marked {
            self.process_node(forwarded.unwrap_or(object));  // enqueue IFF newly marked
        }
        if let Some(new_object) = forwarded {
            unsafe { slot.store(new_object) };  // store IFF forwarded.
        }
    }

Discussion

Is it compatible with mark-compact? @tianleq

Is there any performance issue?

[qinsoon]

I feel we should think more carefully about this. I thought ProcessEdgesWork was replacing TransitiveClosure. However, giving it second thought, I think maybe ProcessEdgesWork is just one implementation of TransitiveClosure. If you search for TransitiveClosure in Java MMTk, you will see there are many types that implements TransitiveClosure that do not yet exist in mmtk-core, such as reference counting's mod buffer, and some write barrier implementation. It is unclear to me whether we will use ProcessEdgesWork for those cases, or we will eventually replace some uses of ProcessEdgesWork in our current code base with TransitiveClosure (which is more general).

I agree that TransitiveClosure seems unnecessary in our current code base. I think this needs to be carefully considered before we make any further change.

For your proposal:

• is_newly_marked suggests marking is happening, which is not true for policies like CopySpace.
• The performance should be measured, as TraceObjectResult introduces more branches to the performance critical code.

[wks]

I looked at various implementations. While most use cases use it as a real transitive closure in the sense of graph theory, other use cases are, in my opinion, abuses. They actually need callback functions that consume either an object or an edge.

What is TransitiveClosure

In Java MMTk (and Rust MMTk alike), TransitiveClosure is an amalgamation of two call-back functions:

• processEdge(ObjectReference reference, Address slot)
• processNode(ObjectReference reference)

Interesting enough, both functions have default failing implementation, allowing its subclasses to implement only one of the two functions. This alone shows that they are two independent callbacks. From my observation, I find that:

Where are they called:

• processEdge is always used by Scanning.scanObject or Scanning.specializedScanObject. They call processEdge on each edge of the object.
• processNode is called in various places:
  • mostly by XxxSpace.traceObject
  • during PROCESS_NEWROOTBUFFER phase in RC collectors, it is called to enqueue objects from the mod buffer
  • in StickyImmix and StickyMS, it is called to enqueue mod buffer objects

I looked at the classes that inherits TransitiveClosure in Java MMTk.

subclasses of TransitiveClosure

• TraceLocal represents the process of finding reachable objects. I think it is the only legitimate subclass of TransitiveClosure. It actually implements both processEdge (scanning the pointed-to object and forward the ref field) and processNode (enqueueing objects).
• RCZero implements processEdge alone. It just stores NULL to a field. RC collectors call Scanning.scanObject(RCZero) to find all ref fields and store NULL into it. Strictly speaking, RCZero is just a per-field callback, not really a "transitive closure" in the graph-theory sense.
  • RCModifiedProcessor and GenRCModifiedProcessor implement processEdge alone. Like RCZero, RC collectors also calls Scanning.scanObject(RCModifiedProcessor) for each object in the mod buffer.
  • RCDecBuffer is also the same: implements processEdge alone, and used as callback of scanObject.
  • ImmortalSpaceDriver.Closure is the same.
• TraceWriteBuffer implements processNode alone, which adds a node into a buffer. It is instantiated in CMSMutator as the remset. In write barrier, CMSMutator.checkAndEnqueueReference calls XxxSpace.traceObject(TraceWriteBuffer, obj) and, if it is newly marked, it will add the obj into remset.

What have we learned?

From the observation above, we see that

1. TransitiveClosure means (at least it is originally supposed to mean) "finding all reachable objects". It processes edges and nodes as it progresses, hence the interface. scanObject enqueues edges, and traceObject marks reachable objects and expands the transitive closure.
2. However, scanObject does not necessarily provide roots of a transitive closure. scanObject may just be used to enumerate object fields.
3. Similarly, traceObject does not necessarily add objects of a transitive closure. traceObject just sees if an object is first visited, and may forward objects.

Generalising scan_object and trace_object

My original post in this issue described a refactoring for XxxSpace::trace_object that decouples it from TransitiveClosure

We can do the same for Scanning::scan_object, too. From my experience with Ruby-MMTk, I think it is also necessary. Currently, the signature is:

    fn scan_object<T: TransitiveClosure>(
        trace: &mut T,
        object: ObjectReference,
        tls: VMWorkerThread,
    );

We can refactor it to:

    fn scan_object<F: FnMut(Address)>(
        object: ObjectReference,
        tls: VMWorkerThread,
        callback: F,
    );

F is equivalent to the process_edge method in the TransitiveClosure, except that it is not a &mut, but a value, and the compiler can inline it if it is small. As an FnMut, it can also capture the &mut TransitiveClosure if necessary.

Generalising "edge"

Treating an edge as Address is sufficient for OpenJDK and so on. For Ruby, and maybe other VMs, too, it may be necessary to generalise "edge", too, because sometimes an "edge" may not be simply a memory location.

    fn scan_object<E: Edge, F: FnMut(Edge)>(
        object: ObjectReference,
        tls: VMWorkerThread,
        callback: F,
    );

Detailed in #573

[tianleq]

@wks I believe it should be compatible with markcompact.

[wks]

Some history of the TransitiveClosure type in Java MMTk and Rust MMTk:

1. In the beginning, there was only TraceLocal.
   • It was semantically the same TraceLocal as it is today. It did not have any super classes.
   • Scanning.scanObject took TraceLocal as argument.
2. Someone introduced a new RC algorithm.
   • It introduced a base class TraceStep for TraceLocal that only had processEdge (was named traceObjectLocation), and used it as the base class of RC trial-deletion steps that visited object fields (i.e. needed to be passed to scanObject), but were not doing tracing as in tracing collectors.
     • Examples include TrialDeletionCollectStep. TrialDeletionGreyStep, TrialDeletionScanStep and TrialDeletionScanBlackStep.
   • Scanning.scanObject then took TraceStep as parameter.
3. Someone then did a refactoring to facilitate concurrent GC and pre-fetching.
   • It inintroduced TransitiveClosure that had both processEdge and processNode. Both processEdge and processNode provided panicking default implementations, so existing subclasses that were not TraceLocal only needed to implement one of them.
   • Scanning.scanObject then took TransitiveClosure as parameter.
4. Trial deletion was later removed, but TransitiveClosure remained.
5. We ported MMTk from Java to Rust.
   • We kept the TransitiveClosure trait, although we do not have any RC-based collectors.
   • We ported the Scanning interface "literally" to Rust, keeping the TransitiveClosure parameter.
6. We introduced the work packet framework.
   • The Scheduler superseded the TraceLocal.
   • We discussed about removing TransitiveClosure in that PR, but it was not removed.

From step 2, we see TraceStep was initially intended to be used as a callback for scanObject. TransitiveClosure is its successor, but it conflated two concerns into one:

1. to support both edge enqueueing and object enqueueing, and
2. to be the callback of scanObject.

And they should be separated.

[wks]

I tried to change the return value of trace_object to something equivalent to Option<ObjectReference>. Running it with lusearch, a GC-intensive benchmark, the effect on execution time and STW time is negligible.

Key: execution_times
|Benchmark|Group            |Trunk(ms)       |                     |       |Branch(ms)      |                                   |       |Diff  |                     |
|:-------:|:---------------:|:--------------:|:-------------------:|:-----:|:--------------:|:---------------------------------:|:-----:|:----:|:-------------------:|
|         |                 |mean            |mean without outliers|median |mean            |mean without outliers              |median |mean  |mean without outliers|
|:-------:|:---------------:|:--------------:|:-------------------:|:-----:|:--------------:|:---------------------------------:|:-----:|:----:|:-------------------:|
|lusearch |mmtk_gc-SemiSpace|20073.55 ±88.02 |20073.55 ±88.02      |20095.0|20103.75 ±123.07|20103.75 ±123.07                   |20013.0|+0.15%|+0.15%               |
|lusearch |mmtk_gc-Immix    |15770.95 ±116.82|15770.95 ±116.82     |15713.5|15773.70 ±140.14|15773.70 ±140.14                   |15714.5|+0.02%|+0.02%               |
|lusearch |mmtk_gc-GenImmix |16416.10 ±36.48 |16416.10 ±36.48      |16428.0|16416.20 ±45.48 |16401.16 ±34.73 :warning: 1 removed|16405.0|+0.00%|-0.09%               |

Key: time.stw
|Benchmark|Group            |Trunk(ms)     |                     |                  |Branch(ms)     |                                  |        |Diff  |                     |
|:-------:|:---------------:|:------------:|:-------------------:|:----------------:|:-------------:|:--------------------------------:|:------:|:----:|:-------------------:|
|         |                 |mean          |mean without outliers|median            |mean           |mean without outliers             |median  |mean  |mean without outliers|
|:-------:|:---------------:|:------------:|:-------------------:|:----------------:|:-------------:|:--------------------------------:|:------:|:----:|:-------------------:|
|lusearch |mmtk_gc-SemiSpace|8453.94 ±69.94|8453.94 ±69.94       |8452.49           |8461.10 ±106.85|8461.10 ±106.85                   |8346.715|+0.08%|+0.08%               |
|lusearch |mmtk_gc-Immix    |3994.37 ±89.71|3994.37 ±89.71       |3982.8450000000003|3984.88 ±91.55 |3984.88 ±91.55                    |3928.17 |-0.24%|-0.24%               |
|lusearch |mmtk_gc-GenImmix |4478.06 ±9.46 |4478.06 ±9.46        |4480.345          |4464.85 ±15.73 |4459.55 ±11.79 :warning: 1 removed|4454.125|-0.29%|-0.41%               |

Key: time.other
|Benchmark|Group            |Trunk(ms)      |                     |         |Branch(ms)     |                                   |        |Diff  |                     |
|:-------:|:---------------:|:-------------:|:-------------------:|:-------:|:-------------:|:---------------------------------:|:------:|:----:|:-------------------:|
|         |                 |mean           |mean without outliers|median   |mean           |mean without outliers              |median  |mean  |mean without outliers|
|:-------:|:---------------:|:-------------:|:-------------------:|:-------:|:-------------:|:---------------------------------:|:------:|:----:|:-------------------:|
|lusearch |mmtk_gc-SemiSpace|11619.89 ±32.51|11619.89 ±32.51      |11629.4  |11642.74 ±40.40|11642.74 ±40.40                    |11634.66|+0.20%|+0.20%               |
|lusearch |mmtk_gc-Immix    |11776.72 ±41.63|11776.72 ±41.63      |11796.96 |11788.97 ±73.40|11760.00 ±43.77 :warning: 1 removed|11791.55|+0.10%|-0.14%               |
|lusearch |mmtk_gc-GenImmix |11938.21 ±36.51|11938.21 ±36.51      |11951.695|11951.49 ±48.90|11934.93 ±36.51 :warning: 1 removed|11943.72|+0.11%|-0.03%               |

[k-sareen]

Sorry, I was wondering what machine did you use and how many invocations did you run it for?

[wks]

Sorry, I was wondering what machine did you use and how many invocations did you run it for?

20 invocations on hare.moma