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
List information: http://vger.kernel.org/majordomo-info.html
* 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.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).