Re: [PATCH v4 1/7] Add delta-islands.{c,h}

[Christian Couder <christian.couder@gmail.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.

>> 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.

>> --- /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.

>   $ 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.

>   $ 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.

>> +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/

>> +};

>> +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.

>> +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.