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
