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

From: Geoffrey Irving <irving@naml.us>
Date: Jun 2, 2008, 16:26 UTC
Message-ID: <7f9d599f0806020926j7ac9fb12jefa5a14fe5708226@mail.gmail.com>
In-Reply-To: <alpine.DEB.1.00.0806021717130.13507@racer.site.net>

On Mon, Jun 2, 2008 at 9:18 AM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Show 19 quoted lines

> Hi,
>
> On Mon, 2 Jun 2008, Geoffrey Irving wrote:
>
>> On Mon, Jun 2, 2008 at 8:37 AM, Johannes Schindelin
>> <Johannes.Schindelin@gmx.de> wrote:
>>
>> > 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.
>
> I don't know... if you have created a cached patch-id for every commit (by
> mistake, for example) and do not need it anymore, it might make git-cherry
> substantially faster to just scrap the cache.

Well, ideally hash maps are O(1), but it could be a difference between a "compare 40 bytes" constant and a "read a 4k block into memory" constant, so in practice yes. Scrapping it entirely will also make the implementation much simpler.

It seems a little sad to wipe all that effort each time, but regenerating the cache is likely to be less expensive than a git-gc, so it shouldn't change any amortized complexities.

Geoffrey