Bug 172406 – REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer

• Component: New Bugs
• Status: RESOLVED FIXED

[Alex Christensen]

REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer

[Alex Christensen]

Created attachment 310740 [details]
Patch

[Build Bot]

Comment on attachment 310740 [details]
Patch

Attachment 310740 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/3780472

New failing tests:
http/tests/cache/disk-cache/disk-cache-revalidation-new-expire-header.html
http/tests/cache/disk-cache/disk-cache-307-status-code.html
http/tests/cache/disk-cache/disk-cache-404-status-code.html
http/tests/cache/zero-length-xhr.html
http/tests/cache/disk-cache/redirect-chain-limits.html
fetch/closing-while-fetching-blob.html
http/tests/cache/disk-cache/disk-cache-vary-cookie.html

[Build Bot]

Created attachment 310747 [details]
Archive of layout-test-results from ews106 for mac-elcapitan-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews106  Port: mac-elcapitan-wk2  Platform: Mac OS X 10.11.6

[Build Bot]

Comment on attachment 310740 [details]
Patch

Attachment 310740 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/3780454

New failing tests:
http/tests/cache/disk-cache/disk-cache-revalidation-new-expire-header.html
http/tests/cache/disk-cache/disk-cache-204-status-code.html
http/tests/cache/disk-cache/disk-cache-307-status-code.html
http/tests/cache/disk-cache/disk-cache-404-status-code.html
http/tests/cache/zero-length-xhr.html
http/tests/cache/disk-cache/disk-cache-last-modified.html
http/tests/cache/disk-cache/disk-cache-disable.html
http/tests/cache/disk-cache/memory-cache-revalidation-updates-disk-cache.html
http/tests/cache/disk-cache/redirect-chain-limits.html
http/tests/cache/disk-cache/resource-becomes-uncacheable.html
http/tests/cache/disk-cache/disk-cache-vary-cookie.html

[Build Bot]

Created attachment 310752 [details]
Archive of layout-test-results from ews126 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews126  Port: ios-simulator-wk2  Platform: Mac OS X 10.11.6

[Alex Christensen]

Created attachment 310786 [details]
Patch

[Alex Christensen]

Created attachment 310788 [details]
Patch

[Brady Eidson]

Comment on attachment 310788 [details]
Patch

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

> Source/WebCore/loader/TextTrackLoader.cpp:95
> +    // FIXME: Replace this with getSomeData to bring O(n) down to O(log(n))

Any reason to not do this right now...?

[Alex Christensen]

Created attachment 310939 [details]
Patch

[Brady Eidson]

Comment on attachment 310939 [details]
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.

[Alex Christensen]

http://trac.webkit.org/r217260