Title: [122672] trunk
- Revision
- 122672
- Author
- [email protected]
- Date
- 2012-07-14 14:38:39 -0700 (Sat, 14 Jul 2012)
Log Message
Accessing the last item in children should be a constant time operation
https://bugs.webkit.org/show_bug.cgi?id=91320
Reviewed by Ojan Vafai.
Source/WebCore:
Traverse nodes from the last item when the target offset we're looking for is closer to the last item
than to the cached item. e.g. if the cached item was at offset 0 in the collection and length was 100,
we should not be looking for the item at offset 95 from the cached item.
Note that this trick can be only used in HTML collection that supports itemBefore and when the length
cache is available.
Also broke shouldSearchFromFirstItem into smaller logical pieces to clarify the intents.
Test: perf/htmlcollection-last-item.html
* html/HTMLCollection.cpp:
(WebCore):
(WebCore::HTMLCollection::isLastItemCloserThanLastOrCachedItem):
(WebCore::HTMLCollection::isFirstItemCloserThanCachedItem):
(WebCore::HTMLCollection::item):
* html/HTMLCollection.h:
(HTMLCollection):
LayoutTests:
Added an asymptotic time complexity test.
* perf/htmlcollection-last-item-expected.txt: Added.
* perf/htmlcollection-last-item.html: Added.
Modified Paths
Added Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (122671 => 122672)
--- trunk/LayoutTests/ChangeLog 2012-07-14 21:34:10 UTC (rev 122671)
+++ trunk/LayoutTests/ChangeLog 2012-07-14 21:38:39 UTC (rev 122672)
@@ -1,3 +1,15 @@
+2012-07-14 Ryosuke Niwa <[email protected]>
+
+ Accessing the last item in children should be a constant time operation
+ https://bugs.webkit.org/show_bug.cgi?id=91320
+
+ Reviewed by Ojan Vafai.
+
+ Added an asymptotic time complexity test.
+
+ * perf/htmlcollection-last-item-expected.txt: Added.
+ * perf/htmlcollection-last-item.html: Added.
+
2012-07-14 Allan Sandfeld Jensen <[email protected]>
[Tests] Unskip not failing tests previously relying on LTC::nodesFromRect implementation
Added: trunk/LayoutTests/perf/htmlcollection-last-item-expected.txt (0 => 122672)
--- trunk/LayoutTests/perf/htmlcollection-last-item-expected.txt (rev 0)
+++ trunk/LayoutTests/perf/htmlcollection-last-item-expected.txt 2012-07-14 21:38:39 UTC (rev 122672)
@@ -0,0 +1,3 @@
+Tests that accessing the last item in children HTMLCollection is a constant time operation.
+PASS
+
Added: trunk/LayoutTests/perf/htmlcollection-last-item.html (0 => 122672)
--- trunk/LayoutTests/perf/htmlcollection-last-item.html (rev 0)
+++ trunk/LayoutTests/perf/htmlcollection-last-item.html 2012-07-14 21:38:39 UTC (rev 122672)
@@ -0,0 +1,27 @@
+<!DOCTYPE html>
+<body>
+<div id="container" style="display: none;"></div>
+<script src=""
+<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)
+{
+ container.children[0].class = 'first item';
+ container.children[container.children.length - 1].class = 'last item';
+}
+
+Magnitude.description("Tests that accessing the last item in children HTMLCollection is a constant time operation.");
+Magnitude.run(setupFunction, test, Magnitude.CONSTANT);
+
+</script>
+</body>
+</html>
Modified: trunk/Source/WebCore/ChangeLog (122671 => 122672)
--- trunk/Source/WebCore/ChangeLog 2012-07-14 21:34:10 UTC (rev 122671)
+++ trunk/Source/WebCore/ChangeLog 2012-07-14 21:38:39 UTC (rev 122672)
@@ -1,3 +1,29 @@
+2012-07-14 Ryosuke Niwa <[email protected]>
+
+ Accessing the last item in children should be a constant time operation
+ https://bugs.webkit.org/show_bug.cgi?id=91320
+
+ Reviewed by Ojan Vafai.
+
+ Traverse nodes from the last item when the target offset we're looking for is closer to the last item
+ than to the cached item. e.g. if the cached item was at offset 0 in the collection and length was 100,
+ we should not be looking for the item at offset 95 from the cached item.
+
+ Note that this trick can be only used in HTML collection that supports itemBefore and when the length
+ cache is available.
+
+ Also broke shouldSearchFromFirstItem into smaller logical pieces to clarify the intents.
+
+ Test: perf/htmlcollection-last-item.html
+
+ * html/HTMLCollection.cpp:
+ (WebCore):
+ (WebCore::HTMLCollection::isLastItemCloserThanLastOrCachedItem):
+ (WebCore::HTMLCollection::isFirstItemCloserThanCachedItem):
+ (WebCore::HTMLCollection::item):
+ * html/HTMLCollection.h:
+ (HTMLCollection):
+
2012-07-14 Mark Rowe <[email protected]>
Fix the Windows build.
Modified: trunk/Source/WebCore/html/HTMLCollection.cpp (122671 => 122672)
--- trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-14 21:34:10 UTC (rev 122671)
+++ trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-14 21:38:39 UTC (rev 122672)
@@ -271,18 +271,25 @@
{
return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
}
-
-bool ALWAYS_INLINE HTMLCollection::shouldSearchFromFirstItem(unsigned offset) const
+
+bool ALWAYS_INLINE HTMLCollection::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
{
+ ASSERT(isLengthCacheValid());
+ unsigned distanceFromLastItem = cachedLength() - offset;
if (!isItemCacheValid())
- return true;
+ return distanceFromLastItem < offset;
- ASSERT(offset != cachedItemOffset());
- if (offset > cachedItemOffset())
+ return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
+}
+
+bool ALWAYS_INLINE HTMLCollection::isFirstItemCloserThanCachedItem(unsigned offset) const
+{
+ ASSERT(isItemCacheValid());
+ if (cachedItemOffset() < offset)
return false;
unsigned distanceFromCachedItem = cachedItemOffset() - offset;
- return !supportsItemBefore() || offset < distanceFromCachedItem;
+ return offset < distanceFromCachedItem;
}
unsigned HTMLCollection::length() const
@@ -319,7 +326,14 @@
static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
#endif
- if (shouldSearchFromFirstItem(offset)) {
+ if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) {
+ // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection
+ unsigned unusedOffsetInArray = 0;
+ Node* lastItem = itemBefore(unusedOffsetInArray, 0);
+ ASSERT(!unusedOffsetInArray);
+ ASSERT(lastItem);
+ setItemCache(lastItem, cachedLength() - 1, 0);
+ } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) {
unsigned offsetInArray = 0;
Node* firstItem = itemAfter(offsetInArray, 0);
if (!firstItem) {
@@ -328,10 +342,11 @@
}
setItemCache(firstItem, 0, offsetInArray);
ASSERT(!cachedItemOffset());
- if (!offset)
- return cachedItem();
}
+ if (cachedItemOffset() == offset)
+ return cachedItem();
+
return itemBeforeOrAfterCachedItem(offset);
}
Modified: trunk/Source/WebCore/html/HTMLCollection.h (122671 => 122672)
--- trunk/Source/WebCore/html/HTMLCollection.h 2012-07-14 21:34:10 UTC (rev 122671)
+++ trunk/Source/WebCore/html/HTMLCollection.h 2012-07-14 21:38:39 UTC (rev 122672)
@@ -115,7 +115,8 @@
bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
Element* itemBefore(unsigned& offsetInArray, Element*) const;
- bool shouldSearchFromFirstItem(unsigned offset) const;
+ bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
+ bool isFirstItemCloserThanCachedItem(unsigned offset) const;
Element* itemBeforeOrAfterCachedItem(unsigned offset) const;
RefPtr<Node> m_base;
_______________________________________________
webkit-changes mailing list
[email protected]
http://lists.webkit.org/mailman/listinfo/webkit-changes
