REGRESSION(r215686): O(n^2) algorithm in CachedRawResource::addDataBuffer
Created attachment 310740 [details] Patch
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
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
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
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
Created attachment 310786 [details] Patch
Created attachment 310788 [details] Patch
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...?
Created attachment 310939 [details] Patch
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.
http://trac.webkit.org/r217260