Re: [PATCH v3 1/6] Documentation/technical: describe bitmap lookup table extension

[Taylor Blau <me@ttaylorr.com>]

On Sun, Jul 10, 2022 at 04:01:11PM +0100, Philip Oakley wrote:
> >> Not sure if this is new in this extension, but should there be a link or
> >> two to the basics of XOR compression and some of the bitmap look up
> >> techniques?
> >>
> >> It's not always obvious if these techniques are 'heuristic' and only
> >> have partial commit data, or they have all the commits listed, Nor
> >> how/why they work. My point is more about giving new readers a hand-up
> >> in their understanding, rather than simple implementation details for
> >> those who already know what is going on. For example, are there any
> >> external articles that you found helpful in getting started that could
> >> be referenced somewhere in the docs?
> > As this series is only about adding a lookup-table extension (and not
> > about bitmap itself), I am not sure whether it's good to include those
> > things in this series.
>
> Thanks for the clarification. I must have slight misread some of the
> discussions and falsely thought it was the XOR compression (which is a
> technique I wasn't really aware of), that was being provided by the
> extension - Where would it be best for me to look up the background to
> your "extension" project?

Yeah, Abhradeep is right that the XOR compression isn't new, we already
serialize bitmaps with optional XOR offsets. The gist is that we give an
offset of some previous bitmap that is used to compress the current one
by XORing the bits in the current bitamp with the previous one. These
XOR-compressed bitmaps are often sparse, so they compress well and
reduce the overall size of the .bitmap.

A slightly more detailed overview can be found in
Documentation/technical/bitmap-format.txt under the bullet point reading
"1-byte XOR-offset".

Thanks,
Taylor