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

[PATCH] pack-bitmap: look for an uninteresting bitmap

From
Derrick Stolee <stolee@gmail.com>
Date
May 24, 2019, 11:31 UTC
Message-ID
<20190524113112.30185-1-dstolee@microsoft.com>
In-Reply-To
<20190523113031.GA17448@sigill.intra.peff.net>
If we try to do a range query such as C..D with topology as
 A_0 - ... - A_10000 - B - C_1 - ... - C_1000 - C
                         \
                           D_1 - ... - D_1000 - D

and none of the commits in {A_i, B, C_j, C} have a computed bitmap, then we will very likely walk many many trees before computing one for the "have" bitmap.

Instead, perform a commit walk to the boundary of C...D and look for computed bitmaps in { B, C_j, C }. If any are found, then it is worth starting from there and building a bitmap. If not, revert to the old method of walking trees.

NOTE: this is only a proof-of-concept, as it fails a test in
t5310-pack-bitmaps.sh (clearly marked as a failure now).
Reported-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
On 5/23/2019 7:30 AM, Jeff King wrote:> +	/*
Show 6 quoted lines
> +	 * First traverse the relevant commits as we would for a normal
> +	 * traversal.
> +	 */
> +	while (commits.nr) {
> +		struct commit *commit = prio_queue_get(&commits);
> +		struct bitmap **dst_bitmap;
I was looking at this code again, and noticed this while() condition.
Shouldn't this use queue_has_nonstale() like in paint_down_to_common()?

Looking at the body of the loop, I don't see a way for the loop to stop without it walking the entire history of C _and_ D.

Based on that, I wrote the patch below as an experiment. The has_uninteresting_bitmap_in_frontier() shamelessly steals code from paint_down_to_common(). Note the failing test, but perhaps there is something salvageable from this.

Thanks, -Stolee

 pack-bitmap.c           | 92 ++++++++++++++++++++++++++++++++++++++++-
 t/t5310-pack-bitmaps.sh |  2 +-
 2 files changed, 91 insertions(+), 3 deletions(-)
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 6069b2fe55..1f4683663e 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -12,6 +12,7 @@
 #include "packfile.h"
 #include "repository.h"
 #include "object-store.h"
+#include "prio-queue.h"
 
 /*
  * An entry on the bitmap index, representing the bitmap for a given
@@ -679,6 +680,81 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
 	return 0;
 }
 
+#define PARENT1         (1u<<16)
+#define PARENT2         (1u<<17)
+#define STALE           (1u<<18)
+
+static const int all_flags = { PARENT1 | PARENT2 | STALE };
+
+static int queue_has_nonstale(struct prio_queue *queue)
+{
+	int i;
+	for (i = 0; i < queue->nr; i++) {
+		struct commit *commit = queue->array[i].data;
+		if (!(commit->object.flags & STALE))
+			return 1;
+	}
+	return 0;
+}
+
+static int has_uninteresting_bitmap_in_frontier(struct repository *r,
+						struct commit_list *list,
+						struct bitmap_index *bitmap_git)
+{
+	int res = 0;
+	struct commit_list *iter = list;
+	struct prio_queue queue = { compare_commits_by_commit_date };
+
+	while (iter) {
+		prio_queue_put(&queue, iter->item);
+		iter = iter->next;
+	}
+
+	while (queue_has_nonstale(&queue)) {
+		struct commit *commit = prio_queue_get(&queue);
+		struct commit_list *parents;
+		int flags;
+
+		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
+		if (flags == (PARENT1 | PARENT2)) {
+			/* Mark parents of a found merge stale */
+			flags |= STALE;
+		}
+
+		if (flags & PARENT1) {
+			khiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, commit->object.oid);
+
+			if (pos < kh_end(bitmap_git->bitmaps)) {
+				res = 1;
+				goto cleanup;
+			}
+		}
+
+		parents = commit->parents;
+		while (parents) {
+			struct commit *p = parents->item;
+			parents = parents->next;
+			if ((p->object.flags & flags) == flags)
+				continue;
+			if (repo_parse_commit(r, p))
+				goto cleanup;
+			p->object.flags |= flags;
+			prio_queue_put(&queue, p);
+		}
+	}
+
+cleanup:
+	clear_prio_queue(&queue);
+
+	iter = list;
+	while (iter) {
+		clear_commit_marks(iter->item, all_flags);
+		iter = iter->next;
+	}
+
+	return res;
+}
+
 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)
 {
 	unsigned int i;
@@ -689,6 +765,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)
 	struct bitmap *wants_bitmap = NULL;
 	struct bitmap *haves_bitmap = NULL;
 
+	struct commit_list *commits = NULL;
+
 	struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
 	/* try to open a bitmapped pack, but don't parse it yet
 	 * because we may not need to use it */
@@ -704,16 +782,22 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)
 		while (object->type == OBJ_TAG) {
 			struct tag *tag = (struct tag *) object;
 
-			if (object->flags & UNINTERESTING)
+			if (object->flags & UNINTERESTING) {
+				object->flags |= PARENT1;
 				object_list_insert(object, &haves);
-			else
+			} else {
+				object->flags |= PARENT2;
 				object_list_insert(object, &wants);
+			}
 
 			if (!tag->tagged)
 				die("bad tag");
 			object = parse_object_or_die(&tag->tagged->oid, NULL);
 		}
 
+		if (object->type == OBJ_COMMIT)
+			commit_list_insert((struct commit *)object, &commits);
+
 		if (object->flags & UNINTERESTING)
 			object_list_insert(object, &haves);
 		else
@@ -740,6 +824,10 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)
 	if (load_pack_bitmap(bitmap_git) < 0)
 		goto cleanup;
 
+	if (!has_uninteresting_bitmap_in_frontier(the_repository, commits, bitmap_git))
+		goto cleanup;
+
+	/* this is the real no-turning-back point! */
 	object_array_clear(&revs->pending);
 
 	if (haves) {
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index a26c8ba9a2..615608fbbf 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -422,7 +422,7 @@ test_expect_success 'fetch without bitmaps ignores delta against old base' '
 '
 
 # And do the same for the bitmap case, where we do expect to find the delta.
-test_expect_success 'fetch with bitmaps can reuse old base' '
+test_expect_failure 'fetch with bitmaps can reuse old base' '
 	test_config pack.usebitmaps true &&
 	test_when_finished "rm -rf client.git" &&
 	git init --bare client.git &&

-- 
2.22.0.rc0
Previous: Ævar Arnfjörð BjarmasonNext: Derrick Stolee
Message 50 of 57 in “some prune optimizations”
  1. 0/3 some prune optimizationsJeff King, Feb 14, 2019
  2. 1/3 prune: lazily perform reachability traversalJeff King, Feb 14, 2019
  3. Eric SunshineFeb 14, 2019
  4. Jeff KingFeb 14, 2019
  5. 2/3 prune: use bitmaps for reachability traversalJeff King, Feb 14, 2019
  6. bitmaps by default? [was: prune: use bitmaps for reachability traversal]Eric Wong, Mar 9, 2019
  7. Jeff KingMar 10, 2019
  8. repack: enable bitmaps by default on bare reposEric Wong, Mar 12, 2019
  9. Ævar Arnfjörð BjarmasonMar 12, 2019
  10. Jeff KingMar 12, 2019
  11. Jeff KingMar 12, 2019
  12. Eric WongMar 13, 2019
  13. Jeff KingMar 13, 2019
  14. repack: enable bitmaps by default on bare reposEric Wong, Mar 14, 2019
  15. Jeff KingMar 14, 2019
  16. 0/2 enable bitmap hash-cache by defaultJeff King, Mar 15, 2019
  17. 1/2 t5310: correctly remove bitmaps for jgit testJeff King, Mar 15, 2019
  18. SZEDER GáborMar 15, 2019
  19. Jeff KingMar 15, 2019
  20. 2/2 pack-objects: default to writing bitmap hash-cacheJeff King, Mar 15, 2019
  21. Ævar Arnfjörð BjarmasonApr 9, 2019
  22. Jeff KingApr 10, 2019
  23. Junio C HamanoApr 25, 2019
  24. Jeff KingMay 4, 2019
  25. Ævar Arnfjörð BjarmasonMay 4, 2019
  26. SZEDER GáborMay 4, 2019
  27. Ævar Arnfjörð BjarmasonMay 8, 2019
  28. Junio C HamanoMay 9, 2019
  29. Jeff KingMay 7, 2019
  30. Ævar Arnfjörð BjarmasonMay 7, 2019
  31. Jeff KingMay 8, 2019
  32. Derrick StoleeMay 8, 2019
  33. Ævar Arnfjörð BjarmasonMay 8, 2019
  34. Jeff KingMay 8, 2019
  35. Jeff KingMay 23, 2019
  36. Derrick StoleeMay 23, 2019
  37. Jeff KingMay 24, 2019
  38. Derrick StoleeMay 24, 2019
  39. Ævar Arnfjörð BjarmasonMay 23, 2019
  40. Jeff KingMay 24, 2019
  41. Ævar Arnfjörð BjarmasonMay 24, 2019
  42. Jeff KingMay 24, 2019
  43. Ævar Arnfjörð BjarmasonMay 24, 2019
  44. SZEDER GáborMay 24, 2019
  45. Ævar Arnfjörð BjarmasonMay 24, 2019
  46. SZEDER GáborMay 24, 2019
  47. Ævar Arnfjörð BjarmasonMay 24, 2019
  48. SZEDER GáborMay 24, 2019
  49. Ævar Arnfjörð BjarmasonMay 24, 2019
  50. pack-bitmap: look for an uninteresting bitmapDerrick Stolee, May 24, 2019
  51. Derrick StoleeApr 15, 2019
  52. Jeff KingApr 18, 2019
  53. t5304: add a test for pruning with bitmapsJeff King, Apr 18, 2019
  54. Derrick StoleeApr 20, 2019
  55. Jeff KingApr 20, 2019
  56. Derrick StoleeApr 20, 2019
  57. 3/3 prune: check SEEN flag for reachabilityJeff King, Feb 14, 2019

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.