Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()
- From
Shawn Pearce <spearce@spearce.org>
- Date
- Apr 2, 2012, 16:39 UTC
- Message-ID
- <CAJo=hJshOBg4pT8nuWZ=eZvj=E9x+4b9M_EANa=02x=NFW2OfQ@mail.gmail.com>
- In-Reply-To
- <201204021024.49706.mfick@codeaurora.org>
On Mon, Apr 2, 2012 at 09:24, Martin Fick <mfick@codeaurora.org> wrote:
Show 17 quoted lines
> On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote: >> Speed up prepare_revision_walk() by adding commits >> without sorting to the commit_list and at the end sort >> the list in one go. Thanks to mergesort() working >> behind the scenes, this is a lot faster for large >> numbers of commits than the current insert sort. > > This speeds up my git push test on my repo with ~100K refs > case from out ~43s to about ~10s. Not bad, thanks! > > The rest of the 10s do not seem to be spent with high CPU on > either the pushing or the receiving side (only a very small > 100% burst on both sides near the end of the operation). I > also ran iotop on the receiving side and could not find any > activity (of course, the repo is likely cached). iftop does > show a decent amount of traffic during this time, so perhaps > we are finally approaching the protocol limit?
The protocol is basically two round trips, receive side tells push side what it has, push side sends data, receive side sends success/error response. It would be more traffic with SSH due to the encryption and custom ACK messages that SSH runs to wrap the stream.
Show 14 quoted lines
> But, I have my doubts on that to be honest. The reason is > because I am able to hack Gerrit to receive this push much > faster (around 3.5s) by reusing a cached RevWalk. Without > the cached RevWalk, Gerrit (using jgit) is about the same as > your new patch ~10s. I am not saying that git is spending > its time in the same place (but it may be) as jgit, but with > jgit, the time I was able to save with the cached RevWalk > was the time spent loading and parsing the RevCommits. This > could be the same thing that git is doing? And while it may > not be I/O (disk) bound so to speak since the packs are > likely cached, it may still be memory bound on that I/O? If > it is memory bound, and not I/O(disk) or CPU bound, I guess > it makes sense that git and jgit would perform about the > same (10s)?
Git can't really do the same thing as "cache the RevWalk". Its spawning a new process that needs to decompress and parse each commit object to determine its timestamp so the commits can be sorted into the priority queue. This is still an O(N) operation given N references.