Re: [PATCH 00/15] git-note: A mechanisim for providing free-form after-the-fact annotations on commits

From: Jeff King <peff@peff.net>
Date: May 29, 2007, 08:22 UTC
Message-ID: <20070529082245.GA15788@coredump.intra.peff.net>
In-Reply-To: <200705290906.29328.johan@herland.net>

On Tue, May 29, 2007 at 09:06:29AM +0200, Johan Herland wrote:

Show 6 quoted lines

> 1. Keep a file, ".git/reverse_tagmap_sorted" with one entry of the form
> "pointee pointer" per line. The file is sorted on "pointee", so we can
> easily do the radix-256-fan-out-followed-by-binary-search trick that
> Linus mentioned in another thread. This should hopefully make lookup
> fairly cheap. BTW, if there is a similar "pointee pointer"-type format
> already being used in git, I'd be happy to use that instead. I looked

I did a similar thing (though rather than having "lines" at all, they were fixed-length pairs of binary sha1 hashes) to implement a negative delta cache (which turned out to be a stupid idea, but the implementation worked):

http://www.gelato.unsw.edu.au/archives/git/0606/23229.html

Show 7 quoted lines

> 2. Keep another file, ".git/reverse_tagmap_unsorted" in front of (1).
> This file has exactly the same format, minus the sorting. It exists just
> to make insertion cheap. Once this file reaches a certain size (i.e.
> when trawling it on lookup becomes slightly painful), we shuffle the
> entries into the sorted file (this would happen automatically on
> insertion of an entry, and should _not_ have to be triggered by 'git-gc'
> etc.).

The implementation I mentioned above collects several "to be inserted" entries (in memory) and then merge sorts the two lists into a new file. So it was fast in terms of comparisons, but it involved writing O(n) entries, which is probably bad for creating a single note.

> Of course, if we think insertion directly into (1) will never be too
> expensive, we can drop (2) altogether.

You can always find the right spot, memmove everything down one slot,
and insert. But that means:
  - the cost of insertion will be proportional to the number of items,
    whereas using an unsorted journal you get to amortize that cost over
    many insertions
  - if you update in place, you have to lock the db for reading while
    you are moving around. If you are always either appending to the
    journal or merging into a new file, you can avoid this.

-Peff