{"thread":{"id":"42873","subject":"[PATCH] fetch-pack: grow stateless RPC windows exponentially","startedAt":"2016-07-18T18:37:23Z","lastAt":"2016-07-20T13:40:35Z","messageCount":17,"participants":["Jonathan Tan","Jonathan Nieder","Junio C Hamano","Stefan Beller","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"291665","messageId":"1468867019-13086-1-git-send-email-jonathantanmy@google.com","threadId":"42873","inReplyTo":null,"subject":"[PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2016-07-18T18:36:59Z","receivedAt":"2016-07-18T18:37:23Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"When updating large repositories, the LARGE_FLUSH limit (that is, the\nlimit at which the window growth strategy switches from exponential to\nlinear) is reached quite quickly. Use a conservative exponential growth\nstrategy when that limit is reached instead.\n\nThis optimization is only applied during stateless RPCs to avoid the\nissue raised and fixed in commit\n44d8dc54e73e8010c4bdf57a422fc8d5ce709029.\n\nSigned-off-by: Jonathan Tan \n---\n fetch-pack.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex b501d5c..3fcbda2 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -251,6 +251,8 @@ static int next_flush(struct fetch_pack_args *args, int count)\n \n \tif (count < flush_limit)\n \t\tcount <<= 1;\n+\telse if (args->stateless_rpc && count >= flush_limit * 10)\n+\t\tcount = count * 11 / 10;\n \telse\n \t\tcount += flush_limit;\n \treturn count;\n-- \n2.8.0.rc3.226.g39d4020\n\n"},{"id":"291669","messageId":"20160718185527.GB29326@google.com","threadId":"42873","inReplyTo":"1468867019-13086-1-git-send-email-jonathantanmy@google.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2016-07-18T18:55:28Z","receivedAt":"2016-07-18T18:55:44Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nJonathan Tan wrote:\n\n> When updating large repositories, the LARGE_FLUSH limit (that is, the\n> limit at which the window growth strategy switches from exponential to\n> linear) is reached quite quickly. Use a conservative exponential growth\n> strategy when that limit is reached instead.\n>\n> This optimization is only applied during stateless RPCs to avoid the\n> issue raised and fixed in commit\n> 44d8dc54e73e8010c4bdf57a422fc8d5ce709029.\n>\n> Signed-off-by: Jonathan Tan \n> ---\n> fetch-pack.c | 2 ++\n> 1 file changed, 2 insertions(+)\n\nYay, thanks for this.\n\nWhen this condition triggers (count >= 10240), we have already\nexperienced 10 rounds of negotiation. Negotiation ought to have\nfinished by then. So this is a pretty conservative change to try to\nsalvage an already bad situation.\n\nThe condition ensures that the exponential growth will go faster\nthan the previous heuristic of linear growth.\n\nMemory usage grows with the number of 'have's to be sent. Linear\ngrowth didn't bound memory usage. This exponential growth makes memory\nusage increase faster, but not aggressively so and the unbounded\nmemory usage is already something we'd want to address separately to\nhandle hostile servers.\n\nAll in all, this looks likely to allow negotiation to finish in fewer\nrounds, speeding up fetch, without much downside, so for what it's\nworth,\n\nReviewed-by: Jonathan Nieder \n\nI'd expect us to need more aggressive improvements to negotiation in the\nend (e.g. finding a way to order SHA-1s sent as 'have's to finish in\nfewer rounds). But this is a good start. Thanks for writing it.\n\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index b501d5c..3fcbda2 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -251,6 +251,8 @@ static int next_flush(struct fetch_pack_args *args, int count)\n> \n> \tif (count < flush_limit)\n> \t\tcount <<= 1;\n> +\telse if (args->stateless_rpc && count >= flush_limit * 10)\n> +\t\tcount = count * 11 / 10;\n> \telse\n> \t\tcount += flush_limit;\n> \treturn count;\n"},{"id":"291672","messageId":"xmqq37n6kbib.fsf@gitster.mtv.corp.google.com","threadId":"42873","inReplyTo":"20160718185527.GB29326@google.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-18T19:10:52Z","receivedAt":"2016-07-18T19:11:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder writes:\n\n> Yay, thanks for this.\n>\n> When this condition triggers (count >= 10240), we have already\n> experienced 10 rounds of negotiation. Negotiation ought to have\n> finished by then. So this is a pretty conservative change to try to\n> salvage an already bad situation.\n>\n> The condition ensures that the exponential growth will go faster\n> than the previous heuristic of linear growth.\n>\n> Memory usage grows with the number of 'have's to be sent. Linear\n> growth didn't bound memory usage. This exponential growth makes memory\n> usage increase faster, but not aggressively so and the unbounded\n> memory usage is already something we'd want to address separately to\n> handle hostile servers.\n>\n> All in all, this looks likely to allow negotiation to finish in fewer\n> rounds, speeding up fetch, without much downside, so for what it's\n> worth,\n>\n> Reviewed-by: Jonathan Nieder \n>\n> I'd expect us to need more aggressive improvements to negotiation in the\n> end (e.g. finding a way to order SHA-1s sent as 'have's to finish in\n> fewer rounds). But this is a good start. Thanks for writing it.\n\nSorry, while I agree with the general sentiment that the windowing\nheuristics can be improved, from your description, I would have\nexpected an updated curve goes like \"aggressive exponential ->\nconservative exponential -> slow linear\", but the new comparison\nreads the other way around, i.e. \"aggressive exponential -> slow\nlinear -> conservative exponential\".\n\nI'd understand if it were more like \"aggressive exponential ->\nconservative exponential\" without linear phase when stateless_rpc is\nin use, though. I just do not quite understand the justification\nbehind the order of three phases introduced by this change.\n\n\n>> diff --git a/fetch-pack.c b/fetch-pack.c\n>> index b501d5c..3fcbda2 100644\n>> --- a/fetch-pack.c\n>> +++ b/fetch-pack.c\n>> @@ -251,6 +251,8 @@ static int next_flush(struct fetch_pack_args *args, int count)\n>> \n>> \tif (count < flush_limit)\n>> \t\tcount <<= 1;\n>> +\telse if (args->stateless_rpc && count >= flush_limit * 10)\n>> +\t\tcount = count * 11 / 10;\n>> \telse\n>> \t\tcount += flush_limit;\n>> \treturn count;\n"},{"id":"291673","messageId":"CAGf8dgJVkkVwJ5aJCQBcYKw7F9g7u3pMsuJHedSGLG6PQk2Keg@mail.gmail.com","threadId":"42873","inReplyTo":"xmqq37n6kbib.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2016-07-18T19:16:09Z","receivedAt":"2016-07-18T19:16:16Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, Jul 18, 2016 at 12:10 PM, Junio C Hamano wrote:\n> I'd understand if it were more like \"aggressive exponential ->\n> conservative exponential\" without linear phase when stateless_rpc is\n> in use, though. I just do not quite understand the justification\n> behind the order of three phases introduced by this change.\n\nAdding conservative exponential phase after the aggressive exponential\nphase was the original intention, but the conservative exponential\napproach (e.g. n' = n * 11 / 10) is slower than the existing linear\n(n' = n + 1024) approach when n < 10240, so I added that intermediate\nphase to avoid a regression in the packet size growth.\n"},{"id":"291675","messageId":"20160718193147.GC29326@google.com","threadId":"42873","inReplyTo":"CAGf8dgJVkkVwJ5aJCQBcYKw7F9g7u3pMsuJHedSGLG6PQk2Keg@mail.gmail.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2016-07-18T19:31:47Z","receivedAt":"2016-07-18T19:32:13Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Tan wrote:\n> On Mon, Jul 18, 2016 at 12:10 PM, Junio C Hamano wrote:\n\n>> I'd understand if it were more like \"aggressive exponential ->\n>> conservative exponential\" without linear phase when stateless_rpc is\n>> in use, though. I just do not quite understand the justification\n>> behind the order of three phases introduced by this change.\n>\n> Adding conservative exponential phase after the aggressive exponential\n> phase was the original intention, but the conservative exponential\n> approach (e.g. n' = n * 11 / 10) is slower than the existing linear\n> (n' = n + 1024) approach when n < 10240, so I added that intermediate\n> phase to avoid a regression in the packet size growth.\n\nYou have full control of the growth function. So how about aggressive\ngrowth until 1024*10?\n\nThat is:\n\nCurrent git:\n n < 1024: aggressive exponential\n\t16, 32, 64, 128, 256, 512, 1024\n 1024 <= n: linear\n\t2048, 3072, 4096, 5120, ...\n\nInitial proposal:\n n < 1024: aggressive exponential\n\t16, 32, 64, 128, 256, 512, 1024\n 1024 <= n < 10240: linear\n\t2048, 307, 4096, 5120, ...\n 10240 <= n: conservative exponential\n\t11264, 12390, ...\n\nNew proposal:\n n < 10240: aggressive exponential\n\t16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384\n 10240 <= n: conservative exponential\n\t18022, 19824, ...\n\nThat way, on one hand it would still never use a smaller window than\ntoday and on the other hand the heuristic would be easier to\nunderstand (only decelarating, instead of decelarating and then\naccelerating again).\n\nThanks,\nJonathan\n"},{"id":"291677","messageId":"xmqqoa5uiumu.fsf@gitster.mtv.corp.google.com","threadId":"42873","inReplyTo":"20160718193147.GC29326@google.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-18T20:00:41Z","receivedAt":"2016-07-18T20:00:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder writes:\n\n> You have full control of the growth function. So how about aggressive\n> growth until 1024*10?\n>\n> That is:\n>\n> Current git:\n> n < 1024: aggressive exponential\n> \t16, 32, 64, 128, 256, 512, 1024\n> 1024 <= n: linear\n> \t2048, 3072, 4096, 5120, ...\n>\n> Initial proposal:\n> n < 1024: aggressive exponential\n> \t16, 32, 64, 128, 256, 512, 1024\n> 1024 <= n < 10240: linear\n> \t2048, 307, 4096, 5120, ...\n> 10240 <= n: conservative exponential\n> \t11264, 12390, ...\n>\n> New proposal:\n> n < 10240: aggressive exponential\n> \t16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384\n> 10240 <= n: conservative exponential\n> \t18022, 19824, ...\n>\n> That way, on one hand it would still never use a smaller window than\n> today and on the other hand the heuristic would be easier to\n> understand (only decelarating, instead of decelarating and then\n> accelerating again).\n\nThat sounds more explainable (I do not know if that is a growth\ncurve that gives us better results, though).\n\nSo, the result would look something like this, perhaps?\n\n fetch-pack.c | 17 +++++++++++------\n 1 file changed, 11 insertions(+), 6 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 3c5dfc4..97fe5f7 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -264,12 +264,17 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)\n \n static int next_flush(struct fetch_pack_args *args, int count)\n {\n-\tint flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;\n-\n-\tif (count < flush_limit)\n-\t\tcount <<= 1;\n-\telse\n-\t\tcount += flush_limit;\n+\tif (args->stateless_rpc) {\n+\t\tif (count < LARGE_FLUSH * 10)\n+\t\t\tcount <<= 1;\n+\t\telse\n+\t\t\tcount = count * 11 / 10;\n+\t} else {\n+\t\tif (count < PIPESAFE_FLUSH)\n+\t\t\tcount <<= 1;\n+\t\telse\n+\t\t\tcount += PIPESAFE_FLUSH;\n+\t}\n \treturn count;\n }\n \n"},{"id":"291685","messageId":"CAGf8dgJWMBbU1rbU1hTOjX9d-b-ocmYs-td9kpQ=skQFM7XcSA@mail.gmail.com","threadId":"42873","inReplyTo":"xmqqoa5uiumu.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2016-07-18T21:05:22Z","receivedAt":"2016-07-18T21:05:29Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, Jul 18, 2016 at 1:00 PM, Junio C Hamano wrote:\n> Jonathan Nieder writes:\n>\n>> You have full control of the growth function. So how about aggressive\n>> growth until 1024*10?\n>>\n>> That is:\n>>\n>> Current git:\n>> n < 1024: aggressive exponential\n>> 16, 32, 64, 128, 256, 512, 1024\n>> 1024 <= n: linear\n>> 2048, 3072, 4096, 5120, ...\n>>\n>> Initial proposal:\n>> n < 1024: aggressive exponential\n>> 16, 32, 64, 128, 256, 512, 1024\n>> 1024 <= n < 10240: linear\n>> 2048, 307, 4096, 5120, ...\n>> 10240 <= n: conservative exponential\n>> 11264, 12390, ...\n>>\n>> New proposal:\n>> n < 10240: aggressive exponential\n>> 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384\n>> 10240 <= n: conservative exponential\n>> 18022, 19824, ...\n>>\n>> That way, on one hand it would still never use a smaller window than\n>> today and on the other hand the heuristic would be easier to\n>> understand (only decelarating, instead of decelarating and then\n>> accelerating again).\n>\n> That sounds more explainable (I do not know if that is a growth\n> curve that gives us better results, though).\n>\n> So, the result would look something like this, perhaps?\n>\n> fetch-pack.c | 17 +++++++++++------\n> 1 file changed, 11 insertions(+), 6 deletions(-)\n>\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 3c5dfc4..97fe5f7 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -264,12 +264,17 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)\n>\n> static int next_flush(struct fetch_pack_args *args, int count)\n> {\n> - int flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;\n> -\n> - if (count < flush_limit)\n> - count <<= 1;\n> - else\n> - count += flush_limit;\n> + if (args->stateless_rpc) {\n> + if (count < LARGE_FLUSH * 10)\n> + count <<= 1;\n> + else\n> + count = count * 11 / 10;\n> + } else {\n> + if (count < PIPESAFE_FLUSH)\n> + count <<= 1;\n> + else\n> + count += PIPESAFE_FLUSH;\n> + }\n> return count;\n> }\n>\n\nUsing aggressive growth until 1024*10 seems like a good idea to me,\nand it would look like that patch. (I would probably redefine\nLARGE_FLUSH to be 10 times its current value instead of multiplying it\nby 10, since it is not used anywhere else.)\n"},{"id":"291690","messageId":"xmqq37n6iq7d.fsf@gitster.mtv.corp.google.com","threadId":"42873","inReplyTo":"CAGf8dgJWMBbU1rbU1hTOjX9d-b-ocmYs-td9kpQ=skQFM7XcSA@mail.gmail.com","subject":"Re: [PATCH] fetch-pack: grow stateless RPC windows exponentially","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-18T21:36:22Z","receivedAt":"2016-07-18T21:36:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> and it would look like that patch. (I would probably redefine\n> LARGE_FLUSH to be 10 times its current value instead of multiplying it\n> by 10, since it is not used anywhere else.)\n\nSounds good. Care to do the final version of the patch to be\napplied?\n\nThanks.\n"},{"id":"291691","messageId":"1468880498-30235-1-git-send-email-jonathantanmy@google.com","threadId":"42873","inReplyTo":"xmqq37n6iq7d.fsf@gitster.mtv.corp.google.com","subject":"[PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2016-07-18T22:21:38Z","receivedAt":"2016-07-18T22:23:07Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"When updating large repositories, the LARGE_FLUSH limit (that is, the\nlimit at which the window growth strategy switches from exponential to\nlinear) is reached quite quickly. Use a conservative exponential growth\nstrategy when that limit is reached instead (and increase LARGE_FLUSH so\nthat there is no regression in window size).\n\nThis optimization is only applied during stateless RPCs to avoid the\nissue raised and fixed in commit\n44d8dc54e73e8010c4bdf57a422fc8d5ce709029.\n\nSigned-off-by: Jonathan Tan \n---\n fetch-pack.c | 19 ++++++++++++-------\n 1 file changed, 12 insertions(+), 7 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex b501d5c..85e77af 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -243,16 +243,21 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)\n \n #define INITIAL_FLUSH 16\n #define PIPESAFE_FLUSH 32\n-#define LARGE_FLUSH 1024\n+#define LARGE_FLUSH 16384\n \n static int next_flush(struct fetch_pack_args *args, int count)\n {\n-\tint flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;\n-\n-\tif (count < flush_limit)\n-\t\tcount <<= 1;\n-\telse\n-\t\tcount += flush_limit;\n+\tif (args->stateless_rpc) {\n+\t\tif (count < LARGE_FLUSH)\n+\t\t\tcount <<= 1;\n+\t\telse\n+\t\t\tcount = count * 11 / 10;\n+\t} else {\n+\t\tif (count < PIPESAFE_FLUSH)\n+\t\t\tcount <<= 1;\n+\t\telse\n+\t\t\tcount += PIPESAFE_FLUSH;\n+\t}\n \treturn count;\n }\n \n-- \n2.8.0.rc3.226.g39d4020\n\n"},{"id":"291693","messageId":"20160718224004.GE29326@google.com","threadId":"42873","inReplyTo":"1468880498-30235-1-git-send-email-jonathantanmy@google.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2016-07-18T22:40:04Z","receivedAt":"2016-07-18T22:40:12Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Tan wrote:\n\n> Signed-off-by: Jonathan Tan \n> ---\n> fetch-pack.c | 19 ++++++++++++-------\n> 1 file changed, 12 insertions(+), 7 deletions(-)\n\nReviewed-by: Jonathan Nieder \n\nThanks again.\n"},{"id":"291730","messageId":"CAGZ79kY+2PYx9oz9tvi0zG-oE6qS-Za7D3ocY1XtqcSsDchz0Q@mail.gmail.com","threadId":"42873","inReplyTo":"1468880498-30235-1-git-send-email-jonathantanmy@google.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-07-19T16:46:10Z","receivedAt":"2016-07-19T16:46:28Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Jul 18, 2016 at 3:21 PM, Jonathan Tan wrote:\n> When updating large repositories, the LARGE_FLUSH limit (that is, the\n> limit at which the window growth strategy switches from exponential to\n> linear) is reached quite quickly. Use a conservative exponential growth\n> strategy when that limit is reached instead (and increase LARGE_FLUSH so\n> that there is no regression in window size).\n\nCare to elaborate on why you choose 11/10 as growth factor?\n\n(As someone who has a tick in micro optimizing:\n9/8 is roughly the same exponent, but the division\nby 8 is easier as it is just a shift by 3. Similar 17/16)\n\nI guess one design criterion was 10 being a round number?\nDoes it make sense to experiment with the factor at all?\nDigging into that, LARGE_FLUSH originates from 6afca450c3f,\n(2011-03-20, fetch-pack: progressively use larger handshake windows),\nand before we only had a linear growth.\n\nSo I guess what I do not understand is why we need to slow down the\nexponential growth at all?\n\nThanks,\nStefan\n\n\n\n>\n> This optimization is only applied during stateless RPCs to avoid the\n> issue raised and fixed in commit\n> 44d8dc54e73e8010c4bdf57a422fc8d5ce709029.\n>\n> Signed-off-by: Jonathan Tan \n> ---\n> fetch-pack.c | 19 ++++++++++++-------\n> 1 file changed, 12 insertions(+), 7 deletions(-)\n>\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index b501d5c..85e77af 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -243,16 +243,21 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)\n>\n> #define INITIAL_FLUSH 16\n> #define PIPESAFE_FLUSH 32\n> -#define LARGE_FLUSH 1024\n> +#define LARGE_FLUSH 16384\n>\n> static int next_flush(struct fetch_pack_args *args, int count)\n> {\n> - int flush_limit = args->stateless_rpc ? LARGE_FLUSH : PIPESAFE_FLUSH;\n> -\n> - if (count < flush_limit)\n> - count <<= 1;\n> - else\n> - count += flush_limit;\n> + if (args->stateless_rpc) {\n> + if (count < LARGE_FLUSH)\n> + count <<= 1;\n> + else\n> + count = count * 11 / 10;\n> + } else {\n> + if (count < PIPESAFE_FLUSH)\n> + count <<= 1;\n> + else\n> + count += PIPESAFE_FLUSH;\n> + }\n> return count;\n> }\n>\n> --\n> 2.8.0.rc3.226.g39d4020\n>\n"},{"id":"291752","messageId":"CAGf8dgL3t7uX7yAux0xc2QMJJdmnM0262Quj4o6gDehwA+4JqQ@mail.gmail.com","threadId":"42873","inReplyTo":"CAGZ79kY+2PYx9oz9tvi0zG-oE6qS-Za7D3ocY1XtqcSsDchz0Q@mail.gmail.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2016-07-19T19:03:24Z","receivedAt":"2016-07-19T19:03:30Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Tue, Jul 19, 2016 at 9:46 AM, Stefan Beller wrote:\n> Care to elaborate on why you choose 11/10 as growth factor?\n>\n> (As someone who has a tick in micro optimizing:\n> 9/8 is roughly the same exponent, but the division\n> by 8 is easier as it is just a shift by 3. Similar 17/16)\n\nI don't have a specific reason for 11/10 as opposed to, say, 9/8 - I\nthink that the time taken to execute this line is negligible compared\nto what's done in the calling code, but I'll change it to 9/8 if there\nis another reason for me to send another patch.\n\n> I guess one design criterion was 10 being a round number?\n> Does it make sense to experiment with the factor at all?\n> Digging into that, LARGE_FLUSH originates from 6afca450c3f,\n> (2011-03-20, fetch-pack: progressively use larger handshake windows),\n> and before we only had a linear growth.\n>\n> So I guess what I do not understand is why we need to slow down the\n> exponential growth at all?\n\nThe current code has an exponential (a' = a * 2) then a linear (a' = a\n+ 1024) growth. I'm not slowing down the exponential growth - that\npart is retained. I'm replacing the linear growth with another\nconservative exponential growth (a' = a * 11 / 10).\n"},{"id":"291758","messageId":"CAGZ79kZxN9uYprMUXMuWpO3mKfw6WTa3uoG=SXWny7St1OfGzA@mail.gmail.com","threadId":"42873","inReplyTo":"CAGf8dgL3t7uX7yAux0xc2QMJJdmnM0262Quj4o6gDehwA+4JqQ@mail.gmail.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-07-19T19:17:50Z","receivedAt":"2016-07-19T19:18:11Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Jul 19, 2016 at 12:03 PM, Jonathan Tan wrote:\n> On Tue, Jul 19, 2016 at 9:46 AM, Stefan Beller wrote:\n>> Care to elaborate on why you choose 11/10 as growth factor?\n>>\n>> (As someone who has a tick in micro optimizing:\n>> 9/8 is roughly the same exponent, but the division\n>> by 8 is easier as it is just a shift by 3. Similar 17/16)\n>\n> I don't have a specific reason for 11/10 as opposed to, say, 9/8 - I\n> think that the time taken to execute this line is negligible compared\n> to what's done in the calling code, but I'll change it to 9/8 if there\n> is another reason for me to send another patch.\n>\n>> I guess one design criterion was 10 being a round number?\n>> Does it make sense to experiment with the factor at all?\n>> Digging into that, LARGE_FLUSH originates from 6afca450c3f,\n>> (2011-03-20, fetch-pack: progressively use larger handshake windows),\n>> and before we only had a linear growth.\n>>\n>> So I guess what I do not understand is why we need to slow down the\n>> exponential growth at all?\n>\n> The current code has an exponential (a' = a * 2) then a linear (a' = a\n> + 1024) growth. I'm not slowing down the exponential growth - that\n> part is retained. I'm replacing the linear growth with another\n> conservative exponential growth (a' = a * 11 / 10).\n\nSorry for the miss understanding. Once we have the new conservative\nexponential, we'd have a fast exponential first (a=2*a) and then after a while\na slower exponential (a=1.1*a). So we have 2 exponential curves with different\ngrowth properties.\n\nSo my question could be reworded as: Why do we need two different exponential\ngrowth phases (as they are both exponential)? And I answered myself with: Oh,\nthe exponents are different, so that's why.\n\nBut then I tried to understand why we choose the 2 exponents as of this patch.\n(Why start with 2 and drop back to 1.1?) Could one exponential phase be\nsufficient with an exponent in between (e.g. a=1.3*a with a larger starting a to\ncompensate for the reduced early growth) ?\n\nOr to reword it another way: Using just one exponential growth is simpler than\n2 different exponential growth phases, so how do we explain the added\ncomplexity?\n\nThanks,\nStefan\n"},{"id":"291760","messageId":"xmqq8twxfn4j.fsf@gitster.mtv.corp.google.com","threadId":"42873","inReplyTo":"CAGf8dgL3t7uX7yAux0xc2QMJJdmnM0262Quj4o6gDehwA+4JqQ@mail.gmail.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-19T19:23:24Z","receivedAt":"2016-07-19T19:23:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n>> So I guess what I do not understand is why we need to slow down the\n>> exponential growth at all?\n>\n> The current code has an exponential (a' = a * 2) then a linear (a' = a\n> + 1024) growth. I'm not slowing down the exponential growth - that\n> part is retained. I'm replacing the linear growth with another\n> conservative exponential growth (a' = a * 11 / 10).\n\nAs stateless-rpc mode is to drive a half-duplex channel, the\nfunction essentially determines how many messages to buffer before\npassing the control to the other side. The increment between number\nthe function is called with and the function returns is how much the\nother side is made to wait, i.e. how long the ping-pong latency is.\n\nEven if it is conservative, I wonder if it is truly a good idea to\nmake it exponentially grow forever from that point of view. Would\nit give essentially the same result to you if we discard the patch\nin question and just raise LARGE_FLUSH to 10k instead?\n\n"},{"id":"291765","messageId":"20160719195347.GF29326@google.com","threadId":"42873","inReplyTo":"xmqq8twxfn4j.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2016-07-19T19:53:47Z","receivedAt":"2016-07-19T19:53:55Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Junio C Hamano wrote:\n\n> Even if it is conservative, I wonder if it is truly a good idea to\n> make it exponentially grow forever from that point of view. Would\n> it give essentially the same result to you if we discard the patch\n> in question and just raise LARGE_FLUSH to 10k instead?\n\nI don't think it would be essentially the same result. As discussed\nbefore, unlike the bidi (ssh:// and git:// protocols) case, linear\ngrowth is expensive in the stateless-rpc (https://) case --- each\nround of negotiation requires re-sending the existing 'have's and\nrequires the peer repeatedly processing this increasingly large list\nof 'have's.\n\nFor comparison, in the bidi case, linear growth of next_flush means\nsending a bounded number of 'have's per round and is quite sensible.\n\nIn the stateless-rpc case, linear growth means getting a bounded\nnumber of 'have's worth of benefit (new 'have's) in each round, in\nexchange for a linearly increasing cost (existing 'have's). That is a\nhigh cost for limited benefit. Exponential growth is a better deal.\n\nJonathan\n"},{"id":"291766","messageId":"xmqqzipde5xb.fsf@gitster.mtv.corp.google.com","threadId":"42873","inReplyTo":"20160719195347.GF29326@google.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-19T20:20:16Z","receivedAt":"2016-07-19T20:20:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder writes:\n\n> In the stateless-rpc case, linear growth means getting a bounded\n> number of 'have's worth of benefit (new 'have's) in each round, in\n> exchange for a linearly increasing cost (existing 'have's). That is a\n> high cost for limited benefit. Exponential growth is a better deal.\n\nAhh, of course (silly me). I somehow forgot the cost of having to\nrepeat what we have already sent to the other side.\n\n"},{"id":"291807","messageId":"20160720134027.GA19194@sigill.intra.peff.net","threadId":"42873","inReplyTo":"20160719195347.GF29326@google.com","subject":"Re: [PATCH v2] fetch-pack: grow stateless RPC windows exponentially","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-20T13:40:27Z","receivedAt":"2016-07-20T13:40:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 19, 2016 at 12:53:47PM -0700, Jonathan Nieder wrote:\n\n> Junio C Hamano wrote:\n> \n> > Even if it is conservative, I wonder if it is truly a good idea to\n> > make it exponentially grow forever from that point of view. Would\n> > it give essentially the same result to you if we discard the patch\n> > in question and just raise LARGE_FLUSH to 10k instead?\n> \n> I don't think it would be essentially the same result. As discussed\n> before, unlike the bidi (ssh:// and git:// protocols) case, linear\n> growth is expensive in the stateless-rpc (https://) case --- each\n> round of negotiation requires re-sending the existing 'have's and\n> requires the peer repeatedly processing this increasingly large list\n> of 'have's.\n> \n> For comparison, in the bidi case, linear growth of next_flush means\n> sending a bounded number of 'have's per round and is quite sensible.\n> \n> In the stateless-rpc case, linear growth means getting a bounded\n> number of 'have's worth of benefit (new 'have's) in each round, in\n> exchange for a linearly increasing cost (existing 'have's). That is a\n> high cost for limited benefit. Exponential growth is a better deal.\n\nThis kind of reasoning would be great in the commit message (and if\npossible, numbers showing empirical improvement). On reading it, I\nunderstood the \"what\", but not why or to what extent the slower growth\nis a problem.\n\n-Peff\n"}]}