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

[PATCH v2 09/15] rev-list: allow commit-only bitmap traversals

From
Jeff King <peff@peff.net>
Date
Feb 14, 2020, 18:22 UTC
Message-ID
<20200214182227.GI150965@coredump.intra.peff.net>
In-Reply-To
<20200214182147.GA654525@coredump.intra.peff.net>

Ever since we added reachability bitmap support, we've been able to use it with rev-list to get the full list of objects, like:

  git rev-list --objects --use-bitmap-index --all

But you can't do so without --objects, since we weren't ready to just show the commits. However, the internals of the bitmap code are mostly ready for this: they avoid opening up trees when walking to fill in the bitmaps. We just need to actually pass in the rev_info to traverse_bitmap_commit_list() so it knows which types to bother triggering our callback for.

For completeness, the perf test now covers both the existing --objects case, as well as the new commits-only behavior (the objects one got way faster when we introduced bitmaps, but obviously isn't improved now).

Here are numbers for linux.git:
  Test                         HEAD^               HEAD
  ------------------------------------------------------------------------
  5310.7: rev-list (commits)   8.29(8.10+0.19)       1.76(1.72+0.04) -78.8%
  5310.8: rev-list (objects)   8.06(7.94+0.12)       8.14(7.94+0.13) +1.0%

That run was cheating a little, as I didn't have any commit-graph in the repository, and we'd built it by default these days when running git-gc. Here are numbers with a commit-graph:

  Test                         HEAD^               HEAD
  ------------------------------------------------------------------------
  5310.7: rev-list (commits)   0.70(0.58+0.12)     0.51(0.46+0.04) -27.1%
  5310.8: rev-list (objects)   6.20(6.09+0.10)     6.27(6.16+0.11) +1.1%
Still an improvement, but a lot less impressive.

We could have the perf script remove any commit-graph to show the out-sized effect, but it probably makes sense to leave it in what would be a more typical setup.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c       |  3 ++-
 builtin/rev-list.c           |  9 +--------
 pack-bitmap.c                | 20 +++++++++++++++-----
 pack-bitmap.h                |  1 +
 reachable.c                  |  2 +-
 t/perf/p5310-pack-bitmaps.sh |  8 ++++++++
 t/t5310-pack-bitmaps.sh      |  6 ++++++
 7 files changed, 34 insertions(+), 15 deletions(-)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 393c20a2d7..06915ebe7f 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -3054,7 +3054,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
 		display_progress(progress_state, nr_result);
 	}
 
-	traverse_bitmap_commit_list(bitmap_git, &add_object_entry_from_bitmap);
+	traverse_bitmap_commit_list(bitmap_git, revs,
+				    &add_object_entry_from_bitmap);
 	return 0;
 }
 
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 70f3207ecc..937324cef0 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -434,18 +434,11 @@ static int try_bitmap_traversal(struct rev_info *revs)
 	if (revs->max_count >= 0)
 		return -1;
 
-	/*
-	 * Our bitmap result will return all objects, and we're not
-	 * yet prepared to show only particular types.
-	 */
-	if (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)
-		return -1;
-
 	bitmap_git = prepare_bitmap_walk(revs);
 	if (!bitmap_git)
 		return -1;
 
-	traverse_bitmap_commit_list(bitmap_git, &show_object_fast);
+	traverse_bitmap_commit_list(bitmap_git, revs, &show_object_fast);
 	free_bitmap_index(bitmap_git);
 	return 0;
 }
diff --git a/pack-bitmap.c b/pack-bitmap.c
index a97b717e55..2fbc748b19 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -599,6 +599,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
 }
 
 static void show_extended_objects(struct bitmap_index *bitmap_git,
+				  struct rev_info *revs,
 				  show_reachable_fn show_reach)
 {
 	struct bitmap *objects = bitmap_git->result;
@@ -612,6 +613,11 @@ static void show_extended_objects(struct bitmap_index *bitmap_git,
 			continue;
 
 		obj = eindex->objects[i];
+		if ((obj->type == OBJ_BLOB && !revs->blob_objects) ||
+		    (obj->type == OBJ_TREE && !revs->tree_objects) ||
+		    (obj->type == OBJ_TAG && !revs->tag_objects))
+			continue;
+
 		show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
 	}
 }
