[webkit-reviews] review granted: [Bug 172406] REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer : [Attachment 310939] Patch

[bugzilla-daemon at webkit.org]

Brady Eidson <beidson at apple.com> has granted Alex Christensen
<achristensen at apple.com>'s request for review:
Bug 172406: REGRESSION(r215686): O(n^2) algorithm in
CachedRawResource::addDataBuffer
https://bugs.webkit.org/show_bug.cgi?id=172406

Attachment 310939: Patch

https://bugs.webkit.org/attachment.cgi?id=310939&action=review




--- Comment #10 from Brady Eidson <beidson at apple.com> ---
Comment on attachment 310939
  --> https://bugs.webkit.org/attachment.cgi?id=310939
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=310939&action=review

> Source/WebCore/ChangeLog:17
> +	   CachedRawResource::calculateIncrementalDataChunk was calling
SharedBuffer::data each time the data
> +	   was appended to the SharedBuffer.  This causes the data to be copied
from two segments to one segment,
> +	   which causes the O(n^2) behavior I was worried about in r215686. 
These append/data/append/data calls
> +	   used to cause O(1) copies per byte which was amortized because of
the exponential growth of the buffer.
> +	   After this change, there should be 0 copies per byte here, and
instead a O(log(n)) binary search in the
> +	   call to std::upper_bound to find the next segment of data with a
given starting location in the SharedBuffer.
> +	   We need to store the additional information of the offsets of the
beginnings of the segments in a
> +	   SharedBuffer. This doesn't asymptotically increase our memory usage,
but it does allow us to asymptotically
> +	   decrease the amount of time it takes to find data at a given offset
in a SharedBuffer from O(n) to O(log(n)).

Some of this comment is double spaced, and some is not.

None should be.