[v2,13/15] pack-bitmap: implement BLOB_NONE filtering
diff mbox series

Message ID 20200214182236.GM150965@coredump.intra.peff.net
State New
Headers show
Series
  • combining object filters and bitmaps
Related show

Commit Message

Jeff King Feb. 14, 2020, 6:22 p.m. UTC
We can easily support BLOB_NONE filters with bitmaps. Since we know the
types of all of the objects, we just need to clear the result bits of
any blobs.

Note two subtleties in the implementation (which I also called out in
comments):

  - we have to include any blobs that were specifically asked for (and
    not reached through graph traversal) to match the non-bitmap version

  - we have to handle in-pack and "ext_index" objects separately.
    Arguably prepare_bitmap_walk() could be adding these ext_index
    objects to the type bitmaps. But it doesn't for now, so let's match
    the rest of the bitmap code here (it probably wouldn't be an
    efficiency improvement to do so since the cost of extending those
    bitmaps is about the same as our loop here, but it might make the
    code a bit simpler).

Here are perf results for the new test on git.git:

  Test                                    HEAD^             HEAD
  --------------------------------------------------------------------------------
  5310.9: rev-list count with blob:none   1.67(1.62+0.05)   0.22(0.21+0.02) -86.8%

Signed-off-by: Jeff King <peff@peff.net>
---
 pack-bitmap.c                      | 74 ++++++++++++++++++++++++++++++
 t/perf/p5310-pack-bitmaps.sh       |  5 ++
 t/t6113-rev-list-bitmap-filters.sh | 14 ++++++
 3 files changed, 93 insertions(+)

Comments

Derrick Stolee Feb. 18, 2020, 7:26 p.m. UTC | #1
On 2/14/2020 1:22 PM, Jeff King wrote:
> We can easily support BLOB_NONE filters with bitmaps. Since we know the
> types of all of the objects, we just need to clear the result bits of
> any blobs.
> 
> Note two subtleties in the implementation (which I also called out in
> comments):
> 
>   - we have to include any blobs that were specifically asked for (and
>     not reached through graph traversal) to match the non-bitmap version

I have a concern here, but maybe I'm worrying about nothing. When a
partial clone asks for a pack of missing blobs, will your code create
an empty bitmap and then add bits to that bitmap one-by-one instead
of appending to a simple object list?

In the typical case where we ask for specific commits and trees, we
expect a very small number of blobs to add to the resulting bitmap.
When no commits or trees are included in the wants, then we don't
need the bitmap at all. IIRC an EWAH bitmap is relatively expensive
to update bits one at a time, so this is not incredibly efficient.

I apologize that I don't have the time to dig into this myself.

>   - we have to handle in-pack and "ext_index" objects separately.
>     Arguably prepare_bitmap_walk() could be adding these ext_index
>     objects to the type bitmaps. But it doesn't for now, so let's match
>     the rest of the bitmap code here (it probably wouldn't be an
>     efficiency improvement to do so since the cost of extending those
>     bitmaps is about the same as our loop here, but it might make the
>     code a bit simpler).
> 
> Here are perf results for the new test on git.git:
> 
>   Test                                    HEAD^             HEAD
>   --------------------------------------------------------------------------------
>   5310.9: rev-list count with blob:none   1.67(1.62+0.05)   0.22(0.21+0.02) -86.8%
...
> diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
> index e52f66ec9e..936742314c 100755
> --- a/t/perf/p5310-pack-bitmaps.sh
> +++ b/t/perf/p5310-pack-bitmaps.sh
> @@ -47,6 +47,11 @@ test_perf 'rev-list (objects)' '
>  	git rev-list --all --use-bitmap-index --objects >/dev/null
>  '
>  
> +test_perf 'rev-list count with blob:none' '
> +	git rev-list --use-bitmap-index --count --objects --all \
> +		--filter=blob:none >/dev/null
> +'

