Re: [Monotone-devel] Merging suspend branch

[Zack Weinberg]

On 7/14/07, William Uther <address@hidden> wrote:
> I've been playing with the branch, and it does slow down listing
> branches quite a bit.  Listing branches isn't too common an
> operation, but I switched things up to try to help this:
>
>    - The main 'suspend' cert change is now in
> project_t::get_branch_heads().
>    - I've added a new lua function: get_branch_heads() which gets the
> branch heads :)
>    - I've added a default ignore_branch() lua hook which checks if
> there are any branch heads and
>      ignores the branch if there are not.
>
> The result is basically the same as before, except that you can
> choose to switch off the checking for heads behaviour when listing
> branches (by changing the lua hook), which makes makes quite a speed
> difference (if you do this operation a lot).

I gotta say I'm not real enthusiastic about this hook.  If the only
reason anyone would ever change it is to speed up an operation at the
expense of clarity in the results, I'd argue that we should fix the
performance problem instead...  Can you think of any other reason
someone would change it?

> I then started looking at why finding branch heads is so slow.  The
> answer is simple: project_t::get_branch_heads() first gets every
> revision in the branch, then erases ancestors.  Getting the heads of
> every branch means considering every revision in the DB.  It might be
> nice some time in the future to cache the heads of each branch in the db.

The information is already kinda-sorta in the database ... there's a
"revision_ancestry" table that just contains (parent, child) pairs.
You can pull out all revisions that are not parents of any other
revision with one SQL query:

 SELECT child FROM revision_ancestry WHERE child NOT IN (SELECT
parent FROM revision_ancestry)

-- on my local database, that executes in 0.2 seconds (including time
to format the results neatly and write them to /dev/null).

zw