[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] speed of "mtn ls branches"
From: |
William Uther |
Subject: |
Re: [Monotone-devel] speed of "mtn ls branches" |
Date: |
Thu, 17 Jan 2008 17:06:37 +1100 |
On 17/01/2008, at 4:00 PM, Zack Weinberg wrote:
On Jan 16, 2008 11:17 PM, William Uther
<address@hidden> wrote:
On 17/01/2008, at 2:35 PM, Tony Tung wrote:
I just downloaded monotone 0.38, and I found the command "mtn ls
branches" to take a lot longer than the previous version I was
using (0.35).
That is almost certainly due to the introduction of 'suspend' certs.
While working on something else today I noticed that the suspend-certs
implementation appears to be doing redundant work. I'm not
remembering exact details, but it looked like: scan through all branch
heads and make a list of non-suspended ones, then check
--ignore-suspend-certs, then if it's not set, do that again.
Before suspend certs the algorithm was:
project_t::get_branch_list()
Get a list of all branch certs used in the db.
Loop over the list of strings adding them to a set of branch_name
elements
Now that it checks the suspend certs, the algorithm is:
project_t::get_branch_list()
Get a list of all branch certs used in the db.
For each branch, get_branch_heads()
if there are any heads then add the branch to the set of
branch_name elements
As part of speeding that up get_branch_heads takes a new argument,
the inverse_graph_cache.
This is populated inside get_branch_heads and is a cache of data used
for erase_ancestors_and_failures.
Note that the app.db.get_branches() call only queries the DB for a
list of branches, it doesn't check
cert validity or deal with suspend certs. It is simply an SQL call.
The other thing you might be referring to is the way that
get_branch_heads works...
First, get all revs with a given branch cert using the db (i.e.
without checking the cert is valid)
Next, erase ancestors and failures (this checks all the branch certs)
Finally, check that any revisions that still exist (which would
have been heads before suspend certs were introduced) do not have
suspend certs.
You cannot merge the suspend cert checking into the
erase_ancestors_and_failures call there. Adding a suspend cert is
NOT the same as removing a branch cert. If you remove a branch cert
from a head then its parents become heads. If you add a suspend cert
to a head then its parents do not become heads.
I don't see any repeated work here.
Note that there is a subtle bug/design choice here: If the only
instance of a revision on a particular branch happens to have an
invalid branch cert (i.e. you have no valid branch certs with that
branch), then the 'mtn ls branches' code without suspend cert checks
(either the old code, or with --ignore-suspend-certs) will return it
anyway. The code with suspend cert checks will not return that as a
valid branch, even though it isn't suspended.
Cheers,
Will :-}
Re: [Monotone-devel] speed of "mtn ls branches", Tony Tung, 2008/01/17
- Re: [Monotone-devel] speed of "mtn ls branches", William Uther, 2008/01/17
- Re: [Monotone-devel] speed of "mtn ls branches", Richard Levitte, 2008/01/17
- Re: [Monotone-devel] speed of "mtn ls branches", William Uther, 2008/01/17
- Re: [Monotone-devel] speed of "mtn ls branches", Daniel Carosone, 2008/01/17
- Re: [Monotone-devel] speed of "mtn ls branches", William Uther, 2008/01/17