git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Taylor Blau <me@ttaylorr.com>
To: Han-Wen Nienhuys <hanwen@google.com>
Cc: "Jakub Narębski" <jnareb@gmail.com>,
	"Abhradeep Chakraborty" <chakrabortyabhradeep79@gmail.com>,
	git@vger.kernel.org
Subject: Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?
Date: Tue, 1 Aug 2023 13:31:33 -0400	[thread overview]
Message-ID: <ZMlBdb5jEW3s7UWX@nand.local> (raw)
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

      parent reply	other threads:[~2023-08-01 17:31 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-03-23 19:26 What is the status of GSoC 2022 work on making Git use roaring bitmaps? Jakub Narębski
2023-03-23 20:26 ` Taylor Blau
2023-03-23 22:01   ` Jakub Narębski
2023-03-24  3:48     ` Abhradeep Chakraborty
2023-03-25 17:40       ` Jakub Narębski
2023-07-31 17:46         ` Han-Wen Nienhuys
2023-07-31 20:18           ` Taylor Blau
2023-08-01 11:26             ` Han-Wen Nienhuys
2023-08-01 11:34               ` Jakub Narębski
2023-08-01 11:54                 ` Han-Wen Nienhuys
2023-08-01 13:17                   ` Jakub Narębski
2023-08-01 17:33                 ` Taylor Blau
2023-08-01 17:43                   ` Jakub Narębski
2023-08-01 17:31               ` Taylor Blau [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=ZMlBdb5jEW3s7UWX@nand.local \
    --to=me@ttaylorr.com \
    --cc=chakrabortyabhradeep79@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=hanwen@google.com \
    --cc=jnareb@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).