On Wed, Mar 10, 2021 at 04:39:22PM -0500, Jeff King wrote:
On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:
quoted
Altogether, this ends up with the following queries, both of which have
been executed in a well-packed linux.git repository:
# Previous query which uses object names as a heuristic to filter
# non-blob objects, which bars us from using bitmap indices because
# they cannot print paths.
$ time git rev-list --objects --filter=blob:limit=200 \
--object-names --all | sed -r '/^.{,41}$/d' | wc -l
4502300
real 1m23.872s
user 1m30.076s
sys 0m6.002s
# New query.
$ time git rev-list --objects --filter-provided \
--filter=object:type=blob --filter=blob:limit=200 \
--use-bitmap-index --all | wc -l
22585
real 0m19.216s
user 0m16.768s
sys 0m2.450s
Those produce very different answers. I guess because in the first one,
you still have a bunch of tree objects, too. You'd do much better to get
the actual types from cat-file, and filter on that. That also lets you
use bitmaps for the traversal portion. E.g.:
They do provide different answers, and you're right that `--batch-check`
would have helped to filter by type. Your idea doesn't really work in my
usecase though to identify LFS pointers, at least not without additional
tooling on top of what you've provided. There'd at least need to be two
git-cat-file(1) processes: one to do the `--batch-check` thing to
actually filter by object type, and one to then read the actual LFS
pointer candidates from disk in order to see whether they are LFS
pointers or not.
Actually, we currently are doing something similar to that at GitLab: we
list all potential candidates via git-rev-list(1), write the output into
`git-cat-file --batch-check`, and anything that is a blob then gets
forwarded into `git-cat-file --batch`.
$ time git rev-list --use-bitmap-index --objects --filter=blob:limit=200 --all |
git cat-file --buffer --batch-check='%(objecttype) %(objectname)' |
perl -lne 'print $1 if /^blob (.*)/' | wc -l
14966
real 0m6.248s
user 0m7.810s
sys 0m0.440s
which is faster than what you showed above (this is on linux.git, but my
result is different; maybe you have more refs than me?). But we should
be able to do better purely internally, so I suspect my computer is just
faster (or maybe your extra refs just aren't well-covered by bitmaps).
Running with your patches I get:
I've got quite a beefy machine with a Ryzen 3 5800X, and I did do a `git
repack -Adfb` right before doig benchmarks. I do have the stable kernel
repository added though, which accounts for quite a lot of additional
references (3938) and objects (9.3M).
$ time git rev-list --objects --use-bitmap-index --all \
--filter-provided --filter=object:type=blob \
--filter=blob:limit=200 | wc -l
16339
real 0m1.309s
user 0m1.234s
sys 0m0.079s
which is indeed faster. It's quite curious that the answer is not the
same, though! I think yours has some bugs. If I sort and diff the
results, I see some commits mentioned in the output. Perhaps this is
--filter-provided not working, as they all seem to be ref tips.
I noticed it, too, and couldn't yet find an answer why that is.
Honestly, I found the NOT_USER_GIVEN flag quite confusing and I'm not at
all sure whether I've got all cases covered correctly. The previous was
how this was handled (`USER_GIVEN` instead of `NOT_USER_GIVEN`) would've
been easier to figure out for this specific usecase. But I guess it was
converted due to specific reasons.
I'll invest some more time to figure out what's happening here.
quoted
To be able to more efficiently answer this query, I've implemented
multiple things:
- A new object type filter `--filter=object:type=<type>` for
git-rev-list(1), which is implemented both for normal graph walks and
for the packfile bitmap index.
- Given that above usecase requires two filters (the object type
and blob size filters), bitmap filters were extended to support
combined filters.
That's probably reasonable, especially because it lets us use bitmaps. I
do have a dream that we'll eventually be able to support more extensive
formatting via log/rev-list, which would allow:
git rev-list --use-bitmap-index --objects --all \
--format=%(objecttype) %(objectname) |
perl -ne 'print $1 if /^blob (.*)/'
That should be faster than the separate cat-file (which has to re-lookup
each object, in addition to the extra pipe overhead), but I expect the
--filter solution should always be faster still, as it can very quickly
eliminate the majority of the objects at the bitmap level.
That'd be nice, even though it wouldn't help in my particular usecase: I
need to read each candidate blob to see whether it's an LFS pointer or
not anyway.
quoted
- git-rev-list(1) doesn't filter user-provided objects and always prints
them. I don't want the listed commits though and only their referenced
potential LFS blobs. So I've added a new flag `--filter-provided`
which marks all provided objects as not-user-provided such that they
get filtered the same as all the other objects.
Yeah, this "user-provided" behavior was quite a surprise to me when I
started implementing the bitmap versions of the existing filters. It's
nice to have the option to specify which you want.
-Peff
Patrick