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

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 25, 2013, 21:17 UTC
Message-ID: <7vtxkl28m7.fsf@alter.siamese.dyndns.org>
In-Reply-To: <CAFFjANRwBBcORhu4mwjESBfr4GJ3zDrgYvUhY=VxK9abv7k2MA@mail.gmail.com>

Vicent Martí <tanoku@gmail.com> writes:

Show 20 quoted lines

>>> +               There is a bitmap for each Git object type, stored in the following
>>> +               order:
>>> +
>>> +                       - Commits
>>> +                       - Trees
>>> +                       - Blobs
>>> +                       - Tags
>>> +
>>> +               In each bitmap, the `n`th bit is set to true if the `n`th object
>>> +               in the packfile index is of that type.
>>> +
>>> +               The obvious consequence is that the XOR of all 4 bitmaps will result
>>> +               in a full set (all bits sets), and the AND of all 4 bitmaps will
>>> +               result in an empty bitmap (no bits set).
>>
>> Instead of XOR did you mean OR here?
>
> Nope, I think XOR makes it more obvious: if the same bit is set on two
> bitmaps, it would be cleared when XORed together, and hence all the
> bits wouldn't be set. An OR would hide this case.

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.

> 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.

> 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?

Thanks.