In SVGSMILElement::findInstanceTime function: FIXME: This searches from the beginning which is inefficient. The list is usually not long (one entry in common cases) but you can construct a case where it does grow.
Created attachment 97430 [details] Speed up SVGSMILElement::findInstanceTime Speed up SVGSMILElement::findInstanceTime because the previous searches from the beginning was not efficient. Replace the linear search to binary search on ordered list.
Comment on attachment 97430 [details] Speed up SVGSMILElement::findInstanceTime View in context: https://bugs.webkit.org/attachment.cgi?id=97430&action=review Nice that you're tackling this, some comments that lead to r-: > Source/WebCore/ChangeLog:10 > + Speed up SVGSMILElement::findInstanceTime because > + the previous searches from the beginning was not efficient. > + Replace the linear search to binary search on ordered list. > + https://bugs.webkit.org/show_bug.cgi?id=61025 > + > + No new tests. (OOPS!) This has to be changed like this: Replace the linear... http:// Speed up .... No new tests this is only a performance tweak. > Source/WebCore/svg/animation/SVGSMILElement.cpp:628 > + if (right < 0) > + return (beginOrEnd == Begin) ? SMILTime::unresolved() : SMILTime::indefinite(); I'd move that upwards: int sizeOfList = list.size(); if (!sizeOfList) return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); .. No braces needed around the condition of the ternary operator. Also common conclusion seems to omit the const from sizeOfList, we don't do that in other places, though I see the benefit. > Source/WebCore/svg/animation/SVGSMILElement.cpp:632 > + ASSERT(0 <= center && center < sizeOfList); Don't use && conditions in assertions, it makes it hard to figure out what exactly happened without further debugging. ASSERT(center >= 0); ASSERT(center < sizeOfList); > Source/WebCore/svg/animation/SVGSMILElement.cpp:641 > + if (time > minimumTime) { > + if (center > 0) { > + right = center - 1; > + center = (left + right) / 2; Hm, I find it very unfortunate that you have to provide your own binary search algorithm. It turns out there's a binarySearch template in wtf/StdLibExtras.h that could be used for this purpose, when tweaking it a little: // Binary search algorithm, calls extractKey on pre-sorted elements in array, // compares result with key (KeyTypes should be comparable with '--', '<', '>'). // Optimized for cases where the array contains the key, checked by assertions. template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)> inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key) The problem here is that this algorithm assumes that the key is always present in the array. That could be changed. If that's done, we could simple use: int sizeOfList = list.size(); if (!sizeOfList) return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); SMILTime* result = binarySearch<SMILTime, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime); ... What do you think? It might be worth to try to re-use an existing binary search algorithm, no?
Created attachment 98707 [details] Speed up SVGSMILElement::findInstanceTime
Comment on attachment 98707 [details] Speed up SVGSMILElement::findInstanceTime Attachment 98707 [details] did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/8946304
Comment on attachment 98707 [details] Speed up SVGSMILElement::findInstanceTime Attachment 98707 [details] did not pass gtk-ews (gtk): Output: http://queues.webkit.org/results/8944342
Comment on attachment 98707 [details] Speed up SVGSMILElement::findInstanceTime View in context: https://bugs.webkit.org/attachment.cgi?id=98707&action=review Almost there, still some tweaks to do, but much better than the last one! > Source/JavaScriptCore/wtf/StdLibExtras.h:128 > // Optimized for cases where the array contains the key, checked by assertions. This comment is not true anymore. > Source/JavaScriptCore/wtf/StdLibExtras.h:130 > +inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, bool isElementContains) Please add sth like: enum BinarySearchMode { KeyMustBePresentInArray, KeyMustNotBePresentInArray }; and switch from bool isElementContains, to "BinarySearchMode mode = KeyMustBePresentInArray". This way you don't need to touch any other place that used binarySearch before, and it's cleaner than a boolean param. > Source/JavaScriptCore/wtf/StdLibExtras.h:133 > { > // The array must contain at least one element (pre-condition, array does conatin key). > // If the array only contains one element, no need to do the comparison. This can be rephrased as well, and you can fix the existing conatin typo. > Source/JavaScriptCore/wtf/StdLibExtras.h:152 > // 'size' should never reach zero. Comment is also not true anymore for isElementContains=false. > Source/JavaScriptCore/wtf/StdLibExtras.h:157 > // If we reach this point we've chopped down to one element, no need to check it matches Ditto. > Source/JavaScriptCore/wtf/StdLibExtras.h:162 > + if (isElementContains) > + ASSERT(size == 1); > + > + if (isElementContains) > + ASSERT(key == extractKey(&array[0])); You can combine these if branches into one. > Source/WebCore/ChangeLog:11 > + No new tests this is only a performance tweak. one space too much. > Source/WebCore/svg/animation/SVGSMILElement.cpp:620 > +{ Style, must be "* position". > Source/WebCore/svg/animation/SVGSMILElement.cpp:633 > + int indexOfResult = (((unsigned)result) - ((unsigned)list.begin())) / sizeof(SMILTime); C-style casts shouldn't be used. Why do you need these casts? The type is also wrong, if you cast then to ptrdiff_t, but I think it's unncessary. > Source/WebCore/svg/animation/SVGSMILElement.cpp:636 > + indexOfResult++; Use postfix ++indexResult. > Source/WebCore/svg/animation/SVGSMILElement.cpp:638 > + if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin) You should add an assert before this line: ASSERT(indexOfResult < sizeOfList). > Source/WebCore/svg/animation/SVGSMILElement.cpp:639 > + // "The special value "indefinite" does not yield an instance time in the begin list." You can move the comment before the if condition, as its our common style. > Source/WebCore/svg/animation/SVGSMILElement.cpp:652 > + indexOfResult++; Use postfix ++indexResult. > Source/WebCore/svg/animation/SVGSMILElement.cpp:659 > + if (indexOfResult + 1 < sizeOfList - 1) { > + return list[indexOfResult + 1]; > } Braces are not needed.
Created attachment 98887 [details] Speed up SVGSMILElement::findInstanceTime
Comment on attachment 98887 [details] Speed up SVGSMILElement::findInstanceTime View in context: https://bugs.webkit.org/attachment.cgi?id=98887&action=review Almost r+, but the ChangeLog is wrong :( > Source/JavaScriptCore/ChangeLog:8 > + Added a new parameter to StdlibExtras.h::binarySerarch function, > + for the case when not sure that the array contains the key value. > + It is needed for an svg function. > + https://bugs.webkit.org/show_bug.cgi?id=61025 ChangeLog still is wrong, please fix it first.
Created attachment 98900 [details] Speed up SVGSMILElement::findInstanceTime
Comment on attachment 98900 [details] Speed up SVGSMILElement::findInstanceTime View in context: https://bugs.webkit.org/attachment.cgi?id=98900&action=review > Source/JavaScriptCore/ChangeLog:8 > + Add a new parameter to StdlibExtras.h::binarySerarch function > + to also handle cases when the array does not contain the key value. > + This is needed for an svg function. > + https://bugs.webkit.org/show_bug.cgi?id=61025 This is the part which is wrong. The WebKit ChangeLog style is: Reviewed by NOBODY (OOPS!). Speed up SVGSMILElement::findInstanceTime https://bugs.webkit.org/show_bug.cgi?id=61025 Your text goes here. > Source/WebCore/ChangeLog:11 > + > + Replace the linear search to binary search on ordered list. > + https://bugs.webkit.org/show_bug.cgi?id=61025 > + > + Speed up SVGSMILElement::findInstanceTime because > + the previous searches from the beginning was not efficient. > + > + No new tests this is only a performance tweak. This has the correct ChangeLog style bug the wrong bug title the title is "Speed up SVGSMILElement::findInstanceTime" not "Replace the linear search to binary search.." -- that should go into the description text.
Please use: Tools/Scripts/prepare-ChangeLog --bug <bug number> --email=<your email address> This will create the ChangeLog for you. You just have to fill the description.
Created attachment 99241 [details] Speed up SVGSMILElement::findInstanceTime
Comment on attachment 99241 [details] Speed up SVGSMILElement::findInstanceTime Good job, r=me!
Comment on attachment 99241 [details] Speed up SVGSMILElement::findInstanceTime Clearing flags on attachment: 99241 Committed r90102: <http://trac.webkit.org/changeset/90102>
All reviewed patches have been landed. Closing bug.
This caused lots of assertion failures, so I rolled it out. (See bug 63714 and duplicates.)
Created attachment 100452 [details] Fix for the out of index error while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1) This loop supposes that our list has at least two elements, so we have to check it.
Comment on attachment 100452 [details] Fix for the out of index error Looks good, let's retry.
Committed r90811: <http://trac.webkit.org/changeset/90811>
This is still causing assertion failures: http://build.webkit.org/results/SnowLeopard%20Intel%20Leaks/r90811%20(18017)/results.html http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html
Reverted r90811 for reason: Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime Committed r90812: <http://trac.webkit.org/changeset/90812>
(In reply to comment #21) > Reverted r90811 for reason: > > Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime > > Committed r90812: <http://trac.webkit.org/changeset/90812> Does it just affect Mac or why isn't it recognized before uploading the patch to the bug report?
(In reply to comment #22) > Does it just affect Mac No. Note that I linked to <http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html> as well, which is from the Windows XP Debug (Tests) bot (as the URL says). > or why isn't it recognized before uploading the patch to the bug report? The Mac and Windows EWS bots don't run tests.
(In reply to comment #23) > (In reply to comment #22) > > Does it just affect Mac > > No. Note that I linked to <http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html> as well, which is from the Windows XP Debug (Tests) bot (as the URL says). > > > or why isn't it recognized before uploading the patch to the bug report? > > The Mac and Windows EWS bots don't run tests. Ok, but the normal process should be creating a debug build and test changes locally. Even more when the patch got rolled out before. Thats why I wondered if it was just recognizable on Mac. But when you say that it happens on Win, it should happen on Qt as well.
Created attachment 100792 [details] Fix for the out of index error The reason of the previous assertions is the converse order of the conditions. if (list[indexOfResult] < minimumTime && sizeOfList - 1 > indexOfResult) Here the first part was evaluated first even if the second part wasn't true (which is responsible for the right indexing). So what we should simple do is just change them.
Any comment would be welcomed. :) The red style bot isn't related to this patch. I guess was an internal error of ews, but I can resend the patch if it's needed.
The modified patch was tested on ubuntu-lucid-x86 environment, and it did not cause any regression.
...on chromium platform.
Comment on attachment 100792 [details] Fix for the out of index error r=me again :-)
Committed r93039: <http://trac.webkit.org/changeset/93039>