1169329 - Do marking breadth-first

Status: RESOLVED WONTFIX

(Core :: JavaScript: GC, defect)

Description

[Terrence Cole [:terrence]]

Attachment: breadth_first_marking-v0.diff

Try run at:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=1a6d0ec59828

It, surprisingly, doesn't appear to have destroyed the world. The try run is quite clean, actually. Moreover, octane does not appear to be any slower locally. I'd like to move forward with landing this.

Comment 1

[Andrew McCreight [:mccr8]]

Out of curiosity, what's the reason for doing this?

Comment 2

[Jon Coppeard (:jonco)]

The patch is a nice simplification but this seems like a fairly fundamental change to the marking algorithm and one which could have unforeseen performance implications so I think we should be careful here.

Terrence, how about checking Talos results for this?

Also, how does this change influence the maximum size of the marking stack?  A quick google points out that BFS uses more stack space than DFS because it stores all yet-to-be explored children of every parent of the current node whereas DFS uses space proportional to the depth.

Comment 3

[Terrence Cole [:terrence]]

(In reply to Jon Coppeard (:jonco) from comment #2)
> The patch is a nice simplification but this seems like a fairly fundamental
> change to the marking algorithm and one which could have unforeseen
> performance implications so I think we should be careful here.

Quite right! I had planned to push this and let it sit for a cycle with the intention of backing it out if AWFY, AWSY, or our OOM metrics budged.  
 
> Terrence, how about checking Talos results for this?

That's a great idea. Also an AWSY run might be worthwhile.

> Also, how does this change influence the maximum size of the marking stack? 
> A quick google points out that BFS uses more stack space than DFS because it
> stores all yet-to-be explored children of every parent of the current node
> whereas DFS uses space proportional to the depth.

Ouch! I had not realized that, but it's pretty obvious in retrospect. I suppose the worst case is going to be much more worse and probably more common with BFS.

Comment 4

[Steve Fink [:sfink] [:s:]]

(In reply to Jon Coppeard (:jonco) from comment #2)
> The patch is a nice simplification but this seems like a fairly fundamental
> change to the marking algorithm and one which could have unforeseen
> performance implications so I think we should be careful here.
> 
> Terrence, how about checking Talos results for this?

Sure, I think we'd only want this if it buys us perf, and I could argue it either way.

> Also, how does this change influence the maximum size of the marking stack? 
> A quick google points out that BFS uses more stack space than DFS because it
> stores all yet-to-be explored children of every parent of the current node
> whereas DFS uses space proportional to the depth.

Yes, this is the big effect. But it depends on your graph. Imagine a rightward-leaning tree:

  O
  |\
  O O
    |\
    O O
      |\
      O O

etc. The DFS will accumulate the full set of left children on the stack during its traversal down. The BFS queue will have a max size of 2. It's much easier to come up with examples where the DFS uses less space than BFS, though.

There are also cache effects. When constructing a node, if you allocate children but don't fill them in (with their children and other gunk), then BFS is good. But if you fully initialize children (including allocating their children) before placing them in the parent, then DFS is more likely to go in allocation order.

Generally speaking, DFS seems to me like it'd be more likely to be what we want, but a hybrid scheme could be the best overall. Though perhaps we're already doing it. We'd want to process leaves or very small subtrees immediately, push nearby stuff, and unshift things that are farther away (likely to be a cache miss by the time we get to them anyway). Or something like that. Apply magical heuristic pixie dust as needed. I think we already process known leaves immediately (as in, fields that never point to other gcthings), so already have the important piece.

Comment 5

[Terrence Cole [:terrence]]

I measured before and after with cachegrind and a hybrid approach that does depth-first only when in the same arena or in the same chunk. None of these schemes performed as well (cache-wise) as the existing depth first approach.