1250966 - Filter out paths which already reached the target node but continue before finishing

Status: RESOLVED FIXED

(DevTools :: Memory, defect, P2)

Description

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

Say the three shortest retaining paths are:

1. root -> a -> target
2. root -> b -> target
3. root -> a -> target -> b -> target

We should filter out path 3 since it is not very helpful and just noise to the results.

Comment 1

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

This can be done in the deduplicatePaths function: https://dxr.mozilla.org/mozilla-central/source/devtools/shared/heapsnapshot/shortest-paths.js#28

Comment 2

[Jim Blandy :jimb]

In normal use, breadth-first traversal should never even discover paths that contain any node more than once. Do these uninteresting paths appear because we have a special case for edges referring to targets, to allow us to collect paths beyond the shortest?

Filtering in deduplicatePaths could result in fewer paths shown than requested. It might be better to do it in the C++: when we reach a target, scan the path back and see if we find ourselves.

Comment 3

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

(In reply to Jim Blandy :jimb from comment #2)
> In normal use, breadth-first traversal should never even discover paths that
> contain any node more than once. Do these uninteresting paths appear because
> we have a special case for edges referring to targets, to allow us to
> collect paths beyond the shortest?

Our breadth-first traversal is a traversal of edges, not nodes, and I think the "never even discover paths that contain any node more than once" property would only apply to node-centric traversals. We end up "visiting" the same node many times when visiting a new edge for the first time that happens to refer to the same node as a previous edge.

> Filtering in deduplicatePaths could result in fewer paths shown than
> requested.

Yes, I considered this and assumed it wasn't a very big deal -- maybe that is an incorrect assumption?

> It might be better to do it in the C++: when we reach a target,
> scan the path back and see if we find ourselves.

This is definitely do-able, but would it significantly change the running time of JS::ubi::ShortestPaths? I'm getting itches of accidentally introducing quadratic behavior, but I don't have anything concrete at the moment.

Comment 4

[Jim Blandy :jimb]

(In reply to Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8] from comment #3)
> Our breadth-first traversal is a traversal of edges, not nodes, and I think
> the "never even discover paths that contain any node more than once"
> property would only apply to node-centric traversals. We end up "visiting"
> the same node many times when visiting a new edge for the first time that
> happens to refer to the same node as a previous edge.

Right, but we only record a backwards edge the first time we reach a node. So it should be impossible for a node to have two different backwards edges, as required if it is to appear more than once (and not an infinite number of times, I guess?) in a path. It's only the special code that records multiple backwards edges for targets that makes these degenerate paths possible.

> > Filtering in deduplicatePaths could result in fewer paths shown than
> > requested.
> 
> Yes, I considered this and assumed it wasn't a very big deal -- maybe that
> is an incorrect assumption?

I don't think it's a huge deal; I think you're right that simple-minded checks in the C++ code could introduce quadratic behavior, which seems more important.

Comment 5

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

Attachment: Ignore retaining paths that are strictly a super set of other paths

This was starting to ignore me, and was a pretty easy fix, so here's a patch. We
were already testing paths with loops, but asserting that they are kept. This
just changes that to assert that they aren't kept.

Comment 6

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

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

Comment 7

[Pulsebot]

https://hg.mozilla.org/integration/fx-team/rev/8a47b4f44a5a

Comment 8

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/8a47b4f44a5a