961329 - Implement finding dominator trees on top of ubi::Node to find retained sizes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Here's one algorithm for computing dominator trees:
A Fast Algorithm for Finding Dominators in a Flowgraph
THOMAS LENGAUER and ROBERT ENDRE TARJAN

https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf

At the JS level, we should have a function that takes a set of globals to use as roots, and then returns a dominator tree including the biggest nodes, and dropping the smaller ones. This *should* allow us to return something that summarizes the heap usefully, while still having a constrained size.

Additionally, we should also be able to pass in to this function an optional set of objects that we *know* we care about specifically, and ensure that they do not get pruned from the dominator tree so that we can find their specific retained sizes.

Comment 1

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

In bug 666426, dominators were introduced to ionmonkey to help with various optimization stuff (I assume SSA related, but I digress). They chose to go with the simple iterative approach instead of using the pdf linked in comment 0 because it is actually faster in many cases than the Lengauer-Tarjan algorithm *and* is easier to implement.

We should further investigate our choice of algorithm, or even jsut use the simple iterative approach and keep in mind that we might be able to get a speed up by switching to the Lenguaer-Tarjan algorithm if this becomes a bottleneck down the line.

http://dxr.mozilla.org/mozilla-central/source/js/src/jit/IonAnalysis.cpp#1059

