bitmap: integrate a lookup table extension to the bitmap format

From: Abhradeep Chakraborty <[email protected]>

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 oids, along with their offset and xor offset. This way git can load only the neccesary bitmaps without loading the previous bitmaps.

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

---
 Documentation/technical/bitmap-format.txt | 31 +++++++++++++++++++++++
 1 file changed, 31 insertions(+)

index 04b3ec21785..34e98787b78 100644
@@ -67,6 +67,14 @@ 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 (0xf) : :::
+			If present, the end of the bitmap file contains a table
+			containing a list of `N` object ids, a list of pairs of
+			offset and xor offset of respective objects, and 4-byte
+			integer denoting the flags (currently none). The format
+			and meaning of the table is described below.
+
 		4-byte entry count (network byte order)
 
 			The total count of entries (bitmapped commits) in this bitmap index.

@@ -205,3 +213,26 @@ 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 end of the `.bitmap`
+contains a lookup table specifying the positions of commits which have a
+bitmap.
+
+For a `.bitmap` containing `nr_entries` reachability bitmaps, the format
+is as follows:
+
+	- `nr_entries` object names.
+
+	- `nr_entries` pairs of 4-byte integers, each in network order.
+	  The first holds the offset from which that commit's bitmap can
+	  be read. The second number holds the position of the commit
+	  whose bitmap the current bitmap is xor'd with in lexicographic
+	  order, or 0xffffffff if the current commit is not xor'd with
+	  anything.
+
+	- One 4-byte network byte order integer specifying
+	  table-specific flags. None exist currently, so this is always
+	  "0".

gitgitgadget

When parsing the .bitmap file, git loads all the bitmaps one by one even if some of the bitmaps are not necessary. We can remove this overhead by loading only the necessary bitmaps. A look up table extension can solve this issue.

The proposed table has:

* a list of nr_entries object ids. These objects are commits that has bitmaps. Ids are stored in lexicographic order (for better searching).
* a list of <offset, xor-offset> pairs (4-byte integers, network-byte order). The i'th pair denotes the offset and xor-offset(respectively) of the bitmap of i'th commit in the previous list. These two informations are necessary because only in this way bitmaps can be found without parsing all the bitmap.
* a 4-byte integer for table specific flags (none exists currently).

Whenever git want to parse the bitmap for a specific commit, it will first refer to the table and will look for the offset and xor-offset for that commit. Git will then try to parse the bitmap located at the offset position. The xor-offset can be used to find the xor-bitmap for the bitmap(if any). This process is recursive and will end if xor-offset is null (i.e. there is no xor-bitmap left).

Abhradeep Chakraborty (5):
Documentation/technical: describe bitmap lookup table extension
pack-bitmap: prepare to read lookup table extension pack-bitmap-write.c: write lookup table extension
bitmap-commit-table: add tests for the bitmap lookup table
bitmap-lookup-table: add performance tests

Taylor Blau (1):
builtin/pack-objects.c: learn pack.writeBitmapLookupTable

 Documentation/config/pack.txt             |   7 +
 Documentation/technical/bitmap-format.txt |  31 ++++
 builtin/pack-objects.c                    |   8 +
 pack-bitmap-write.c                       |  59 +++++++-
 pack-bitmap.c                             | 172 +++++++++++++++++++++-
 pack-bitmap.h                             |   1 +
 t/perf/p5310-pack-bitmaps.sh              |  60 +++++---
 t/perf/p5326-multi-pack-bitmaps.sh        |  55 ++++---
 t/t5310-pack-bitmaps.sh                   |  14 ++
 t/t5326-multi-pack-bitmaps.sh             |  19 +++
 10 files changed, 375 insertions(+), 51 deletions(-)

base-commit: 5699ec1b0aec51b9e9ba5a2785f65970c5a95d84
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1266%2FAbhra303%2Fbitmap-commit-table-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1266/Abhra303/bitmap-commit-table-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1266

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Bitmap lookup table extension can let git to parse only the necessary bitmaps without loading the previous bitmaps one by one.

Teach git to read and use the bitmap lookup table extension.

---
 pack-bitmap.c | 172 ++++++++++++++++++++++++++++++++++++++++++++++++--
 pack-bitmap.h |   1 +
 2 files changed, 166 insertions(+), 7 deletions(-)

index 36134222d7a..d5e5973a79f 100644
@@ -15,6 +15,7 @@
 #include "list-objects-filter-options.h"
 #include "midx.h"
 #include "config.h"
+#include "hash-lookup.h"
 
 /*
  * An entry on the bitmap index, representing the bitmap for a given

@@ -82,6 +83,13 @@ struct bitmap_index {
 	/* The checksum of the packfile or MIDX; points into map. */
 	const unsigned char *checksum;
 
+	/*
+	 * If not NULL, these point into the various commit table sections
+	 * (within map).
+	 */
+	unsigned char *table_lookup;
+	unsigned char *table_offsets;
+
 	/*
 	 * Extended index.
 	 *

@@ -185,6 +193,24 @@ static int load_bitmap_header(struct bitmap_index *index)
 			index->hashes = (void *)(index_end - cache_size);
 			index_end -= cache_size;
 		}
+
+		if (flags & BITMAP_OPT_LOOKUP_TABLE &&
+		    git_env_bool("GIT_READ_COMMIT_TABLE", 1)) {
+			uint32_t entry_count = ntohl(header->entry_count);
+			uint32_t table_size =
+				(entry_count * the_hash_algo->rawsz) /* oids */ +
+				(entry_count * sizeof(uint32_t)) /* offsets */ +
+				(entry_count * sizeof(uint32_t)) /* xor offsets */ +
+				(sizeof(uint32_t)) /* flags */;
+
+			if (table_size > index_end - index->map - header_size)
+				return error("corrupted bitmap index file (too short to fit commit table)");
+
+			index->table_lookup = (void *)(index_end - table_size);
+			index->table_offsets = index->table_lookup + the_hash_algo->rawsz * entry_count;
+
+			index_end -= table_size;
+		}
 	}
 
 	index->entry_count = ntohl(header->entry_count);

@@ -470,7 +496,7 @@ static int load_bitmap(struct bitmap_index *bitmap_git)
 		!(bitmap_git->tags = read_bitmap_1(bitmap_git)))
 		goto failed;
 
-	if (load_bitmap_entries_v1(bitmap_git) < 0)
+	if (!bitmap_git->table_lookup && load_bitmap_entries_v1(bitmap_git) < 0)
 		goto failed;
 
 	return 0;

@@ -557,14 +583,145 @@ struct include_data {
 	struct bitmap *seen;
 };
 
-struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
-				      struct commit *commit)
+static struct stored_bitmap *stored_bitmap_for_commit(struct bitmap_index *bitmap_git,
+						      struct commit *commit,
+						      uint32_t *pos_hint);
+
+static inline const unsigned char *bitmap_oid_pos(struct bitmap_index *bitmap_git,
+						  uint32_t pos)
+{
+	return bitmap_git->table_lookup + (pos * the_hash_algo->rawsz);
+}
+
+static inline const void *bitmap_offset_pos(struct bitmap_index *bitmap_git,
+					    uint32_t pos)
+{
+	return bitmap_git->table_offsets + (pos * 2 * sizeof(uint32_t));
+}
+
+static inline const void *xor_position_pos(struct bitmap_index *bitmap_git,
+					   uint32_t pos)
+{
+	return (unsigned char*) bitmap_offset_pos(bitmap_git, pos) + sizeof(uint32_t);
+}
+
+static int bitmap_lookup_cmp(const void *_va, const void *_vb)
+{
+	return hashcmp(_va, _vb);
+}
+
+static int bitmap_table_lookup(struct bitmap_index *bitmap_git,
+			       struct object_id *oid,
+			       uint32_t *commit_pos)
+{
+	unsigned char *found = bsearch(oid->hash, bitmap_git->table_lookup,
+				       bitmap_git->entry_count,
+				       the_hash_algo->rawsz, bitmap_lookup_cmp);
+	if (found)
+		*commit_pos = (found - bitmap_git->table_lookup) / the_hash_algo->rawsz;
+	return !!found;
+}
+
+static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
+						    struct object_id *oid,
+						    uint32_t commit_pos)
+{
+	uint32_t xor_pos;
+	off_t bitmap_ofs;
+
+	int flags;
+	struct ewah_bitmap *bitmap;
+	struct stored_bitmap *xor_bitmap;
+
+	bitmap_ofs = get_be32(bitmap_offset_pos(bitmap_git, commit_pos));
+	xor_pos = get_be32(xor_position_pos(bitmap_git, commit_pos));
+
+	/*
+	 * Lazily load the xor'd bitmap if required (and we haven't done so
+	 * already). Make sure to pass the xor'd bitmap's position along as a
+	 * hint to avoid an unnecessary binary search in
+	 * stored_bitmap_for_commit().
+	 */
+	if (xor_pos == 0xffffffff) {
+		xor_bitmap = NULL;
+	} else {
+		struct commit *xor_commit;
+		struct object_id xor_oid;
+
+		oidread(&xor_oid, bitmap_oid_pos(bitmap_git, xor_pos));
+
+		xor_commit = lookup_commit(the_repository, &xor_oid);
+		if (!xor_commit)
+			return NULL;
+
+		xor_bitmap = stored_bitmap_for_commit(bitmap_git, xor_commit,
+						      &xor_pos);
+	}
+
+	/*
+	 * Don't bother reading the commit's index position or its xor
+	 * offset:
+	 *
+	 *   - The commit's index position is irrelevant to us, since
+	 *     load_bitmap_entries_v1 only uses it to learn the object
+	 *     id which is used to compute the hashmap's key. We already
+	 *     have an object id, so no need to look it up again.
+	 *
+	 *   - The xor_offset is unusable for us, since it specifies how
+	 *     many entries previous to ours we should look at. This
+	 *     makes sense when reading the bitmaps sequentially (as in
+	 *     load_bitmap_entries_v1()), since we can keep track of
+	 *     each bitmap as we read them.
+	 *
+	 *     But it can't work for us, since the bitmap's don't have a
+	 *     fixed size. So we learn the position of the xor'd bitmap
+	 *     from the commit table (and resolve it to a bitmap in the
+	 *     above if-statement).
+	 *
+	 * Instead, we can skip ahead and immediately read the flags and
+	 * ewah bitmap.
+	 */
+	bitmap_git->map_pos = bitmap_ofs + sizeof(uint32_t) + sizeof(uint8_t);
+	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+	bitmap = read_bitmap_1(bitmap_git);
+	if (!bitmap)
+		return NULL;
+
+	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
+}
+
+static struct stored_bitmap *stored_bitmap_for_commit(struct bitmap_index *bitmap_git,
+						      struct commit *commit,
+						      uint32_t *pos_hint)
 {
 	khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
 					   commit->object.oid);
-	if (hash_pos >= kh_end(bitmap_git->bitmaps))
+	if (hash_pos >= kh_end(bitmap_git->bitmaps)) {
+		uint32_t commit_pos;
+		if (!bitmap_git->table_lookup)
+			return NULL;
+
+		/* NEEDSWORK: cache misses aren't recorded. */
+		if (pos_hint)
+			commit_pos = *pos_hint;
+		else if (!bitmap_table_lookup(bitmap_git,
+					      &commit->object.oid,
+					      &commit_pos))
+			return NULL;
+		return lazy_bitmap_for_commit(bitmap_git, &commit->object.oid,
+					      commit_pos);
+	}
+	return kh_value(bitmap_git->bitmaps, hash_pos);
+}
+
+struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
+				      struct commit *commit)
+{
+	struct stored_bitmap *sb = stored_bitmap_for_commit(bitmap_git, commit,
+							    NULL);
+	if (!sb)
 		return NULL;
-	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
+	return lookup_stored_bitmap(sb);
 }
 
 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,

@@ -1699,8 +1856,9 @@ void test_bitmap_walk(struct rev_info *revs)
 	if (revs->pending.nr != 1)
 		die("you must specify exactly one commit to test");
 
-	fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
-		bitmap_git->version, bitmap_git->entry_count);
+	if (!bitmap_git->table_lookup)
+		fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
+			bitmap_git->version, bitmap_git->entry_count);
 
 	root = revs->pending.objects[0].item;
 	bm = bitmap_for_commit(bitmap_git, (struct commit *)root);

index 3d3ddd77345..37f86787a4d 100644
@@ -26,6 +26,7 @@ struct bitmap_disk_header {
 enum pack_bitmap_opts {
 	BITMAP_OPT_FULL_DAG = 1,
 	BITMAP_OPT_HASH_CACHE = 4,
+	BITMAP_OPT_LOOKUP_TABLE = 16,
 };
 
 enum pack_bitmap_flags {

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Teach git to write bitmap lookup table extension. The table has the following information:

- N no of Object ids of each bitmapped commits

- A list of offset, xor-offset pair; the i'th pair denotes the offsets and xor-offsets of i'th commit in the previous list.

- 4-byte integer denoting the flags

---
 pack-bitmap-write.c | 59 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 57 insertions(+), 2 deletions(-)

index c43375bd344..9e88a64dd65 100644
@@ -650,7 +650,8 @@ static const struct object_id *oid_access(size_t pos, const void *table)
 
 static void write_selected_commits_v1(struct hashfile *f,
 				      struct pack_idx_entry **index,
-				      uint32_t index_nr)
+				      uint32_t index_nr,
+				      off_t *offsets)
 {
 	int i;
 

@@ -663,6 +664,9 @@ static void write_selected_commits_v1(struct hashfile *f,
 		if (commit_pos < 0)
 			BUG("trying to write commit not in index");
 
+		if (offsets)
+			offsets[i] = hashfile_total(f);
+
 		hashwrite_be32(f, commit_pos);
 		hashwrite_u8(f, stored->xor_offset);
 		hashwrite_u8(f, stored->flags);

@@ -671,6 +675,49 @@ static void write_selected_commits_v1(struct hashfile *f,
 	}
 }
 
+static int table_cmp(const void *_va, const void *_vb)
+{
+	return oidcmp(&writer.selected[*(uint32_t*)_va].commit->object.oid,
+		      &writer.selected[*(uint32_t*)_vb].commit->object.oid);
+}
+
+static void write_lookup_table(struct hashfile *f,
+			       off_t *offsets)
+{
+	uint32_t i;
+	uint32_t flags = 0;
+	uint32_t *table, *table_inv;
+
+	ALLOC_ARRAY(table, writer.selected_nr);
+	ALLOC_ARRAY(table_inv, writer.selected_nr);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table[i] = i;
+	QSORT(table, writer.selected_nr, table_cmp);
+	for (i = 0; i < writer.selected_nr; i++)
+		table_inv[table[i]] = i;
+
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *selected = &writer.selected[table[i]];
+		struct object_id *oid = &selected->commit->object.oid;
+
+		hashwrite(f, oid->hash, the_hash_algo->rawsz);
+	}
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *selected = &writer.selected[table[i]];
+
+		hashwrite_be32(f, offsets[table[i]]);
+		hashwrite_be32(f, selected->xor_offset
+			       ? table_inv[table[i] - selected->xor_offset]
+			       : 0xffffffff);
+	}
+
+	hashwrite_be32(f, flags);
+
+	free(table);
+	free(table_inv);
+}
+
 static void write_hash_cache(struct hashfile *f,
 			     struct pack_idx_entry **index,
 			     uint32_t index_nr)

