# [PATCH] fetch-pack: grow stateless RPC windows exponentially 17 messages from 2016-07-18 to 2016-07-20. Participants: Jonathan Tan, Jonathan Nieder, Junio C Hamano, Stefan Beller, Jeff King. Thread: https://gitlist.dev/t/42873 ## Jonathan Tan, 2016-07-18 18:36 Subject: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: <1468867019-13086-1-git-send-email-jonathantanmy@google.com> URL: https://gitlist.dev/e/1468867019-13086-1-git-send-email-jonathantanmy%40google.com ``` 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 ``` ## Jonathan Nieder, 2016-07-18 18:55 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: <20160718185527.GB29326@google.com> URL: https://gitlist.dev/e/20160718185527.GB29326%40google.com In-Reply-To: <1468867019-13086-1-git-send-email-jonathantanmy@google.com> ``` 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; ``` ## Junio C Hamano, 2016-07-18 19:10 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/xmqq37n6kbib.fsf%40gitster.mtv.corp.google.com In-Reply-To: <20160718185527.GB29326@google.com> ``` 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; ``` ## Jonathan Tan, 2016-07-18 19:16 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/CAGf8dgJVkkVwJ5aJCQBcYKw7F9g7u3pMsuJHedSGLG6PQk2Keg%40mail.gmail.com In-Reply-To: ``` 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. ``` ## Jonathan Nieder, 2016-07-18 19:31 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: <20160718193147.GC29326@google.com> URL: https://gitlist.dev/e/20160718193147.GC29326%40google.com In-Reply-To: ``` 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 ``` ## Junio C Hamano, 2016-07-18 20:00 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/xmqqoa5uiumu.fsf%40gitster.mtv.corp.google.com In-Reply-To: <20160718193147.GC29326@google.com> ``` 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; } ``` ## Jonathan Tan, 2016-07-18 21:05 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/CAGf8dgJWMBbU1rbU1hTOjX9d-b-ocmYs-td9kpQ%3DskQFM7XcSA%40mail.gmail.com In-Reply-To: ``` 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.) ``` ## Junio C Hamano, 2016-07-18 21:36 Subject: Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/xmqq37n6iq7d.fsf%40gitster.mtv.corp.google.com In-Reply-To: ``` 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. ``` ## Jonathan Tan, 2016-07-18 22:21 Subject: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: <1468880498-30235-1-git-send-email-jonathantanmy@google.com> URL: https://gitlist.dev/e/1468880498-30235-1-git-send-email-jonathantanmy%40google.com In-Reply-To: ``` 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 --- 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 ``` ## Jonathan Nieder, 2016-07-18 22:40 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: <20160718224004.GE29326@google.com> URL: https://gitlist.dev/e/20160718224004.GE29326%40google.com In-Reply-To: <1468880498-30235-1-git-send-email-jonathantanmy@google.com> ``` Jonathan Tan wrote: > Signed-off-by: Jonathan Tan > --- > fetch-pack.c | 19 ++++++++++++------- > 1 file changed, 12 insertions(+), 7 deletions(-) Reviewed-by: Jonathan Nieder Thanks again. ``` ## Stefan Beller, 2016-07-19 16:46 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/CAGZ79kY%2B2PYx9oz9tvi0zG-oE6qS-Za7D3ocY1XtqcSsDchz0Q%40mail.gmail.com In-Reply-To: <1468880498-30235-1-git-send-email-jonathantanmy@google.com> ``` On Mon, Jul 18, 2016 at 3:21 PM, 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 (and increase LARGE_FLUSH so > that there is no regression in window size). 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? Thanks, Stefan > > 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 | 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 > ``` ## Jonathan Tan, 2016-07-19 19:03 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/CAGf8dgL3t7uX7yAux0xc2QMJJdmnM0262Quj4o6gDehwA%2B4JqQ%40mail.gmail.com In-Reply-To: ``` On Tue, Jul 19, 2016 at 9:46 AM, Stefan Beller 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). ``` ## Stefan Beller, 2016-07-19 19:17 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/CAGZ79kZxN9uYprMUXMuWpO3mKfw6WTa3uoG%3DSXWny7St1OfGzA%40mail.gmail.com In-Reply-To: ``` On Tue, Jul 19, 2016 at 12:03 PM, Jonathan Tan wrote: > On Tue, Jul 19, 2016 at 9:46 AM, Stefan Beller 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). Sorry for the miss understanding. Once we have the new conservative exponential, we'd have a fast exponential first (a=2*a) and then after a while a slower exponential (a=1.1*a). So we have 2 exponential curves with different growth properties. So my question could be reworded as: Why do we need two different exponential growth phases (as they are both exponential)? And I answered myself with: Oh, the exponents are different, so that's why. But then I tried to understand why we choose the 2 exponents as of this patch. (Why start with 2 and drop back to 1.1?) Could one exponential phase be sufficient with an exponent in between (e.g. a=1.3*a with a larger starting a to compensate for the reduced early growth) ? Or to reword it another way: Using just one exponential growth is simpler than 2 different exponential growth phases, so how do we explain the added complexity? Thanks, Stefan ``` ## Junio C Hamano, 2016-07-19 19:23 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/xmqq8twxfn4j.fsf%40gitster.mtv.corp.google.com In-Reply-To: ``` Jonathan Tan writes: >> 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). As stateless-rpc mode is to drive a half-duplex channel, the function essentially determines how many messages to buffer before passing the control to the other side. The increment between number the function is called with and the function returns is how much the other side is made to wait, i.e. how long the ping-pong latency is. 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? ``` ## Jonathan Nieder, 2016-07-19 19:53 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: <20160719195347.GF29326@google.com> URL: https://gitlist.dev/e/20160719195347.GF29326%40google.com In-Reply-To: ``` 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. Jonathan ``` ## Junio C Hamano, 2016-07-19 20:20 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: URL: https://gitlist.dev/e/xmqqzipde5xb.fsf%40gitster.mtv.corp.google.com In-Reply-To: <20160719195347.GF29326@google.com> ``` Jonathan Nieder writes: > 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. Ahh, of course (silly me). I somehow forgot the cost of having to repeat what we have already sent to the other side. ``` ## Jeff King, 2016-07-20 13:40 Subject: Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially Message-ID: <20160720134027.GA19194@sigill.intra.peff.net> URL: https://gitlist.dev/e/20160720134027.GA19194%40sigill.intra.peff.net In-Reply-To: <20160719195347.GF29326@google.com> ``` On Tue, Jul 19, 2016 at 12:53:47PM -0700, Jonathan Nieder wrote: > 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. This kind of reasoning would be great in the commit message (and if possible, numbers showing empirical improvement). On reading it, I understood the "what", but not why or to what extent the slower growth is a problem. -Peff ```