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

From: Ramsay Jones <ramsay@ramsayjones.plus.com>
Date: Aug 13, 2018, 12:17 UTC
Message-ID: <7a780fe9-e8bf-804a-82e6-8df81cd5c41c@ramsayjones.plus.com>
In-Reply-To: <CAP8UFD1tX+rAxQc47o-50Kzo6hnX9mTWH2BPSq9HiO_OgBzYTw@mail.gmail.com>

On 13/08/18 04:33, Christian Couder wrote:

> On Mon, Aug 13, 2018 at 3:14 AM, Ramsay Jones

[snip]

Show 10 quoted lines

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

Yes, that's fine.

Show 13 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/
>

That is a fine discussion, without a firm conclusion, but I don't think you can simply do nothing here:

  $ cat -n junk.c
       1	#include <stdint.h>
       2	
       3	struct island_bitmap {
       4		uint32_t refcount;
       5		uint32_t bits[];
       6	};
       7	
  $ gcc --std=c89 --pedantic -c junk.c
  junk.c:5:11: warning: ISO C90 does not support flexible array members [-Wpedantic]
    uint32_t bits[];
             ^~~~
  $ gcc --std=c99 --pedantic -c junk.c
  $

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

If it had been dst_ (or target), I would not have had a 'huh?' moment, but it is not all that important.

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

Yep, good point.

ATB, Ramsay Jones