@@ -695,6 +742,7 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 {
 	static uint16_t default_version = 1;
 	static uint16_t flags = BITMAP_OPT_FULL_DAG;
+	off_t *offsets = NULL;
 	struct strbuf tmp_file = STRBUF_INIT;
 	struct hashfile *f;
 

@@ -715,8 +763,14 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	dump_bitmap(f, writer.trees);
 	dump_bitmap(f, writer.blobs);
 	dump_bitmap(f, writer.tags);
-	write_selected_commits_v1(f, index, index_nr);
 
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		CALLOC_ARRAY(offsets, index_nr);
+
+	write_selected_commits_v1(f, index, index_nr, offsets);
+
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		write_lookup_table(f, offsets);
 	if (options & BITMAP_OPT_HASH_CACHE)
 		write_hash_cache(f, index, index_nr);
 

@@ -730,4 +784,5 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 		die_errno("unable to rename temporary bitmap file to '%s'", filename);
 
 	strbuf_release(&tmp_file);
+	free(offsets);
 }

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Add tests to check the working of the newly implemented lookup table.

---
 t/t5310-pack-bitmaps.sh       | 14 ++++++++++++++
 t/t5326-multi-pack-bitmaps.sh | 19 +++++++++++++++++++
 2 files changed, 33 insertions(+)

index f775fc1ce69..f05d3e6ace7 100755
@@ -43,6 +43,20 @@ test_expect_success 'full repack creates bitmaps' '
 
 basic_bitmap_tests
 
+test_expect_success 'using lookup table does not affect basic bitmap tests' '
+	test_config pack.writeBitmapLookupTable true &&
+	git repack -adb
+'
+basic_bitmap_tests
+
+test_expect_success 'using lookup table does not let each entries to be parsed one by one' '
+	test_config pack.writeBitmapLookupTable true &&
+	git repack -adb &&
+	git rev-list --test-bitmap HEAD 2>out &&
+	grep "Found bitmap for" out &&
+	! grep "Bitmap v1 test "
+'
+
 test_expect_success 'incremental repack fails when bitmaps are requested' '
 	test_commit more-1 &&
 	test_must_fail git repack -d 2>err &&

index 4fe57414c13..85fbdf5e4bb 100755
@@ -306,5 +306,24 @@ test_expect_success 'graceful fallback when missing reverse index' '
 		! grep "ignoring extra bitmap file" err
 	)
 '
+test_expect_success 'multi-pack-index write --bitmap writes lookup table if enabled' '
+	rm -fr repo &&
+	git init repo &&
+	test_when_finished "rm -fr repo" &&
+	(
+		cd repo &&
+		test_commit_bulk 106 &&
+
+		git repack -d &&
+
+		git config pack.writeBitmapLookupTable true &&
+		git multi-pack-index write --bitmap &&
+
+		git rev-list --test-bitmap HEAD 2>out &&
+		grep "Found bitmap for" out &&
+		! grep "Bitmap v1 test "
+
+	)
+'
 
 test_done

gitgitgadget

From: Taylor Blau <[email protected]>

Teach git to provide a way for users to enable/disable bitmap lookup table extension by providing a config option named 'writeBitmapLookupTable'.

---
 Documentation/config/pack.txt | 7 +++++++
 builtin/pack-objects.c        | 8 ++++++++
 2 files changed, 15 insertions(+)

index ad7f73a1ead..e12008d2415 100644
@@ -164,6 +164,13 @@ When writing a multi-pack reachability bitmap, no new namehashes are
 computed; instead, any namehashes stored in an existing bitmap are
 permuted into their appropriate location when writing a new bitmap.
 
+pack.writeBitmapLookupTable::
+	When true, git will include a "lookup table" section in the
+	bitmap index (if one is written). This table is used to defer
+	loading individual bitmaps as late as possible. This can be
+	beneficial in repositories which have relatively large bitmap
+	indexes. Defaults to false.
+
 pack.writeReverseIndex::
 	When true, git will write a corresponding .rev file (see:
 	link:../technical/pack-format.html[Documentation/technical/pack-format.txt])

index cc5f41086da..3ba20301980 100644
@@ -3148,6 +3148,14 @@ static int git_pack_config(const char *k, const char *v, void *cb)
 		else
 			write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
 	}
