151410 - Replace depth-first search from showdependencytree with breadth-first search

Status: NEW

(Bugzilla :: Creating/Changing Bugs, defect)

Description

[timeless]

*  151209 [---, [e-mail]] - Bugzilla seems to be much slower since the
upgrade.
    * 151281 [---, [e-mail]] - duplicates.cgi performance work.
* 151217 [---, [e-mail]] - Invalid column reference.
* 151281 [---, [e-mail]] - duplicates.cgi performance work.

If bug 151281 was posted before big 151209 then 151209's child would be listed
as already in the tree.

we currently give priority by depth which is silly.

Comment 1

[Dave Miller [:justdave]]

timeless asked me to look at this...  I have no clue how to fix it.  (And I have
too much else going on right now to go find a clue ;)

Clarifying summary...

Comment 2

[Dave Miller [:justdave]]

The User Interface component now belongs to Gerv.  Reassigning all UNCONFIRMED
and NEW (but not ASSIGNED) bugs currently owned by Myk (the previous component
owner) to Gerv.

Comment 3

[Dave Miller [:justdave]]

Reassigning back to Myk.  That stuff about Gerv taking over the User Interface
component turned out to be short-lived.  Please pardon our confusion, and I'm
very sorry about the spam.

Comment 4

[chaduv]

This problem only occurs if the bug showing up multiple times does not have any 
bugs blocking it. Compare the URL given with 
http://bugzilla.mozilla.org/showdependencytree.cgi?id=70229, and look at bug 
46768. To me, it looks something like...

*  8623 [mozilla1.0, [e-mail]] - API: UnregisterComponent shouldn't 
return nsresult.
   *  46768 [mozilla1.0, [e-mail]] - rework component manager.
      *  115853 [mozilla1.0, [e-mail]] - nsIComponentRegistrar need to be 
frozen. 
**snip**
*  46768 [mozilla1.0, [e-mail]] - This bug appears elsewhere in this 
tree. 

The relevant code is 
http://lxr.mozilla.org/mozilla/source/webtools/bugzilla/template/en/default/bug/
dependency-tree.html.tmpl#104

Apologies for IE breaking links, I don't have Moz on this machine.

Comment 5

[Myk Melez [:myk] [@mykmelez]]

pushing off

chaduv: if you have a fix, feel free to reassign to yourself and bump back to 2.18

Comment 6

[Vlad Dascalu]

I'll slightly modify this report.

Currently we use a depth first search algorithm in order to generate the 
dependency tree ( http://www.google.com/search?q=depth+first+search )

Our implementation, and the method in itself, has several disadvantages:

-> big memory footprint (currently we store the same hash once for each depth 
level, as a local variable, which is silly and increases the memory footprint 
as well)

-> recursive implementation (currently we call the same function each time we 
go lower in the tree, which increases the memory footprint as well; besides, 
Perl must be worried about memorising the point of return in the recursivity, 
which adds up)

-> reproductibility of the tree (currently the first bug ID gets explored 
completely, then the second and so on, so changing the order of the IDs in the 
dependson field might lead to a completely different graph)

-> we give priority by order, not by depth (this is related to the previous 
item, and leads to pretty silly results)


Switching to a BFS algorithm would resolve those issues. We would end up having 
only one queue, where we use a FIFO (first in first out) algorithm in order to 
build the dependency tree. The memory footprint becomes lower, and the 
dependency tree gets reproductible.

Comment 7

[Vlad Dascalu]

Oh, and because right now the depth that each bugs receives in the dependency 
tree is related to the order in which bug IDs appear in the "dependson" field, 
changing their order might result in removing/adding bugs in the tree (without 
changing the max depth).

Comment 8

[Vlad Dascalu]

Also, in the current implementation, every node from the tree gets explored, 
even if maxdepth is set to 1.

Comment 9

[Vlad Dascalu]

Attachment: Version 1

I'm not located in front of my usual localhost, so I can't test this property.
It couldn't even compile on all configs.

If someone could give it a spin it would be appreciated.

Comment 10

[Vlad Dascalu]

Attachment: Version 2

Comment 11

[Vlad Dascalu]

Due to comment #8, the CPU usage will drop as well in the new implementation. 
So this patch drops both the CPU and the memory footprint of 
showdependencytree.cgi.

Comment 12

[Vlad Dascalu]

Attachment: Version 3

Comment 13

[Vlad Dascalu]

Attachment: Version 4

Comment 14

[Vlad Dascalu]

Comment on attachment 141734 [details] [diff] [review]
Version 4

Since kiko is flu-recovering, another pair of eyes on this one would be quite
cool :-)

Comment 15

[Jouni Heikniemi]

