On 10/18/13 3:11 PM, Tab Atkins Jr. wrote:
There's no perf boost available for searching by id on an arbitrary
element. The reason you may get a better perf for the normal
functions is that documents cache a map from id->element on
themselves, so you just have to do a fast hash-lookup. Arbitrary
elements don't have this map (it would be way too much memory cost),
so it'll fall back to a standard tree search, exactly as a
querySelector would.
Tab, you keep saying that. Let's try science instead of guessing.
Performance of getting an element by ID depends on whether you have to
do the following:
1) Perform string concatenation (like '#'+foo) to get the string to pas
to the browser.
2) Walk an entire subtree (this can be avoided by using the
id-to-element-list hash and then checking the results to see if they
match, in cases when the root of the search is in the document).
3) Do complicated selector checking while walking the tree.
4) Probably other factors.
Luckily, we have SVGSVGElement.prototype.getElementById available to
compare to Element.prototype.querySelector. We also have at least two
distinct implementations (Chrome and Firefox are the ones I tried), and
luckily some of them are open-source so we can examine the impact of
different implementation strategies.
With that in mind, I wrote up a testcase [1] to test the cases that do
and do not require a string concatenation for the querySelector call
(see item 1 in list above), in and out of the document (see item 2 in
list above). I used a fairly large subtree that needs walking (1000
elements), but you can modify the testcase to your heart's content.
I then tested it in three implementations: Chrome (which I'm treating as
a black-box for now), stock Firefox (in which
SVGSVGElement.prototype.getElementById in fact calls querySelector
internally, after CSS-escaping the input and whatnot) and a modified
Firefox [2], in which SVGSVGElement.prototype.getElementById just does a
naive tree-walk with no attempt to fast-path the in-document case. I
also included document.getElementById as a control. The numbers are as
follows, where all numbers are nanoseconds per call on my hardware.
Note that for lower iteration counts the effects of running in slower
JIT levels might also pop up; those shouldn't affect things by more than
10ns or so per loop iteration in this case, I expect.
Chrome:
document.getElementById: 55
In-tree querySelector: 220
In-tree querySelector, no string concat: 100
In-tree getElementById: 55
Out-of-tree querySelector: 2115
Out-of-tree querySelector, no string concat: 1995
Out-of-tree getElementById: 270
Stock Firefox:
document.getElementById: 60
In-tree querySelector: 140
In-tree querySelector, no string concat: 130
In-tree getElementById: 185
Out-of-tree querySelector: 905
Out-of-tree querySelector, no string concat: 910
Out-of-tree getElementById: 975
Modified Firefox:
document.getElementById: 60
In-tree querySelector: 125
In-tree querySelector, no string concat: 120
In-tree getElementById: 215
Out-of-tree querySelector: 885
Out-of-tree querySelector, no string concat: 880
Out-of-tree getElementById: 205
So it looks to me like in practice Element.getElementById could be quite
a bit faster than the equivalent querySelector call, for both the
in-tree case (where both can avoid walking the tree) and the out-of-tree
case (where both need to walk the tree).
Food for thought.
-Boris
[1] The testcase:
<!DOCTYPE html>
<script>
document.write("<svg id='root' width='0' height='0'>");
for (var i = 0; i < 100; ++i) {
document.write("<rect/>");
}
document.write("<rect id='test'/>");
document.write("</svg>\n");
</script>
<pre><script>
var node;
var count = 200000;
function doTests(root, elementId, descQS, descQSNoConcat, descGEBI) {
var start = new Date;
for (var i = 0; i < count; ++i)
node = root.querySelector("#" + elementId);
var stop = new Date;
document.writeln(descQS + ((stop - start) / count * 1e6));
var start = new Date;
for (var i = 0; i < count; ++i)
node = root.querySelector("#test");
var stop = new Date;
document.writeln(descQSNoConcat + ((stop - start) / count * 1e6));
var start = new Date;
for (var i = 0; i < count; ++i)
node = root.getElementById(elementId);
var stop = new Date;
document.writeln(descGEBI + ((stop - start) / count * 1e6));
}
var root = document.getElementById("root");
var start = new Date;
for (var i = 0; i < count; ++i)
node = document.getElementById("test");
var stop = new Date;
document.writeln("document.getElementById: " + ((stop - start) /
count * 1e6));
doTests(root, "test",
"In-tree querySelector: ",
"In-tree querySelector, no string concat: ",
"In-tree getElementById: ");
root.remove();
doTests(root, "test",
"Out-of-tree querySelector: ",
"Out-of-tree querySelector, no string concat: ",
"Out-of-tree getElementById: ");
</script>
[2] The diff I applied locally to a tip-ish Firefox:
diff --git a/content/svg/content/src/SVGSVGElement.cpp
b/content/svg/content/src/SVGSVGElement.cpp
--- a/content/svg/content/src/SVGSVGElement.cpp
+++ b/content/svg/content/src/SVGSVGElement.cpp
@@ -438,11 +438,15 @@ SVGSVGElement::CreateSVGTransformFromMat
Element*
SVGSVGElement::GetElementById(const nsAString& elementId, ErrorResult& rv)
{
- nsAutoString selector(NS_LITERAL_STRING("#"));
- nsStyleUtil::AppendEscapedCSSIdent(PromiseFlatString(elementId),
selector);
- nsIContent* element = QuerySelector(selector, rv);
- if (!rv.Failed() && element) {
- return element->AsElement();
+ for (nsIContent* kid = nsINode::GetFirstChild(); kid;
+ kid = kid->GetNextNode(this)) {
+ if (!kid->IsElement()) {
+ continue;
+ }
+ nsIAtom* id = kid->AsElement()->GetID();
+ if (id && id->Equals(elementId)) {
+ return kid->AsElement();
+ }
}
return nullptr;
}