+
+	if (!strcmp(k, "pack.writebitmaplookuptable")) {
+		if (git_config_bool(k, v))
+			write_bitmap_options |= BITMAP_OPT_LOOKUP_TABLE;
+		else
+			write_bitmap_options &= ~BITMAP_OPT_LOOKUP_TABLE;
+	}
+
 	if (!strcmp(k, "pack.usebitmaps")) {
 		use_bitmap_index_default = git_config_bool(k, v);
 		return 0;

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Add performance tests for bitmap lookup table extension.

---
 t/perf/p5310-pack-bitmaps.sh       | 60 +++++++++++++++++++-----------
 t/perf/p5326-multi-pack-bitmaps.sh | 55 +++++++++++++++++----------
 2 files changed, 73 insertions(+), 42 deletions(-)

index 7ad4f237bc3..a8d9414de92 100755
@@ -10,10 +10,11 @@ test_perf_large_repo
 # since we want to be able to compare bitmap-aware
 # git versus non-bitmap git
 #
-# We intentionally use the deprecated pack.writebitmaps
+# We intentionally use the deprecated pack.writeBitmaps
 # config so that we can test against older versions of git.
 test_expect_success 'setup bitmap config' '
-	git config pack.writebitmaps true
+	git config pack.writeBitmaps true &&
+	git config pack.writeReverseIndex true
 '
 
 # we need to create the tag up front such that it is covered by the repack and

@@ -28,27 +29,42 @@ test_perf 'repack to disk' '
 
 test_full_bitmap
 
-test_expect_success 'create partial bitmap state' '
-	# pick a commit to represent the repo tip in the past
-	cutoff=$(git rev-list HEAD~100 -1) &&
-	orig_tip=$(git rev-parse HEAD) &&
-
-	# now kill off all of the refs and pretend we had
-	# just the one tip
-	rm -rf .git/logs .git/refs/* .git/packed-refs &&
-	git update-ref HEAD $cutoff &&
-
-	# and then repack, which will leave us with a nice
-	# big bitmap pack of the "old" history, and all of
-	# the new history will be loose, as if it had been pushed
-	# up incrementally and exploded via unpack-objects
-	git repack -Ad &&
-
-	# and now restore our original tip, as if the pushes
-	# had happened
-	git update-ref HEAD $orig_tip
+test_perf 'use lookup table' '
+    git config pack.writeBitmapLookupTable true
 '
 
-test_partial_bitmap
+test_perf 'repack to disk (lookup table)' '
+    git repack -adb
+'
+
+test_full_bitmap
+
+for i in false true
+do
+	$i && lookup=" (lookup table)"
+	test_expect_success "create partial bitmap state$lookup" '
+		git config pack.writeBitmapLookupTable '"$i"' &&
+		# pick a commit to represent the repo tip in the past
+		cutoff=$(git rev-list HEAD~100 -1) &&
+		orig_tip=$(git rev-parse HEAD) &&
+
+		# now kill off all of the refs and pretend we had
+		# just the one tip
+		rm -rf .git/logs .git/refs/* .git/packed-refs &&
+		git update-ref HEAD $cutoff &&
+
+		# and then repack, which will leave us with a nice
+		# big bitmap pack of the "old" history, and all of
+		# the new history will be loose, as if it had been pushed
+		# up incrementally and exploded via unpack-objects
+		git repack -Ad &&
+
+		# and now restore our original tip, as if the pushes
+		# had happened
+		git update-ref HEAD $orig_tip
+	'
+
+	test_partial_bitmap
+done
 
 test_done

gitgitgadget

Right; any extensions that are added to the existing .bitmap format must have a size that is predictable in order for readers to locate the next extension, if any.

Agreed. Abhradeep and I discussed whether or not it was worth exploring a new .bitmap format, and the consensus we reached was that it may be required in the future (if we explored a compression scheme other than EWAH or made some other backwards-incompatible change), but as of yet it isn't necessary. So we avoided it to eliminate unnecessary churn, especially of on-disk formats.

I agree. The bitmap reader does not warn or die when it sees unrecognized extensions, that way new extensions can be added without rendering all previously-written bitmaps useless. But in order to understand an extension on bit N, the reader must also understand extensions N-1, N-2, and so on (in order to locate the end of extension N).

Yeah, we should support >4GB bitmaps here. An overflow table could work, but I agree with Stolee that in practice it won't matter. Most .bitmap files that I've looked at in the wild have around ~500 entries at most, and are usually small. So the cost of widening this section isn't a big deal.

But note that the entry count is only one component of the bitmap size:
the individual entry lengths obviously matter too. And in repositories whose bitmaps exceed 500 entries, the entries themselves are often several million bits long (before compression) already. So it is certainly possible to exceed 4GB without having an astronomical entry count.

So doubling the width of this extension might add an extra 250 KiB or so, which is negligible.

I would much rather see us do that in cases where it makes sense (small number of entries, minimal cost to wider records, etc.) than adding unnecessary complexity via an extra lookup table for >4GB offsets.

I can't remember what I had on my mind when I wrote this ;-).

Abhradeep -- do you have any thoughts about what this might be used for? I'll try to remember it myself, but I imagine that we could just as easily remove this altogether and avoid the confusion.

(See above).

Thanks,
Taylor

Well put. It might help to have a concrete example of where we expect this to help and not help. I suspect that some of this will show up in your work updating the perf suite to use this new table, but I imagine that we'll find something like:

In cases where the result can be read or computed without significant additional traversal (e.g., all commits of interest already have bitmaps computed), we can save some time loading and parsing a majority of the bitmap file that we will never read.

But in cases where the bitmaps are out-of-date, or there is significant traversal required to go from the reference tips to what's contained in the .bitmap file, this table provides minimal benefit (or something).

Of course, you should verify that that is actually true before we insert it into the commit message as such ;-). But that sort of information may help readers understand what the purpose of this change is towards the beinning of the series.

Here and elsewhere: I typically use my <[email protected]> address when contributing to Git. So any trailers that mention my email or commits that you send on my behalf should use that address, too.

Here is an attempt to reword this a bit:

The bitmap lookup table extension was documented by an earlier change, but Git does not yet know how to parse that information. The extension allows parsing a smaller portion of the bitmap file in order to find bitmaps for specific commits.

Normally, I don't mind doing the read portion after the write portion, but it would be nice to have them in the opposite order so we can test writing the extension _and Git ignoring the extension_ before implementing the parsing. As it stands, most of the code in this patch is untested until patch 5.

General outline attempt:

1. Document the format.
2. Write the extension if the flag is given.
3. Add pack.writeBitmapLookupTable and add tests that write the lookup table (and do other bitmap reads on that data).
4. Read the lookup table. The tests from step 3 already cover acting upon the lookup table. (Perhaps we add a mode here that disables GIT_READ_COMMIT_TABLE since that is not used anywhere else.)
5. Performance tests.

s/no/number, s/Object/object, s/ids/IDs, and s/commits/commit

s/pair/pairs

    static int table_cmp(const void *_va, const void *_vb)
    {
      struct commit *c1 = &writer.selected[*(uint32_t*)_va];
      struct commit *c2 = &writer.selected[*(uint32_t*)_vb];

      return oidcmp(&c1->object.oid, &c2->object.oid);
    }

No, it doesn't refuse to operate on the .bitmap file. It just ignores the extension. Will update the commit message.

Hmm, well said. Will update it.

Yeah, of course! They are sorted in lexicographical order for binary search.

I think I blundered here. I forgot that the xor-offset is relative to the current bitmap. The current proposed code takes it as ABSOLUTE value and tries to find the commit on that position (in the list of commit ids). So, there are two faults in my code - (1) As the xor-offset have an upper limit (which is 10 probably; not sure), any of the first 10 commits is always selected. (2) As xor-offsets are relative to the current bitmap, it depends On the order of the bitmaps. These bitmaps are ordered by the date of their corresponding commit and commit ids in the lookup table are ordered lexicographically. So, we can't use that xor-offset to find the xor'd commit position.

Will fix it.

I think you're right. I should use 64-bit types here.

Flags are at the end of this extension.

Thanks :)

Honestly, I never understood the logic behind adding this flag option. I thought you have a reason to do that. Even I was thinking of curving it to 1 byte. I will remove it then.

Thanks :)

The performance tests cover tests for command like "git rev-list --count --objects --all", "simulated clone", "simulated fetch" etc. And I tested it with both the Git and Linux. In both cases, the average cost of "Without lookup table" is bigger than "with lookup table". The margin of difference is bigger for linux. Though, I need to fix the calculation of xor-offset (see my reply to derrick), the fix will not affect the performance too much. So, what you're saying is true. I think I didn't write the bitmap out-of-date test though.

Ohh, sorry! Will fix it.

Yes, it is intentional. My previous patch (formatting the bitmap-format.txt) uses nested description lists. ":::" means it is the level 3 description list. The space is required else asciidoc will assume that it is level 4 description list.

I think at that time I thought it would add extra cost of computing the actual commit ids from those index position. So, I didn't go further here.

I still have a feeling that there is some way to get rid of this list of commit ids. But at the same time, I do not want to add extra computation to the code.

Ok, will look into it.

Let us for now remove it.

Thanks :)

Yes, you're right. It's kind of embarrassment for me :)

If the flag was Oxf it would enable all the extensions.

Got it. Thanks.

GIT_TEST_* is perfect. This was mainly for testing purpose.

size_t instead? Should we use st_mult() and st_add() everywhere?

Yeah, it would be better to use st_*().

Ok.

Ok.

Hmm, got the point. I need to fix the xor-offset related issue first (That I said earlier) before doing this.

Yeah, of course!

Thanks :)

This is mainly for testing, GIT_TEST_READ_COMMIT_TABLE is perfect.

Ok.

This is exactly what I said in my first reply. I made a mistake here.
(1) As xor_pos is relative to the current bitmap, it depends on the bitmap entry order. These two order are not same. One is ordered by date, another is lexicographically ordered. I will fix it.

Now I got the point. I wonder what if we leave it as it is. How much will it affect the code?

It is using recursive strategy. The first call to stored_bitmap_for_commit function do not have pos_hint. So, it uses bitmap_table_lookup to find the commit position in the list and makes a call to lazy_bitmap_for_commit function. This function gets the offset and xor-offset using the commit id's position in the list. If xor-offset exists, it is using this xor-offset to get the xor-bitmap by calling stored_bitmap_for_commit again. But this time pos_hint is xor-offset. This goes on till the last non-xor bitmap has found.

As I said before, xor-offset should be an absolute value to make it work correctly.

No, this is necessary. "Bitmap v1 test (%d entries loaded)" means all the bitmap entries has been loaded. It is basically for load_bitmap_entries_bitmap_v1 function which loads all the bitmaps One by one. But if there is a lookup table, prepare_bitmap_git function will not load every entries and thus printing the above line is wrong.

Thanks :)

Even I myself got confused! Before sending the patch to the mailing list, I was clear about that. That's why I didn't catch the so called mistake I have been notifying till now. Thanks Taylor for asking the question!

I should add a comment before the line so that people can understand it. Let us parse table_inv[table[i] - selected->xor_offset] -

Suppose bitmap entries be like -

Bitmap 0 (for commit 0)
Bitmap 1 (for commit 1)
Bitmap 2 (for commit 2)
Bitmap 3 (for commit 3)
.
.
.
Bitmap 20 (for commit 20)

These bitmaps are ordered by the date of their corresponding commit. table array maps commit's lexicographic order to its bitmap order. table_inv stores the reverse (i.e. it maps bitmap order to lexicographic order). Say for example, if commit 4 is lexicographically first among all the Commits then table[0] is 4. Similarly table[1]=2, table[2]=1 etc. table_inv[4] is 0, table_inv[2]=1 etc.

Now suppose commit 4's bitmap has xor-relation with commit 2's bitmap. So, xor-offset for bitmap 4 is 2. And table[0] - selected->xor_offset is equal to 4-2 = 2. It is pointing to the commit 2. Now, 2 is in bitmap Order. We need to convert it into lexicographic order. So, table_inv[2] gives us the lexicographic order position of commit 2 I.e. 1.

Long story short, there is no issue regarding xor_offset. This xor_offset is not relative to the current commit. It is absolute.

Sorry for the initial claim :)

I think removing it makes more sense. Since many of the other fields are 4-bytes wide, it's important for alignment purposes that those fields have addresses which are a multiple of four (relative to the start of the region, hence the 4-byte wide flags field).

But I'd just as soon get rid of it, so I think that makes sense to me.

Thanks,
Taylor

It should be negligible relative to everything else, I would imagine. The function that converts an index position into an object ID is nth_packed_object_id().

I'm hoping that the additional complexity is minor. And if we can save some extra bytes that aren't necessary in the first place without compromising on performance, I think that's worthwhile to do.

Thanks,
Taylor

It happens ;). Let's use 0x10 instead.

Thanks,
Taylor

Ok. I will look into it then.

Most of the reviews has been addressed. Hope I will be able to submit it soon.

Thanks :)

I'm not sure, and I think that it depends a lot on the repository and query that we're running.

I'd imagine that the effect is probably measurable, but small. Each hash lookup is cheap, but if there are many such lookups (a large proportion of which end up resulting in "no, we haven't loaded this bitmap yet" and then "...because no such bitmap exists for that commit") at some point it is worth it to fault all of the commits that _do_ have bitmaps in and answer authoritatively.

In other words, right now we have to do two queries when an commit doesn't have a bitmap stored:

- first, a lookup to see whether we have already loaded a bitmap for that commit

- then, a subsequent lookup to see whether the .bitmap file itself has a bitmap for that commit, but we just haven't loaded it yet

If we knew that we had loaded all of the bitmaps in the file, then we could simplify the above two queries into one, since whatever the first one returns is enough to know whether or not a bitmap exists at all.

Ahhh. Thanks for refreshing my memory. I wonder if you think there is a convenient way to work some of this into a short comment to help other readers in the future, too.

Yep, makes sense.

Right, that part makes sense to me. But I wonder if we should still print something, perhaps just "Bitmap v1 test" or "Bitmap v1 test (%d entries)" omitting the "loaded" part.

Thanks,
Taylor

Ahhhhh. Makes perfect sense. Thanks!

Thanks,
Taylor

These tests look good, though I left a few notes below which boil down to recommending a separate commit to set pack.writeReverseIndex=true, and some suggestions for how to clean up the diff in the two performance scripts you modified.

I would be interested to see the relevant results from running these perf scripts on a reasonably large-sized repository, e.g. the kernel or similar.

For the next version of this series, would you mind running these scripts and including the results in this commit message?

    test_partial_bitmap () {
      local enabled="$1"
      test_expect_success "create partial bitmap state (lookup=$enabled)" '
        git config pack.writeBitmapLookupTable "$enabled" &&
        [...]
      '
    }

    test_partial_bitmap false
    test_partial_bitmap true

Hmm, agreed.

Actually, Derrick has suggested to go with iterative approach[1] instead of Recursive approach. What's your view on it?

Yeah, of course we can!

Thanks :)

[1] https://lore.kernel.org/git/[email protected]/

I don't have a strong feeling about it. In practice, we seem to top out at ~500 bitmaps or so for large-ish repositories, so I would be surprised to see this result in stack exhaustion even in the worst case (every bitmap xor'd with the previous one, forming a long chain).

But it doesn't hurt to be defensive, so I think it's worth it as long as you don't find the implementation too complex.

Thanks,
Taylor

From: Abhradeep Chakraborty <[email protected]>

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.

---
 Documentation/technical/bitmap-format.txt | 41 +++++++++++++++++++++++
 1 file changed, 41 insertions(+)

index 04b3ec21785..7d4e450d3d8 100644
@@ -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.

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

The bitmap lookup table extension was documentated by an earlier change, but Git does not yet knowhow to write that extension.

Teach git to write bitmap lookup table extension. The table contains the list of N <commit pos, offset, xor offset>` triplets. These triplets are sorted according to their commit pos (ascending order). The meaning of each data in the i'th triplet is given below:

- Commit pos is the position of the commit in the pack-index (or midx) to which the i'th bitmap belongs. It is a 4 byte network byte order integer.

- offset is the position of the i'th bitmap.

- xor offset denotes the position of the triplet with whose bitmap the current triplet's bitmap need to xor with.

---
 pack-bitmap-write.c | 72 +++++++++++++++++++++++++++++++++++++++++++--
 pack-bitmap.h       |  5 ++--
 2 files changed, 73 insertions(+), 4 deletions(-)

index c43375bd344..899a4a941e1 100644
@@ -650,7 +650,9 @@ static const struct object_id *oid_access(size_t pos, const void *table)
 
 static void write_selected_commits_v1(struct hashfile *f,
 				      struct pack_idx_entry **index,
-				      uint32_t index_nr)
+				      uint32_t index_nr,
+				      uint64_t *offsets,
+				      uint32_t *commit_positions)
 {
 	int i;
 

@@ -663,6 +665,11 @@ static void write_selected_commits_v1(struct hashfile *f,
 		if (commit_pos < 0)
 			BUG("trying to write commit not in index");
 
+		if (offsets)
+			offsets[i] = hashfile_total(f);
+		if (commit_positions)
+			commit_positions[i] = commit_pos;
+
 		hashwrite_be32(f, commit_pos);
 		hashwrite_u8(f, stored->xor_offset);
 		hashwrite_u8(f, stored->flags);

@@ -671,6 +678,55 @@ static void write_selected_commits_v1(struct hashfile *f,
 	}
 }
 
+static int table_cmp(const void *_va, const void *_vb, void *commit_positions)
+{
+	int8_t result = 0;
+	uint32_t *positions = (uint32_t *) commit_positions;
+	uint32_t a = positions[*(uint32_t *)_va];
+	uint32_t b = positions[*(uint32_t *)_vb];
+
+	if (a > b)
+		result = 1;
+	else if (a < b)
+		result = -1;
+	else
+		result = 0;
+
+	return result;
+}
+
+static void write_lookup_table(struct hashfile *f,
+			       uint64_t *offsets,
+			       uint32_t *commit_positions)
+{
+	uint32_t i;
+	uint32_t *table, *table_inv;
+
+	ALLOC_ARRAY(table, writer.selected_nr);
+	ALLOC_ARRAY(table_inv, writer.selected_nr);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table[i] = i;
+
+	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table_inv[table[i]] = i;
+
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *selected = &writer.selected[table[i]];
+		uint32_t xor_offset = selected->xor_offset;
+
+		hashwrite_be32(f, commit_positions[table[i]]);
+		hashwrite_be64(f, offsets[table[i]]);
+		hashwrite_be32(f, xor_offset ?
+				table_inv[table[i] - xor_offset]: 0xffffffff);
+	}
+
+	free(table);
+	free(table_inv);
+}
+
 static void write_hash_cache(struct hashfile *f,
 			     struct pack_idx_entry **index,
 			     uint32_t index_nr)

@@ -695,6 +751,8 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 {
 	static uint16_t default_version = 1;
 	static uint16_t flags = BITMAP_OPT_FULL_DAG;
+	uint64_t *offsets = NULL;
+	uint32_t *commit_positions = NULL;
 	struct strbuf tmp_file = STRBUF_INIT;
 	struct hashfile *f;
 

@@ -715,8 +773,16 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	dump_bitmap(f, writer.trees);
 	dump_bitmap(f, writer.blobs);
 	dump_bitmap(f, writer.tags);
-	write_selected_commits_v1(f, index, index_nr);
 
+	if (options & BITMAP_OPT_LOOKUP_TABLE) {
+		CALLOC_ARRAY(offsets, index_nr);
+		CALLOC_ARRAY(commit_positions, index_nr);
+	}
+
+	write_selected_commits_v1(f, index, index_nr, offsets, commit_positions);
+
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		write_lookup_table(f, offsets, commit_positions);
 	if (options & BITMAP_OPT_HASH_CACHE)
 		write_hash_cache(f, index, index_nr);
 

@@ -730,4 +796,6 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 		die_errno("unable to rename temporary bitmap file to '%s'", filename);
 
 	strbuf_release(&tmp_file);
+	free(offsets);
+	free(commit_positions);
 }

index 3d3ddd77345..67a9d0fc303 100644
@@ -24,8 +24,9 @@ struct bitmap_disk_header {
 #define NEEDS_BITMAP (1u<<22)
 
 enum pack_bitmap_opts {
-	BITMAP_OPT_FULL_DAG = 1,
-	BITMAP_OPT_HASH_CACHE = 4,
+	BITMAP_OPT_FULL_DAG = 0x1,
+	BITMAP_OPT_HASH_CACHE = 0x4,
+	BITMAP_OPT_LOOKUP_TABLE = 0x10,
 };
 
 enum pack_bitmap_flags {

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Teach git to provide a way for users to enable/disable bitmap lookup table extension by providing a config option named 'writeBitmapLookupTable'. Default is true.

Also add test to verify writting of lookup table.

---
 Documentation/config/pack.txt |  7 +++++++
 builtin/multi-pack-index.c    |  8 ++++++++
 builtin/pack-objects.c        | 10 +++++++++-
 midx.c                        |  3 +++
 midx.h                        |  1 +
 pack-bitmap-write.c           |  2 ++
 t/t5310-pack-bitmaps.sh       |  3 ++-
 t/t5326-multi-pack-bitmaps.sh | 13 +++++++++++++
 8 files changed, 45 insertions(+), 2 deletions(-)

index ad7f73a1ead..6e1f454c4d6 100644
@@ -164,6 +164,13 @@ When writing a multi-pack reachability bitmap, no new namehashes are
 computed; instead, any namehashes stored in an existing bitmap are
 permuted into their appropriate location when writing a new bitmap.
 
+pack.writeBitmapLookupTable::
+	When true, git will include a "lookup table" section in the
+	bitmap index (if one is written). This table is used to defer
+	loading individual bitmaps as late as possible. This can be
+	beneficial in repositories which have relatively large bitmap
+	indexes. Defaults to true.
+
 pack.writeReverseIndex::
 	When true, git will write a corresponding .rev file (see:
 	link:../technical/pack-format.html[Documentation/technical/pack-format.txt])

index 5edbb7fe86e..3757616f09c 100644
@@ -87,6 +87,13 @@ static int git_multi_pack_index_write_config(const char *var, const char *value,
 			opts.flags &= ~MIDX_WRITE_BITMAP_HASH_CACHE;
 	}
 
+	if (!strcmp(var, "pack.writebitmaplookuptable")) {
+		if (git_config_bool(var, value))
+			opts.flags |= MIDX_WRITE_BITMAP_LOOKUP_TABLE;
+		else
+			opts.flags &= ~MIDX_WRITE_BITMAP_LOOKUP_TABLE;
+	}
+
 	/*
 	 * We should never make a fall-back call to 'git_default_config', since
 	 * this was already called in 'cmd_multi_pack_index()'.

@@ -123,6 +130,7 @@ static int cmd_multi_pack_index_write(int argc, const char **argv)
 	};
 
 	opts.flags |= MIDX_WRITE_BITMAP_HASH_CACHE;
+	opts.flags |= MIDX_WRITE_BITMAP_LOOKUP_TABLE;
 
 	git_config(git_multi_pack_index_write_config, NULL);
 

index 39e28cfcafc..d6a33fd486c 100644
@@ -228,7 +228,7 @@ static enum {
 	WRITE_BITMAP_QUIET,
 	WRITE_BITMAP_TRUE,
 } write_bitmap_index;
-static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;
+static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE | BITMAP_OPT_LOOKUP_TABLE;
 
 static int exclude_promisor_objects;
 

@@ -3148,6 +3148,14 @@ static int git_pack_config(const char *k, const char *v, void *cb)
 		else
 			write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
 	}
+
+	if (!strcmp(k, "pack.writebitmaplookuptable")) {
+		if (git_config_bool(k, v))
+			write_bitmap_options |= BITMAP_OPT_LOOKUP_TABLE;
+		else
+			write_bitmap_options &= ~BITMAP_OPT_LOOKUP_TABLE;
+	}
+
 	if (!strcmp(k, "pack.usebitmaps")) {
 		use_bitmap_index_default = git_config_bool(k, v);
 		return 0;

index 5f0dd386b02..9c26d04bfde 100644
@@ -1072,6 +1072,9 @@ static int write_midx_bitmap(char *midx_name, unsigned char *midx_hash,
 	if (flags & MIDX_WRITE_BITMAP_HASH_CACHE)
 		options |= BITMAP_OPT_HASH_CACHE;
 
+	if (flags & MIDX_WRITE_BITMAP_LOOKUP_TABLE)
+		options |= BITMAP_OPT_LOOKUP_TABLE;
+
 	prepare_midx_packing_data(&pdata, ctx);
 
 	commits = find_commits_for_midx_bitmap(&commits_nr, refs_snapshot, ctx);

index 22e8e53288e..5578cd7b835 100644
@@ -47,6 +47,7 @@ struct multi_pack_index {
 #define MIDX_WRITE_REV_INDEX (1 << 1)
 #define MIDX_WRITE_BITMAP (1 << 2)
 #define MIDX_WRITE_BITMAP_HASH_CACHE (1 << 3)
+#define MIDX_WRITE_BITMAP_LOOKUP_TABLE (1 << 4)
 
 const unsigned char *get_midx_checksum(struct multi_pack_index *m);
 void get_midx_filename(struct strbuf *out, const char *object_dir);

index 899a4a941e1..79be0cf80e6 100644
@@ -713,6 +713,7 @@ static void write_lookup_table(struct hashfile *f,
 	for (i = 0; i < writer.selected_nr; i++)
 		table_inv[table[i]] = i;
 
+	trace2_region_enter("pack-bitmap-write", "writing_lookup_table", the_repository);
 	for (i = 0; i < writer.selected_nr; i++) {
 		struct bitmapped_commit *selected = &writer.selected[table[i]];
 		uint32_t xor_offset = selected->xor_offset;

@@ -725,6 +726,7 @@ static void write_lookup_table(struct hashfile *f,
 
 	free(table);
 	free(table_inv);
+	trace2_region_leave("pack-bitmap-write", "writing_lookup_table", the_repository);
 }
 
 static void write_hash_cache(struct hashfile *f,

index f775fc1ce69..c669ed959e9 100755
@@ -38,7 +38,8 @@ test_expect_success 'full repack creates bitmaps' '
 	ls .git/objects/pack/ | grep bitmap >output &&
 	test_line_count = 1 output &&
 	grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
-	grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace
+	grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace &&
+	grep "\"label\":\"writing_lookup_table\"" trace
 '
 
 basic_bitmap_tests

index 4fe57414c13..43be49617b8 100755
@@ -307,4 +307,17 @@ test_expect_success 'graceful fallback when missing reverse index' '
 	)
 '
 
+test_expect_success 'multi-pack-index write writes lookup table if enabled' '
+	rm -fr repo &&
+	git init repo &&
+	test_when_finished "rm -fr repo" &&
+	(
+		cd repo &&
+		test_commit base &&
+		git repack -ad &&
+		GIT_TRACE2_EVENT="$(pwd)/trace" \
+			git multi-pack-index write --bitmap &&
+		grep "\"label\":\"writing_lookup_table\"" trace
+	)
+'
 test_done

gitgitgadget

When parsing the .bitmap file, git loads all the bitmaps one by one even if some of the bitmaps are not necessary. We can remove this overhead by loading only the necessary bitmaps. A look up table extension can solve this issue.

Changes since v1:

This is the second version which addressed all (I think) the reviews. Please notify me if some reviews are not addressed :)

* The table size is decreased and the format has also changed. It now contains nr_entries triplets of size 4+8+4 bytes. Each triplet contains the following things - (1) 4 byte commit position (in the pack-index or midx) (2) 8 byte offset and (3) 4 byte xor triplet (i.e. with whose bitmap the current triplet's bitmap has to xor) position.
* Performance tests are splitted into two commits. First contains the actual performance tests and second enables the pack.writeReverseIndex (as suggested by Taylor).
* st_*() functions are used.
* commit order is changed according to Derrick's suggestion.
* Iterative approach is used instead of recursive approach to parse xor bitmaps. (As suggested by Derrick).
* Some minor bug fixes of previous version.

Initial version:

The proposed table has:

* a list of nr_entries object ids. These objects are commits that has bitmaps. Ids are stored in lexicographic order (for better searching).
* a list of <offset, xor-offset> pairs (4-byte integers, network-byte order). The i'th pair denotes the offset and xor-offset(respectively) of the bitmap of i'th commit in the previous list. These two informations are necessary because only in this way bitmaps can be found without parsing all the bitmap.
* a 4-byte integer for table specific flags (none exists currently).

Whenever git want to parse the bitmap for a specific commit, it will first refer to the table and will look for the offset and xor-offset for that commit. Git will then try to parse the bitmap located at the offset position. The xor-offset can be used to find the xor-bitmap for the bitmap(if any).

Abhradeep Chakraborty (6):
Documentation/technical: describe bitmap lookup table extension pack-bitmap-write.c: write lookup table extension
pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests
pack-bitmap: prepare to read lookup table extension
bitmap-lookup-table: add performance tests for lookup table p5310-pack-bitmaps.sh: enable pack.writeReverseIndex for testing

 Documentation/config/pack.txt             |   7 +
 Documentation/technical/bitmap-format.txt |  41 +++++
 builtin/multi-pack-index.c                |   8 +
 builtin/pack-objects.c                    |  10 +-
 midx.c                                    |   3 +
 midx.h                                    |   1 +
 pack-bitmap-write.c                       |  74 ++++++++-
 pack-bitmap.c                             | 193 ++++++++++++++++++++--
 pack-bitmap.h                             |   5 +-
 t/perf/p5310-pack-bitmaps.sh              |  66 ++++----
 t/perf/p5326-multi-pack-bitmaps.sh        |  93 ++++++-----
 t/t5310-pack-bitmaps.sh                   |  10 +-
 t/t5326-multi-pack-bitmaps.sh             |  14 ++
 13 files changed, 439 insertions(+), 86 deletions(-)

base-commit: 39c15e485575089eb77c769f6da02f98a55905e0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1266%2FAbhra303%2Fbitmap-commit-table-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1266/Abhra303/bitmap-commit-table-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1266

Range-diff vs v1:

1: 2e22ca5069a ! 1: 4d11be66cfa Documentation/technical: describe bitmap lookup table extension
@@ Commit message
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 oids, along with their
- offset and xor offset. This way git can load only the neccesary bitmaps
- without loading the previous bitmaps.
+ 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 <[email protected]>
- Mentored-by: Taylor Blau <[email protected]>
+ Co-Authored-by: Taylor Blau <[email protected]>
+ Mentored-by: Taylor Blau <[email protected]>

@@ Documentation/technical/bitmap-format.txt: MIDXs, both the bit-cache and rev-cac
described below.

+ ** {empty}
-+ BITMAP_OPT_LOOKUP_TABLE (0xf) : :::
++ BITMAP_OPT_LOOKUP_TABLE (0x10): :::
+ If present, the end of the bitmap file contains a table
-+ containing a list of N object ids, a list of pairs of
-+ offset and xor offset of respective objects, and 4-byte
-+ integer denoting the flags (currently none). The format
-+ and meaning of the table is described below.
++ 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)

@@ Documentation/technical/bitmap-format.txt: Note that this hashing scheme is tied
+Commit lookup table
+-------------------
+
-+If the BITMAP_OPT_LOOKUP_TABLE flag is set, the end of the .bitmap -+contains a lookup table specifying the positions of commits which have a -+bitmap.
++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 format -+is as follows:
++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 -
+
-+ - nr_entries object names.
++ * {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.
+
-+ - nr_entries pairs of 4-byte integers, each in network order.
-+ The first holds the offset from which that commit's bitmap can
-+ be read. The second number holds the position of the commit
-+ whose bitmap the current bitmap is xor'd with in lexicographic
-+ order, or 0xffffffff if the current commit is not xor'd with
-+ anything.
++ * {empty}
++ offset (8 byte integer, network byte order): ::
++ The offset from which that commit's bitmap can be read.
+
-+ - One 4-byte network byte order integer specifying
-+ table-specific flags. None exist currently, so this is always
-+ "0".
++ * {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.
3: ed91ebf69a8 ! 2: d118f1d45e6 pack-bitmap-write.c: write lookup table extension

     @@ Metadata
       ## Commit message ##
          pack-bitmap-write.c: write lookup table extension
      
     -    Teach git to write bitmap lookup table extension. The table has the
     -    following information:
     +    The bitmap lookup table extension was documentated by an earlier
     +    change, but Git does not yet knowhow to write that extension.
      
     -        - `N` no of Object ids of each bitmapped commits
     +    Teach git to write bitmap lookup table extension. The table contains
     +    the list of `N` <commit pos, offset, xor offset>` triplets. These
     +    triplets are sorted according to their commit pos (ascending order).
     +    The meaning of each data in the i'th triplet is given below:
      
     -        - A list of offset, xor-offset pair; the i'th pair denotes the
     -          offsets and xor-offsets of i'th commit in the previous list.
     +      - Commit pos is the position of the commit in the pack-index
     +        (or midx) to which the i'th bitmap belongs. It is a 4 byte
     +        network byte order integer.
      
     -        - 4-byte integer denoting the flags
     +      - offset is the position of the i'th bitmap.
      
     -    Co-authored-by: Taylor Blau <[email protected]>
     -    Mentored-by: Taylor Blau <[email protected]>
     +      - xor offset denotes the position of the triplet with whose
     +        bitmap the current triplet's bitmap need to xor with.
     +
     +    Co-authored-by: Taylor Blau <[email protected]>
     +    Mentored-by: Taylor Blau <[email protected]>
          Co-mentored-by: Kaartic Sivaraam <[email protected]>
          Signed-off-by: Abhradeep Chakraborty <[email protected]>
      
     @@ pack-bitmap-write.c: static const struct object_id *oid_access(size_t pos, const
       				      struct pack_idx_entry **index,
      -				      uint32_t index_nr)
      +				      uint32_t index_nr,
     -+				      off_t *offsets)
     ++				      uint64_t *offsets,
     ++				      uint32_t *commit_positions)
       {
       	int i;
       
     @@ pack-bitmap-write.c: static void write_selected_commits_v1(struct hashfile *f,
       
      +		if (offsets)
      +			offsets[i] = hashfile_total(f);
     ++		if (commit_positions)
     ++			commit_positions[i] = commit_pos;
      +
       		hashwrite_be32(f, commit_pos);
       		hashwrite_u8(f, stored->xor_offset);
     @@ pack-bitmap-write.c: static void write_selected_commits_v1(struct hashfile *f,
       	}
       }
       
     -+static int table_cmp(const void *_va, const void *_vb)
     ++static int table_cmp(const void *_va, const void *_vb, void *commit_positions)
      +{
     -+	return oidcmp(&writer.selected[*(uint32_t*)_va].commit->object.oid,
     -+		      &writer.selected[*(uint32_t*)_vb].commit->object.oid);
     ++	int8_t result = 0;
     ++	uint32_t *positions = (uint32_t *) commit_positions;
     ++	uint32_t a = positions[*(uint32_t *)_va];
     ++	uint32_t b = positions[*(uint32_t *)_vb];
     ++
     ++	if (a > b)
     ++		result = 1;
     ++	else if (a < b)
     ++		result = -1;
     ++	else
     ++		result = 0;
     ++
     ++	return result;
      +}
      +
      +static void write_lookup_table(struct hashfile *f,
     -+			       off_t *offsets)
     ++			       uint64_t *offsets,
     ++			       uint32_t *commit_positions)
      +{
      +	uint32_t i;
     -+	uint32_t flags = 0;
      +	uint32_t *table, *table_inv;
      +
      +	ALLOC_ARRAY(table, writer.selected_nr);
     @@ pack-bitmap-write.c: static void write_selected_commits_v1(struct hashfile *f,
      +
      +	for (i = 0; i < writer.selected_nr; i++)
      +		table[i] = i;
     -+	QSORT(table, writer.selected_nr, table_cmp);
     ++
     ++	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);
     ++
      +	for (i = 0; i < writer.selected_nr; i++)
      +		table_inv[table[i]] = i;
      +
      +	for (i = 0; i < writer.selected_nr; i++) {
      +		struct bitmapped_commit *selected = &writer.selected[table[i]];
     -+		struct object_id *oid = &selected->commit->object.oid;
     ++		uint32_t xor_offset = selected->xor_offset;
      +
     -+		hashwrite(f, oid->hash, the_hash_algo->rawsz);
     ++		hashwrite_be32(f, commit_positions[table[i]]);
     ++		hashwrite_be64(f, offsets[table[i]]);
     ++		hashwrite_be32(f, xor_offset ?
     ++				table_inv[table[i] - xor_offset]: 0xffffffff);
      +	}
     -+	for (i = 0; i < writer.selected_nr; i++) {
     -+		struct bitmapped_commit *selected = &writer.selected[table[i]];
     -+
     -+		hashwrite_be32(f, offsets[table[i]]);
     -+		hashwrite_be32(f, selected->xor_offset
     -+			       ? table_inv[table[i] - selected->xor_offset]
     -+			       : 0xffffffff);
     -+	}
     -+
     -+	hashwrite_be32(f, flags);
      +
      +	free(table);
      +	free(table_inv);
     @@ pack-bitmap-write.c: void bitmap_writer_finish(struct pack_idx_entry **index,
       {
       	static uint16_t default_version = 1;
       	static uint16_t flags = BITMAP_OPT_FULL_DAG;
     -+	off_t *offsets = NULL;
     ++	uint64_t *offsets = NULL;
     ++	uint32_t *commit_positions = NULL;
       	struct strbuf tmp_file = STRBUF_INIT;
       	struct hashfile *f;
       
     @@ pack-bitmap-write.c: void bitmap_writer_finish(struct pack_idx_entry **index,
       	dump_bitmap(f, writer.tags);
      -	write_selected_commits_v1(f, index, index_nr);
       
     -+	if (options & BITMAP_OPT_LOOKUP_TABLE)
     ++	if (options & BITMAP_OPT_LOOKUP_TABLE) {
      +		CALLOC_ARRAY(offsets, index_nr);
     ++		CALLOC_ARRAY(commit_positions, index_nr);
     ++	}
      +
     -+	write_selected_commits_v1(f, index, index_nr, offsets);
     ++	write_selected_commits_v1(f, index, index_nr, offsets, commit_positions);
      +
      +	if (options & BITMAP_OPT_LOOKUP_TABLE)
     -+		write_lookup_table(f, offsets);
     ++		write_lookup_table(f, offsets, commit_positions);
       	if (options & BITMAP_OPT_HASH_CACHE)
       		write_hash_cache(f, index, index_nr);
       
     @@ pack-bitmap-write.c: void bitmap_writer_finish(struct pack_idx_entry **index,
       
       	strbuf_release(&tmp_file);
      +	free(offsets);
     ++	free(commit_positions);
       }
     +
     + ## pack-bitmap.h ##
     +@@ pack-bitmap.h: struct bitmap_disk_header {
     + #define NEEDS_BITMAP (1u<<22)
     + 
     + enum pack_bitmap_opts {
     +-	BITMAP_OPT_FULL_DAG = 1,
     +-	BITMAP_OPT_HASH_CACHE = 4,
     ++	BITMAP_OPT_FULL_DAG = 0x1,
     ++	BITMAP_OPT_HASH_CACHE = 0x4,
     ++	BITMAP_OPT_LOOKUP_TABLE = 0x10,
     + };
     + 
     + enum pack_bitmap_flags {

4: 661c1137e1c ! 3: 7786dc879f0 builtin/pack-objects.c: learn pack.writeBitmapLookupTable
@@
## Metadata ##
-Author: Taylor Blau <[email protected]>
+Author: Abhradeep Chakraborty <[email protected]>

## Commit message ##
- builtin/pack-objects.c: learn pack.writeBitmapLookupTable
+ pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests

Teach git to provide a way for users to enable/disable bitmap lookup table extension by providing a config option named 'writeBitmapLookupTable'.
+ Default is true.

- Signed-off-by: Taylor Blau <[email protected]>
+ Also add test to verify writting of lookup table.
+
+ Co-Authored-by: Taylor Blau <[email protected]>

+ Mentored-by: Taylor Blau <[email protected]>
+ Co-Mentored-by: Kaartic Sivaraam <[email protected]>

## Documentation/config/pack.txt ##
@@ Documentation/config/pack.txt: When writing a multi-pack reachability bitmap, no new namehashes are
@@ Documentation/config/pack.txt: When writing a multi-pack reachability bitmap, no
+ bitmap index (if one is written). This table is used to defer
+ loading individual bitmaps as late as possible. This can be
+ beneficial in repositories which have relatively large bitmap
-+ indexes. Defaults to false.
++ indexes. Defaults to true.
+
pack.writeReverseIndex::
When true, git will write a corresponding .rev file (see:
link:../technical/pack-format.html[Documentation/technical/pack-format.txt])

+ ## builtin/multi-pack-index.c ##
+@@ builtin/multi-pack-index.c: static int git_multi_pack_index_write_config(const char *var, const char *value,
+ opts.flags &= ~MIDX_WRITE_BITMAP_HASH_CACHE;
+ }
+
++ if (!strcmp(var, "pack.writebitmaplookuptable")) {
++ if (git_config_bool(var, value))
++ opts.flags |= MIDX_WRITE_BITMAP_LOOKUP_TABLE;
++ else
++ opts.flags &= ~MIDX_WRITE_BITMAP_LOOKUP_TABLE;
++ }
++
+ /*
+ * We should never make a fall-back call to 'git_default_config', since
+ * this was already called in 'cmd_multi_pack_index()'.
+@@ builtin/multi-pack-index.c: static int cmd_multi_pack_index_write(int argc, const char **argv)
+ };
+
+ opts.flags |= MIDX_WRITE_BITMAP_HASH_CACHE;
++ opts.flags |= MIDX_WRITE_BITMAP_LOOKUP_TABLE;
+
+ git_config(git_multi_pack_index_write_config, NULL);
+
+
## builtin/pack-objects.c ##
+@@ builtin/pack-objects.c: static enum {
+ WRITE_BITMAP_QUIET,
+ WRITE_BITMAP_TRUE,
+ } write_bitmap_index;
+-static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;
++static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE | BITMAP_OPT_LOOKUP_TABLE;
+
+ static int exclude_promisor_objects;
+
@@ builtin/pack-objects.c: static int git_pack_config(const char *k, const char *v, void *cb)
else
write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
@@ builtin/pack-objects.c: static int git_pack_config(const char *k, const char *v,
if (!strcmp(k, "pack.usebitmaps")) {
use_bitmap_index_default = git_config_bool(k, v);
return 0;
+
+ ## midx.c ##
+@@ midx.c: static int write_midx_bitmap(char *midx_name, unsigned char *midx_hash,
+ if (flags & MIDX_WRITE_BITMAP_HASH_CACHE)
+ options |= BITMAP_OPT_HASH_CACHE;
+
++ if (flags & MIDX_WRITE_BITMAP_LOOKUP_TABLE)
++ options |= BITMAP_OPT_LOOKUP_TABLE;
++
+ prepare_midx_packing_data(&pdata, ctx);
+
+ commits = find_commits_for_midx_bitmap(&commits_nr, refs_snapshot, ctx);
+
+ ## midx.h ##
+@@ midx.h: struct multi_pack_index {
+ #define MIDX_WRITE_REV_INDEX (1 << 1)
+ #define MIDX_WRITE_BITMAP (1 << 2)
+ #define MIDX_WRITE_BITMAP_HASH_CACHE (1 << 3)
++#define MIDX_WRITE_BITMAP_LOOKUP_TABLE (1 << 4)
+
+ const unsigned char *get_midx_checksum(struct multi_pack_index *m);
+ void get_midx_filename(struct strbuf *out, const char *object_dir);
+
+ ## pack-bitmap-write.c ##
+@@ pack-bitmap-write.c: static void write_lookup_table(struct hashfile *f,
+ for (i = 0; i < writer.selected_nr; i++)
+ table_inv[table[i]] = i;
+
++ trace2_region_enter("pack-bitmap-write", "writing_lookup_table", the_repository);
+ for (i = 0; i < writer.selected_nr; i++) {
+ struct bitmapped_commit *selected = &writer.selected[table[i]];
+ uint32_t xor_offset = selected->xor_offset;
+@@ pack-bitmap-write.c: static void write_lookup_table(struct hashfile *f,
+
+ free(table);
+ free(table_inv);
++ trace2_region_leave("pack-bitmap-write", "writing_lookup_table", the_repository);
+ }
+
+ static void write_hash_cache(struct hashfile *f,
+
+ ## t/t5310-pack-bitmaps.sh ##
+@@ t/t5310-pack-bitmaps.sh: test_expect_success 'full repack creates bitmaps' '
+ ls .git/objects/pack/ | grep bitmap >output &&
+ test_line_count = 1 output &&
+ grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
+- grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace
++ grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace &&
++ grep "\"label\":\"writing_lookup_table\"" trace
+ '
+
+ basic_bitmap_tests
+
+ ## t/t5326-multi-pack-bitmaps.sh ##
+@@ t/t5326-multi-pack-bitmaps.sh: test_expect_success 'graceful fallback when missing reverse index' '
+ )
+ '
+
++test_expect_success 'multi-pack-index write writes lookup table if enabled' '
++ rm -fr repo &&
++ git init repo &&
++ test_when_finished "rm -fr repo" &&
++ (
++ cd repo &&
++ test_commit base &&
++ git repack -ad &&
++ GIT_TRACE2_EVENT="$(pwd)/trace" \
++ git multi-pack-index write --bitmap &&
++ grep "\"label\":\"writing_lookup_table\"" trace
++ )
++'
+ test_done
2: d139a4c48aa ! 4: 4fbfcff8a20 pack-bitmap: prepare to read lookup table extension

     @@ Metadata
       ## Commit message ##
          pack-bitmap: prepare to read lookup table extension
      
     -    Bitmap lookup table extension can let git to parse only the necessary
     -    bitmaps without loading the previous bitmaps one by one.
     +    Earlier change teaches Git to write bitmap lookup table. But Git
     +    does not know how to parse them.
      
     -    Teach git to read and use the bitmap lookup table extension.
     +    Teach Git to parse the existing bitmap lookup table. The older
     +    versions of git are not affected by it. Those versions ignore the
     +    lookup table.
      
     -    Co-Authored-by: Taylor Blau <[email protected]>
     -    Mentored-by: Taylor Blau <[email protected]>
     -    Co-Mentored-by: Kaartic Sivaraam <[email protected]>
          Signed-off-by: Abhradeep Chakraborty <[email protected]>
     +    Mentored-by: Taylor Blau <[email protected]>
     +    Co-Mentored-by: Kaartic Sivaraam <[email protected]>
      
       ## pack-bitmap.c ##
     -@@
     - #include "list-objects-filter-options.h"
     - #include "midx.h"
     - #include "config.h"
     -+#include "hash-lookup.h"
     - 
     - /*
     -  * An entry on the bitmap index, representing the bitmap for a given
      @@ pack-bitmap.c: struct bitmap_index {
       	/* The checksum of the packfile or MIDX; points into map. */
       	const unsigned char *checksum;
       
      +	/*
     -+	 * If not NULL, these point into the various commit table sections
     ++	 * If not NULL, this point into the commit table extension
      +	 * (within map).
      +	 */
      +	unsigned char *table_lookup;
     -+	unsigned char *table_offsets;
      +
       	/*
       	 * Extended index.
     @@ pack-bitmap.c: static int load_bitmap_header(struct bitmap_index *index)
       		}
      +
      +		if (flags & BITMAP_OPT_LOOKUP_TABLE &&
     -+		    git_env_bool("GIT_READ_COMMIT_TABLE", 1)) {
     -+			uint32_t entry_count = ntohl(header->entry_count);
     -+			uint32_t table_size =
     -+				(entry_count * the_hash_algo->rawsz) /* oids */ +
     -+				(entry_count * sizeof(uint32_t)) /* offsets */ +
     -+				(entry_count * sizeof(uint32_t)) /* xor offsets */ +
     -+				(sizeof(uint32_t)) /* flags */;
     ++			git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1)) {
     ++			size_t table_size = 0;
     ++			size_t triplet_sz = st_add3(sizeof(uint32_t),    /* commit position */
     ++							sizeof(uint64_t),    /* offset */
     ++							sizeof(uint32_t));    /* xor offset */
      +
     ++			table_size = st_add(table_size,
     ++					st_mult(ntohl(header->entry_count),
     ++						triplet_sz));
      +			if (table_size > index_end - index->map - header_size)
     -+				return error("corrupted bitmap index file (too short to fit commit table)");
     -+
     ++				return error("corrupted bitmap index file (too short to fit lookup table)");
      +			index->table_lookup = (void *)(index_end - table_size);
     -+			index->table_offsets = index->table_lookup + the_hash_algo->rawsz * entry_count;
     -+
      +			index_end -= table_size;
      +		}
       	}
       
       	index->entry_count = ntohl(header->entry_count);
     +@@ pack-bitmap.c: static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
     + 
     + 	hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
     + 
     +-	/* a 0 return code means the insertion succeeded with no changes,
     +-	 * because the SHA1 already existed on the map. this is bad, there
     +-	 * shouldn't be duplicated commits in the index */
     ++	/* A 0 return code means the insertion succeeded with no changes,
     ++	 * because the SHA1 already existed on the map. If lookup table
     ++	 * is NULL, this is bad, there shouldn't be duplicated commits
     ++	 * in the index.
     ++	 *
     ++	 * If table_lookup exists, that means the desired bitmap is already
     ++	 * loaded. Either this bitmap has been stored directly or another
     ++	 * bitmap has a direct or indirect xor relation with it. */
     + 	if (ret == 0) {
     +-		error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
     +-		return NULL;
     ++		if (!index->table_lookup) {
     ++			error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
     ++			return NULL;
     ++		}
     ++		return kh_value(index->bitmaps, hash_pos);
     + 	}
     + 
     + 	kh_value(index->bitmaps, hash_pos) = stored;
      @@ pack-bitmap.c: static int load_bitmap(struct bitmap_index *bitmap_git)
       		!(bitmap_git->tags = read_bitmap_1(bitmap_git)))
       		goto failed;
     @@ pack-bitmap.c: struct include_data {
       	struct bitmap *seen;
       };
       
     --struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
     --				      struct commit *commit)
     -+static struct stored_bitmap *stored_bitmap_for_commit(struct bitmap_index *bitmap_git,
     -+						      struct commit *commit,
     -+						      uint32_t *pos_hint);
     -+
     -+static inline const unsigned char *bitmap_oid_pos(struct bitmap_index *bitmap_git,
     -+						  uint32_t pos)
     ++static inline const void *bitmap_get_triplet(struct bitmap_index *bitmap_git, uint32_t xor_pos)
      +{
     -+	return bitmap_git->table_lookup + (pos * the_hash_algo->rawsz);
     ++	size_t triplet_sz = st_add3(sizeof(uint32_t), sizeof(uint64_t), sizeof(uint32_t));
     ++	const void *p = bitmap_git->table_lookup + st_mult(xor_pos, triplet_sz);
     ++	return p;
      +}
      +
     -+static inline const void *bitmap_offset_pos(struct bitmap_index *bitmap_git,
     -+					    uint32_t pos)
     ++static uint64_t triplet_get_offset(const void *triplet)
      +{
     -+	return bitmap_git->table_offsets + (pos * 2 * sizeof(uint32_t));
     ++	const void *p = (unsigned char*) triplet + sizeof(uint32_t);
     ++	return get_be64(p);
      +}
      +
     -+static inline const void *xor_position_pos(struct bitmap_index *bitmap_git,
     -+					   uint32_t pos)
     ++static uint32_t triplet_get_xor_pos(const void *triplet)
      +{
     -+	return (unsigned char*) bitmap_offset_pos(bitmap_git, pos) + sizeof(uint32_t);
     ++	const void *p = (unsigned char*) triplet + st_add(sizeof(uint32_t), sizeof(uint64_t));
     ++	return get_be32(p);
      +}
      +
     -+static int bitmap_lookup_cmp(const void *_va, const void *_vb)
     ++static int triplet_cmp(const void *va, const void *vb)
      +{
     -+	return hashcmp(_va, _vb);
     ++	int result = 0;
     ++	uint32_t *a = (uint32_t *) va;
     ++	uint32_t b = get_be32(vb);
     ++	if (*a > b)
     ++		result = 1;
     ++	else if (*a < b)
     ++		result = -1;
     ++	else
     ++		result = 0;
     ++
     ++	return result;
      +}
      +
     -+static int bitmap_table_lookup(struct bitmap_index *bitmap_git,
     -+			       struct object_id *oid,
     -+			       uint32_t *commit_pos)
     ++static uint32_t bsearch_pos(struct bitmap_index *bitmap_git, struct object_id *oid,
     ++						uint32_t *result)
      +{
     -+	unsigned char *found = bsearch(oid->hash, bitmap_git->table_lookup,
     -+				       bitmap_git->entry_count,
     -+				       the_hash_algo->rawsz, bitmap_lookup_cmp);
     -+	if (found)
     -+		*commit_pos = (found - bitmap_git->table_lookup) / the_hash_algo->rawsz;
     -+	return !!found;
     ++	int found;
     ++
     ++	if (bitmap_git->midx)
     ++		found = bsearch_midx(oid, bitmap_git->midx, result);
     ++	else
     ++		found = bsearch_pack(oid, bitmap_git->pack, result);
     ++
     ++	return found;
      +}
      +
      +static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
     -+						    struct object_id *oid,
     -+						    uint32_t commit_pos)
     ++					  struct commit *commit)
      +{
     -+	uint32_t xor_pos;
     -+	off_t bitmap_ofs;
     -+
     ++	uint32_t commit_pos, xor_pos;
     ++	uint64_t offset;
      +	int flags;
     ++	const void *triplet = NULL;
     ++	struct object_id *oid = &commit->object.oid;
      +	struct ewah_bitmap *bitmap;
     -+	struct stored_bitmap *xor_bitmap;
     ++	struct stored_bitmap *xor_bitmap = NULL;
     ++	size_t triplet_sz = st_add3(sizeof(uint32_t), sizeof(uint64_t), sizeof(uint32_t));
      +
     -+	bitmap_ofs = get_be32(bitmap_offset_pos(bitmap_git, commit_pos));
     -+	xor_pos = get_be32(xor_position_pos(bitmap_git, commit_pos));
     ++	int found = bsearch_pos(bitmap_git, oid, &commit_pos);
      +
     -+	/*
     -+	 * Lazily load the xor'd bitmap if required (and we haven't done so
     -+	 * already). Make sure to pass the xor'd bitmap's position along as a
     -+	 * hint to avoid an unnecessary binary search in
     -+	 * stored_bitmap_for_commit().
     -+	 */
     -+	if (xor_pos == 0xffffffff) {
     -+		xor_bitmap = NULL;
     -+	} else {
     -+		struct commit *xor_commit;
     ++	if (!found)
     ++		return NULL;
     ++
     ++	triplet = bsearch(&commit_pos, bitmap_git->table_lookup, bitmap_git->entry_count,
     ++						triplet_sz, triplet_cmp);
     ++	if (!triplet)
     ++		return NULL;
     ++
     ++	offset = triplet_get_offset(triplet);
     ++	xor_pos = triplet_get_xor_pos(triplet);
     ++
     ++	if (xor_pos != 0xffffffff) {
     ++		int xor_flags;
     ++		uint64_t offset_xor;
     ++		uint32_t *xor_positions;
      +		struct object_id xor_oid;
     ++		size_t size = 0;
      +
     -+		oidread(&xor_oid, bitmap_oid_pos(bitmap_git, xor_pos));
     ++		ALLOC_ARRAY(xor_positions, bitmap_git->entry_count);
     ++		while (xor_pos != 0xffffffff) {
     ++			xor_positions[size++] = xor_pos;
     ++			triplet = bitmap_get_triplet(bitmap_git, xor_pos);
     ++			xor_pos = triplet_get_xor_pos(triplet);
     ++		}
      +
     -+		xor_commit = lookup_commit(the_repository, &xor_oid);
     -+		if (!xor_commit)
     -+			return NULL;
     ++		while (size){
     ++			xor_pos = xor_positions[size - 1];
     ++			triplet = bitmap_get_triplet(bitmap_git, xor_pos);
     ++			commit_pos = get_be32(triplet);
     ++			offset_xor = triplet_get_offset(triplet);
     ++
     ++			if (nth_bitmap_object_oid(bitmap_git, &xor_oid, commit_pos) < 0) {
     ++				free(xor_positions);
     ++				return NULL;
     ++			}
     ++
     ++			bitmap_git->map_pos = offset_xor + sizeof(uint32_t) + sizeof(uint8_t);
     ++			xor_flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
     ++			bitmap = read_bitmap_1(bitmap_git);
     ++
     ++			if (!bitmap){
     ++				free(xor_positions);
     ++				return NULL;
     ++			}
     ++
     ++			xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_oid, xor_bitmap, xor_flags);
     ++			size--;
     ++		}
      +
     -+		xor_bitmap = stored_bitmap_for_commit(bitmap_git, xor_commit,
     -+						      &xor_pos);
     ++		free(xor_positions);
      +	}
      +
     -+	/*
     -+	 * Don't bother reading the commit's index position or its xor
     -+	 * offset:
     -+	 *
     -+	 *   - The commit's index position is irrelevant to us, since
     -+	 *     load_bitmap_entries_v1 only uses it to learn the object
     -+	 *     id which is used to compute the hashmap's key. We already
     -+	 *     have an object id, so no need to look it up again.
     -+	 *
     -+	 *   - The xor_offset is unusable for us, since it specifies how
     -+	 *     many entries previous to ours we should look at. This
     -+	 *     makes sense when reading the bitmaps sequentially (as in
     -+	 *     load_bitmap_entries_v1()), since we can keep track of
     -+	 *     each bitmap as we read them.
     -+	 *
     -+	 *     But it can't work for us, since the bitmap's don't have a
     -+	 *     fixed size. So we learn the position of the xor'd bitmap
     -+	 *     from the commit table (and resolve it to a bitmap in the
     -+	 *     above if-statement).
     -+	 *
     -+	 * Instead, we can skip ahead and immediately read the flags and
     -+	 * ewah bitmap.
     -+	 */
     -+	bitmap_git->map_pos = bitmap_ofs + sizeof(uint32_t) + sizeof(uint8_t);
     ++	bitmap_git->map_pos = offset + sizeof(uint32_t) + sizeof(uint8_t);
      +	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
      +	bitmap = read_bitmap_1(bitmap_git);
     ++
      +	if (!bitmap)
      +		return NULL;
      +
      +	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
      +}
      +
     -+static struct stored_bitmap *stored_bitmap_for_commit(struct bitmap_index *bitmap_git,
     -+						      struct commit *commit,
     -+						      uint32_t *pos_hint)
     + struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
     + 				      struct commit *commit)
       {
       	khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
       					   commit->object.oid);
      -	if (hash_pos >= kh_end(bitmap_git->bitmaps))
     +-		return NULL;
      +	if (hash_pos >= kh_end(bitmap_git->bitmaps)) {
     -+		uint32_t commit_pos;
     ++		struct stored_bitmap *bitmap = NULL;
      +		if (!bitmap_git->table_lookup)
      +			return NULL;
      +
     -+		/* NEEDSWORK: cache misses aren't recorded. */
     -+		if (pos_hint)
     -+			commit_pos = *pos_hint;
     -+		else if (!bitmap_table_lookup(bitmap_git,
     -+					      &commit->object.oid,
     -+					      &commit_pos))
     ++		/* NEEDSWORK: cache misses aren't recorded */
     ++		bitmap = lazy_bitmap_for_commit(bitmap_git, commit);
     ++		if(!bitmap)
      +			return NULL;
     -+		return lazy_bitmap_for_commit(bitmap_git, &commit->object.oid,
     -+					      commit_pos);
     ++		return lookup_stored_bitmap(bitmap);
      +	}
     -+	return kh_value(bitmap_git->bitmaps, hash_pos);
     -+}
     -+
     -+struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
     -+				      struct commit *commit)
     -+{
     -+	struct stored_bitmap *sb = stored_bitmap_for_commit(bitmap_git, commit,
     -+							    NULL);
     -+	if (!sb)
     - 		return NULL;
     --	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
     -+	return lookup_stored_bitmap(sb);
     + 	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
       }
       
     - static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
      @@ pack-bitmap.c: void test_bitmap_walk(struct rev_info *revs)
       	if (revs->pending.nr != 1)
       		die("you must specify exactly one commit to test");
       
      -	fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
     --		bitmap_git->version, bitmap_git->entry_count);
     ++	fprintf(stderr, "Bitmap v%d test (%d entries)\n",
     + 		bitmap_git->version, bitmap_git->entry_count);
     + 
      +	if (!bitmap_git->table_lookup)
      +		fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
      +			bitmap_git->version, bitmap_git->entry_count);
     - 
     ++
       	root = revs->pending.objects[0].item;
       	bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
     + 
     +@@ pack-bitmap.c: void test_bitmap_walk(struct rev_info *revs)
     + 
     + int test_bitmap_commits(struct repository *r)
     + {
     +-	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
     ++	struct bitmap_index *bitmap_git = NULL;
     + 	struct object_id oid;
     + 	MAYBE_UNUSED void *value;
     + 
     ++	/* As this function is only used to print bitmap selected
     ++	 * commits, we don't have to read the commit table.
     ++	 */
     ++	setenv("GIT_TEST_READ_COMMIT_TABLE", "0", 1);
     ++
     ++	bitmap_git = prepare_bitmap_git(r);
     + 	if (!bitmap_git)
     + 		die("failed to load bitmap indexes");
     + 
     +@@ pack-bitmap.c: int test_bitmap_commits(struct repository *r)
     + 		printf("%s\n", oid_to_hex(&oid));
     + 	});
     + 
     ++	setenv("GIT_TEST_READ_COMMIT_TABLE", "1", 1);
     + 	free_bitmap_index(bitmap_git);
     + 
     + 	return 0;
      
     - ## pack-bitmap.h ##
     -@@ pack-bitmap.h: struct bitmap_disk_header {
     - enum pack_bitmap_opts {
     - 	BITMAP_OPT_FULL_DAG = 1,
     - 	BITMAP_OPT_HASH_CACHE = 4,
     -+	BITMAP_OPT_LOOKUP_TABLE = 16,
     - };
     + ## t/t5310-pack-bitmaps.sh ##
     +@@ t/t5310-pack-bitmaps.sh: test_expect_success 'full repack creates bitmaps' '
     + 	grep "\"label\":\"writing_lookup_table\"" trace
     + '
     + 
     ++test_expect_success 'using lookup table loads only necessary bitmaps' '
     ++	git rev-list --test-bitmap HEAD 2>out &&
     ++	! grep "Bitmap v1 test (106 entries loaded)" out &&
     ++	grep "Found bitmap for" out
     ++'
     ++
     + basic_bitmap_tests
       
     - enum pack_bitmap_flags {
     + test_expect_success 'incremental repack fails when bitmaps are requested' '
     +@@ t/t5310-pack-bitmaps.sh: test_expect_success 'pack reuse respects --incremental' '
     + 
     + test_expect_success 'truncated bitmap fails gracefully (ewah)' '
     + 	test_config pack.writebitmaphashcache false &&
     ++	test_config pack.writebitmaplookuptable false &&
     + 	git repack -ad &&
     + 	git rev-list --use-bitmap-index --count --all >expect &&
     + 	bitmap=$(ls .git/objects/pack/*.bitmap) &&
     +
     + ## t/t5326-multi-pack-bitmaps.sh ##
     +@@ t/t5326-multi-pack-bitmaps.sh: test_expect_success 'multi-pack-index write writes lookup table if enabled' '
     + 		grep "\"label\":\"writing_lookup_table\"" trace
     + 	)
     + '
     ++
     + test_done
 5:  a404779a30f < -:  ----------- bitmap-commit-table: add tests for the bitmap lookup table
 6:  f5f725a3fe2 ! 5:  96c0041688f bitmap-lookup-table: add performance tests

@@ Metadata
Author: Abhradeep Chakraborty <[email protected]>

## Commit message ##
- bitmap-lookup-table: add performance tests
+ bitmap-lookup-table: add performance tests for lookup table

- Add performance tests for bitmap lookup table extension.
+ Add performance tests to verify the performance of lookup table.
+
+ Lookup table makes Git run faster in most of the cases. Below is the
+ result of t/perf/p5310-pack-bitmaps.sh.perf/p5326-multi-pack-bitmaps.sh
+ gives similar result. The repository used in the test is linux kernel.
+
+ Test this tree
+ --------------------------------------------------------------------------
+ 5310.4: repack to disk (lookup=false) 295.94(250.45+15.24)
+ 5310.5: simulated clone 12.52(5.07+1.40)
+ 5310.6: simulated fetch 1.89(2.94+0.24)
+ 5310.7: pack to file (bitmap) 41.39(20.33+7.20)
+ 5310.8: rev-list (commits) 0.98(0.59+0.12)
+ 5310.9: rev-list (objects) 3.40(3.27+0.10)
+ 5310.10: rev-list with tag negated via --not 0.07(0.02+0.04)
+ --all (objects)
+ 5310.11: rev-list with negative tag (objects) 0.23(0.16+0.06)
+ 5310.12: rev-list count with blob:none 0.26(0.18+0.07)
+ 5310.13: rev-list count with blob:limit=1k 6.45(5.94+0.37)
+ 5310.14: rev-list count with tree:0 0.26(0.18+0.07)
+ 5310.15: simulated partial clone 4.99(3.19+0.45)
+ 5310.19: repack to disk (lookup=true) 269.67(174.70+21.33)
+ 5310.20: simulated clone 11.03(5.07+1.11)
+ 5310.21: simulated fetch 0.79(0.79+0.17)
+ 5310.22: pack to file (bitmap) 43.03(20.28+7.43)
+ 5310.23: rev-list (commits) 0.86(0.54+0.09)
+ 5310.24: rev-list (objects) 3.35(3.26+0.07)
+ 5310.25: rev-list with tag negated via --not 0.05(0.00+0.03)
+ --all (objects)
+ 5310.26: rev-list with negative tag (objects) 0.22(0.16+0.05)
+ 5310.27: rev-list count with blob:none 0.22(0.16+0.05)
+ 5310.28: rev-list count with blob:limit=1k 6.45(5.87+0.31)
+ 5310.29: rev-list count with tree:0 0.22(0.16+0.05)
+ 5310.30: simulated partial clone 5.17(3.12+0.48)
+
+ Test 4-15 are tested without using lookup table. Same tests are
+ repeated in 16-30 (using lookup table).

- Mentored-by: Taylor Blau <[email protected]>
- Co-mentored-by: Kaartic Sivaraam <[email protected]>

+ Mentored-by: Taylor Blau <[email protected]>
+ Co-Mentored-by: Kaartic Sivaraam <[email protected]>

## t/perf/p5310-pack-bitmaps.sh ##
-@@ t/perf/p5310-pack-bitmaps.sh: test_perf_large_repo
- # since we want to be able to compare bitmap-aware
- # git versus non-bitmap git
- #
--# We intentionally use the deprecated pack.writebitmaps
-+# We intentionally use the deprecated pack.writeBitmaps
- # config so that we can test against older versions of git.
- test_expect_success 'setup bitmap config' '
-- git config pack.writebitmaps true
-+ git config pack.writeBitmaps true &&
-+ git config pack.writeReverseIndex true
+@@ t/perf/p5310-pack-bitmaps.sh: test_expect_success 'setup bitmap config' '
+ git config pack.writebitmaps true
'

- # we need to create the tag up front such that it is covered by the repack and -@@ t/perf/p5310-pack-bitmaps.sh: test_perf 'repack to disk' '
-
- test_full_bitmap
-
+-# we need to create the tag up front such that it is covered by the repack and +-# thus by generated bitmaps.
+-test_expect_success 'create tags' '
+- git tag --message="tag pointing to HEAD" perf-tag HEAD
+-'
+-
+-test_perf 'repack to disk' '
+- git repack -ad
+-'
+-
+-test_full_bitmap
+-
-test_expect_success 'create partial bitmap state' '
- # pick a commit to represent the repo tip in the past
- cutoff=$(git rev-list HEAD~100 -1) &&
@@ t/perf/p5310-pack-bitmaps.sh: test_perf 'repack to disk' '
- # and now restore our original tip, as if the pushes
- # had happened
- git update-ref HEAD $orig_tip
-+test_perf 'use lookup table' '
-+ git config pack.writeBitmapLookupTable true
- '
-
+-'
+-
-test_partial_bitmap
-+test_perf 'repack to disk (lookup table)' '
-+ git repack -adb
-+'
++test_bitmap () {
++ local enabled="$1"
+
-+test_full_bitmap
++ # we need to create the tag up front such that it is covered by the repack and
++ # thus by generated bitmaps.
++ test_expect_success 'create tags' '
++ git tag --message="tag pointing to HEAD" perf-tag HEAD
++ '
+
-+for i in false true
-+do
-+ $i && lookup=" (lookup table)"
-+ test_expect_success "create partial bitmap state$lookup" '
-+ git config pack.writeBitmapLookupTable '"$i"' &&
++ test_expect_success "use lookup table: $enabled" '
++ git config pack.writeBitmapLookupTable '"$enabled"'
++ '
++
++ test_perf "repack to disk (lookup=$enabled)" '
++ git repack -ad
++ '
++
++ test_full_bitmap
++
++ test_expect_success "create partial bitmap state (lookup=$enabled)" '
+ # pick a commit to represent the repo tip in the past
+ cutoff=$(git rev-list HEAD~100 -1) &&
+ orig_tip=$(git rev-parse HEAD) &&
@@ t/perf/p5310-pack-bitmaps.sh: test_perf 'repack to disk' '
+ # and now restore our original tip, as if the pushes
+ # had happened
+ git update-ref HEAD $orig_tip
-+ '
++ '
++}
+
-+ test_partial_bitmap
-+done
++test_bitmap false
++test_bitmap true

test_done

## t/perf/p5326-multi-pack-bitmaps.sh ##
-@@ t/perf/p5326-multi-pack-bitmaps.sh: test_expect_success 'drop pack bitmap' ' +@@ t/perf/p5326-multi-pack-bitmaps.sh: test_description='Tests performance using midx bitmaps'

- test_full_bitmap
+ test_perf_large_repo

+-# we need to create the tag up front such that it is covered by the repack and +-# thus by generated bitmaps.
+-test_expect_success 'create tags' '
+- git tag --message="tag pointing to HEAD" perf-tag HEAD
+-'
+-
+-test_expect_success 'start with bitmapped pack' '
+- git repack -adb
+-'
+-
+-test_perf 'setup multi-pack index' '
+- git multi-pack-index write --bitmap
+-'
+-
+-test_expect_success 'drop pack bitmap' '
+- rm -f .git/objects/pack/pack-*.bitmap
+-'
+-
+-test_full_bitmap
+-
-test_expect_success 'create partial bitmap state' '
- # pick a commit to represent the repo tip in the past
- cutoff=$(git rev-list HEAD~100 -1) &&
@@ t/perf/p5326-multi-pack-bitmaps.sh: test_expect_success 'drop pack bitmap' '
- # and now restore our original tip, as if the pushes
- # had happened
- git update-ref HEAD $orig_tip
-+test_expect_success 'use lookup table' '
-+ git config pack.writeBitmapLookupTable true
- '
-
+-'
+-
-test_partial_bitmap
-+test_perf 'setup multi-pack-index (lookup table)' '
-+ git multi-pack-index write --bitmap
-+'
++test_bitmap () {
++ local enabled="$1"
++
++ # we need to create the tag up front such that it is covered by the repack and
++ # thus by generated bitmaps.
++ test_expect_success 'create tags' '
++ git tag --message="tag pointing to HEAD" perf-tag HEAD
++ '
+
-+test_full_bitmap
++ test_expect_success "use lookup table: $enabled" '
++ git config pack.writeBitmapLookupTable '"$enabled"'
++ '
++
++ test_expect_success "start with bitmapped pack (lookup=$enabled)" '
++ git repack -adb
++ '
++
++ test_perf "setup multi-pack index (lookup=$enabled)" '
++ git multi-pack-index write --bitmap
++ '
+
-+for i in false true
-+do
-+ $i && lookup=" (lookup table)"
-+ test_expect_success "create partial bitmap state$lookup" '
-+ git config pack.writeBitmapLookupTable '"$i"' &&
++ test_expect_success "drop pack bitmap (lookup=$enabled)" '
++ rm -f .git/objects/pack/pack-*.bitmap
++ '
++
++ test_full_bitmap
++
++ test_expect_success "create partial bitmap state (lookup=$enabled)" '
+ # pick a commit to represent the repo tip in the past
+ cutoff=$(git rev-list HEAD~100 -1) &&
+ orig_tip=$(git rev-parse HEAD) &&
@@ t/perf/p5326-multi-pack-bitmaps.sh: test_expect_success 'drop pack bitmap' '
+ # and now restore our original tip, as if the pushes
+ # had happened
+ git update-ref HEAD $orig_tip
-+ '
++ '
++}
+
-+ test_partial_bitmap
-+done
++test_bitmap false
++test_bitmap true

test_done
-: ----------- > 6: fe556b58814 p5310-pack-bitmaps.sh: enable pack.writeReverseIndex for testing

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Add performance tests to verify the performance of lookup table.

Lookup table makes Git run faster in most of the cases. Below is the result of t/perf/p5310-pack-bitmaps.sh.perf/p5326-multi-pack-bitmaps.sh gives similar result. The repository used in the test is linux kernel.

Test this tree
--------------------------------------------------------------------------

5310.4: repack to disk (lookup=false)                   295.94(250.45+15.24)
5310.5: simulated clone                                 12.52(5.07+1.40)
5310.6: simulated fetch                                 1.89(2.94+0.24)
5310.7: pack to file (bitmap)                           41.39(20.33+7.20)
5310.8: rev-list (commits)                              0.98(0.59+0.12)
5310.9: rev-list (objects)                              3.40(3.27+0.10)
5310.10: rev-list with tag negated via --not		0.07(0.02+0.04)
         --all (objects)
5310.11: rev-list with negative tag (objects)           0.23(0.16+0.06)
5310.12: rev-list count with blob:none                  0.26(0.18+0.07)
5310.13: rev-list count with blob:limit=1k              6.45(5.94+0.37)
5310.14: rev-list count with tree:0                     0.26(0.18+0.07)
5310.15: simulated partial clone                        4.99(3.19+0.45)
5310.19: repack to disk (lookup=true)                   269.67(174.70+21.33)
5310.20: simulated clone                                11.03(5.07+1.11)
5310.21: simulated fetch                                0.79(0.79+0.17)
5310.22: pack to file (bitmap)                          43.03(20.28+7.43)
5310.23: rev-list (commits)                             0.86(0.54+0.09)
5310.24: rev-list (objects)                             3.35(3.26+0.07)
5310.25: rev-list with tag negated via --not		0.05(0.00+0.03)
	 --all (objects)
5310.26: rev-list with negative tag (objects)           0.22(0.16+0.05)
5310.27: rev-list count with blob:none                  0.22(0.16+0.05)
5310.28: rev-list count with blob:limit=1k              6.45(5.87+0.31)
5310.29: rev-list count with tree:0                     0.22(0.16+0.05)
5310.30: simulated partial clone                        5.17(3.12+0.48)

Test 4-15 are tested without using lookup table. Same tests are repeated in 16-30 (using lookup table).

---
 t/perf/p5310-pack-bitmaps.sh       | 77 ++++++++++++++-----------
 t/perf/p5326-multi-pack-bitmaps.sh | 93 ++++++++++++++++--------------
 2 files changed, 94 insertions(+), 76 deletions(-)

index 7ad4f237bc3..6ff42bdd391 100755
@@ -16,39 +16,48 @@ test_expect_success 'setup bitmap config' '
 	git config pack.writebitmaps true
 '
 
-# we need to create the tag up front such that it is covered by the repack and
-# thus by generated bitmaps.
-test_expect_success 'create tags' '
-	git tag --message="tag pointing to HEAD" perf-tag HEAD
-'
-
-test_perf 'repack to disk' '
-	git repack -ad
-'
-
-test_full_bitmap
-
-test_expect_success 'create partial bitmap state' '
-	# pick a commit to represent the repo tip in the past
-	cutoff=$(git rev-list HEAD~100 -1) &&
-	orig_tip=$(git rev-parse HEAD) &&
-
-	# now kill off all of the refs and pretend we had
-	# just the one tip
-	rm -rf .git/logs .git/refs/* .git/packed-refs &&
-	git update-ref HEAD $cutoff &&
-
-	# and then repack, which will leave us with a nice
-	# big bitmap pack of the "old" history, and all of
-	# the new history will be loose, as if it had been pushed
-	# up incrementally and exploded via unpack-objects
-	git repack -Ad &&
-
-	# and now restore our original tip, as if the pushes
-	# had happened
-	git update-ref HEAD $orig_tip
-'
-
-test_partial_bitmap
+test_bitmap () {
+    local enabled="$1"
+
+	# we need to create the tag up front such that it is covered by the repack and
+	# thus by generated bitmaps.
+	test_expect_success 'create tags' '
+		git tag --message="tag pointing to HEAD" perf-tag HEAD
+	'
+
+	test_expect_success "use lookup table: $enabled" '
+		git config pack.writeBitmapLookupTable '"$enabled"'
+	'
+
+	test_perf "repack to disk (lookup=$enabled)" '
+		git repack -ad
+	'
+
+	test_full_bitmap
+
+    test_expect_success "create partial bitmap state (lookup=$enabled)" '
+		# pick a commit to represent the repo tip in the past
+		cutoff=$(git rev-list HEAD~100 -1) &&
+		orig_tip=$(git rev-parse HEAD) &&
+
+		# now kill off all of the refs and pretend we had
+		# just the one tip
+		rm -rf .git/logs .git/refs/* .git/packed-refs &&
+		git update-ref HEAD $cutoff &&
+
+		# and then repack, which will leave us with a nice
+		# big bitmap pack of the "old" history, and all of
+		# the new history will be loose, as if it had been pushed
+		# up incrementally and exploded via unpack-objects
+		git repack -Ad &&
+
+		# and now restore our original tip, as if the pushes
+		# had happened
+		git update-ref HEAD $orig_tip
+    '
+}
+
+test_bitmap false
+test_bitmap true
 
 test_done

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Enable pack.writeReverseIndex to true to see the effect of writing the reverse index in the existing bitmap tests (with and without lookup table).

Below is the result of performance test. Output format is in seconds.

Test this tree
-------------------------------------------------------------------

5310.4: repack to disk (lookup=false)           294.92(257.60+14.29)
5310.5: simulated clone                         14.97(8.95+1.31)
5310.6: simulated fetch                         1.64(2.77+0.20)
5310.7: pack to file (bitmap)                   41.76(29.33+6.77)
5310.8: rev-list (commits)                      0.71(0.49+0.09)
5310.9: rev-list (objects)                      4.65(4.55+0.09)
5310.10: rev-list with tag negated via --not	0.08(0.02+0.05)
	 --all (objects)
5310.11: rev-list with negative tag (objects)   0.06(0.01+0.04)
5310.12: rev-list count with blob:none          0.09(0.03+0.05)
5310.13: rev-list count with blob:limit=1k      7.58(7.06+0.33)
5310.14: rev-list count with tree:0             0.09(0.03+0.06)
5310.15: simulated partial clone                8.64(8.04+0.35)
5310.19: repack to disk (lookup=true)           249.86(191.57+19.50)
5310.20: simulated clone                        13.67(8.83+1.06)
5310.21: simulated fetch                        0.50(0.63+0.13)
5310.22: pack to file (bitmap)                  41.24(28.99+6.67)
5310.23: rev-list (commits)                     0.67(0.50+0.07)
5310.24: rev-list (objects)                     4.88(4.79+0.08)
5310.25: rev-list with tag negated via --not    0.04(0.00+0.03)
	 --all (objects)
5310.26: rev-list with negative tag (objects)   0.05(0.00+0.04)
5310.27: rev-list count with blob:none          0.05(0.01+0.03)
5310.28: rev-list count with blob:limit=1k      8.02(7.16+0.34)
5310.29: rev-list count with tree:0             0.05(0.01+0.04)
5310.30: simulated partial clone                8.57(8.16+0.32)

Tests 4-15 are without the use of lookup table. The rests are repeatation of the previous tests but using lookup table.

---
 t/perf/p5310-pack-bitmaps.sh | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 6ff42bdd391..9848c5d5040 100755
@@ -13,7 +13,8 @@ test_perf_large_repo
 # We intentionally use the deprecated pack.writebitmaps
 # config so that we can test against older versions of git.
 test_expect_success 'setup bitmap config' '
-	git config pack.writebitmaps true
+	git config pack.writebitmaps true &&
+	git config pack.writeReverseIndex true
 '
 
 test_bitmap () {

gitgitgadget

From: Abhradeep Chakraborty <[email protected]>

Earlier change teaches Git to write bitmap lookup table. But Git does not know how to parse them.

Teach Git to parse the existing bitmap lookup table. The older versions of git are not affected by it. Those versions ignore the lookup table.

---
 pack-bitmap.c                 | 193 ++++++++++++++++++++++++++++++++--
 t/t5310-pack-bitmaps.sh       |   7 ++
 t/t5326-multi-pack-bitmaps.sh |   1 +
 3 files changed, 191 insertions(+), 10 deletions(-)

index 36134222d7a..9e09c5824fc 100644
@@ -82,6 +82,12 @@ struct bitmap_index {
 	/* The checksum of the packfile or MIDX; points into map. */
 	const unsigned char *checksum;
 
+	/*
+	 * If not NULL, this point into the commit table extension
+	 * (within map).
+	 */
+	unsigned char *table_lookup;
+
 	/*
 	 * Extended index.
 	 *

@@ -185,6 +191,22 @@ static int load_bitmap_header(struct bitmap_index *index)
 			index->hashes = (void *)(index_end - cache_size);
 			index_end -= cache_size;
 		}
+
+		if (flags & BITMAP_OPT_LOOKUP_TABLE &&
+			git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1)) {
+			size_t table_size = 0;
+			size_t triplet_sz = st_add3(sizeof(uint32_t),    /* commit position */
+							sizeof(uint64_t),    /* offset */
+							sizeof(uint32_t));    /* xor offset */
+
+			table_size = st_add(table_size,
+					st_mult(ntohl(header->entry_count),
+						triplet_sz));
+			if (table_size > index_end - index->map - header_size)
+				return error("corrupted bitmap index file (too short to fit lookup table)");
+			index->table_lookup = (void *)(index_end - table_size);
+			index_end -= table_size;
+		}
 	}
 
 	index->entry_count = ntohl(header->entry_count);

