Re: [PATCH 09/16] documentation: add documentation for the bitmap format

From: Vicent Martí <tanoku@gmail.com>
Date: Jun 25, 2013, 22:08 UTC
Message-ID: <CAFFjANRqZ0U5tGhgjACUtquyVKCyuHiS3CC2Xxwo0J1UJVrf=g@mail.gmail.com>
In-Reply-To: <7vtxkl28m7.fsf@alter.siamese.dyndns.org>

On Tue, Jun 25, 2013 at 11:17 PM, Junio C Hamano <gitster@pobox.com> wrote:

Show 7 quoted lines

> What case are you talking about?
>
> The n-th object must be one of these four types and can never be of
> more than one type at the same time, so a natural expectation from
> the reader is "If you OR them together, you will get the same set".
> If you say "If you XOR them", that forces the reader to wonder when
> these bitmaps ever can overlap at the same bit position.

I guess this is just wording. I don't particularly care about the distinction, but I'll change it to OR.

Show 14 quoted lines

>
>> To sum it up: I'd like to see this format be strictly in Network Byte
>> Order,
>
> Good.
>
> I've been wondering what you meant by "cannot be mmap-ed" from the
> very beginning.  We mmapped the index for a long time, and it is
> defined in terms of network byte order.  Of course, pack .idx files
> are in network byte order, too, and we mmap them without problems.
> It seems that it primarily came from your fear that using network
> byte order may be unnecessarily hard to perform well, and it would
> be a good thing to do to try to do so first instead of punting from
> the beginning.

It cannot be mmapped not particularly because of endianness issues, but because the original format is not indexed and requires a full parse of the whole index before it can be accessed programatically. The wrong endianness just increases the parse time.

Show 9 quoted lines

>
>> and I'm going to try to make it run fast enough in that
>> encoding.
>
> Hmph.  Is it an option to start from what JGit does, so that people
> can use both JGit and your code on the same repository?  And then if
> you do not succeed, after trying to optimize in-core processing
> using that on-disk format to make it fast enough, start thinking
> about tweaking the on-disk format?

I'm afraid this is not an option. I have an old patchset that implements JGit v1 bitmap loading (and in fact that's how I initially developed these series -- by loading the bitmaps from JGit for debugging), but I discarded it because it simply doesn't pan out in production. ~3 seconds time to spawn `upload-pack` is not an option for us. I did not develop a tweaked on-disk format out of boredom.

I could dig up the patch if you're particularly interested in backwards compatibility, but since it was several times slower than the current iteration, I have no interest (time, actually) to maintain it, brush it up, and so on. I have already offered myself to port the v2 format to JGit as soon as it's settled. It sounds like a better investment of all our times.

Following up on Shawn's comments, I removed the little-endian support from the on-disk format and implemented lazy loading of the bitmaps to make up for it. The result is decent (slowed down from 250ms to 300ms) and it lets us keep the whole format as NWO on disk. I think it's a good tradeback.

The relevant commits are available on my fork of Git (I'll be sending v2 of the patchset once I finish tackling the other reviews):

    https://github.com/vmg/git/commit/d6cdd4329a547580bbc0143764c726c48b887271
    https://github.com/vmg/git/commit/d8ec342fee87425e05c0db1e1630db8424612c71

As it stands right now, the only two changes from v1 of the on-disk format are:

- There is an index at the end. This is a good idea.
- The bitmaps are sorted in packfile-index order, not in packfile
order. This is a good idea.

As always, all your feedback is appreciated, but please keep in mind I have strict performance concerns.

German kisses, vmg