Summary: | Iterating backwards over HTMLCollection is O(n^2) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Ryosuke Niwa <rniwa> | ||||||||
Component: | DOM | Assignee: | Ryosuke Niwa <rniwa> | ||||||||
Status: | RESOLVED FIXED | ||||||||||
Severity: | Normal | CC: | darin, haraken, kling, koivisto, ojan, sam | ||||||||
Priority: | P2 | ||||||||||
Version: | 528+ (Nightly build) | ||||||||||
Hardware: | Unspecified | ||||||||||
OS: | Unspecified | ||||||||||
Bug Depends on: | |||||||||||
Bug Blocks: | 89919, 91320, 91334 | ||||||||||
Attachments: |
|
Description
Ryosuke Niwa
2012-07-13 19:05:16 PDT
Created attachment 152400 [details]
Fixes the bug
Comment on attachment 152400 [details] Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=152400&action=review > Source/WebCore/html/HTMLCollection.cpp:245 > + return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traverseNextNode(base); Oops, this won't fly, will it? Created attachment 152402 [details]
Fixed a bug
Created attachment 152403 [details]
demo
Open it on Safari/Chrome without my patch. It'll take 4s or so to run. With my patch, it takes 5ms.
Comment on attachment 152402 [details] Fixed a bug View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review > Source/WebCore/html/HTMLCollection.cpp:321 > - if (!isItemCacheValid() || cachedItemOffset() > index) { > + if (shouldSearchFromFirstItem(offset)) { Now, there's one more optimization we can implement when the length cache is available and the distance to the last item is less than the distance to the cached item but we can implement that optimization in a follow up patch instead. Comment on attachment 152402 [details] Fixed a bug View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review > Source/WebCore/html/HTMLCollection.cpp:240 > +template<bool forward> Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter? Comment on attachment 152402 [details] Fixed a bug View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review > Source/WebCore/html/HTMLCollection.cpp:245 > + if (forward) > + return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base); > + return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base); This is one of the cases where i prefer if (forward) return ... else return ... Committed r122660: <http://trac.webkit.org/changeset/122660> (In reply to comment #6) > (From update of attachment 152402 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review > > > Source/WebCore/html/HTMLCollection.cpp:240 > > +template<bool forward> > > Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter? I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward. (In reply to comment #9) > (In reply to comment #6) > > (From update of attachment 152402 [details] [details]) > > View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review > > > > > Source/WebCore/html/HTMLCollection.cpp:240 > > > +template<bool forward> > > > > Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter? > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward. This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated. (In reply to comment #10) > (In reply to comment #9) > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward. > > This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated. The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down. (In reply to comment #11) > (In reply to comment #10) > > (In reply to comment #9) > > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward. > > > > This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated. > > The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down. I don't understand this last sentence. If it slows us down enough to matter, it should show up in benchmarks or profiles. This is a different case than something like ref/deref where the cost is scattered throughout the entire codebase and thus would never show up in a profile (although, it does show up in benchmarks!). When the cost is all in a single loop (on the javascript side), you should be able to see something significant. I'm pretty sure dromaeo benchmarks hammer this code pretty hard. I believe you that this code is performance critical, I just don't think we should complicate the code in places where we haven't proven that it matters. (In reply to comment #12) > (In reply to comment #11) > > (In reply to comment #10) > > > (In reply to comment #9) > > > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward. > > > > > > This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated. > > > > The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down. > > I don't understand this last sentence. If it slows us down enough to matter, it should show up in benchmarks or profiles. The equivalent code in DynamicNodeList shows up in profile result on Dromaeo. > This is a different case than something like ref/deref where the cost is scattered throughout the entire codebase and thus would never show up in a profile (although, it does show up in benchmarks!). It's exactly like that. Adding a single function call is usually cheap but if you keep adding lots of function calls, then it'll eventually slow us down. |