(In reply to Ryan Pearl [:rpearl] from bug 666426 comment #1)
> Created attachment 541218 [details] [diff] [review]
> build a dominator tree
> 
> This builds a dominator tree in an O(n^2) pass, using the algorithm from the
> paper "A Simple, Fast Dominance Algorithm" by Cooper et al. 
> 
> With careful engineering, the Lengauer-Tarjan which runs in O(n * log(n))
> could be used. 
> 
> However, from the paper describing the current algorithm, 
> "For the dominance calculation, the iterative algorithm runs about 2.5 times
> faster than Lengauer-Tarjan, on average. The improvement slowly decreases as
> the number of blocks increases. This is what we would expect: the Lengauer
> and Tarjan algorithm has a greater startup cost, which gets amortized in
> larger graphs. Of course, the Lengauer-Tarjan results should catch up
> quickly based on the relative asymptotic complexity. That this is not the
> case argues strongly that real-world codes have low connectivity of
> irreducible loops and their shapes allow for comparatively fast
> intersections."

Comment 2

[Jim Blandy :jimb]

(In reply to Nick Fitzgerald [:fitzgen] from comment #1)
> In bug 666426, dominators were introduced to ionmonkey to help with various
> optimization stuff (I assume SSA related, but I digress). They chose to go
> with the simple iterative approach instead of using the pdf linked in
> comment 0 because it is actually faster in many cases than the
> Lengauer-Tarjan algorithm *and* is easier to implement.

*Excellent* find.

Comment 3

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

"A Simple, Fast Dominance Algorithm" by Cooper et all: http://www.cs.rice.edu/~keith/EMBED/dom.pdf

Comment 4

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: WIP

It compiles!

And successfully fails assertions when you run the test!

Comment 5

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: WIP

Another WIP.

After talking with :jimb, we're going to hold off on saving the full dominator tree and just do retained sizes for now.

Need to create jsapi-tests which create a mock ubi::Node implementation for testing.

Need to replace ubi::Node with just an index in a lot of places to avoid unnecessary hash map lookups.

Related to above: Need to profile and speed this sucker up.

Comment 6

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: WIP

Woohoo! Finding retained sizes works! (Although ubi::Node still doesn't supply actual shallow sizes so retained sizes in this case is more like how many nodes I dominate).

Comment 7

[Jim Blandy :jimb]

(In reply to Nick Fitzgerald [:fitzgen] from comment #6)
> Woohoo! Finding retained sizes works! (Although ubi::Node still doesn't
> supply actual shallow sizes so retained sizes in this case is more like how
> many nodes I dominate).

Fantastic!

How long does it take to run on gmail?

Comment 8

[Jim Blandy :jimb]

Shouldn't the argument to D.M.DominatorTree.p.getRetainedSize be a Debugger.Object? Then we'd just use Debugger::unwrapDebuggeeValue instead of CheckedUnwrap.

Comment 9

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

(In reply to Jim Blandy :jimb from comment #7)
> (In reply to Nick Fitzgerald [:fitzgen] from comment #6)
> > Woohoo! Finding retained sizes works! (Although ubi::Node still doesn't
> > supply actual shallow sizes so retained sizes in this case is more like how
> > many nodes I dominate).
> 
> Fantastic!
> 
> How long does it take to run on gmail?

https://gist.github.com/fitzgen/10395937

Didn't test on gmail, but a few other pretty heavy sites. Takes 45 - 60 *seconds* on the sites I checked :(

I think it's pretty much walking the whole browser's heap every time -- I think if we don't follow cross compartment ubi::Node edges we'll be a lot better off.

Still haven't made improvements where we use indices instead of looking up hashmap values a ton of times for every iteration of the hottest loop. Hoping this will give a lot of perf benefit as well as clean up the code a bunch.

Comment 10

[Jim Blandy :jimb]

Let's get that HashSet<int> hack in there, and see how it goes. And adding 'compartment()' to ubi::Node is straightforward.

Comment 11

[Jim Blandy :jimb]

Oh, I guess that's only a storage win; it has nothing to do with how *often* we do table lookups. NM.

Comment 12

[Jim Blandy :jimb]

It's worth noting that the Cooper algorithm's performance was being measured on control flow graphs, not heap graphs. And he says:

> Of course, the Lengauer-Tarjan results should catch up
> quickly based on the relative asymptotic complexity. That this is not the
> case argues strongly that real-world codes have low connectivity of
> irreducible loops and their shapes allow for comparatively fast
> intersections.

In other words, he's speculating that the simpler algorithm's acceptable performance is due to incidental characteristics of the way people write code. I wouldn't expect heap graphs to have much in common with control flow graphs.

At some point, we may want to try implementing the Lengauer-Tarjan algorithm.

Comment 13

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Jim points out that if/when we limit the DTs to compartments of interest, we will have to treat "external" inbound edges from other compartments as roots. Luckily, they are all right here: https://hg.mozilla.org/mozilla-central/file/5010b38abf18/js/src/jscompartment.h#l201

Comment 14

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: WIP

This patch has creating dominators down to ~1150ms on CNN.com. Would obviously like to get it faster, but this is pretty good considering that it used to take ~60s!

Comment 15

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: profile

Screenshot of some profiling.

Spending ~72% of time in the |DominatorTree::create| method itself and ~25% of time in the post order traversal. Didn't expect so much time in the traversal. Also surprised that the intersect function isn't showing up at all.

Comment 16

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: WIP

Ok, down to ~605ms! This patch makes it so that we convert the predecessor HashSets to plain old C arrays once we are done collecting them. This makes sense because when we are collecting the predecessor sets, we are testing for membership a bunch, but after that we only iterate over them a bunch of times and never test membership again.

I still need to add custom sweep logic to remove entries from the DominatorTree's internal table as entries are collected.

I think this is fast enough to land.

As a follow up, I want to change the |captureDominatorTree| method to return a promise and move the actual dominator tree computation off the main thread. Once we've done the traversal and built up the predecessor sets, we don't need anything from ubi::Nodes anymore (except their shallow sizes, which we can trivially fetch before spawning the thread) because we've built up a reversed copy of the heap graph. Once we dominator tree computation on the new thread completes, it would resolve the promise.

Comment 17

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

On cnn.com, we get:

130,377 nodes
410,498 edges

The "simple, engineered" paper claims that the Lengauer-Tarjan algorithm amortizes around 30,000 nodes and starts beating the engineered approach. We are well above that gate here, so we should probably file a follow up to investigate switching algorithms.

Comment 18

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: dominators.patch

I think we're ready to start the review cycle :)

Try push: https://tbpl.mozilla.org/?tree=Try&rev=e007c7301119

Comment 19

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Comment on attachment 8421397 [details] [diff] [review]
dominators.patch

Clearing review since this needs to be rebased on top of the new ubi node stuff, and also needs a green try push.

Comment 20

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: dominators.patch

Rebased and compiling + passing tests locally. No try push yet because the ubi::Node::compartment try push is failing so this one would too. Gotta fix that first.

Comment 22

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Implement JS::ubi::DominatorTree

This commit adds the `JS::ubi::DominatorTree` class. It uses the simple,
engineered algorithm for finding immediate dominators described in "A Simple,
Fast Dominance Algorithm" by Cooper et al[0]. This commit does not expose
dominator trees to JS, or provide any means of walking the dominator tree. These
things are reserved for future changesets.

[0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf

Comment 23

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=8a5f2b9b7534

Comment 24

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Implement JS::ubi::DominatorTree

This commit adds the `JS::ubi::DominatorTree` class. It uses the simple,
engineered algorithm for finding immediate dominators described in "A Simple,
Fast Dominance Algorithm" by Cooper et al[0]. This commit does not expose
dominator trees to JS, or provide any means of walking the dominator tree. These
things are reserved for future changesets.

[0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf

Comment 25

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

This version should fix those warnings in opt builds: https://treeherder.mozilla.org/#/jobs?repo=try&revision=a88a85ebcc95

Comment 26

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

Comment on attachment 8688026 [details] [diff] [review]
Implement JS::ubi::DominatorTree

Review of attachment 8688026 [details] [diff] [review]:
-----------------------------------------------------------------

Ok, I've wasted way too much time today thinking about the algorithm and confusing myself repeatedly trying to find heuristic optimizations. This looks good to me.

::: js/public/UbiNodeDominatorTree.h
@@ +22,5 @@
> +namespace JS {
> +namespace ubi {
> +
> +/**
> + * In a graph with a root node `R`, a node `A` is said to "dominate" a node `B`

*directed graph

@@ +47,5 @@
> + *     the original node wasn't (directly or indirectly) referencing them. In
> + *     other words, the retained size is the shallow size of a node plus the
> + *     shallow sizes of every other node it dominates. For example, the root
> + *     node in a binary tree might have a small shallow size that does not take
> + *     up much space itself, but it dominates the rest of the binary tree and

(assuming no external pointers into the tree)

@@ +78,5 @@
> +  private:
> +    // Data members.
> +    mozilla::Vector<Node> postOrder;
> +    NodeToIndexMap nodeToPostOrderIndex;
> +    mozilla::Vector<size_t> doms;

This is a big vector, right? Do you need 64 bits, or would uint32_t work? (Same comment for NodeToIndexMap, of course.)

@@ +100,5 @@
> +                finger1 = doms[finger1];
> +            while (finger2 < finger1)
> +                finger2 = doms[finger2];
> +        }
> +        return finger1;

I guess there's a root node that this is guaranteed to terminate at?

I'm idly wondering whether the more straightforward

  while (finger1 != finger2) {
    if (finger1 < finger2)
       ....
    else if (finger2 < finger1)
       ....

would be more optimizeable (as in, automatically, by the compiler) through some funky asm trick that would only require comparing (subtracting?) the two values once. The code as written (and I know it comes straight from the paper) seems like it forces the != and </> comparisons to be separate.

@@ +179,5 @@
> +                MOZ_ASSERT(ptr);
> +                predecessorVectors[i].infallibleAppend(ptr->value());
> +            }
> +        }
> +        predecessorSets.finish();

Ok, I'm just twiddling things here, but does this really require a Vector of Vectors? Would it complicate things too much to count the total number of predecessors when building the predecessor sets, then use a single Vector of the right size where node i's predecessors are stored at indexes v[i] .. v[i+1]-1? (So you'd have a initial size-N section giving start indexes for predecessors for each node, then the predecessors themselves packed tight.) It's an abuse of the type system (it's conceptually a Vector of Vectors, only instead of storing N <length,separately alloced array> pairs you'd dangerously typelessly encode them into a flat vector of 32- or 64-bit ints.) But I always think of heap graphs as *huge*, so I'm paranoid about space.

Even if it's worthwhile, it's obviously followup material.

::: js/public/UbiNodePostOrder.h
@@ +174,2 @@
>                  return false;
> +            }

This all seems nice and pure and correct, but would it be faster yet still correct if you directly iterated over all of the edges here?

while (!stack.empty())
    (node, edges) = stack.pop()
    for (e : edges)
        visit(e)
        if (!seen(e.referent))
            seen.add(e.referent)
            push(e.referent)
    visit(node)

It seems like you would get more cache bouncing when keeping half-eaten nodes on the stack, but maybe it's better? Or maybe my alternative is wrong for some reason I'm not thinking of.

Comment 27

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Thanks for the speedy review turn around!

(In reply to Steve Fink [:sfink, :s:] from comment #26)
> @@ +78,5 @@
> > +  private:
> > +    // Data members.
> > +    mozilla::Vector<Node> postOrder;
> > +    NodeToIndexMap nodeToPostOrderIndex;
> > +    mozilla::Vector<size_t> doms;
> 
> This is a big vector, right? Do you need 64 bits, or would uint32_t work?
> (Same comment for NodeToIndexMap, of course.)

I think uint32_t should work fine, since we will OOM before there are more than UINT32_MAX nodes.

> @@ +100,5 @@
> > +                finger1 = doms[finger1];
> > +            while (finger2 < finger1)
> > +                finger2 = doms[finger2];
> > +        }
> > +        return finger1;
> 
> I guess there's a root node that this is guaranteed to terminate at?

I can add some more assertions here, but yes. doms[length - 1] is the root, which points to itself as its dom, so in the worst (and probably also most common) case we walk both fingers all the way up to doms[length - 1].

> I'm idly wondering whether the more straightforward
> 
>   while (finger1 != finger2) {
>     if (finger1 < finger2)
>        ....
>     else if (finger2 < finger1)
>        ....
> 
> would be more optimizeable (as in, automatically, by the compiler) through
> some funky asm trick that would only require comparing (subtracting?) the
> two values once. The code as written (and I know it comes straight from the
> paper) seems like it forces the != and </> comparisons to be separate.

Inspected the emitted asm and you're right! Nice eye :P

> @@ +179,5 @@
> > +                MOZ_ASSERT(ptr);
> > +                predecessorVectors[i].infallibleAppend(ptr->value());
> > +            }
> > +        }
> > +        predecessorSets.finish();
> 
> Ok, I'm just twiddling things here, but does this really require a Vector of
> Vectors? Would it complicate things too much to count the total number of
> predecessors when building the predecessor sets, then use a single Vector of
> the right size where node i's predecessors are stored at indexes v[i] ..
> v[i+1]-1? (So you'd have a initial size-N section giving start indexes for
> predecessors for each node, then the predecessors themselves packed tight.)
> It's an abuse of the type system (it's conceptually a Vector of Vectors,
> only instead of storing N <length,separately alloced array> pairs you'd
> dangerously typelessly encode them into a flat vector of 32- or 64-bit
> ints.) But I always think of heap graphs as *huge*, so I'm paranoid about
> space.
> 
> Even if it's worthwhile, it's obviously followup material.

You're right to think of these things as huge because they are or at least definitely can be. This is a good suggestion, I've file bug 1225531 to track it.

> ::: js/public/UbiNodePostOrder.h
> @@ +174,2 @@
> >                  return false;
> > +            }
> 
> This all seems nice and pure and correct, but would it be faster yet still
> correct if you directly iterated over all of the edges here?
> 
> while (!stack.empty())
>     (node, edges) = stack.pop()
>     for (e : edges)
>         visit(e)
>         if (!seen(e.referent))
>             seen.add(e.referent)
>             push(e.referent)
>     visit(node)
> 
> It seems like you would get more cache bouncing when keeping half-eaten
> nodes on the stack, but maybe it's better? Or maybe my alternative is wrong
> for some reason I'm not thinking of.

Maybe I am missing something, but I think that this would no longer be post-order because you're pushing edge referents without visiting them and then visiting the current node, meaning that the current node is visited before all of its referents are visited.

Comment 28

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/65fd70e90f5c

Comment 29

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

(In reply to Nick Fitzgerald [:fitzgen][:nf] from comment #27)
> Thanks for the speedy review turn around!
> 
> (In reply to Steve Fink [:sfink, :s:] from comment #26)
> > while (!stack.empty())
> >     (node, edges) = stack.pop()
> >     for (e : edges)
> >         visit(e)
> >         if (!seen(e.referent))
> >             seen.add(e.referent)
> >             push(e.referent)
> >     visit(node)
> > 
> > It seems like you would get more cache bouncing when keeping half-eaten
> > nodes on the stack, but maybe it's better? Or maybe my alternative is wrong
> > for some reason I'm not thinking of.
> 
> Maybe I am missing something, but I think that this would no longer be
> post-order because you're pushing edge referents without visiting them and
> then visiting the current node, meaning that the current node is visited
> before all of its referents are visited.

Oops! Uh, yeah. How about:

  while (!stack.empty)
    (node, edges) = stack.pop()
    if (edges.empty())
      visit(node)
      continue
    push(node, empty edges)
    for (e : edges)
      visit(e)
      if (!seen(e.referent))
        seen.add(e.referent)
        push(e.referent, e.referent.edges)

or equivalently with mutation:

  while (!stack.empty)
    (node, edges) = stack.top()
    if (edges.empty())
      stack.pop()
      visit(node)
      continue
    while (!edges.empty())
      e = edges.pop()
      visit(e)
      if (!seen(e.referent))
        seen.add(e.referent)
        push(e.referent, e.referent.edges)

but maybe this is getting pretty close to what you already have.

Comment 30

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/65fd70e90f5c