patchfetch-pack: grow stateless RPC windows exponentially

> When updating large repositories, the LARGE_FLUSH limit (that is, the
> limit at which the window growth strategy switches from exponential to
> linear) is reached quite quickly. Use a conservative exponential growth
> strategy when that limit is reached instead.
>
> This optimization is only applied during stateless RPCs to avoid the
> issue raised and fixed in commit
> 44d8dc54e73e8010c4bdf57a422fc8d5ce709029.
>
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 2 ++
>  1 file changed, 2 insertions(+)

> diff --git a/fetch-pack.c b/fetch-pack.c
> index b501d5c..3fcbda2 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -251,6 +251,8 @@ static int next_flush(struct fetch_pack_args *args, int count)
>  
>  	if (count < flush_limit)
>  		count <<= 1;
> +	else if (args->stateless_rpc && count >= flush_limit * 10)
> +		count = count * 11 / 10;
>  	else
>  		count += flush_limit;
>  	return count;

> Yay, thanks for this.
>
> When this condition triggers (count >= 10240), we have already
> experienced 10 rounds of negotiation.  Negotiation ought to have
> finished by then.  So this is a pretty conservative change to try to
> salvage an already bad situation.
>
> The condition ensures that the exponential growth will go faster
> than the previous heuristic of linear growth.
>
> Memory usage grows with the number of 'have's to be sent.  Linear
> growth didn't bound memory usage. This exponential growth makes memory
> usage increase faster, but not aggressively so and the unbounded
> memory usage is already something we'd want to address separately to
> handle hostile servers.
>
> All in all, this looks likely to allow negotiation to finish in fewer
> rounds, speeding up fetch, without much downside, so for what it's
> worth,
>
> Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>
>
> I'd expect us to need more aggressive improvements to negotiation in the
> end (e.g. finding a way to order SHA-1s sent as 'have's to finish in
> fewer rounds).  But this is a good start.  Thanks for writing it.

>> diff --git a/fetch-pack.c b/fetch-pack.c
>> index b501d5c..3fcbda2 100644
>> --- a/fetch-pack.c
>> +++ b/fetch-pack.c
>> @@ -251,6 +251,8 @@ static int next_flush(struct fetch_pack_args *args, int count)
>>  
>>  	if (count < flush_limit)
>>  		count <<= 1;
>> +	else if (args->stateless_rpc && count >= flush_limit * 10)
>> +		count = count * 11 / 10;
>>  	else
>>  		count += flush_limit;
>>  	return count;

>> I'd understand if it were more like "aggressive exponential ->
>> conservative exponential" without linear phase when stateless_rpc is
>> in use, though.  I just do not quite understand the justification
>> behind the order of three phases introduced by this change.
>
> Adding conservative exponential phase after the aggressive exponential
> phase was the original intention, but the conservative exponential
> approach (e.g. n' = n * 11 / 10) is slower than the existing linear
> (n' = n + 1024) approach when n < 10240, so I added that intermediate
> phase to avoid a regression in the packet size growth.

> You have full control of the growth function.  So how about aggressive
> growth until 1024*10?
>
> That is:
>
> Current git:
>   n < 1024: aggressive exponential
> 	16, 32, 64, 128, 256, 512, 1024
>   1024 <= n: linear
> 	2048, 3072, 4096, 5120, ...
>
> Initial proposal:
>   n < 1024: aggressive exponential
> 	16, 32, 64, 128, 256, 512, 1024
>   1024 <= n < 10240: linear
> 	2048, 307, 4096, 5120, ...
>   10240 <= n: conservative exponential
> 	11264, 12390, ...
>
> New proposal:
>   n < 10240: aggressive exponential
> 	16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384
>   10240 <= n: conservative exponential
> 	18022, 19824, ...
>
> That way, on one hand it would still never use a smaller window than
> today and on the other hand the heuristic would be easier to
> understand (only decelarating, instead of decelarating and then
> accelerating again).

> Jonathan Nieder <jrnieder@gmail.com> writes:
>
>> You have full control of the growth function.  So how about aggressive
>> growth until 1024*10?
>>
>> That is:
>>
>> Current git:
>>   n < 1024: aggressive exponential
>>       16, 32, 64, 128, 256, 512, 1024
>>   1024 <= n: linear
>>       2048, 3072, 4096, 5120, ...
>>
>> Initial proposal:
>>   n < 1024: aggressive exponential
>>       16, 32, 64, 128, 256, 512, 1024
>>   1024 <= n < 10240: linear
>>       2048, 307, 4096, 5120, ...
>>   10240 <= n: conservative exponential
>>       11264, 12390, ...
>>
>> New proposal:
>>   n < 10240: aggressive exponential
>>       16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384
>>   10240 <= n: conservative exponential
>>       18022, 19824, ...
>>
>> That way, on one hand it would still never use a smaller window than
>> today and on the other hand the heuristic would be easier to
>> understand (only decelarating, instead of decelarating and then
>> accelerating again).
>
> That sounds more explainable (I do not know if that is a growth
> curve that gives us better results, though).
>
> So, the result would look something like this, perhaps?
>
>  fetch-pack.c | 17 +++++++++++------
>  1 file changed, 11 insertions(+), 6 deletions(-)
>
> diff --git a/fetch-pack.c b/fetch-pack.c
> index 3c5dfc4..97fe5f7 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -264,12 +264,17 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)
>
>  static int next_flush(struct fetch_pack_args *args, int count)
>  {
> -       int flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;
> -
> -       if (count < flush_limit)
> -               count <<= 1;
> -       else
> -               count += flush_limit;
> +       if (args->stateless_rpc) {
> +               if (count < LARGE_FLUSH * 10)
> +                       count <<= 1;
> +               else
> +                       count = count * 11 / 10;
> +       } else {
> +               if (count < PIPESAFE_FLUSH)
> +                       count <<= 1;
> +               else
> +                       count += PIPESAFE_FLUSH;
> +       }
>         return count;
>  }
>

> When updating large repositories, the LARGE_FLUSH limit (that is, the
> limit at which the window growth strategy switches from exponential to
> linear) is reached quite quickly. Use a conservative exponential growth
> strategy when that limit is reached instead (and increase LARGE_FLUSH so
> that there is no regression in window size).

>
> This optimization is only applied during stateless RPCs to avoid the
> issue raised and fixed in commit
> 44d8dc54e73e8010c4bdf57a422fc8d5ce709029.
>
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 19 ++++++++++++-------
>  1 file changed, 12 insertions(+), 7 deletions(-)
>
> diff --git a/fetch-pack.c b/fetch-pack.c
> index b501d5c..85e77af 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -243,16 +243,21 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)
>
>  #define INITIAL_FLUSH 16
>  #define PIPESAFE_FLUSH 32
> -#define LARGE_FLUSH 1024
> +#define LARGE_FLUSH 16384
>
>  static int next_flush(struct fetch_pack_args *args, int count)
>  {
> -       int flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;
> -
> -       if (count < flush_limit)
> -               count <<= 1;
> -       else
> -               count += flush_limit;
> +       if (args->stateless_rpc) {
> +               if (count < LARGE_FLUSH)
> +                       count <<= 1;
> +               else
> +                       count = count * 11 / 10;
> +       } else {
> +               if (count < PIPESAFE_FLUSH)
> +                       count <<= 1;
> +               else
> +                       count += PIPESAFE_FLUSH;
> +       }
>         return count;
>  }
>
> --
> 2.8.0.rc3.226.g39d4020
>