@@ -211,12 +233,20 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 
 	hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
 
-	/* a 0 return code means the insertion succeeded with no changes,
-	 * because the SHA1 already existed on the map. this is bad, there
-	 * shouldn't be duplicated commits in the index */
+	/* A 0 return code means the insertion succeeded with no changes,
+	 * because the SHA1 already existed on the map. If lookup table
+	 * is NULL, this is bad, there shouldn't be duplicated commits
+	 * in the index.
+	 *
+	 * If table_lookup exists, that means the desired bitmap is already
+	 * loaded. Either this bitmap has been stored directly or another
+	 * bitmap has a direct or indirect xor relation with it. */
 	if (ret == 0) {
-		error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
-		return NULL;
+		if (!index->table_lookup) {
+			error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
+			return NULL;
+		}
+		return kh_value(index->bitmaps, hash_pos);
 	}
 
 	kh_value(index->bitmaps, hash_pos) = stored;

@@ -470,7 +500,7 @@ static int load_bitmap(struct bitmap_index *bitmap_git)
 		!(bitmap_git->tags = read_bitmap_1(bitmap_git)))
 		goto failed;
 
-	if (load_bitmap_entries_v1(bitmap_git) < 0)
+	if (!bitmap_git->table_lookup && load_bitmap_entries_v1(bitmap_git) < 0)
 		goto failed;
 
 	return 0;

