Re: [PATCH 09/16] documentation: add documentation for the bitmap format
flat view
From: Thomas Rast <hidden>
Date: 2016-06-15 22:57:55
Vicent Marti [off-list ref] writes:
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
^
quoted hunk ↗ jump to hunk
+ - 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?
+ - 2 bytes of RESERVED data (used right now for better packing).
What do they mean?
quoted hunk ↗ jump to hunk
+ 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?
quoted hunk ↗ jump to hunk
+== 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.
--
Thomas Rast
trast@{inf,student}.ethz.ch