Re: [PATCH v4 1/7] Add delta-islands.{c,h}
- From
Christian Couder <christian.couder@gmail.com>
- Date
- Aug 13, 2018, 03:33 UTC
- Message-ID
- <CAP8UFD1tX+rAxQc47o-50Kzo6hnX9mTWH2BPSq9HiO_OgBzYTw@mail.gmail.com>
- In-Reply-To
- <2113c74c-b230-6ea1-a980-d6d008bac759@ramsayjones.plus.com>
On Mon, Aug 13, 2018 at 3:14 AM, Ramsay Jones <ramsay@ramsayjones.plus.com> wrote:
> On 12/08/18 06:11, Christian Couder wrote:
>> Because the inefficiency primarily arises when an >> object is delitified against another object that does > > s/delitified/deltified/ ?
Ok, this will be in the next reroll if any.
Show 5 quoted lines
>> not exist in the same fork, we partition objects into >> sets that appear in the same fork, and define >> "delta islands". When finding delta base, we do not >> allow an object outside the same island to be >> considered as its base.
Show 51 quoted lines
>> --- /dev/null >> +++ b/delta-islands.c >> @@ -0,0 +1,493 @@ >> +#include "cache.h" >> +#include "attr.h" >> +#include "object.h" >> +#include "blob.h" >> +#include "commit.h" >> +#include "tag.h" >> +#include "tree.h" >> +#include "delta.h" >> +#include "pack.h" >> +#include "tree-walk.h" >> +#include "diff.h" >> +#include "revision.h" >> +#include "list-objects.h" >> +#include "progress.h" >> +#include "refs.h" >> +#include "khash.h" > > I was wondering how many copies of the inline functions > introduced by this header we had, so: > > $ nm git | grep ' t ' | cut -d' ' -f3 | sort | uniq -c | sort -rn | grep kh_ > 3 kh_resize_sha1 > 3 kh_put_sha1 > 3 kh_init_sha1 > 3 kh_get_sha1 > 1 kh_resize_str > 1 kh_resize_sha1_pos > 1 kh_put_str > 1 kh_put_sha1_pos > 1 kh_init_str > 1 kh_init_sha1_pos > 1 kh_get_str > 1 kh_get_sha1_pos > 1 kh_destroy_sha1 > $ > > Looking at the individual object files, we see: > > $ nm pack-bitmap-write.o | grep ' t ' | grep kh_ > 00000000000001cc t kh_get_sha1 > 00000000000001b7 t kh_init_sha1 > 000000000000085e t kh_put_sha1 > 0000000000000310 t kh_resize_sha1 > $ > > So, the two instances of the sha1 hash-map are never > destroyed (kh_destroy_sha1 is not present in the object > file).
This is interesting (even though it seems related to more code than the current patch series).
As those hash maps are in 'struct bitmap_writer' and a static instance is used:
static struct bitmap_writer writer;
it maybe ok.
Show 13 quoted lines
> $ nm pack-bitmap.o | grep ' t ' | grep kh_ > 00000000000002d9 t kh_destroy_sha1 > 000000000000032b t kh_get_sha1 > 0000000000000daa t kh_get_sha1_pos > 00000000000002c4 t kh_init_sha1 > 0000000000000d95 t kh_init_sha1_pos > 00000000000009bd t kh_put_sha1 > 0000000000001432 t kh_put_sha1_pos > 000000000000046f t kh_resize_sha1 > 0000000000000eee t kh_resize_sha1_pos > $ > > The sha1_pos hash-map is not destroyed here.
Yeah, maybe a line like:
kh_destroy_pos(b->ext_index.positions);
is missing from free_bitmap_index()?
Adding that should be in a separate patch from this series though.
Show 13 quoted lines
> $ nm delta-islands.o | grep ' t ' | grep kh_ > 00000000000002be t kh_get_sha1 > 0000000000000e52 t kh_get_str > 00000000000002a9 t kh_init_sha1 > 0000000000000e3d t kh_init_str > 0000000000000950 t kh_put_sha1 > 00000000000014e4 t kh_put_str > 0000000000000402 t kh_resize_sha1 > 0000000000000f96 t kh_resize_str > $ > > And neither the sha1 or str hash-maps are destroyed here. > (That is not necessarily a problem, of course! ;-) )
The instances are declared as static:
static khash_sha1 *island_marks;
static kh_str_t *remote_islands;
so it maybe ok.
Show 7 quoted lines
>> +struct island_bitmap {
>> + uint32_t refcount;
>> + uint32_t bits[];
>
> Use FLEX_ARRAY here? We are slowly moving toward requiring
> certain C99 features, but I can't remember a flex array
> weather-balloon patch.This was already discussed by Junio and Peff there:
https://public-inbox.org/git/20180727130229.GB18599@sigill.intra.peff.net/
>> +};
Show 15 quoted lines
>> +int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)
>
> Hmm, what does the trg_ prefix stand for?
>
>> +{
>> + khiter_t trg_pos, src_pos;
>> +
>> + /* If we aren't using islands, assume everything goes together. */
>> + if (!island_marks)
>> + return 1;
>> +
>> + /*
>> + * If we don't have a bitmap for the target, we can delta it
>
> ... Ah, OK, trg_ => target.I am ok to replace "trg" with "target" (or maybe "dst"? or something else) and "src" with "source" if you think it would make things clearer.
Show 23 quoted lines
>> +static void add_ref_to_island(const char *island_name, const struct object_id *oid)
>> +{
>> + uint64_t sha_core;
>> + struct remote_island *rl = NULL;
>> +
>> + int hash_ret;
>> + khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);
>> +
>> + if (hash_ret) {
>> + kh_key(remote_islands, pos) = xstrdup(island_name);
>> + kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));
>> + }
>> +
>> + rl = kh_value(remote_islands, pos);
>> + oid_array_append(&rl->oids, oid);
>> +
>> + memcpy(&sha_core, oid->hash, sizeof(uint64_t));
>> + rl->hash += sha_core;
>
> Hmm, so the first 64-bits of the oid of each ref that is part of
> this island is added together as a 'hash' for the island. And this
> is used to de-duplicate the islands? Any false positives? (does it
> matter - it would only affect performance, not correctness, right?)I would think that a false positive from pure chance is very unlikely. We would need to approach billions of delta islands (as 2 to the power 64/2 is in the order of billions) for the probability to be significant. GitHub has less than 50 millions users and it is very unlikely that a significant proportion of these users will fork the same repo.
Now if there is a false positive because two forks have exactly the same refs, then it is not a problem if they are considered the same, because they are actually the same.
>> +}
> Sorry, I spent so long reading this patch, I have run out of > time tonight (and I am busy tomorrow) to read the rest of the > series.
Thank you for your interesting review, Christian.