@@ -557,13 +587,145 @@ struct include_data {
 	struct bitmap *seen;
 };
 
+static inline const void *bitmap_get_triplet(struct bitmap_index *bitmap_git, uint32_t xor_pos)
+{
+	size_t triplet_sz = st_add3(sizeof(uint32_t), sizeof(uint64_t), sizeof(uint32_t));
+	const void *p = bitmap_git->table_lookup + st_mult(xor_pos, triplet_sz);
+	return p;
+}
+
+static uint64_t triplet_get_offset(const void *triplet)
+{
+	const void *p = (unsigned char*) triplet + sizeof(uint32_t);
+	return get_be64(p);
+}
+
+static uint32_t triplet_get_xor_pos(const void *triplet)
+{
+	const void *p = (unsigned char*) triplet + st_add(sizeof(uint32_t), sizeof(uint64_t));
+	return get_be32(p);
+}
+
+static int triplet_cmp(const void *va, const void *vb)
+{
+	int result = 0;
+	uint32_t *a = (uint32_t *) va;
+	uint32_t b = get_be32(vb);
+	if (*a > b)
+		result = 1;
+	else if (*a < b)
+		result = -1;
+	else
+		result = 0;
+
+	return result;
+}
+
+static uint32_t bsearch_pos(struct bitmap_index *bitmap_git, struct object_id *oid,
+						uint32_t *result)
+{
+	int found;
+
+	if (bitmap_git->midx)
+		found = bsearch_midx(oid, bitmap_git->midx, result);
+	else
+		found = bsearch_pack(oid, bitmap_git->pack, result);
+
+	return found;
+}
+
+static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
+					  struct commit *commit)
+{
+	uint32_t commit_pos, xor_pos;
+	uint64_t offset;
+	int flags;
+	const void *triplet = NULL;
+	struct object_id *oid = &commit->object.oid;
+	struct ewah_bitmap *bitmap;
+	struct stored_bitmap *xor_bitmap = NULL;
+	size_t triplet_sz = st_add3(sizeof(uint32_t), sizeof(uint64_t), sizeof(uint32_t));
+
+	int found = bsearch_pos(bitmap_git, oid, &commit_pos);
+
+	if (!found)
+		return NULL;
+
+	triplet = bsearch(&commit_pos, bitmap_git->table_lookup, bitmap_git->entry_count,
+						triplet_sz, triplet_cmp);
+	if (!triplet)
+		return NULL;
+
+	offset = triplet_get_offset(triplet);
+	xor_pos = triplet_get_xor_pos(triplet);
+
+	if (xor_pos != 0xffffffff) {
+		int xor_flags;
+		uint64_t offset_xor;
+		uint32_t *xor_positions;
+		struct object_id xor_oid;
+		size_t size = 0;
+
+		ALLOC_ARRAY(xor_positions, bitmap_git->entry_count);
+		while (xor_pos != 0xffffffff) {
+			xor_positions[size++] = xor_pos;
+			triplet = bitmap_get_triplet(bitmap_git, xor_pos);
+			xor_pos = triplet_get_xor_pos(triplet);
+		}
+
+		while (size){
+			xor_pos = xor_positions[size - 1];
+			triplet = bitmap_get_triplet(bitmap_git, xor_pos);
+			commit_pos = get_be32(triplet);
+			offset_xor = triplet_get_offset(triplet);
+
+			if (nth_bitmap_object_oid(bitmap_git, &xor_oid, commit_pos) < 0) {
+				free(xor_positions);
+				return NULL;
+			}
+
+			bitmap_git->map_pos = offset_xor + sizeof(uint32_t) + sizeof(uint8_t);
+			xor_flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+			bitmap = read_bitmap_1(bitmap_git);
+
+			if (!bitmap){
+				free(xor_positions);
+				return NULL;
+			}
+
+			xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_oid, xor_bitmap, xor_flags);
+			size--;
+		}
+
+		free(xor_positions);
+	}
+
+	bitmap_git->map_pos = offset + sizeof(uint32_t) + sizeof(uint8_t);
+	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+	bitmap = read_bitmap_1(bitmap_git);
+
+	if (!bitmap)
+		return NULL;
+
+	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
+}
+
 struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
 				      struct commit *commit)
 {
 	khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
 					   commit->object.oid);