I wondered why you chose to extend these tests instead of using
p5600-partial-clone.sh, but I guess this script definitely creates
the bitmap for the test. When I tested p5600-partial-clone.sh below,
I manually repacked the Linux repo to have a bitmap:

Test                          v2.25.0               HEAD                    
----------------------------------------------------------------------------
5600.2: clone without blobs   79.81(111.34+11.35)   36.00(69.37+7.30) -54.9%
5600.3: checkout of result    45.56(114.59+4.81)    46.43(80.50+5.41) +1.9% 

Perhaps results for these tests would also be appropriate for your
commit messages?

Note the +1.9% for the checkout. It's unlikely that this is actually
something meaningful, but it _could_ be related to my concerns above
about building a blob list from an empty bitmap.

Thanks,
-Stolee
Derrick Stolee Feb. 18, 2020, 7:36 p.m. UTC | #2
On 2/18/2020 2:26 PM, Derrick Stolee wrote:
> On 2/14/2020 1:22 PM, Jeff King wrote:
>> +test_perf 'rev-list count with blob:none' '
>> +	git rev-list --use-bitmap-index --count --objects --all \
>> +		--filter=blob:none >/dev/null
>> +'
> 
> I wondered why you chose to extend these tests instead of using
> p5600-partial-clone.sh, but I guess this script definitely creates
> the bitmap for the test. When I tested p5600-partial-clone.sh below,
> I manually repacked the Linux repo to have a bitmap:
> 
> Test                          v2.25.0               HEAD                    
> ----------------------------------------------------------------------------
> 5600.2: clone without blobs   79.81(111.34+11.35)   36.00(69.37+7.30) -54.9%
> 5600.3: checkout of result    45.56(114.59+4.81)    46.43(80.50+5.41) +1.9% 
> 
> Perhaps results for these tests would also be appropriate for your
> commit messages?

And speaking of valuable performance tests to update: should we take
the loop of fetch tests in p5311-pack-bitmaps-fetch.sh and make
equivalent versions in p5600-partial-clone.sh? It would be good to
make sure that the incremental fetches also improve in this scenario.

Thanks,
-Stolee
Jeff King Feb. 18, 2020, 8:24 p.m. UTC | #3
On Tue, Feb 18, 2020 at 02:26:53PM -0500, Derrick Stolee wrote:

> On 2/14/2020 1:22 PM, Jeff King wrote:
> > We can easily support BLOB_NONE filters with bitmaps. Since we know the
> > types of all of the objects, we just need to clear the result bits of
> > any blobs.
> > 
> > Note two subtleties in the implementation (which I also called out in
> > comments):
> > 
> >   - we have to include any blobs that were specifically asked for (and
> >     not reached through graph traversal) to match the non-bitmap version
> 
> I have a concern here, but maybe I'm worrying about nothing. When a
> partial clone asks for a pack of missing blobs, will your code create
> an empty bitmap and then add bits to that bitmap one-by-one instead
> of appending to a simple object list?

Yes. They'd all be listed in revs->pending, so we'd add them to our
array of "wants", and then create a bitmap. There's no traversal cost,
but we'd pay the cost to open the bitmap file. But...

> In the typical case where we ask for specific commits and trees, we
> expect a very small number of blobs to add to the resulting bitmap.
> When no commits or trees are included in the wants, then we don't
> need the bitmap at all. IIRC an EWAH bitmap is relatively expensive
> to update bits one at a time, so this is not incredibly efficient.

There's no ewah bitmap at play here at all. The internal bitmap we
create in memory for the walk is a real uncompressed bitmap, so settings
and retrieving bits is pretty cheap.

I'd worry much more about the fact that we had to parse the whole bitmap
file (which for historical format reasons involves actually running over
all of the bytes in the file).

