We're seeing some performance issues in ImageQualityController::objectDestroyed(), which appears to be O(N^2) at least. This is on a version of the IBench test suite.
<rdar://problem/8869495>
Multiple-second pauses! This is quite serious.
Created attachment 79309 [details] Bottom-up shark trace
I don't think it's worse than O(n), it's just that it's getting called for every single RenderBoxModelObject. The linear search through the hash map for all the objects in pairs is kind of gross. One alternative would be to make it a HashMap of HashMaps, with the RenderBoxModelObject as the outer key, and the void* pointer as the inner key. Then we could get rid of the linear search, since we could find all the relevant data for any RBMO in one lookup, and get rid of the second loop since we can just release all the data at once. There was a reason I didn't do this the first time around, but I can't remember what it is now. Another alternative would be to put a flag bit on each RenderBoxModelObject when it gets put in the ImageQualityController, and only call objectDestroyed() if the flag is set. In the sample trace, it's getting called for a TableCell, which is never going to end up in the ImageQualityController. I can't see a free bit anywhere on RBMO, though. :(
(In reply to comment #4) Stephen, an O(n) algorithm that runs once for every object is O(n) * O(n) = O(n^2).
Yes, I understand. I thought he was saying the function itself was O(n^2).
Created attachment 79372 [details] Testing patch This is a rough draft attempt at a fix (not heavily tested) using the HashMap of HashMaps idea. Simon, could you try patch this against your benchmark?
(In reply to comment #4) > The linear search through the hash map for all the objects in pairs is kind of gross. Right. It’s unacceptable. We should have done review- on the original patch because of this. > One alternative would be to make it a HashMap of HashMaps, with the RenderBoxModelObject as the outer key, and the void* pointer as the inner key. We will need to do this. > Another alternative would be to put a flag bit on each RenderBoxModelObject when it gets put in the ImageQualityController, and only call objectDestroyed() if the flag is set. I suspect we will also need to add this bit. We can’t afford an additional hash table lookup for every single destruction of a RenderBoxModelObject. This pattern has come up in the past and we have used the combination of flag bit and hash table for it there. See, for example, the "rare data" map in Node.cpp. There actually is a bit available in RenderObject.h. It claims there are 32 used bits and there are no free bits available, but there are 31 bits used.
Seems a shame to waste a RenderObject bit on this.
(In reply to comment #8) > (In reply to comment #4) > > The linear search through the hash map for all the objects in pairs is kind of gross. > > Right. It’s unacceptable. We should have done review- on the original patch because of this. > > > One alternative would be to make it a HashMap of HashMaps, with the RenderBoxModelObject as the outer key, and the void* pointer as the inner key. > > We will need to do this. > > > Another alternative would be to put a flag bit on each RenderBoxModelObject when it gets put in the ImageQualityController, and only call objectDestroyed() if the flag is set. > > I suspect we will also need to add this bit. > > We can’t afford an additional hash table lookup for every single destruction of a RenderBoxModelObject. Note that before my patches, back in r61340, there was still a lookup for every object, as long as any image draws were outstanding. However, we used to delete the ImageQualityController (then called RenderBoxModelScaleData) when all image draws had expired. If that was acceptable then, we could go back to doing that. It would save having to use a bit, although it would still do the lookup when image draws are outstanding (as it did before).
I verified that there is 1 bit spare on RenderObject, and that RenderBoxModelObject is 64 bytes and has no spare padding. So maybe you'll have to use that bit on RO. I question whether we need the m_isDragging bit in RO. Seems like this could be stored externally.
Created attachment 79434 [details] Patch
(In reply to comment #12) > Created an attachment (id=79434) [details] > Patch This one is a proper patch, with the ImageQualityController deletion as above, a ChangeLog and a modicum of testing.
Created attachment 79451 [details] Patch
(In reply to comment #14) > Created an attachment (id=79451) [details] > Patch Further testing showed that the previous patch regressed the fix introduced in r72282. This version passes that test, although it relies on IntSize(0, 0) being a good "out of band" value. I think this is ok -- visually, it doesn't much matter what we do on a (0, 0) resize. (Sigh. Now I remember why I didn't like using nested HashMaps. AFAICT, if the outer hash map lookup fails, it's impossible to initialize an iterator to the inner hash map to represent "not found", since there's no inner hash map to get the end() of.)
Comment on attachment 79451 [details] Patch Do we have any feel for how often RenderObjects are destroyed while repaints are pending?
(In reply to comment #16) > (From update of attachment 79451 [details]) > Do we have any feel for how often RenderObjects are destroyed while repaints are pending? In short: feel, yes, data, no. I would imagine it would happen a lot for something like iBench, where I'm guessing it tears down the page immediately after drawing it. In real life browsing, not so much.
Comment on attachment 79451 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=79451&action=review How can we measure the performance impact of deleting and recreating the controller? I’ll say review+ even though I have some uncertainties. > Source/WebCore/rendering/RenderBoxModelObject.cpp:147 > + IntSize oldSize = innerMap ? innerMap->get(layer) : IntSize(); How about using a separate bool haveOldSize or isFirstResize instead of treating 0, 0 as a magic value? > Source/WebCore/rendering/RenderBoxModelObject.cpp:170 > - // If this is the first time resizing this image, or its size is the > + // If this is the first time resizing this image, or its size is the Why the change?
(In reply to comment #18) > (From update of attachment 79451 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=79451&action=review > > How can we measure the performance impact of deleting and recreating the controller? Good question. I'm hoping Simon's iBench runs will tell us. > > I’ll say review+ even though I have some uncertainties. > > > Source/WebCore/rendering/RenderBoxModelObject.cpp:147 > > + IntSize oldSize = innerMap ? innerMap->get(layer) : IntSize(); > > How about using a separate bool haveOldSize or isFirstResize instead of treating 0, 0 as a magic value? Good idea; done. > > Source/WebCore/rendering/RenderBoxModelObject.cpp:170 > > - // If this is the first time resizing this image, or its size is the > > + // If this is the first time resizing this image, or its size is the > > Why the change? Mistake; fixed. Thanks for the review.
Created attachment 79639 [details] Patch
I tested the patch on iBench today. Sorry, it took me so long, I was having network issues yesterday that didn't allow for good numbers. The pauses no longer occur and ImageQualityController::objectDestroyed now only counts for .2% of the samples on iBench.
Comment on attachment 79639 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=79639&action=review It’s not good that objectDestroyed shows up on the profile for the iBench HTML test at all, but this is much better than before. > Source/WebCore/ChangeLog:16 > + Fix performance regression in ImageQualityController::objectDestroyed(). > + https://bugs.webkit.org/show_bug.cgi?id=52645 > + > + * rendering/RenderBoxModelObject.cpp: > + (WebCore::ImageQualityController::isEmpty): > + (WebCore::ImageQualityController::removeLayer): > + (WebCore::ImageQualityController::set): > + (WebCore::ImageQualityController::objectDestroyed): > + (WebCore::ImageQualityController::highQualityRepaintTimerFired): > + (WebCore::ImageQualityController::shouldPaintAtLowQuality): > + (WebCore::imageQualityController): > + (WebCore::RenderBoxModelObject::~RenderBoxModelObject): This is not a great change log entry. It doesn’t explain why this is a good change or even say what the change is.
What's the status here? Is it going to land soon?
Sorry for the delay. I've been travelling and am not in my usual office. I'm just going to clean up the ChangeLog a bit as Darin suggested, and hopefully will land it today.
great, thanks! (In reply to comment #24) > Sorry for the delay. I've been travelling and am not in my usual office. I'm just going to clean up the ChangeLog a bit as Darin suggested, and hopefully will land it today.
Committed r76825: <http://trac.webkit.org/changeset/76825>
http://trac.webkit.org/changeset/76825 might have broken GTK Linux 64-bit Debug The following tests are not passing: accessibility/crashing-a-tag-in-map.html css1/box_properties/clear.html css1/box_properties/float.html css1/box_properties/height.html css1/box_properties/width.html css1/formatting_model/height_of_lines.html css1/formatting_model/replaced_elements.html css1/text_properties/vertical_align.html css2.1/t0803-c5501-imrgn-t-00-b-ag.html css2.1/t0803-c5502-mrgn-r-00-c-ag.html css2.1/t0803-c5503-imrgn-b-00-b-a.html css2.1/t0803-c5504-mrgn-l-00-c-ag.html css2.1/t0803-c5505-mrgn-00-b-ag.html css2.1/t0803-c5505-mrgn-03-c-ag.html css2.1/t0804-c5509-padn-l-03-f-g.html css2.1/t0804-c5510-padn-00-b-ag.html css2.1/t0905-c414-flt-01-d-g.html css2.1/t0905-c414-flt-wrap-01-d-g.html css2.1/t0905-c5525-fltclr-00-c-ag.html css2.1/t0905-c5525-fltmrgn-00-c-ag.html
This patch caused a whole bunch of tests to crash on chromium port as well: css1/box_properties/clear.html css1/box_properties/float.html css1/box_properties/height.html css1/box_properties/width.html css1/formatting_model/height_of_lines.html css1/formatting_model/replaced_elements.html css1/text_properties/vertical_align.html css2.1/t0803-c5501-imrgn-t-00-b-ag.html css2.1/t0803-c5502-mrgn-r-00-c-ag.html css2.1/t0803-c5503-imrgn-b-00-b-a.html css2.1/t0803-c5504-mrgn-l-00-c-ag.html css2.1/t0803-c5505-mrgn-00-b-ag.html css2.1/t0803-c5505-mrgn-03-c-ag.html css2.1/t0804-c5509-padn-l-03-f-g.html css2.1/t0804-c5510-padn-00-b-ag.html css2.1/t0905-c414-flt-01-d-g.html css2.1/t0905-c414-flt-wrap-01-d-g.html css2.1/t0905-c5525-fltclr-00-c-ag.html css2.1/t0905-c5525-fltmrgn-00-c-ag.html css2.1/t0905-c5526-fltclr-00-c-ag.html css2.1/t090501-c414-flt-02-d-g.html css2.1/t090501-c414-flt-03-b-g.html css2.1/t090501-c414-flt-ln-01-d-g.html css2.1/t090501-c5525-flt-l-00-b-g.html css2.1/t090501-c5525-flt-r-00-b-g.html css2.1/t1002-c5523-width-00-b-g.html css2.1/t1002-c5523-width-01-b-g.html css2.1/t100304-c43-rpl-bbx-00-d-g.html css2.1/t100304-c43-rpl-bbx-01-d-g.html css2.1/t1004-c43-rpl-bbx-00-d-ag.html css2.1/t1004-c43-rpl-ibx-00-d-ag.html css2.1/t1004-c5524-width-00-b-g.html css2.1/t1005-c5524-width-00-b-g.html css2.1/t1005-c5524-width-01-b-g.html css2.1/t1008-c44-ln-box-00-d-ag.html css2.1/t1008-c44-ln-box-01-d-ag.html css2.1/t1008-c44-ln-box-02-d-ag.html css2.1/t1008-c44-ln-box-03-d-ag.html css2.1/t100801-c544-valgn-00-a-ag.html css2.1/t100801-c544-valgn-01-d-ag.html css2.1/t100801-c544-valgn-02-d-agi.html css2.1/t100801-c544-valgn-03-d-agi.html css2.1/t100801-c544-valgn-04-d-agi.html fast/block/positioning/replaced-inside-fixed-top-bottom.html fast/blockflow/block-level-images.html fast/canvas/canvas-as-image-incremental-repaint.html fast/canvas/canvas-as-image.html fast/css/content-dynamic.html fast/dom/Window/btoa-pnglet.html fast/events/pointer-events-2.html fast/forms/input-appearance-height.html fast/forms/input-type-change.html I'm rolling out the patch.
Any information on what the crash was? The long list of tests has some value, but the backtrace of the crash would be even more helpful.
You can see GTK assertion failures at http://build.webkit.org/results/GTK%20Linux%2032-bit%20Debug/r76827%20(13457)/results.html css1/box_properties/clear.html got this: ASSERTION FAILED: !HashTranslator::equal(KeyTraits::emptyValue(), key) (../../JavaScriptCore/wtf/HashTable.h:465 void WTF::HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) [with T = const void*, HashTranslator = WTF::HashMapTranslator<std::pair<const void*, WebCore::IntSize>, WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, WTF::PtrHash<const void*> >, Key = const void*, Value = std::pair<const void*, WebCore::IntSize>, Extractor = WTF::PairFirstExtractor<std::pair<const void*, WebCore::IntSize> >, HashFunctions = WTF::PtrHash<const void*>, Traits = WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, KeyTraits = WTF::HashTraits<const void*>]) [50151:267:856657279602876:ERROR:process_util_posix.cc(106)] Received signal 11 0 DumpRenderTree 0x00003bba _mh_execute_header + 11194 1 DumpRenderTree 0x005acf73 start + 5831647 2 libSystem.B.dylib 0x95f5c2bb _sigtramp + 43 3 ??? 0xffffffff 0x0 + 4294967295 4 DumpRenderTree 0x013b4fb9 float WebCore::narrowPrecisionToFloat<double>(double) + 393667 5 DumpRenderTree 0x013b5311 float WebCore::narrowPrecisionToFloat<double>(double) + 394523 6 DumpRenderTree 0x013b5360 float WebCore::narrowPrecisionToFloat<double>(double) + 394602 7 DumpRenderTree 0x013aec60 float WebCore::narrowPrecisionToFloat<double>(double) + 368234 8 DumpRenderTree 0x013af532 float WebCore::narrowPrecisionToFloat<double>(double) + 370492 9 DumpRenderTree 0x013af6ba float WebCore::narrowPrecisionToFloat<double>(double) + 370884 10 DumpRenderTree 0x013cc176 float WebCore::narrowPrecisionToFloat<double>(double) + 488320 11 DumpRenderTree 0x013ccd20 float WebCore::narrowPrecisionToFloat<double>(double) + 491306 12 DumpRenderTree 0x0142509d float WebCore::narrowPrecisionToFloat<double>(double) + 852647 13 DumpRenderTree 0x013cc4ac float WebCore::narrowPrecisionToFloat<double>(double) + 489142 14 DumpRenderTree 0x0136333c float WebCore::narrowPrecisionToFloat<double>(double) + 58694 15 DumpRenderTree 0x01369ea3 float WebCore::narrowPrecisionToFloat<double>(double) + 86189 16 DumpRenderTree 0x0136a21d float WebCore::narrowPrecisionToFloat<double>(double) + 87079 17 DumpRenderTree 0x014382fb float WebCore::narrowPrecisionToFloat<double>(double) + 931077 18 DumpRenderTree 0x0143ccc8 float WebCore::narrowPrecisionToFloat<double>(double) + 949970 19 DumpRenderTree 0x0143c768 float WebCore::narrowPrecisionToFloat<double>(double) + 948594 20 DumpRenderTree 0x0143cd96 float WebCore::narrowPrecisionToFloat<double>(double) + 950176 21 DumpRenderTree 0x01430c46 float WebCore::narrowPrecisionToFloat<double>(double) + 900688 22 DumpRenderTree 0x01430fc9 float WebCore::narrowPrecisionToFloat<double>(double) + 901587 23 DumpRenderTree 0x01369291 float WebCore::narrowPrecisionToFloat<double>(double) + 83099 24 DumpRenderTree 0x01369499 float WebCore::narrowPrecisionToFloat<double>(double) + 83619 25 DumpRenderTree 0x01369daf float WebCore::narrowPrecisionToFloat<double>(double) + 85945 26 DumpRenderTree 0x0136a21d float WebCore::narrowPrecisionToFloat<double>(double) + 87079 27 DumpRenderTree 0x01369291 float WebCore::narrowPrecisionToFloat<double>(double) + 83099 28 DumpRenderTree 0x01369499 float WebCore::narrowPrecisionToFloat<double>(double) + 83619 29 DumpRenderTree 0x01369daf float WebCore::narrowPrecisionToFloat<double>(double) + 85945 30 DumpRenderTree 0x0136a21d float WebCore::narrowPrecisionToFloat<double>(double) + 87079 31 DumpRenderTree 0x013df821 float WebCore::narrowPrecisionToFloat<double>(double) + 567851 32 DumpRenderTree 0x013e03c5 float WebCore::narrowPrecisionToFloat<double>(double) + 570831 33 DumpRenderTree 0x013dfa3a float WebCore::narrowPrecisionToFloat<double>(double) + 568388 34 DumpRenderTree 0x013e04b3 float WebCore::narrowPrecisionToFloat<double>(double) + 571069 35 DumpRenderTree 0x012dc39b float WebCore::narrowPrecisionToCGFloat<double>(double) + 5695527 36 DumpRenderTree 0x00e85262 float WebCore::narrowPrecisionToCGFloat<double>(double) + 1144558 37 DumpRenderTree 0x000aacbd start + 579881 38 DumpRenderTree 0x000aad91 start + 580093 39 DumpRenderTree 0x000d95a6 start + 770578 40 DumpRenderTree 0x00057bbc start + 239656 41 DumpRenderTree 0x00057e3a start + 240294 42 DumpRenderTree 0x0004f735 start + 205729 43 DumpRenderTree 0x0004f916 start + 206210 44 DumpRenderTree 0x00039f70 start + 117724 45 DumpRenderTree 0x00039fdb start + 117831 46 DumpRenderTree 0x0005908e start + 244986 47 DumpRenderTree 0x0005912a start + 245142 48 DumpRenderTree 0x0007ba2f start + 386715 49 DumpRenderTree 0x0124e758 float WebCore::narrowPrecisionToCGFloat<double>(double) + 5114852 50 DumpRenderTree 0x0124e8c8 float WebCore::narrowPrecisionToCGFloat<double>(double) + 5115220 51 DumpRenderTree 0x0124e979 float WebCore::narrowPrecisionToCGFloat<double>(double) + 5115397 52 DumpRenderTree 0x01233951 float WebCore::narrowPrecisionToCGFloat<double>(double) + 5004765 53 DumpRenderTree 0x01273f00 float WebCore::narrowPrecisionToCGFloat<double>(double) + 5268364 54 DumpRenderTree 0x0126a2ed float WebCore::narrowPrecisionToCGFloat<double>(double) + 5228409 55 DumpRenderTree 0x0009051d start + 471433 56 DumpRenderTree 0x01a04ee7 webkit::npapi::CarbonPluginWindowTracker::CreateDummyWindowForDelegate(void*) + 398985 57 DumpRenderTree 0x01a222b1 webkit::npapi::CarbonPluginWindowTracker::CreateDummyWindowForDelegate(void*) + 518739 58 DumpRenderTree 0x01a2272b webkit::npapi::CarbonPluginWindowTracker::CreateDummyWindowForDelegate(void*) + 519885 59 DumpRenderTree 0x01a22766 webkit::npapi::CarbonPluginWindowTracker::CreateDummyWindowForDelegate(void*) + 519944 60 DumpRenderTree 0x00584dd7 start + 5667395 61 DumpRenderTree 0x00584f61 start + 5667789 ax: bbadbeef, bx: 13b26f6, cx: 0, dx: 0 di: bfffb848, si: bfffb848, bp: bfffb6b8, sp: bfffb680, ss: 1f, flags: 10286 ip: 13b2744, cs: 17, ds: 1f, es: 1f, fs: 0, gs: 37
http://trac.webkit.org/changeset/76826 is also on the blame list but given the tests in which crash occurred, that change is unlikely the cause.
This change also caused crashes on Leopard: http://build.webkit.org/results/Leopard%20Intel%20Debug%20(Tests)/r76826%20(26653)/results.html
(In reply to comment #30) > ASSERTION FAILED: !HashTranslator::equal(KeyTraits::emptyValue(), key) > (../../JavaScriptCore/wtf/HashTable.h:465 void WTF::HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) [with T = const void*, HashTranslator = WTF::HashMapTranslator<std::pair<const void*, WebCore::IntSize>, WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, WTF::PtrHash<const void*> >, Key = const void*, Value = std::pair<const void*, WebCore::IntSize>, Extractor = WTF::PairFirstExtractor<std::pair<const void*, WebCore::IntSize> >, HashFunctions = WTF::PtrHash<const void*>, Traits = WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, KeyTraits = WTF::HashTraits<const void*>]) This means that someone is calling a function on a hash table with 0 for the key. Either a find, contains, get, or even set or add. If the rest of the backtrace was accurate, we could see exactly which call, but that should be enough to go on.
(In reply to comment #33) > (In reply to comment #30) > > ASSERTION FAILED: !HashTranslator::equal(KeyTraits::emptyValue(), key) > > (../../JavaScriptCore/wtf/HashTable.h:465 void WTF::HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) [with T = const void*, HashTranslator = WTF::HashMapTranslator<std::pair<const void*, WebCore::IntSize>, WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, WTF::PtrHash<const void*> >, Key = const void*, Value = std::pair<const void*, WebCore::IntSize>, Extractor = WTF::PairFirstExtractor<std::pair<const void*, WebCore::IntSize> >, HashFunctions = WTF::PtrHash<const void*>, Traits = WTF::PairHashTraits<WTF::HashTraits<const void*>, WTF::HashTraits<WebCore::IntSize> >, KeyTraits = WTF::HashTraits<const void*>]) > > This means that someone is calling a function on a hash table with 0 for the key. Either a find, contains, get, or even set or add. If the rest of the backtrace was accurate, we could see exactly which call, but that should be enough to go on. I didn't realize that 0 was invalid as a hash key. That's going to be a problem. Basically, the layer in the innerMap is only valid in the background case (only layers have backgrounds). For the non-background image case, the layer is always 0. That pointer is never dereferenced; it's just "data", so I suppose I could use 0x1, or even pass the RenderBoxModelObject address again, as long as it's the same value at lookup time. Sorry for the mess (my bad for only building Release and not Debug).
(In reply to comment #34) > (only layers have backgrounds) "Wait a minute. Strike that. Reverse it."
Created attachment 80369 [details] Patch
(In reply to comment #36) > Created an attachment (id=80369) [details] > Patch This patch is the same as the previous, except that in the non-background image case it passes the Image pointer instead of 0 as the (void*) layer (see RenderImage.cpp).
Committed r76866: <http://trac.webkit.org/changeset/76866>