Accessing the last item in children should be a constant time operation
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 14 Jul 2012 21:38:39 +0000 (21:38 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 14 Jul 2012 21:38:39 +0000 (21:38 +0000)
commit79e8a3a084e593016126d531c2f6451293b65a80
treefbd3fc8c6f69cf7bf51e6251f9c2e2057d5ee361
parent937768ca916be66c35d7358ed006a7c3a1971b45
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@122672 268f45cc-cd09-0410-ab3c-d52691b4dbfc
LayoutTests/ChangeLog
LayoutTests/perf/htmlcollection-last-item-expected.txt [new file with mode: 0644]
LayoutTests/perf/htmlcollection-last-item.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/html/HTMLCollection.cpp
Source/WebCore/html/HTMLCollection.h