I think that's somewhat orthogonal to this patch, though. The same
pessimality would be true of anybody fetching a couple blobs, whether
they use filters or not (and really, there's no reason that the
follow-up fetch for blobs in a filtered repository would need to use
filters, but for some reason it does).

It would be an easy optimization to say "we have only blobs, don't
bother opening the bitmap file", but I think that should come on top.
However, I have a suspicion that we actually call parse_object() on each
blob before we even get to the bitmap code (via get_reference()). If so,
that's a much larger low-hanging fruit.

> > --- a/t/perf/p5310-pack-bitmaps.sh
> [...]
> 
> I wondered why you chose to extend these tests instead of using
> p5600-partial-clone.sh, but I guess this script definitely creates
> the bitmap for the test. When I tested p5600-partial-clone.sh below,
> I manually repacked the Linux repo to have a bitmap:

Right, when the two features combine, we have to either pick a test
script that hits one or the other, or create a new one. Especially since
this one covers the full and partial bitmap states, I think it's nice to
reuse that work.

> Test                          v2.25.0               HEAD                    
> ----------------------------------------------------------------------------
> 5600.2: clone without blobs   79.81(111.34+11.35)   36.00(69.37+7.30) -54.9%
> 5600.3: checkout of result    45.56(114.59+4.81)    46.43(80.50+5.41) +1.9% 
> 
> Perhaps results for these tests would also be appropriate for your
> commit messages?

I think your p5600.2 is basically the same as what I ended up with
in p5310 for the final commit (when pack-objects finally learns to use
these filters, too). But we want to make sure we are testing with
bitmaps, so I don't think we'd want to count on the sample repo having
bitmaps already.

I think this speaks to the general problems with the perf suite, in that
we probably ought to be testing combinations of repos and tests, rather
than manually creating situations in each script).

> Note the +1.9% for the checkout. It's unlikely that this is actually
> something meaningful, but it _could_ be related to my concerns above
> about building a blob list from an empty bitmap.

In my experience with the perf suite, 2% is most likely noise
(especially for a filesystem-heavy operation like checkout). Note that
the difference in system time covers almost all of the wall-clock time.

It is curious that the user time in your second test dropped so
drastically, but didn't create a wall-clock improvement. I've often seen
weirdness there with the CPU clock changing due to external factors.

-Peff
Jeff King Feb. 18, 2020, 8:30 p.m. UTC | #4
On Tue, Feb 18, 2020 at 02:36:55PM -0500, Derrick Stolee wrote:

> > I wondered why you chose to extend these tests instead of using
> > p5600-partial-clone.sh, but I guess this script definitely creates
> > the bitmap for the test. When I tested p5600-partial-clone.sh below,
> > I manually repacked the Linux repo to have a bitmap:
> > 
> > Test                          v2.25.0               HEAD                    
> > ----------------------------------------------------------------------------
> > 5600.2: clone without blobs   79.81(111.34+11.35)   36.00(69.37+7.30) -54.9%
> > 5600.3: checkout of result    45.56(114.59+4.81)    46.43(80.50+5.41) +1.9% 
> > 
> > Perhaps results for these tests would also be appropriate for your
> > commit messages?
> 
> And speaking of valuable performance tests to update: should we take
> the loop of fetch tests in p5311-pack-bitmaps-fetch.sh and make
> equivalent versions in p5600-partial-clone.sh? It would be good to
> make sure that the incremental fetches also improve in this scenario.

I don't think it would make sense to add them permanently, since p5600
doesn't necessarily have bitmaps in effect.

But in any case, those tests are mostly about pack-objects realizing
when we can use on-disk deltas due to the presence of bitmaps. If we're
avoiding sending blobs, then that cuts out a huge chunk of opportunity
for it to make any improvement (it might still have some impact because
of trees, though). So I'd expect the effect to be muted.

I dunno. It's true that I just hypothesized a result which we could
confirm. But the perf tests are quite expensive to run (and p5311 is one
of the more expensive ones). I'm not sure that repeating those tests
combined with partial clones carries a lot of regression-testing value
to merit adding that expense to all future runs.

