Optimize prune_boring in converter.py to not do exponential recursion avoidably
Categories
(Core :: Graphics, enhancement)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox85 | --- | fixed |
People
(Reporter: kats, Assigned: kats)
References
(Blocks 1 open bug)
Details
Attachments
(1 file)
When following the steps from bug 1675579 the prune_boring step in the converter seems to get stuck. But it's actually doing a branching recursion that takes a really long time to complete, because the tree structure it ends up with has a lot of nodes with multiple parents that are identical. So instead of just moving up to the parent and processing it once, it recurses on the same parent twice. If this happens for multiple nodes, it becomes exponential, on the order of 2^n where n is the depth of the tree.
Anyway, this can be optimized by collapsing identical parent nodes into a single node.
|
Assignee | |
Comment 1•4 years ago
|
||
If a changeset has multiple parents, and those parents get pruned away
such that the changeset ends up with identical parents, we now collapse
those parents into a single parent. This avoids unnecessary recursion
and repetition of work. Generally this is only a problem when processing
a large number of changesets, as the recursion will be exponential with
the depth of the tree, and small numbers of changesets generally have
shallow trees.
Pushed by kgupta@mozilla.staktrace.com: https://hg.mozilla.org/integration/autoland/rev/f8859e759c68 Speed up converter.py when processing a big set of changes. r=jrmuizel
|
||
Comment 3•4 years ago
|
||
| bugherder | ||
Description
•