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

RESOLVED FIXED in Firefox 48

Status

P2
normal
RESOLVED FIXED
3 years ago
4 months ago

People

(Reporter: fitzgen, Assigned: fitzgen)

Tracking

unspecified
Firefox 48

Firefox Tracking Flags

(firefox48 fixed)

Details

Attachments

(1 attachment)

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

Comment 2

3 years ago
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.

Comment 4

3 years ago
(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.
Created attachment 8738810 [details] [diff] [review]
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.
Attachment #8738810 - Flags: review?(jimb)
Try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=2438fa47526f
Assignee: nobody → nfitzgerald
Status: NEW → ASSIGNED

Updated

3 years ago
Attachment #8738810 - Flags: review?(jimb) → review+
Keywords: checkin-needed

Comment 8

3 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/8a47b4f44a5a
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
status-firefox48: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → Firefox 48

Updated

4 months ago
Product: Firefox → DevTools
You need to log in before you can comment on or make changes to this bug.