haikuwebkit/LayoutTests/perf/htmlcollection-backwards-it...

29 lines
685 B
HTML
Raw Permalink Normal View History

Iterating backwards over HTMLCollection is O(n^2) https://bugs.webkit.org/show_bug.cgi?id=91306 Reviewed by Anders Carlsson. Source/WebCore: Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter. Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now, added a new boolean flag indicating whether a given HTML collection supports itemBefore or not, and left those HTML collections that override itemAfter alone. This also paves our way to share more code between DynamicNodeList and HTMLCollection. Test: perf/htmlcollection-backwards-iteration.html * dom/DynamicNodeList.h: (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType. (WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added. (DynamicNodeListCacheBase): (WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that we can. * html/HTMLAllCollection.cpp: (WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override itemAfter. * html/HTMLCollection.cpp: (WebCore::HTMLCollection::HTMLCollection): (WebCore::HTMLCollection::create): (WebCore::isAcceptableElement): Made it a static local function instead of a static member. (WebCore::nextNode): Templatized. (WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized. (WebCore::HTMLCollection::itemBefore): Added. (WebCore::HTMLCollection::itemAfter): (WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset the item cache to the first item. We obviously do if the cache is invalid. If the target offset is after the cached offset, then we shouldn't go back regardless of availability of itemBefore. Otherwise, we go back to the first item iff itemBefore is not available or the distance from the cached offset to the target offset is greater than the target offset itself. (WebCore::HTMLCollection::length): (WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere. (WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate nodes backwards using itemBefore. Once we're in this branch, we should always find a matching item since the target offset was less than the cached offset, and offsets are non-negative. If we had ever reached the end of the loop without finding an item, it indicates that the cache has been invalid and we have some serious bug elsewhere. * html/HTMLCollection.h: (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase): (HTMLCollection): * html/HTMLOptionsCollection.cpp: (WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't override itemAfter. * html/HTMLFormCollection.cpp: (WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides itemAfter. * html/HTMLNameCollection.cpp: (WebCore::HTMLNameCollection::HTMLNameCollection): Ditto. * html/HTMLPropertiesCollection.cpp: (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection): * html/HTMLTableRowsCollection.cpp: (WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection): LayoutTests: Add an asymptotic time complexity test. * perf/htmlcollection-backwards-iteration-expected.txt: Added. * perf/htmlcollection-backwards-iteration.html: Added. Canonical link: https://commits.webkit.org/109132@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@122660 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-07-14 07:08:55 +00:00
<!DOCTYPE html>
<body>
<div id="container" style="display: none;"></div>
<script src="../resources/magnitude-perf.js"></script>
<script>
var container = document.getElementById('container');
function setupFunction(magnitude)
{
container.innerHTML = '';
for (var i = 0; i < magnitude; i++)
container.appendChild(document.createElement('div'));
}
function test(magnitude)
{
var children = container.children;
for (var i = children.length; i > 0;i--)
children[i - 1].class = 'hi';
}
Magnitude.description("Tests that iterating over HTMLCollection backwards is linear.");
Magnitude.run(setupFunction, test, Magnitude.LINEAR);
</script>
</body>
</html>