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

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

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 <jonathantanmy@google.com>
> ---
>  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 <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;

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

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> 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 <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.

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;

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

[Jonathan Tan]

On Mon, Jul 18, 2016 at 12:10 PM, Junio C Hamano <gitster@pobox.com> 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.

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 <gitster@pobox.com> 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

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

[Junio C Hamano]

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;
 }
 

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

[Jonathan Tan]

On Mon, Jul 18, 2016 at 1:00 PM, Junio C Hamano <gitster@pobox.com> wrote:
> 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;
>  }
>

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

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

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> 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.

[PATCH v2] 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 (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

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

[Jonathan Nieder]

Jonathan Tan wrote:

> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 19 ++++++++++++-------
>  1 file changed, 12 insertions(+), 7 deletions(-)

Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks again.

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

[Stefan Beller]

On Mon, Jul 18, 2016 at 3:21 PM, Jonathan Tan <jonathantanmy@google.com> 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 <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
>

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

[Jonathan Tan]

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

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

[Stefan Beller]

On Tue, Jul 19, 2016 at 12:03 PM, Jonathan Tan <jonathantanmy@google.com> wrote:
> 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).

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

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

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> 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?

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

[Jonathan Nieder]

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

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

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> 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.

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

[Jeff King]

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