@@ -872,16 +878,20 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
 }
 
 void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
+				 struct rev_info *revs,
 				 show_reachable_fn show_reachable)
 {
 	assert(bitmap_git->result);
 
 	show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);
-	show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
-	show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
-	show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
-
-	show_extended_objects(bitmap_git, show_reachable);
+	if (revs->tree_objects)
+		show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
+	if (revs->blob_objects)
+		show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
+	if (revs->tag_objects)
+		show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
+
+	show_extended_objects(bitmap_git, revs, show_reachable);
 }
 
 static uint32_t count_object_type(struct bitmap_index *bitmap_git,
diff --git a/pack-bitmap.h b/pack-bitmap.h
index 466c5afa09..b0c06a212e 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -44,6 +44,7 @@ struct bitmap_index *prepare_bitmap_git(struct repository *r);
 void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits,
 			      uint32_t *trees, uint32_t *blobs, uint32_t *tags);
 void traverse_bitmap_commit_list(struct bitmap_index *,
+				 struct rev_info *revs,
 				 show_reachable_fn show_reachable);
 void test_bitmap_walk(struct rev_info *revs);
 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);
diff --git a/reachable.c b/reachable.c
index 8f50235b28..0919f025c4 100644
--- a/reachable.c
+++ b/reachable.c
@@ -225,7 +225,7 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,
 
 	bitmap_git = prepare_bitmap_walk(revs);
 	if (bitmap_git) {
-		traverse_bitmap_commit_list(bitmap_git, mark_object_seen);
+		traverse_bitmap_commit_list(bitmap_git, revs, mark_object_seen);
 		free_bitmap_index(bitmap_git);
 		return;
 	}
diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
index 6a3a42531b..e52f66ec9e 100755
--- a/t/perf/p5310-pack-bitmaps.sh
+++ b/t/perf/p5310-pack-bitmaps.sh
@@ -39,6 +39,14 @@ test_perf 'pack to file (bitmap)' '
 	git pack-objects --use-bitmap-index --all pack1b </dev/null >/dev/null
 '
 
