Re: [PATCH] Adding a cache of commit to patch-id pairs to speed up git-cherry

["Geoffrey Irving" <irving@naml.us>]

On Mon, Jun 2, 2008 at 8:37 AM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Mon, 2 Jun 2008, Geoffrey Irving wrote:
>
>> On Sun, Jun 1, 2008 at 11:42 PM, Jeff King <peff@peff.net> wrote:
>> > On Mon, Jun 02, 2008 at 07:13:14AM +0100, Johannes Schindelin wrote:
>> >
>> >> I do not think that this "read-the-entire-table-into-memory" paradigm
>> >> is a wise choice. mmap()ing, I would have understood, but reading a
>> >> potentially pretty large table into memory?
>> >
>> > When I was just a git-youth, I wrote a fast mmap-based cache for
>> > storing SHA1 pairs. It might give some direction. You should be able
>> > to find it here:
>> >
>> >  http://mid.gmane.org/20060629035849.GA30749@coredump.intra.peff.net
>> >
>> > It mmaps and binary searches a sorted list. New entries are added to
>> > an in-memory list, and then at the end of a run, the two sorted lists
>> > are merged to create the new on-disk version.
>>
>> I don't need sorting (and neither did you), so I think a hash table is
>> better (O(1) instead of O(log n), and we don't even need to compute hash
>> keys.  I'll leave it up to you and Dscho (or anyone else who cares to
>> chime in) which one you think I should do.
>
> My tests suggested that the lookup time advantage of hashes makes them a
> more appropriate choice than sorted lists, if you look up often, but add
> rarely.
>
> Another issue that just hit me: this cache is append-only, so if it grows
> too large, you have no other option than to scratch and recreate it.
> Maybe this needs porcelain support, too?  (git gc?)

If so, the correct operation is to go through the hash and remove
entries that refer to commits that no longer exist.  I can add this if
you want.  Hopefully somewhere along the way git-gc constructs an easy
to traverse list of extant commits, and this will be straightforward.

Geoffrey