Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Junio C Hamano]

Jonathan Tan  writes:

> and it would look like that patch. (I would probably redefine
> LARGE_FLUSH to be 10 times its current value instead of multiplying it
> by 10, since it is not used anywhere else.)

Sounds good.  Care to do the final version of the patch to be
applied?

Thanks.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Jonathan Tan]

On Mon, Jul 18, 2016 at 1:00 PM, Junio C Hamano  wrote:
> Jonathan Nieder  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;
>  }
>

Using aggressive growth until 1024*10 seems like a good idea to me,
and it would look like that patch. (I would probably redefine
LARGE_FLUSH to be 10 times its current value instead of multiplying it
by 10, since it is not used anywhere else.)
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Junio C Hamano]

Jonathan Nieder  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;
 }
 
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Jonathan Nieder]

Jonathan Tan wrote:
> On Mon, Jul 18, 2016 at 12:10 PM, Junio C Hamano  wrote:

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

Thanks,
Jonathan
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Jonathan Tan]

On Mon, Jul 18, 2016 at 12:10 PM, Junio C Hamano  wrote:
> 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.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Junio C Hamano]

Jonathan Nieder  writes:

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

Sorry, while I agree with the general sentiment that the windowing
heuristics can be improved, from your description, I would have
expected an updated curve goes like "aggressive exponential ->
conservative exponential -> slow linear", but the new comparison
reads the other way around, i.e. "aggressive exponential -> slow
linear -> conservative exponential".

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.


>> 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;
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially

[Jonathan Nieder]

Hi,

Jonathan Tan wrote:

> 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 
> ---
>  fetch-pack.c | 2 ++
>  1 file changed, 2 insertions(+)

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 

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;
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH] fetch-pack: grow stateless RPC windows exponentially

[Jonathan Tan]

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 
---
 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;
-- 
2.8.0.rc3.226.g39d4020

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html