Comment on attachment 141734 [details] [diff] [review]
Version 4

To me, it looks like the code is printing out the whole tree regardless of what
I select for maxdepth.

>+    # Generates a dependency tree for a given bug.  Use a FIFO (first in
>+    # first out) method in order to implement a breath first search algorithm
>+    # for building the tree.

Nit: "breaDth" first search; the summary for this bug is also wrong.

>+    my ($bug_id, $relationship, $bugs, $ids) = @_;
>+    my @pendingBugs = ($bug_id);

While you're at it, please add some comments describing the contents of these
variables so that readers can later on better understand the algorithm.

>+    # Record this depth in the global $realdepth variable if it's farther 
>+    # than we've gone before.
>+    $realdepth = max($realdepth, $depth);

Why? What's the idea of this "realdepth"? What do we use it for?

Comment 16

[Christian Reis]

Comment on attachment 141734 [details] [diff] [review]
Version 4

Off the hook till jouni's comments are addressed.

Comment 17

[Vlad Dascalu]

Attachment: Version 5

Identical with version 4 but with the spelling error fixed.

Comment 18

[Vlad Dascalu]

> Why? What's the idea of this "realdepth"? What do we use it for?

Practically we take the largest depth in those 2 trees (the dependson tree and
the blocks tree), and that's the realdepth.

We use it in the template to gray out buttons if they become invalid. For
example, if the realdepth is 3, and we are currently viewing the trees with the
maxdepth already on 3, the ">" button (increase maxdepth) becomes gray. Instead
if maxdepth is 2 and realdepth is 3, the button ">" is available.

That's how the current CVS code works at the moment.

Comment 19

[Vlad Dascalu]

The current CVS code computes the whole tree in order to send to the template
the realdepth value, which represents how large the full tree really is.
However, if the maxdepth value is already set, then we already need to send the
information whether realdepth is equal to maxdepth or if it's larger.

For example, if maxdepth is 3, then realdepth = 4 or realdepth = 400 makes no
difference. We can stop always to maxdepth + 1 (in the worst case, when maxdepth
is defined) in order to avoid computation efforts.

Comment 20

[Dave Miller [:justdave]]

OK, since the dependencygraph performance sucks, I was experimenting with some
way to get the entire operation to run server-side on the MySQL server, to save
from having hundreds or thousands of one-row queries getting run.  I have not
yet come up with anything that could be applied to dependency graphs, but I did
come up with something that might work for dependency trees...

select d1.blocked,
       d1.dependson,
       d2.dependson,
       d3.dependson,
       d4.dependson,
       d5.dependson,
       d6.dependson,
       d7.dependson
from dependencies d1
     left join dependencies d2 on d1.dependson = d2.blocked
     left join dependencies d3 on d2.dependson = d3.blocked
     left join dependencies d4 on d3.dependson = d4.blocked
     left join dependencies d5 on d4.dependson = d5.blocked
     left join dependencies d6 on d5.dependson = d6.blocked
     left join dependencies d7 on d6.dependson = d7.blocked
where d1.blocked=173124;

I ran this initially with only 5 blocked columns, and it took 6 seconds on b.m.o
and returned 142 rows.

Adding a 6th column and re-running took 0.01 second and returned 145 rows.
Adding a 7th column and re-running took 0.01 second and returned 148 rows.

I think the short time on adding columns is probably due to MySQL 4's query caching.

It would make sense to run this with the number of columns specified in maxdepth
if we know what maxdepth is.  If there is no maxdepth set, the short timing on
re-runs seems to indicate that it would be very performant to run it with 5
columns to start and just keep adding columns and re-running until the last
column comes up all NULL.

Thoughts?

Comment 21

[Christian Reis]

Wow. That *is* gnarly -- a function that did that query and then packed these
bits into a list of lists would be really cool (perhaps omitting the blocked
column).

(What we really want, of course, is a CONNECT BY PRIOR, but MySQL has yet to
grow that bit of Oracle personality.)

Comment 22

[Christian Reis]

Something to think about, Tiago.

Comment 23

[Max Kanat-Alexander]

This bug has not been touched by its owner in over six months, even though it is
targeted to 2.20, for which the freeze is 10 days away. Unsetting the target
milestone, on the assumption that nobody is actually working on it or has any
plans to soon.

If you are the owner, and you plan to work on the bug, please give it a real
target milestone. If you are the owner, and you do *not* plan to work on it,
please reassign it to [e-mail] or a .bugs component owner. If you are
*anybody*, and you get this comment, and *you* plan to work on the bug, please
reassign it to yourself if you have the ability.

Comment 24

[timeless]

could someone please adopt this bug? what needs to be done to it?

vladd, why did you abandon this bug? :(~