+test_perf 'rev-list (commits)' '
+	git rev-list --all --use-bitmap-index >/dev/null
+'
+
+test_perf 'rev-list (objects)' '
+	git rev-list --all --use-bitmap-index --objects >/dev/null
+'
+
 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) &&
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index b8645ae070..2c64d0c441 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -80,6 +80,12 @@ rev_list_tests() {
 		test_cmp expect actual
 	'
 
+	test_expect_success "enumerate commits ($state)" '
+		git rev-list --use-bitmap-index HEAD >actual &&
+		git rev-list HEAD >expect &&
+		test_bitmap_traversal --no-confirm-bitmaps expect actual
+	'
+
 	test_expect_success "enumerate --objects ($state)" '
 		git rev-list --objects --use-bitmap-index HEAD >actual &&
 		git rev-list --objects HEAD >expect &&

-- 
2.25.0.796.gcc29325708
Previous: Junio C HamanoNext: Derrick Stolee
Message 55 of 73 in “combining object filters and bitmaps”
  1. 0/13 combining object filters and bitmapsJeff King, Feb 13, 2020
  2. 01/13 pack-bitmap: factor out type iterator initializationJeff King, Feb 13, 2020
  3. Junio C HamanoFeb 13, 2020
  4. 02/13 pack-bitmap: fix leak of haves/wants object listsJeff King, Feb 13, 2020
  5. Junio C HamanoFeb 13, 2020
  6. 03/13 rev-list: fallback to non-bitmap traversal when filteringJeff King, Feb 13, 2020
  7. Junio C HamanoFeb 13, 2020
  8. Jeff KingFeb 13, 2020
  9. 04/13 rev-list: consolidate bitmap-disabling optionsJeff King, Feb 13, 2020
  10. 05/13 rev-list: factor out bitmap-optimized routinesJeff King, Feb 13, 2020
  11. Junio C HamanoFeb 13, 2020
  12. 06/13 rev-list: make --count work with --objectsJeff King, Feb 13, 2020
  13. Junio C HamanoFeb 13, 2020
  14. Jeff KingFeb 13, 2020
  15. 07/13 rev-list: allow bitmaps when counting objectsJeff King, Feb 13, 2020
  16. Junio C HamanoFeb 13, 2020
  17. Jeff KingFeb 13, 2020
  18. 08/13 pack-bitmap: basic noop bitmap filter infrastructureJeff King, Feb 13, 2020
  19. 09/13 rev-list: use bitmap filters for traversalJeff King, Feb 13, 2020
  20. Junio C HamanoFeb 13, 2020
  21. Jeff KingFeb 13, 2020
  22. 10/13 bitmap: add bitmap_unset() functionJeff King, Feb 13, 2020
  23. 11/13 pack-bitmap: implement BLOB_NONE filteringJeff King, Feb 13, 2020
  24. 12/13 pack-bitmap: implement BLOB_LIMIT filteringJeff King, Feb 13, 2020
  25. Junio C HamanoFeb 13, 2020
  26. 13/13 pack-objects: support filters with bitmapsJeff King, Feb 13, 2020
  27. 0/15 combining object filters and bitmapsJeff King, Feb 14, 2020
  28. 01/15 pack-bitmap: factor out type iterator initializationJeff King, Feb 14, 2020
  29. Taylor BlauFeb 15, 2020
  30. 03/15 rev-list: fallback to non-bitmap traversal when filteringJeff King, Feb 14, 2020
  31. Taylor BlauFeb 15, 2020
  32. 04/15 pack-bitmap: refuse to do a bitmap traversal with pathspecsJeff King, Feb 14, 2020
  33. Junio C HamanoFeb 14, 2020
  34. Jeff KingFeb 14, 2020
  35. 05/15 rev-list: factor out bitmap-optimized routinesJeff King, Feb 14, 2020
  36. Taylor BlauFeb 15, 2020
  37. 06/15 rev-list: make --count work with --objectsJeff King, Feb 14, 2020
  38. Taylor BlauFeb 15, 2020
  39. Jeff KingFeb 15, 2020
  40. Junio C HamanoFeb 16, 2020
  41. Jeff KingFeb 18, 2020
  42. Junio C HamanoFeb 18, 2020
  43. Jeff KingFeb 18, 2020
  44. Junio C HamanoFeb 18, 2020
  45. Jeff KingFeb 18, 2020
  46. Derrick StoleeFeb 18, 2020
  47. Jeff KingFeb 18, 2020
  48. 08/15 t5310: factor out bitmap traversal comparisonJeff King, Feb 14, 2020
  49. Taylor BlauFeb 15, 2020
  50. Jeff KingFeb 15, 2020
  51. 07/15 rev-list: allow bitmaps when counting objectsJeff King, Feb 14, 2020
  52. Taylor BlauFeb 15, 2020
  53. Jeff KingFeb 15, 2020
  54. Junio C HamanoFeb 16, 2020
  55. 09/15 rev-list: allow commit-only bitmap traversalsJeff King, Feb 14, 2020
  56. Derrick StoleeFeb 18, 2020
  57. Jeff KingFeb 18, 2020
  58. Derrick StoleeFeb 18, 2020
  59. 10/15 pack-bitmap: basic noop bitmap filter infrastructureJeff King, Feb 14, 2020
  60. 02/15 pack-bitmap: fix leak of haves/wants object listsJeff King, Feb 14, 2020
  61. Taylor BlauFeb 15, 2020
  62. Jeff KingFeb 15, 2020
  63. Derrick StoleeFeb 18, 2020
  64. Jeff KingFeb 18, 2020
  65. 11/15 rev-list: use bitmap filters for traversalJeff King, Feb 14, 2020
  66. 12/15 bitmap: add bitmap_unset() functionJeff King, Feb 14, 2020
  67. 15/15 pack-objects: support filters with bitmapsJeff King, Feb 14, 2020
  68. 14/15 pack-bitmap: implement BLOB_LIMIT filteringJeff King, Feb 14, 2020
  69. 13/15 pack-bitmap: implement BLOB_NONE filteringJeff King, Feb 14, 2020
  70. Derrick StoleeFeb 18, 2020
  71. Derrick StoleeFeb 18, 2020
  72. Jeff KingFeb 18, 2020
  73. Jeff KingFeb 18, 2020

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

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