rtc::Buffer: Grow capacity by at least 1.5x to prevent quadratic behavior

rtc::Buffer: Grow capacity by at least 1.5x to prevent quadratic behavior

BUG=webrtc:6009
Committed: https://crrev.com/c853597598198f2d4e57abaaa127d16fe5611410
Cr-Commit-Position: refs/heads/master@{#13214}

[kwiberg-webrtc, 2016-06-18 09:42:54]

kwiberg@webrtc.org changed reviewers:
+ pbos@webrtc.org, sprang@webrtc.org

[sprang_webrtc, 2016-06-20 09:27:44]

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h
File webrtc/base/buffer.h (right):

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode275
webrtc/base/buffer.h:275: EnsureCapacityWithHeadroom(size, true);
Do we really want with headroom here, as it's an explicit size request?

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode316
webrtc/base/buffer.h:316: : capacity;
This seems a little odd. If capacity > 1.5 * capacity_, we expand without the
1.5x margin?

[kwiberg-webrtc, 2016-06-20 09:51:31]

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h
File webrtc/base/buffer.h (right):

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode275
webrtc/base/buffer.h:275: EnsureCapacityWithHeadroom(size, true);
On 2016/06/20 09:27:44, språng wrote:
> Do we really want with headroom here, as it's an explicit size request?

It's an explicit *size* request, but the caller doesn't necessarily care about
*capacity* (except that it has to grow large enough, obviously). My thinking is
that callers that want the extra control can use EnsureCapacity(); this makes it
harder for callers that don't care to accidentally shoot themselves in the foot.

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode316
webrtc/base/buffer.h:316: : capacity;
On 2016/06/20 09:27:44, språng wrote:
> This seems a little odd. If capacity > 1.5 * capacity_, we expand without the
> 1.5x margin? 

capacity is the requested capacity. If that's >= 1.5 times current capacity,
there's no need for us to increase the capacity by more than the caller asked
for. Remember, all that's needed to ensure good performance is that we keep the
number of reallocations small, and we do that by always reallocating to a new
buffer that's at least 1.5x the size of the old one. Whether that happens
because we allocate more than the user asked for or because the user happened to
actually ask for a size that's >= 1.5x larger doesn't matter.

[sprang_webrtc, 2016-06-20 09:56:28]

lgtm

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h
File webrtc/base/buffer.h (right):

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode275
webrtc/base/buffer.h:275: EnsureCapacityWithHeadroom(size, true);
On 2016/06/20 09:51:31, kwiberg-webrtc wrote:
> On 2016/06/20 09:27:44, språng wrote:
> > Do we really want with headroom here, as it's an explicit size request?
> 
> It's an explicit *size* request, but the caller doesn't necessarily care about
> *capacity* (except that it has to grow large enough, obviously). My thinking
is
> that callers that want the extra control can use EnsureCapacity(); this makes
it
> harder for callers that don't care to accidentally shoot themselves in the
foot.

Acknowledged.

https://codereview.webrtc.org/2078873005/diff/1/webrtc/base/buffer.h#newcode316
webrtc/base/buffer.h:316: : capacity;
On 2016/06/20 09:51:31, kwiberg-webrtc wrote:
> On 2016/06/20 09:27:44, språng wrote:
> > This seems a little odd. If capacity > 1.5 * capacity_, we expand without
the
> > 1.5x margin? 
> 
> capacity is the requested capacity. If that's >= 1.5 times current capacity,
> there's no need for us to increase the capacity by more than the caller asked
> for. Remember, all that's needed to ensure good performance is that we keep
the
> number of reallocations small, and we do that by always reallocating to a new
> buffer that's at least 1.5x the size of the old one. Whether that happens
> because we allocate more than the user asked for or because the user happened
to
> actually ask for a size that's >= 1.5x larger doesn't matter.

OK, fair enough.

[kwiberg-webrtc, 2016-06-20 10:31:58]

The CQ bit was checked by kwiberg@webrtc.org

[commit-bot: I haz the power, 2016-06-20 10:32:03]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2078873005/1

[commit-bot: I haz the power, 2016-06-20 11:47:43]

Committed patchset #1 (id:1)

[commit-bot: I haz the power, 2016-06-20 11:47:49]

Description was changed from

==========
rtc::Buffer: Grow capacity by at least 1.5x to prevent quadratic behavior

BUG=webrtc:6009
==========

to

==========
rtc::Buffer: Grow capacity by at least 1.5x to prevent quadratic behavior

BUG=webrtc:6009

Committed: https://crrev.com/c853597598198f2d4e57abaaa127d16fe5611410
Cr-Commit-Position: refs/heads/master@{#13214}
==========

[commit-bot: I haz the power, 2016-06-20 11:47:50]

Patchset 1 (id:??) landed as
https://crrev.com/c853597598198f2d4e57abaaa127d16fe5611410
Cr-Commit-Position: refs/heads/master@{#13214}