Re: [whatwg] Proposal: Adding methods like getElementById and getElementsByTagName to DocumentFragments

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;
  }

Received on Friday, 18 October 2013 21:57:16 UTC