On Tue, Jun 25, 2013 at 5:58 PM, Thomas Rast <trast@xxxxxxxxxxx> wrote: > >> This is the technical documentation and design rationale for the new >> Bitmap v2 on-disk format. > > Hrmpf, that's what I get for reading the series in order... > >> + The folowing flags are supported: > ^^ > > typos marked by ^ > >> + By storing all the hashes in a cache together with the bitmapsin > ^^ > >> + 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 > ^ > >> + - 1-byte XOR-offset >> + The xor offset used to compress this bitmap. For an entry >> + in position `x`, a XOR offset of `y` means that the actual >> + bitmap representing for this commit is composed by XORing the >> + bitmap for this entry with the bitmap in entry `x-y` (i.e. >> + the bitmap `y` entries before this one). >> + >> + Note that this compression can be recursive. In order to >> + XOR this entry with a previous one, the previous entry needs >> + to be decompressed first, and so on. >> + >> + The hard-limit for this offset is 160 (an entry can only be >> + xor'ed against one of the 160 entries preceding it). This >> + number is always positivea, and hence entries are always xor'ed > ^ > >> + with **previous** bitmaps, not bitmaps that will come afterwards >> + in the index. > > Clever. Why 160 though? JGit implementation detail. It's the equivalent of the delta-window in `pack-objects` for example. HINT HINT: in practice, JGit only looks 16 positions behind to find deltas, and we do the same. So the practical limit is 16. harhar > >> + - 2 bytes of RESERVED data (used right now for better packing). > > What do they mean? > >> + With an index at the end of the file, we can load only this index in memory, >> + allowing for very efficient access to all the available bitmaps lazily (we >> + have their offsets in the mmaped file). > > Is there anything preventing you from mmap()ing the index also? Yeah, this format allows you to easily do a SHA1 bsearch with custom step to lookup entries on the bitmap index, except for the fact that the index is not sorted by SHA1, so you'd need a linear search instead. :) I decided against it because during most complex invocations of `pack-objects`, we perform a couple thousand commit lookups to see if they have a bitmap in the index, so it makes a lot of sense to load the index tightly in a hash table before hand (which takes very little time, to be fair). We more-than-make up for the loading time by having much much faster lookups. I felt it was the right tradeoff (JGit does the same, but in their case, because they cannot mmap. :p) >> +== Appendix A: Serialization format for an EWAH bitmap >> + >> +Ewah bitmaps are serialized in the protocol as the JAVAEWAH >> +library, making them backwards compatible with the JGit >> +implementation: >> + >> + - 4-byte number of bits of the resulting UNCOMPRESSED bitmap >> + >> + - 4-byte number of words of the COMPRESSED bitmap, when stored >> + >> + - N x 8-byte words, as specified by the previous field >> + >> + This is the actual content of the compressed bitmap. >> + >> + - 4-byte position of the current RLW for the compressed >> + bitmap >> + >> +Note that the byte order for this serialization is not defined by >> +default. The byte order for all the content in a serialized EWAH >> +bitmap can be known by the byte order flags in the header of the >> +bitmap index file. > > Please document the RLW format here. Har har. I was going to comment on your review of the Ewah patchset, but might as well do it here: the only thing I know about Ewah bitmaps is that they work. And I know this because I did extensive fuzz testing of my C port. Unfortunately, the original Java code I ported from has 0 comments, so any documentation here would have to be reverse-engineered. Personally, I'd lean towards considering Ewah an external dependency (black box); the headers for the library are commented accordingly, clearly explaining the interfaces while hiding implementation details. Of course, you're welcome to help me reverse engineer the implementation, but I'm not sure this would be of much value. It'd be better to make sure it passes the extensive test suite of the Java version, and assume that Mr Lemire designed a sound format for the bitmaps. Swiss kisses, vmg -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html