Jonathan Tan [off-list ref] writes:
+static int write_oid(const struct object_id *oid, struct packed_git *pack,
+ uint32_t pos, void *data)
+{
+ int fd = *(int *)data;
+
+ xwrite(fd, oid_to_hex(oid), GIT_SHA1_HEXSZ);
+ xwrite(fd, "\n", 1);
+ return 0;
+}
+
+static void repack_promisor_objects(const struct packed_objects_args *args,
+ struct string_list *names)
+{
+ struct child_process cmd = CHILD_PROCESS_INIT;
+ FILE *out;
+ struct strbuf line = STRBUF_INIT;
+
+ prepare_packed_objects(&cmd, args);
+ cmd.in = -1;
+
+ if (start_command(&cmd))
+ die("Could not start pack-objects to repack promisor objects");
+
+ for_each_packed_object(write_oid, &cmd.in,
+ FOR_EACH_OBJECT_PROMISOR_ONLY);
+ close(cmd.in);
for_each_object_in_pack() is a fine way to make sure that you list
everythning in a pack, but I suspect it is a horrible way to feed a
list of objects to pack-objects, as it goes by the .idx order, which
is by definition a way to enumerate objects in a randomly useless
order.
Do we already have an access to the in-core reverse index for the
pack at this point in the code? If so, we can enumerate the objects
in the offset order without incurring a lot of cost (building the
in-core revindex is the more expensive part). When writing a pack,
we try to make sure that related objects are written out close to
each other [*1*], so listing them in the offset order (with made-up
pathname information to _force_ that objects that live close
together in the original pack are grouped together by getting
similar names) might give us a better than horrible deltification.
I dunno.
Side note *1*: "related" has two axis, and one is relevant
for better deltification, while the other is not useful.
The one I have in mind here is that we write set of blobs
that belong to the same "delta family" together.
I do not think such a "make it a bit better than horrible" is necessary
in an initial version, but it deserves an in-code NEEDSWORK comment
to remind us that we need to measure and experiment.
Thanks.
for_each_object_in_pack() is a fine way to make sure that you list
everythning in a pack, but I suspect it is a horrible way to feed a
list of objects to pack-objects, as it goes by the .idx order, which
is by definition a way to enumerate objects in a randomly useless
order.
That's true.
Do we already have an access to the in-core reverse index for the
pack at this point in the code?
As far as I can tell, no. These patches construct the list of promisor
objects in repack.c (which does not use the revindex at all), to be
processed by pack-objects in a different process (which does use the
revindex in reuse-delta mode, which is the default). I guess that we
could have access to the revindex if we were to libify pack-objects and
run it in the same process as repack.c or if we were to add a special
mode to pack-objects that reads for itself the list of all the promisor
objects.
If so, we can enumerate the objects
in the offset order without incurring a lot of cost (building the
in-core revindex is the more expensive part). When writing a pack,
we try to make sure that related objects are written out close to
each other [*1*], so listing them in the offset order (with made-up
pathname information to _force_ that objects that live close
together in the original pack are grouped together by getting
similar names) might give us a better than horrible deltification.
I dunno.
Before I write the NEEDSWORK comment, just to clarify - do you mean
better than horrible object locality? I think deltification still occurs
because pack-objects sorts the input when doing the windowed
deltification, for example:
git rev-parse HEAD:fetch-pack.c HEAD HEAD^ HEAD^^ \
HEAD^^^ v2.17.0:fetch-pack.c | git pack-objects --window=2 abc
produces a packfile with a delta, as checked by `verify-pack -v`.
Side note *1*: "related" has two axis, and one is relevant
for better deltification, while the other is not useful.
The one I have in mind here is that we write set of blobs
that belong to the same "delta family" together.
As far as I can see, they do not need to be adjacent in the packfile to
have one be a delta against the other.
I do not think such a "make it a bit better than horrible" is necessary
in an initial version, but it deserves an in-code NEEDSWORK comment
to remind us that we need to measure and experiment.
OK, I'll do this in the next reroll.
On Tue, Aug 07, 2018 at 04:23:04PM -0700, Jonathan Tan wrote:
quoted
Do we already have an access to the in-core reverse index for the
pack at this point in the code?
As far as I can tell, no. These patches construct the list of promisor
objects in repack.c (which does not use the revindex at all), to be
processed by pack-objects in a different process (which does use the
revindex in reuse-delta mode, which is the default). I guess that we
could have access to the revindex if we were to libify pack-objects and
run it in the same process as repack.c or if we were to add a special
mode to pack-objects that reads for itself the list of all the promisor
objects.
It's not the end of the world to access the revindex here. It requires
effort proportional to the size of the packfile, which makes it a bad
choice for operations that want to touch only a few objects. But here
you're iterating over the whole packfile anyway.
I think that the for_each_packed_object() interface should visit items
in pack order. Something like this (I'd probably change the name of the
inner "i" variable for clarity, but I didn't here to minimize the diff):
diff --git a/packfile.c b/packfile.c
index 04d387f312..334f47e4cd 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1887,10 +1887,13 @@ int has_pack_index(const unsigned char *sha1)
int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)
{
- uint32_t i;
+ uint32_t in_pack;
int r = 0;
- for (i = 0; i < p->num_objects; i++) {
+ load_pack_revindex(p);
+
+ for (in_pack = 0; in_pack < p->num_objects; in_pack++) {
+ uint32_t i = p->revindex[in_pack].nr;
struct object_id oid;
if (!nth_packed_object_oid(&oid, p, i))
Possibly it should be an optional flag, in case the caller is going to
eventually sort by sha1 anyway. But the major caller that sorts by sha1
is cat-file's --batch-all-objects option. And IMHO that is actually a
bad default. Try timing this in a fully-packed repository:
time git cat-file --batch-all-objects --buffer --batch | wc -c
versus this:
time git show-index <.git/objects/pack/*.idx |
sort -n |
awk '{print $2}' |
git cat-file --buffer --batch | wc -c
On my git.git repo, it's literally 7x faster to do the latter, because
of locality in resolving deltas.
So I think we should consider at least making it an option for cat-file
to do the iteration in pack-ish order (it can't be perfect, of course,
because there may be multiple packs, loose objects, etc, but
approximating it is a good idea).
I guess it has to be an option, since we advertise in the manpage that
the output is sorted by hash.
quoted
If so, we can enumerate the objects
in the offset order without incurring a lot of cost (building the
in-core revindex is the more expensive part). When writing a pack,
we try to make sure that related objects are written out close to
each other [*1*], so listing them in the offset order (with made-up
pathname information to _force_ that objects that live close
together in the original pack are grouped together by getting
similar names) might give us a better than horrible deltification.
I dunno.
Before I write the NEEDSWORK comment, just to clarify - do you mean
better than horrible object locality? I think deltification still occurs
because pack-objects sorts the input when doing the windowed
deltification, for example:
git rev-parse HEAD:fetch-pack.c HEAD HEAD^ HEAD^^ \
HEAD^^^ v2.17.0:fetch-pack.c | git pack-objects --window=2 abc
produces a packfile with a delta, as checked by `verify-pack -v`.
You're going to get a lot of reused deltas from the old pack, but you'll
probably miss opportunities to delta objects between packs. And
pack-object's compute_write_order() will fix some of the issues:
- it will group objects of each type together
- it will group delta "families" together
So the resulting packfile may not actually be _too_ bad with respect to
delta locality. Where it will fail is:
- there's no locality with respect to history, so a traversal will have
bad I/O patterns as it skips all over the packfile
- the delta heuristics do use the incoming order (which usually is from
a traversal) as a hint. But IMHO that is way less important than
lacking the names. Even if you have an actual traversal, two versions
of the same file may be separated by hundreds of other blob changes
in the middle. Traversal order doesn't help you; putting things with
similar names next to each other does.
For traversals using bitmaps, we have a "name hash cache" in the
.bitmap file, which stores the 32-bit hash of the name. That lets us
put similar names next to each other without actually knowing the
names. If we absolutely can't traverse as part of the strategy for
repacking a promisor pack, then it may be worth trying to figure out
how to carry that hash around.
-Peff