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

[Junio C Hamano <gitster@pobox.com>]

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

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