-Peff

Patch
diff mbox series

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 48c8694f92..dcf8a9aadf 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -712,6 +712,73 @@  static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
 	return 0;
 }
 
+static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,
+				     struct object_list *tip_objects)
+{
+	struct bitmap *result = bitmap_new();
+	struct object_list *p;
+
+	for (p = tip_objects; p; p = p->next) {
+		int pos;
+
+		if (p->item->type != OBJ_BLOB)
+			continue;
+
+		pos = bitmap_position(bitmap_git, &p->item->oid);
+		if (pos < 0)
+			continue;
+
+		bitmap_set(result, pos);
+	}
+
+	return result;
+}
+
+static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
+				    struct object_list *tip_objects,
+				    struct bitmap *to_filter)
+{
+	struct eindex *eindex = &bitmap_git->ext_index;
+	struct bitmap *tips;
+	struct ewah_iterator it;
+	eword_t mask;
+	uint32_t i;
+
+	/*
+	 * The non-bitmap version of this filter never removes
+	 * blobs which the other side specifically asked for,
+	 * so we must match that behavior.
+	 */
+	tips = find_tip_blobs(bitmap_git, tip_objects);
+
+	/*
+	 * We can use the blob type-bitmap to work in whole words
+	 * for the objects that are actually in the bitmapped packfile.
+	 */
+	for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
+	     i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
+	     i++) {
+		if (i < tips->word_alloc)
+			mask &= ~tips->words[i];
+		to_filter->words[i] &= ~mask;
+	}
+
+	/*
+	 * Clear any blobs that weren't in the packfile (and so would not have
+	 * been caught by the loop above. We'll have to check them
+	 * individually.
+	 */
+	for (i = 0; i < eindex->count; i++) {
+		uint32_t pos = i + bitmap_git->pack->num_objects;
+		if (eindex->objects[i]->type == OBJ_BLOB &&
+		    bitmap_get(to_filter, pos) &&
+		    !bitmap_get(tips, pos))
+			bitmap_unset(to_filter, pos);
+	}
+
+	bitmap_free(tips);
+}
+
 static int filter_bitmap(struct bitmap_index *bitmap_git,
 			 struct object_list *tip_objects,
 			 struct bitmap *to_filter,
@@ -720,6 +787,13 @@  static int filter_bitmap(struct bitmap_index *bitmap_git,
 	if (!filter || filter->choice == LOFC_DISABLED)
 		return 0;
 
+	if (filter->choice == LOFC_BLOB_NONE) {
+		if (bitmap_git)
+			filter_bitmap_blob_none(bitmap_git, tip_objects,
+						to_filter);
+		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 e52f66ec9e..936742314c 100755
--- a/t/perf/p5310-pack-bitmaps.sh
+++ b/t/perf/p5310-pack-bitmaps.sh
@@ -47,6 +47,11 @@  test_perf 'rev-list (objects)' '
 	git rev-list --all --use-bitmap-index --objects >/dev/null
 '
 
+test_perf 'rev-list count with blob:none' '
+	git rev-list --use-bitmap-index --count --objects --all \
+		--filter=blob:none >/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/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index 977f8d0930..f4e6d582f0 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh
@@ -21,4 +21,18 @@  test_expect_success 'filters fallback to non-bitmap traversal' '
 	test_cmp expect actual
 '
 
+test_expect_success 'blob:none filter' '
+	git rev-list --objects --filter=blob:none HEAD >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=blob:none HEAD >actual &&
+	test_bitmap_traversal expect actual
+'
+
+test_expect_success 'blob:none filter with specified blob' '
+	git rev-list --objects --filter=blob:none HEAD HEAD:two.t >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=blob:none HEAD HEAD:two.t >actual &&
+	test_bitmap_traversal expect actual
+'
+
 test_done