Closed Bug 1250966 Opened 6 years ago Closed 6 years ago

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

Categories

(DevTools :: Memory, defect, P2)

defect

Tracking

(firefox48 fixed)

RESOLVED FIXED
Firefox 48
Tracking Status
firefox48 --- fixed

People

(Reporter: fitzgen, Assigned: fitzgen)

References

Details

Attachments

(1 file)

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.
Has STR: --- → irrelevant
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.
(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.
(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.
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.
Attachment #8738810 - Flags: review?(jimb)
Try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=2438fa47526f
Assignee: nobody → nfitzgerald
Status: NEW → ASSIGNED
Attachment #8738810 - Flags: review?(jimb) → review+
https://hg.mozilla.org/mozilla-central/rev/8a47b4f44a5a
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → Firefox 48
Product: Firefox → DevTools
You need to log in before you can comment on or make changes to this bug.