Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially
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
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
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 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
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
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
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
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