Performance fix for H264 RBSP parsing.

Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

R=pbos@webrtc.org
TBR=mflodman@webrtc.org
BUG=

Committed: https://crrev.com/1642620a7d9fef7c1dca3bb0d7b172debe3b3d4c
Cr-Commit-Position: refs/heads/master@{#13167}

[sprang_webrtc, 2016-06-16 12:15:42]

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

[pbos-webrtc, 2016-06-16 12:18:31]

lgtm, can you file a bug for this not being amortized constant?

[sprang_webrtc, 2016-06-16 12:18:49]

The CQ bit was checked by sprang@webrtc.org

[commit-bot: I haz the power, 2016-06-16 12:18:58]

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

[commit-bot: I haz the power, 2016-06-16 12:30:27]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-06-16 12:30:28]

Try jobs failed on following builders:
  ios_arm64_rel on tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/ios_arm64_rel/builds/10559)

[sprang_webrtc, 2016-06-16 13:24:35]

sprang@webrtc.org changed reviewers:
+ mflodman@webrtc.org

[sprang_webrtc, 2016-06-16 13:24:35]

+mflodman as owner for webrtc/base

[sprang_webrtc, 2016-06-16 13:47:47]

Description was changed from

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

BUG=
==========

to

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

TBR=mflodman@webrtc.org
BUG=
==========

[sprang_webrtc, 2016-06-16 13:55:03]

Description was changed from

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

TBR=mflodman@webrtc.org
BUG=
==========

to

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

R=pbos@webrtc.org
TBR=mflodman@webrtc.org
BUG=

Committed:
https://chromium.googlesource.com/external/webrtc/+/1642620a7d9fef7c1dca3bb0d...
==========

[sprang_webrtc, 2016-06-16 13:55:04]

Committed patchset #2 (id:20001) manually as
1642620a7d9fef7c1dca3bb0d7b172debe3b3d4c (presubmit successful).

[commit-bot: I haz the power, 2016-06-16 13:55:06]

Description was changed from

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

R=pbos@webrtc.org
TBR=mflodman@webrtc.org
BUG=

Committed:
https://chromium.googlesource.com/external/webrtc/+/1642620a7d9fef7c1dca3bb0d...
==========

to

==========
Performance fix for H264 RBSP parsing.

An rtc::Buffer is used to write output of RBSP parsing, usually one byte
at a time. It turns out that container will then expand its capacity one
byte at a time, for each byte reallocating the whole buffer and copying
the contents over, turning this into an O(n^2) operation.

Fix is for now only to preallocate the container storage. Longer term, I
think we should mull over if we really need custom containers...

R=pbos@webrtc.org
TBR=mflodman@webrtc.org
BUG=

Committed: https://crrev.com/1642620a7d9fef7c1dca3bb0d7b172debe3b3d4c
Cr-Commit-Position: refs/heads/master@{#13167}
==========

[tommi, 2016-06-16 21:13:30]

wrt to custom containers, I think that preallocating is still appropriate.  Even
if there's an algorithm that reduces the amount of reallocations but is still
guesswork, if we already know how much we'll need, allocating once will beat any
such algorithm.

[sprang_webrtc, 2016-06-17 07:46:58]

On 2016/06/16 21:13:30, tommi-webrtc wrote:
> wrt to custom containers, I think that preallocating is still appropriate. 
Even
> if there's an algorithm that reduces the amount of reallocations but is still
> guesswork, if we already know how much we'll need, allocating once will beat
any
> such algorithm.

Try, preallocating is always preferable, but it's still very dangerous to just
assume that this will always be done and seriously degrade performance
otherwise.
I've filed https://bugs.chromium.org/p/webrtc/issues/detail?id=6009

As for my comment about containers, that was just a general remark in the
context
of moving away from our own implementations to stl things where it makes sense,
such as scoped_ptr -> unique_ptr. Note sure what's new with std::vector et al

[pbos-webrtc, 2016-06-17 08:30:40]

On 2016/06/17 07:46:58, språng wrote:
> On 2016/06/16 21:13:30, tommi-webrtc wrote:
> > wrt to custom containers, I think that preallocating is still appropriate. 
> Even
> > if there's an algorithm that reduces the amount of reallocations but is
still
> > guesswork, if we already know how much we'll need, allocating once will beat
> any
> > such algorithm.
> 
> Try, preallocating is always preferable, but it's still very dangerous to just
> assume that this will always be done and seriously degrade performance
> otherwise.
> I've filed https://bugs.chromium.org/p/webrtc/issues/detail?id=6009
> 
> As for my comment about containers, that was just a general remark in the
> context
> of moving away from our own implementations to stl things where it makes
sense,
> such as scoped_ptr -> unique_ptr. Note sure what's new with std::vector et al

If we don't do 2x growth, then I think it should crash on AppendData if that's
out of bounds for the stored capacity, or log serious warnings.