-	if (hash_pos >= kh_end(bitmap_git->bitmaps))
-		return NULL;
+	if (hash_pos >= kh_end(bitmap_git->bitmaps)) {
+		struct stored_bitmap *bitmap = NULL;
+		if (!bitmap_git->table_lookup)
+			return NULL;
+
+		/* NEEDSWORK: cache misses aren't recorded */
+		bitmap = lazy_bitmap_for_commit(bitmap_git, commit);
+		if(!bitmap)
+			return NULL;
+		return lookup_stored_bitmap(bitmap);
+	}
 	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
 }
 

@@ -1699,9 +1861,13 @@ void test_bitmap_walk(struct rev_info *revs)
 	if (revs->pending.nr != 1)
 		die("you must specify exactly one commit to test");
 
-	fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
+	fprintf(stderr, "Bitmap v%d test (%d entries)\n",
 		bitmap_git->version, bitmap_git->entry_count);
 
+	if (!bitmap_git->table_lookup)
+		fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
+			bitmap_git->version, bitmap_git->entry_count);
+
 	root = revs->pending.objects[0].item;
 	bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
 

@@ -1753,10 +1919,16 @@ void test_bitmap_walk(struct rev_info *revs)
 
 int test_bitmap_commits(struct repository *r)
 {
-	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
+	struct bitmap_index *bitmap_git = NULL;
 	struct object_id oid;
 	MAYBE_UNUSED void *value;
 
+	/* As this function is only used to print bitmap selected
+	 * commits, we don't have to read the commit table.
+	 */
+	setenv("GIT_TEST_READ_COMMIT_TABLE", "0", 1);
+
+	bitmap_git = prepare_bitmap_git(r);
 	if (!bitmap_git)
 		die("failed to load bitmap indexes");
 

@@ -1764,6 +1936,7 @@ int test_bitmap_commits(struct repository *r)
 		printf("%s\n", oid_to_hex(&oid));
 	});
 
