Re: Get all tips quickly

[Michael Haggerty <mhagger@alum.mit.edu>]

On 04/13/2014 04:19 PM, Kirill Likhodedov wrote:
> What is fastest possible way to get all “tips” (leafs of the Git log
> graph) in a Git repository with hashes of commits they point to?
> 
> We at JetBrains are tuning performance of Git log integration in our
> IntelliJ IDEA and want to get all tips as fast as possible. Currently
> we use 'git log —branches --tags --remotes --no-walk’, but the
> problem is that it is slow if there are a lot of references. In our
> repository we have about 35K tags, and therefore the tags is the main
> slowdown. On the other hand, we have just a couple of dozens of tips
> as well as branch references, and `git log --branches --remotes` is
> very fast.
> 
> So we are searching a way to get tags pointing to the graph leafs
> faster.

The fastest ways to get all references plus the commits that are pointed
at by annotated references would probably be `git show-ref -d`.  The
funny-looking entries like "refs/tags/v1.7.0^{}" are the annotated tags
peeled to the object that they ultimately refer.  But this command
doesn't tell the types of the objects, and there can be trees and blobs
mixed in.

If your question is also to figure out the minimum set of references
that are needed to include all tips (i.e., commits with no descendants),
then the answer is trickier.  There is a command that should do what you
say:

    git merge-base --independent <commit>...

but (1) with a lot of references, your arguments wouldn't all fit on the
command line (recursive use of xargs might be needed), (2) I don't know
if "merge-base --independent" is programmed to work efficiently on so
many inputs, and (3) I don't know of a cheap way of getting a list of
all commits referred to by references (i.e., dereferencing annotated
tags but ignoring references/annotated tags that refer to trees or blobs).


Another approach is to start by finding the leaf commits by SHA-1.  You
can do this by listing all commits, and listing all commits' parents,
and then finding the objects that appear in the first list but not the
second.  This could look like

    comm -23 \
        <(git log --all --pretty=format:'%H' | sort -u) \
        <(git log --all --pretty=format:'%P' | tr ' ' '\n' | sort -u)

If you want reference names corresponding to these SHA-1s, you could use
name-rev to convert the SHA-1s into refnames:

    git rev-parse --symbolic-full-name $(
        comm -23 \
            <(git log --all --pretty=format:'%H' | sort -u) \
            <(git log --all --pretty=format:'%P' | tr ' ' '\n' | sort -u) |
        git name-rev --stdin --name-only
        )

The "rev-parse --symbolic-full-name" is needed because "name-ref" seems
only able to emit abbreviated reference names.


In practice, you might want to cache some of the results to avoid having
to do a full tree traversal every time.

> We also tried to read tags by manually parsing .git files (it is
> faster than invoking git log), but unfortunately annotated tags in
> .git/refs/tags/ are written without the hashes they point to (unlike
> .git/packed-refs).

I strongly recommend against parsing these files yourselves.  Your
software would not be robust against any future changes to the file
formats etc.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/