Closed Bug 572614 Opened 11 years ago Closed 11 years ago

Eliminate double hash lookups in GetElementById().

Categories

(Core :: DOM: Core & HTML, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: jst, Assigned: jst)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

Attachments

(1 file)

Right now when GetElementById() is called we first do a string->atom hash lookup, and then an atom->element hash lookup. There's no reason for this, we should simply make the hash that holds the elements by their id be string based and completely avoid the atom lookup.

With the attached patch a tight loop that does document.getElementById() looking for a non-existent element is about 35% faster, and looking for an existing one is ~21% faster.
Attachment #451833 - Flags: review?(jonas)
Assignee: nobody → jst
Comment on attachment 451833 [details] [diff] [review]
Use a string hash.

> nsDocument::GetElementById(const nsAString& aElementId)
> {
>-  nsCOMPtr<nsIAtom> idAtom(do_GetAtom(aElementId));
>-  if (!idAtom) {
>-    // This can only fail due to OOM when the atom doesn't exist, in which
>-    // case there can't be an entry for it.
>+  if (!CheckGetElementByIdArg(aElementId)) {
>     return nsnull;
>   }
> 
>-  if (!CheckGetElementByIdArg(idAtom)) {
>-    return nsnull;
>-  }
>-
>-  nsIdentifierMapEntry *entry = mIdentifierMap.PutEntry(idAtom);
>+  nsIdentifierMapEntry *entry = mIdentifierMap.GetEntry(aElementId);
>   return entry ? entry->GetIdElement() : nsnull;
> }

Did you check that s/PutEntry/GetEntry/ doesn't regress dromaeo the same way it did for me?

r=me with that changed or checked.
Attachment #451833 - Flags: review?(jonas) → review+
Yup, was going to mention that here too but forgot. I did test both with my local testcase and with dromaeo, and here on Linux calling GetEntry() is faster both on my testcase and on dromaeo. I haven't had a chance to compare both in Shark on a mac yet (but getting close to being able to do that easily) so I may hold off on landing this until I have looked into that bit further.
And here's the Dromaeo results of those tests, GetEntry() on the left, PutEntry() on the right: http://dromaeo.com/?id=107522,107523
Blocks: 572688
This landed, marking FIXED.

http://hg.mozilla.org/mozilla-central/rev/3d65cff5c900
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Just curious why function $() I made below gives a better performance?
Can we still improve the speed? 
Safari is faster than Firefox when doing document.getElementById()

=========

var i,j,k = 100000;
var objid = 'alink'

_$ = document;
_$.$ = _$.getElementById;

function $(id, refresh) {
  if (typeof id == "string") {
      //id = !refresh && id in $ ? $[id] : ($[id] = _$.$(id));
      id = !refresh &&  $[id] || ($[id] = _$.$(id));
  }
  return id;
}

j = document.getElementById(objid);

if(!j){
 j = document.createElement('a');
 j.id = objid;
 document.body.appendChild(j);
}

var d4, d3, d2, d1 = new Date();
for(i=0;i<k;i++) j = document.getElementById(objid);
d2 = new Date();
for(i=0;i<k;i++) j = _$.$(objid);
d3 = new Date();
for(i=0;i<k;i++) j = $(objid);
d4 = new Date();
[d2-d1, d3-d2, d4-d3];


gives ==>
388,247,122
> Just curious why function $() I made below gives a better performance?

Because it has to do a lot less work?  |document.getElementById(objid)| has to get the "document" property from the window, get the "getElementById" property from the document, call the resulting function, which needs to be converted into a C++ call on the right C++ object (which needs to be found from the given JS object), and then one has to take the resulting C++ object from the C++ call and find the corresponding JS object to it (or create one).

Your function, after the first call, just does a direct memory fetch in jit-generated machine code, without having to call into C++ or come back from it....

That said, over here with your testcase and a build with this bug's patch in it the numbers I see are something on the order of:

  19,42,7 

For comparison, Safari 4 gives me:

  20,25,13

(as expected; somewhat slower for the well-traced pure JS, about the same for the native call).
Depends on: 575462
In FF4.0b9pre tracemonkey I get several messages:
Warning: Empty string passed to getElementById().
Source File: chrome://browser/content/browser.xul
Line: 0
The HG Blame points to this bug.

I realize that you are trying to be helpful with the warning. Unfortunately this kind of message is not helpful. It has no line number and no call stack. So we we see it what can we do? We can't tell if it is in our code, the platform, or any of the other 15 extensions we have loaded. So we have to spend an hour just to figure out that we won't be able to figure it out. Then we have to see the message several times an hour every day until it magically goes away.
> The HG Blame points to this bug.

If you actually look at the diff, this bug just moved that code; it didn't add it.

The code that encounters the problem does not have access to the line number or callstack; it doesn't even have to be called from JS (and often isn't), so pretending like the currently-active JS callstack is necessarily relevant would just be wrong.  The warning is there for platform developers, really, who should be using debug builds and can thus trivially breakpoint on the warning and see what the callstacks (C and JS) look like.

For the C stack, this can even be done on Windows with release builds, of course, using the symbol server.  Furthermore, if the JS stack _is_ relevant, you can examine it in a debugger if you have symbols (so any debug build or any build on Windows).  It really doesn't take an hour to do said examining...
(In reply to comment #8)
> > The HG Blame points to this bug.
> 
> If you actually look at the diff, this bug just moved that code; it didn't add
> it.

Yes I saw that but how can one find the right bug in that case?
 
> The warning is there for platform developers, really, who
> should be using debug builds and can thus trivially breakpoint on the warning
> and see what the callstacks (C and JS) look like.

Yes, this is a wonderful message for platform developers. So it should be DEBUG or ASSERT right?
> Yes I saw that but how can one find the right bug in that case?

You click on the "changeset link", click the "parent" link, then look up the hg blame for the file as of _that_ revision.  Or hg anno -r locally if you have a tree and don't want to mess with hgweb.

> So it should be DEBUG or ASSERT right?

Well, the idea is that if something in the platform does this then testers report it and then it can be debugged and fixed....

That said, I'm not sure why we bother warning on this particular issue at all.
But that has nothing to do with this bug; if you want to change how this warning is handled, please file a separate bug on that.
Bug 624311 - Please stop sending "Empty string passed to getElementById()."
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.