+	setenv("GIT_TEST_READ_COMMIT_TABLE", "1", 1);
 	free_bitmap_index(bitmap_git);
 
 	return 0;

index c669ed959e9..10d7691d973 100755
@@ -42,6 +42,12 @@ test_expect_success 'full repack creates bitmaps' '
 	grep "\"label\":\"writing_lookup_table\"" trace
 '
 
+test_expect_success 'using lookup table loads only necessary bitmaps' '
+	git rev-list --test-bitmap HEAD 2>out &&
+	! grep "Bitmap v1 test (106 entries loaded)" out &&
+	grep "Found bitmap for" out
+'
+
 basic_bitmap_tests
 
 test_expect_success 'incremental repack fails when bitmaps are requested' '

@@ -255,6 +261,7 @@ test_expect_success 'pack reuse respects --incremental' '
 
 test_expect_success 'truncated bitmap fails gracefully (ewah)' '
 	test_config pack.writebitmaphashcache false &&
+	test_config pack.writebitmaplookuptable false &&
 	git repack -ad &&
 	git rev-list --use-bitmap-index --count --all >expect &&
 	bitmap=$(ls .git/objects/pack/*.bitmap) &&

index 43be49617b8..7d36dbcf722 100755
@@ -320,4 +320,5 @@ test_expect_success 'multi-pack-index write writes lookup table if enabled' '
 		grep "\"label\":\"writing_lookup_table\"" trace
 	)
 '
+
 test_done

gitgitgadget

s/neccesary/necessary/

s/documentated/documented/

s/knowhow/know how/

	uint32_t xor_offset = selected->xor_offset;
	uint32_t xor_row = 0xffffffff;

	if (xor_offset) {
		uint32_t xor_order = table[i] - xor_offset;
		xor_row = table_inf[xor_order];
	}

I wonder if it makes sense to have it default to 'false' for now, but to change that default after the feature has been shipped and running in production for a while.

s/writting/writing/

I didn't check the previous patches, but your sign-off should be the last line of the message. (You are singing off on all previous content, and any later content is not covered by your sign-off.)

		if (flags & BITMAP_OPT_LOOKUP_TABLE &&
		    git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1)) {

			size_t triplet_sz = st_add3(sizeof(uint32_t),  /* commit position */
						    sizeof(uint64_t),  /* offset */
						    sizeof(uint32_t)); /* xor offset */

			size_t triplet_sz = sizeof(uint32_t) + /* commit position */
					    sizeof(uint64_t) +  /* offset */
					    sizeof(uint32_t); /* xor offset */

			size_t table_size = st_mult(ntohl(header->entry_count),
						    triplet_sz));

			    struct object_id *oid,
			    uint32_t *result)

...