[v2,1/6] Documentation/technical: describe bitmap lookup table extension

Commit Message

Abhradeep Chakraborty June 26, 2022, 1:10 p.m. UTC

From: Abhradeep Chakraborty <[e-mail]>

When reading bitmap file, git loads each and every bitmap one by one
even if all the bitmaps are not required. A "bitmap lookup table"
extension to the bitmap format can reduce the overhead of loading
bitmaps which stores a list of bitmapped commit id pos (in the midx
or pack, along with their offset and xor offset. This way git can
load only the neccesary bitmaps without loading the previous bitmaps.

The older version of Git ignores the lookup table extension and doesn't
throw any kind of warning or error while parsing the bitmap file.

Add some information for the new "bitmap lookup table" extension in the
bitmap-format documentation.

Co-Authored-by: Taylor Blau <[e-mail]>
Mentored-by: Taylor Blau <[e-mail]>
Co-Mentored-by: Kaartic Sivaraam <[e-mail]>
Signed-off-by: Abhradeep Chakraborty <[e-mail]>
---
 Documentation/technical/bitmap-format.txt | 41 +++++++++++++++++++++++
 1 file changed, 41 insertions(+)

Comments

Derrick Stolee June 27, 2022, 2:18 p.m. UTC | #1

On 6/26/2022 9:10 AM, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <[e-mail]>
> 
> When reading bitmap file, git loads each and every bitmap one by one
> even if all the bitmaps are not required. A "bitmap lookup table"
> extension to the bitmap format can reduce the overhead of loading
> bitmaps which stores a list of bitmapped commit id pos (in the midx
> or pack, along with their offset and xor offset. This way git can
> load only the neccesary bitmaps without loading the previous bitmaps.

s/neccesary/necessary/

> +			** {empty}
> +			BITMAP_OPT_LOOKUP_TABLE (0x10): :::
> +			If present, the end of the bitmap file contains a table
> +			containing a list of `N` <commit pos, offset, xor offset>

(Note that "commit pos" and "xor offset" here don't have underscores, but
your discussion below does use "xor_offset" with underscores.)

> +			triplets. The format and meaning of the table is described
> +			below.
> ++
> +NOTE: This xor_offset is different from the bitmap's xor_offset.
> +Bitmap's xor_offset is relative i.e. it tells how many bitmaps we have
> +to go back from the current bitmap. Lookup table's xor_offset tells the
> +position of the triplet in the list whose bitmap the current commit's
> +bitmap have to xor with.

I found this difficult to parse. Here is an attempt at a rewording. Please
let me know if I misunderstood something when reading your version:

  NOTE: The xor_offset stored in the BITMAP_OPT_LOOKUP_TABLE is different
  from the xor_offset used in the bitmap data table. The xor_offset in this
  table indicates the row number within this table of the commit whose
  bitmap is used for the XOR computation with the current commit's stored
  bitmap to create the proper logical reachability bitmap.

This does make me think that "xor_offset" should really be "xor_row" or
something like that.

>  		4-byte entry count (network byte order)
>  
>  			The total count of entries (bitmapped commits) in this bitmap index.
> @@ -205,3 +218,31 @@ Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
>  If implementations want to choose a different hashing scheme, they are
>  free to do so, but MUST allocate a new header flag (because comparing
>  hashes made under two different schemes would be pointless).
> +
> +Commit lookup table
> +-------------------
> +
> +If the BITMAP_OPT_LOOKUP_TABLE flag is set, the last `N * (4 + 8 + 4)`
> +(preceding the name-hash cache and trailing hash) of the `.bitmap` file
> +contains a lookup table specifying the information needed to get the
> +desired bitmap from the entries without parsing previous unnecessary
> +bitmaps.
> +
> +For a `.bitmap` containing `nr_entries` reachability bitmaps, the table
> +contains a list of `nr_entries` <commit pos, offset, xor offset> triplets.
> +The content of i'th triplet is -
> +
> +	* {empty}
> +	commit pos (4 byte integer, network byte order): ::
> +	It stores the object position of the commit (in the midx or pack index)
> +	to which the i'th bitmap in the bitmap entries belongs.

Ok, we are saving some space here, but relying on looking into the pack-index
or multi-pack-index to get the actual commit OID.

Since this is sorted by the order that stores the bitmaps, binary search will
no longer work on this list (unless we enforce that on the rest of the bitmap
file). I am going to expect that you parse this table into a hashmap in order
to allow fast commit lookups. I'll keep an eye out for that implementation.

> +	* {empty}
> +	offset (8 byte integer, network byte order): ::
> +	The offset from which that commit's bitmap can be read.
> +
> +	* {empty}
> +	xor offset (4 byte integer, network byte order): ::
> +	It holds the position of the triplet with whose bitmap the
> +	current bitmap need to xor. If the current triplet's bitmap
> +	do not have any xor bitmap, it defaults to 0xffffffff.

This last sentence seems backward. Perhaps:

  If the value is 0xffffffff, then the current bitmap has no xor bitmap.

Thanks,
-Stolee

Taylor Blau June 27, 2022, 3:48 p.m. UTC | #2

On Mon, Jun 27, 2022 at 10:18:51AM -0400, Derrick Stolee wrote:
> On 6/26/2022 9:10 AM, Abhradeep Chakraborty via GitGitGadget wrote:
> > +			triplets. The format and meaning of the table is described
> > +			below.
> > ++
> > +NOTE: This xor_offset is different from the bitmap's xor_offset.
> > +Bitmap's xor_offset is relative i.e. it tells how many bitmaps we have
> > +to go back from the current bitmap. Lookup table's xor_offset tells the
> > +position of the triplet in the list whose bitmap the current commit's
> > +bitmap have to xor with.
>
> I found this difficult to parse. Here is an attempt at a rewording. Please
> let me know if I misunderstood something when reading your version:
>
>   NOTE: The xor_offset stored in the BITMAP_OPT_LOOKUP_TABLE is different
>   from the xor_offset used in the bitmap data table. The xor_offset in this
>   table indicates the row number within this table of the commit whose
>   bitmap is used for the XOR computation with the current commit's stored
>   bitmap to create the proper logical reachability bitmap.
>
> This does make me think that "xor_offset" should really be "xor_row" or
> something like that.

To be fair, I found Stolee's version equally difficult to parse. I
wonder if something like the following would be clearer:

    NOTE: Unlike the xor_offset used to compress an individual bitmap,
    this value stores an *absolute* index into the lookup table, not a
    location relative to the current entry.

> > +For a `.bitmap` containing `nr_entries` reachability bitmaps, the table
> > +contains a list of `nr_entries` <commit pos, offset, xor offset> triplets.
> > +The content of i'th triplet is -
> > +
> > +	* {empty}
> > +	commit pos (4 byte integer, network byte order): ::
> > +	It stores the object position of the commit (in the midx or pack index)
> > +	to which the i'th bitmap in the bitmap entries belongs.
>
> Ok, we are saving some space here, but relying on looking into the pack-index
> or multi-pack-index to get the actual commit OID.
>
> Since this is sorted by the order that stores the bitmaps, binary search will
> no longer work on this list (unless we enforce that on the rest of the bitmap
> file). I am going to expect that you parse this table into a hashmap in order
> to allow fast commit lookups. I'll keep an eye out for that implementation.

The main purpose of this series is to avoid having to construct such a
table ahead of time. This is more or less akin to what the existing
implementation already does in load_bitmap_entries_v1(), though that
function has to read (but not decompress!) all bitmaps.

But I disagree that this isn't binary searchable. The object positions
are in MIDX or pack .idx order, so they are sorted lexicographically.
The comparator implementation could either take as its key an object_id,
and then convert each of the "commit pos" fields themselves to
object_ids and call oidcmp().

Or we could go the other way (as it looks like Abhradeep did in a later
patch) and convert the key's object_id into the index or MIDX-relative
position, and search for that.

> > +	* {empty}
> > +	offset (8 byte integer, network byte order): ::
> > +	The offset from which that commit's bitmap can be read.
> > +
> > +	* {empty}
> > +	xor offset (4 byte integer, network byte order): ::
> > +	It holds the position of the triplet with whose bitmap the
> > +	current bitmap need to xor. If the current triplet's bitmap
> > +	do not have any xor bitmap, it defaults to 0xffffffff.
>
> This last sentence seems backward. Perhaps:
>
>   If the value is 0xffffffff, then the current bitmap has no xor bitmap.

Perhaps even more concisely:

    The position of a triplet whose bitmap is used to compress this one,
    or 0xffffffff if no such bitmap exists.

Thanks,
Taylor

Abhradeep Chakraborty June 27, 2022, 4:51 p.m. UTC | #3

Derrick Stolee <[e-mail]> wrote:

> I found this difficult to parse. Here is an attempt at a rewording. Please
> let me know if I misunderstood something when reading your version:
>
>   NOTE: The xor_offset stored in the BITMAP_OPT_LOOKUP_TABLE is different
>   from the xor_offset used in the bitmap data table. The xor_offset in this
>   table indicates the row number within this table of the commit whose
>   bitmap is used for the XOR computation with the current commit's stored
>   bitmap to create the proper logical reachability bitmap.
>
> This does make me think that "xor_offset" should really be "xor_row" or
> something like that.

Thanks. `xor_row` seems nice to me.

> > +	* {empty}
> > +	commit pos (4 byte integer, network byte order): ::
> > +	It stores the object position of the commit (in the midx or pack index)
> > +	to which the i'th bitmap in the bitmap entries belongs.
>
> Ok, we are saving some space here, but relying on looking into the pack-index
> or multi-pack-index to get the actual commit OID.

Seems like I didn't update this particular part. At the time of writing this
patch, I was clear that I would store these triplets in the bitmap's order.
But when I started to implement the "read" part, I realised that these triplets
need to be ordered in ascending order. So I did update the "write extension"
patch but somehow missed this particular part.

Just to be clear, bitmaps are sorted by their commit's date (as far as I know).
Bitmaps for recent commits comes before bitmaps for older commits. So these
two orders are not same. Thus hashmap would not work here.

Will update this portion.

Thanks :)

Patch

diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt
index 04b3ec21785..7d4e450d3d8 100644
--- a/Documentation/technical/bitmap-format.txt
+++ b/Documentation/technical/bitmap-format.txt
@@ -67,6 +67,19 @@  MIDXs, both the bit-cache and rev-cache extensions are required.
 			pack/MIDX. The format and meaning of the name-hash is
 			described below.
 
+			** {empty}
+			BITMAP_OPT_LOOKUP_TABLE (0x10): :::
+			If present, the end of the bitmap file contains a table
+			containing a list of `N` <commit pos, offset, xor offset>
+			triplets. The format and meaning of the table is described
+			below.
++
+NOTE: This xor_offset is different from the bitmap's xor_offset.
+Bitmap's xor_offset is relative i.e. it tells how many bitmaps we have
+to go back from the current bitmap. Lookup table's xor_offset tells the
+position of the triplet in the list whose bitmap the current commit's
+bitmap have to xor with.
+
 		4-byte entry count (network byte order)
 
 			The total count of entries (bitmapped commits) in this bitmap index.
@@ -205,3 +218,31 @@  Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
 If implementations want to choose a different hashing scheme, they are
 free to do so, but MUST allocate a new header flag (because comparing
 hashes made under two different schemes would be pointless).
+
+Commit lookup table
+-------------------
+
+If the BITMAP_OPT_LOOKUP_TABLE flag is set, the last `N * (4 + 8 + 4)`
+(preceding the name-hash cache and trailing hash) of the `.bitmap` file
+contains a lookup table specifying the information needed to get the
+desired bitmap from the entries without parsing previous unnecessary
+bitmaps.
+
+For a `.bitmap` containing `nr_entries` reachability bitmaps, the table
+contains a list of `nr_entries` <commit pos, offset, xor offset> triplets.
+The content of i'th triplet is -
+
+	* {empty}
+	commit pos (4 byte integer, network byte order): ::
+	It stores the object position of the commit (in the midx or pack index)
+	to which the i'th bitmap in the bitmap entries belongs.
+
+	* {empty}
+	offset (8 byte integer, network byte order): ::
+	The offset from which that commit's bitmap can be read.
+
+	* {empty}
+	xor offset (4 byte integer, network byte order): ::
+	It holds the position of the triplet with whose bitmap the
+	current bitmap need to xor. If the current triplet's bitmap
+	do not have any xor bitmap, it defaults to 0xffffffff.