Repo.revision_history() is slow

Comparing commits just compares their hashes so this shouldn't be a problem - it's not significantly less efficient than working with those hashes as strings directly. We eventually retrieve the full contents of the commit anyway to be able see what its parents and commit timestamp are.

Commits are only retrieved once for each sha anyway, so I don't see the point of caching them.

history is a list intentionally, so it can be sorted. Optionally we could keep a set of sha's that have already been processed so that we don't have to iterate the lsit each time.

Another optimization I see is using binary search to find the right place to insert a commit sha.

The current implementation now runs for 19minutes without returning. This implementation returns after 12 seconds cpu time with the same repository. I am not completely sure that the sorting will be correct (in the extreme case that an older commit has a newer timestamp).

def revision_history(self, head):
    """Returns a list of the commits reachable from head.

    Returns a list of commit objects. the first of which will be the commit
    of head, then following theat will be the parents.

    Raises NotCommitError if any no commits are referenced, including if the
    head parameter isn't the sha of a commit.

    XXX: work out how to handle merges.
    """
    # We build the list backwards, as parents are more likely to be older
    # than children
    try:
        pending_commits = [self.commit(head)]
    except KeyError:
        raise MissingCommitError(head)

    all_commits = set()
    sorted_commits = []
    while pending_commits != []:
        pending_commits.sort(key=lambda x:x.commit_time, reverse=True)
        commit = pending_commits.pop(0)

        if commit.id in all_commits:
            continue

        all_commits.add(commit.id)
        sorted_commits.append(commit)
        for parent in commit.parents:
            try:
                pending_commits.append(self.commit(parent))
            except KeyError:
                raise MissingCommitError(parent)
    sorted_commits.reverse()
    return sorted_commits

Using commit instead of commit.id for the all_commits set does not make any significant difference.

Benjamin:
Thanks for the suggestions on improving the revision-walking code. One more improvement that could make a lot of difference in your implementation would be to avoid re-sorting the list on every iteration by using a priority queue (e.g. with the heapq module in Python's standard library).

I have a long patch series that implements revision-walking in a general way using a pqueue with lots of additional options. For some solid benchmark numbers: I can walk the >23k commits in git.git, starting from a loose repo and a hot disk cache, in about 8 seconds wall time. About 80% of that time is spent in commit parsing, so I think my commit-walking code is pretty fast. To put that in perspective, 'git log' on the same repo is about 10x faster.

My benchmark script is attached. I'll share my implementation when I can, but unfortunately it's at the end of a 40+ patch series at the moment.