Skip to content

Reorganise mark&sweep trait #903

@aapoalas

Description

@aapoalas

The GC is currently implemented through a single trait that implements a "batched" (also could be called "width first") marking algorithm. This becomes a problem with massively deep ephemeron chains, like the one tested by staging/sm/regress/regress-1507322-deep-weakmap.js:

function TestGC2(m) {
  // generate a linked list of 99999 ephemerons
  var head = new Object;
  for (var key = head, i = 0; i < 99999; i++, key = m.get(key)) {
    m.set(key, new Object);
  }
  // run GC; our width first algorithm runs 99999 steps
  $262.gc();
  // check that the linked list is still there (there's no logic here to actually detect errors though)
  for (key = head; key != undefined; key = m.get(key)) {}
}
TestGC2(new WeakMap);

// check that we get here before a timeout
assert.sameValue(true, true, "deep weakmaps");

We timeout with this test due to the width-first logic of our GC, as it takes us around 26 seconds to finish. Here it would be more beneficial to use a depth-first search.

What we probably want to do then is to first perform the width-first search, either eagerly marking all WeakMaps we find and queueing up those ephemerons that have an unmarked key, OR maybe even delegating all WeakMap lookups until we find no more strong references and then performing a final depth-first marking phase with all found WeakMaps traced. After this we'll (likely) have an empty list of queued items, but it's also possible that we'll have some pending ephemerons around. Tracing these ephemerons will then reveal a new item to queue, which will mark the key of another pending ephemeron, etc... At this point we'll want to switch to a depth-first search.

The problem is how to enable this:

  • Split the HeapMarkAndSweep into HeapMark and HeapSweep.
  • Split HeapMark into HeapTraceData and HeapTraceHandle, or possibly HeapMarkWidthFirst and HeapMarkDepthFirst.
  • Create a HeapHandle trait to colocate helper APIs on HeapHandles, like get_index.

The idea in HeapTraceData and HeapTraceHandle is that HeapTraceData is used to trace through data stored on the heap to find other heap handles: this trait doesn't actually care what is done with the handles, it just provides access to them. The HeapTraceHandle is then the trait that defines what is done with the handle: is it pushed into a queue for future marking (width-first), or is it traced to find the heap data for more data?

Metadata

Metadata

Assignees

No one assigned

    Labels

    technicalRequires building something new and exciting in Rust

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions