From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: peff@peff.net, chriscool@tuxfamily.org
Subject: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering
Date: Mon, 4 May 2020 17:12:35 -0600 [thread overview]
Message-ID: <87b21d72bb588f7366d928544aeaf4de68b027a7.1588633810.git.me@ttaylorr.com> (raw)
In-Reply-To: <cover.1588633810.git.me@ttaylorr.com>
In the previous patch, we made it easy to define other filters that
exclude all objects of a certain type. Use that in order to implement
bitmap-level filtering for the '--filter=tree:<n>' filter when 'n' is
equal to 0.
The general case is not helped by bitmaps, since for values of 'n > 0',
the object filtering machinery requires a full-blown tree traversal in
order to determine the depth of a given tree. Caching this is
non-obvious, too, since the same tree object can have a different depth
depending on the context (e.g., a tree was moved up in the directory
hierarchy between two commits).
But, the 'n = 0' case can be helped, and this patch does so. Running
p5310.11 in this tree and on master with the kernel, we can see that
this case is helped substantially:
Test master this tree
--------------------------------------------------------------------------------
5310.11: rev-list count with tree:0 10.68(10.39+0.27) 0.06(0.04+0.01) -99.4%
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap.c | 25 ++++++++++++++++++++++++-
t/perf/p5310-pack-bitmaps.sh | 5 +++++
t/t6113-rev-list-bitmap-filters.sh | 21 +++++++++++++++++++++
3 files changed, 50 insertions(+), 1 deletion(-)
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 3693c9e62f..195ee8cad0 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
eword_t mask;
uint32_t i;
- if (type != OBJ_BLOB)
+ if (type != OBJ_BLOB && type != OBJ_TREE)
BUG("filter_bitmap_exclude_type: unsupported type '%d'", type);
/*
@@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
bitmap_free(tips);
}
+static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
+ struct object_list *tip_objects,
+ struct bitmap *to_filter,
+ unsigned long limit)
+{
+ if (limit)
+ BUG("filter_bitmap_tree_depth given non-zero limit");
+
+ filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
+ OBJ_TREE);
+ filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
+ OBJ_BLOB);
+}
+
static int filter_bitmap(struct bitmap_index *bitmap_git,
struct object_list *tip_objects,
struct bitmap *to_filter,
@@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,
return 0;
}
+ if (filter->choice == LOFC_TREE_DEPTH &&
+ filter->tree_exclude_depth == 0) {
+ if (bitmap_git)
+ filter_bitmap_tree_depth(bitmap_git, tip_objects,
+ to_filter,
+ filter->tree_exclude_depth);
+ return 0;
+ }
+
/* filter choice not handled */
return -1;
}
diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
index 80c53edca7..75ccf9f4e3 100755
--- a/t/perf/p5310-pack-bitmaps.sh
+++ b/t/perf/p5310-pack-bitmaps.sh
@@ -53,6 +53,11 @@ test_perf 'rev-list count with blob:limit=1k' '
--filter=blob:limit=1k >/dev/null
'
+test_perf 'rev-list count with tree:0' '
+ git rev-list --use-bitmap-index --count --objects --all \
+ --filter=tree:0 >/dev/null
+'
+
test_perf 'simulated partial clone' '
git pack-objects --stdout --all --filter=blob:none </dev/null >/dev/null
'
diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index 145603f124..2b551e6fd0 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh
@@ -53,4 +53,25 @@ test_expect_success 'blob:limit filter with specified blob' '
test_bitmap_traversal expect actual
'
+test_expect_success 'tree:0 filter' '
+ git rev-list --objects --filter=tree:0 HEAD >expect &&
+ git rev-list --use-bitmap-index \
+ --objects --filter=tree:0 HEAD >actual &&
+ test_bitmap_traversal expect actual
+'
+
+test_expect_success 'tree:0 filter with specified blob, tree' '
+ git rev-list --objects --filter=tree:0 HEAD HEAD:two.t >expect &&
+ git rev-list --use-bitmap-index \
+ --objects --filter=tree:0 HEAD HEAD:two.t >actual &&
+ test_bitmap_traversal expect actual
+'
+
+test_expect_success 'tree:1 filter' '
+ git rev-list --objects --filter=tree:1 HEAD >expect &&
+ git rev-list --use-bitmap-index \
+ --objects --filter=tree:1 HEAD >actual &&
+ test_cmp expect actual
+'
+
test_done
--
2.26.0.113.ge9739cdccc
next prev parent reply other threads:[~2020-05-04 23:12 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-04 23:12 [PATCH 0/4] pack-bitmap: use bitmaps for traversals with '--filter=tree:0' Taylor Blau
2020-05-04 23:12 ` [PATCH 1/4] list-objects-filter: treat NULL filter_options as "disabled" Taylor Blau
2020-05-05 5:07 ` Junio C Hamano
2020-05-04 23:12 ` [PATCH 2/4] pack-bitmap.c: make object filtering functions generic Taylor Blau
2020-05-05 5:12 ` Junio C Hamano
2020-05-04 23:12 ` Taylor Blau [this message]
2020-05-05 5:25 ` [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering Junio C Hamano
2020-05-05 15:59 ` Taylor Blau
2020-05-05 18:20 ` Junio C Hamano
2020-05-04 23:12 ` [PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal Taylor Blau
2020-05-05 5:40 ` Junio C Hamano
2020-05-05 16:00 ` Taylor Blau
-- strict thread matches above, loose matches on Subject: below --
2020-04-22 23:13 [PATCH 0/4] pack-bitmap: use bitmaps for traversals with '--filter=tree:0' Taylor Blau
2020-04-22 23:13 ` [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering Taylor Blau
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87b21d72bb588f7366d928544aeaf4de68b027a7.1588633810.git.me@ttaylorr.com \
--to=me@ttaylorr.com \
--cc=chriscool@tuxfamily.org \
--cc=git@vger.kernel.org \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.