git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?

From
Taylor Blau <me@ttaylorr.com>
Date
Aug 1, 2023, 17:31 UTC
Message-ID
<ZMlBdb5jEW3s7UWX@nand.local>
In-Reply-To
<CAFQ2z_MzWauauzq_fKdcKTXahutLtADb7uHTh7ysinGNOx75nQ@mail.gmail.com>
On Tue, Aug 01, 2023 at 01:26:19PM +0200, Han-Wen Nienhuys wrote:
> > One thing that I was able to do to produce slightly smaller Roaring+Run
>
> Just for my edification: what is "Roaring + Run" ?

Roaring+Run refers to a modified version of the Roaring bitset compression scheme which has an additional container type to represent runs of a single (set) bit.

The run container stores the lower 16-bits of bit position of the start of the run, and then it uses another 16-bit value to store the length of the run.

For more, this paper from David Lemire is a good start:
  https://arxiv.org/pdf/1402.6407.pdf

Thanks, Taylor

Previous: Jakub Narębski
Message 14 of 14 in “What is the status of GSoC 2022 work on making Git use roaring bitmaps?”
  1. Jakub NarębskiMar 23, 2023
  2. Taylor BlauMar 23, 2023
  3. Jakub NarębskiMar 23, 2023
  4. Abhradeep ChakrabortyMar 24, 2023
  5. Jakub NarębskiMar 25, 2023
  6. Han-Wen NienhuysJul 31, 2023
  7. Taylor BlauJul 31, 2023
  8. Han-Wen NienhuysAug 1, 2023
  9. Jakub NarębskiAug 1, 2023
  10. Han-Wen NienhuysAug 1, 2023
  11. Jakub NarębskiAug 1, 2023
  12. Taylor BlauAug 1, 2023
  13. Jakub NarębskiAug 1, 2023
  14. Taylor BlauAug 1, 2023

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.