> Care to elaborate on why you choose 11/10 as growth factor?
>
> (As someone who has a tick in micro optimizing:
> 9/8 is roughly the same exponent, but the division
> by 8 is easier as it is just a shift by 3. Similar 17/16)

> I guess one design criterion was 10 being a round number?
> Does it make sense to experiment with the factor at all?
> Digging into that, LARGE_FLUSH originates from 6afca450c3f,
> (2011-03-20, fetch-pack: progressively use larger handshake windows),
> and before we only had a linear growth.
>
> So I guess what I do not understand is why we need to slow down the
> exponential growth at all?

> On Tue, Jul 19, 2016 at 9:46 AM, Stefan Beller <sbeller@google.com> wrote:
>> Care to elaborate on why you choose 11/10 as growth factor?
>>
>> (As someone who has a tick in micro optimizing:
>> 9/8 is roughly the same exponent, but the division
>> by 8 is easier as it is just a shift by 3. Similar 17/16)
>
> I don't have a specific reason for 11/10 as opposed to, say, 9/8 - I
> think that the time taken to execute this line is negligible compared
> to what's done in the calling code, but I'll change it to 9/8 if there
> is another reason for me to send another patch.
>
>> I guess one design criterion was 10 being a round number?
>> Does it make sense to experiment with the factor at all?
>> Digging into that, LARGE_FLUSH originates from 6afca450c3f,
>> (2011-03-20, fetch-pack: progressively use larger handshake windows),
>> and before we only had a linear growth.
>>
>> So I guess what I do not understand is why we need to slow down the
>> exponential growth at all?
>
> The current code has an exponential (a' = a * 2) then a linear (a' = a
> + 1024) growth. I'm not slowing down the exponential growth - that
> part is retained. I'm replacing the linear growth with another
> conservative exponential growth (a' = a * 11 / 10).

>> So I guess what I do not understand is why we need to slow down the
>> exponential growth at all?
>
> The current code has an exponential (a' = a * 2) then a linear (a' = a
> + 1024) growth. I'm not slowing down the exponential growth - that
> part is retained. I'm replacing the linear growth with another
> conservative exponential growth (a' = a * 11 / 10).

> Junio C Hamano wrote:
> 
> > Even if it is conservative, I wonder if it is truly a good idea to
> > make it exponentially grow forever from that point of view.  Would
> > it give essentially the same result to you if we discard the patch
> > in question and just raise LARGE_FLUSH to 10k instead?
> 
> I don't think it would be essentially the same result.  As discussed
> before, unlike the bidi (ssh:// and git:// protocols) case, linear
> growth is expensive in the stateless-rpc (https://) case --- each
> round of negotiation requires re-sending the existing 'have's and
> requires the peer repeatedly processing this increasingly large list
> of 'have's.
> 
> For comparison, in the bidi case, linear growth of next_flush means
> sending a bounded number of 'have's per round and is quite sensible.
> 
> In the stateless-rpc case, linear growth means getting a bounded
> number of 'have's worth of benefit (new 'have's) in each round, in
> exchange for a linearly increasing cost (existing 'have's).  That is a
> high cost for limited benefit.  Exponential growth is a better deal.