Atomize the namespace manager

RESOLVED FIXED in Firefox 49

Status

()

RESOLVED FIXED
3 years ago
2 years ago

People

(Reporter: bholley, Assigned: bholley)

Tracking

(Blocks: 1 bug)

unspecified
mozilla49
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox49 fixed)

Details

(Whiteboard: btpp-active)

Attachments

(1 attachment)

(Assignee)

Description

3 years ago
I'm rather surprised this isn't the case already. In any case, we need this for stylo. I have patches.
(Assignee)

Updated

3 years ago
Summary: Atomize the namespace table → Atomize the namespace manager
We don't do this because it now requires two hashtable lookups to go from a string to a namespace id, instead of one hashtable lookup.  What's the win, exactly, and why do we need this for stylo?
(Assignee)

Comment 3

3 years ago
(In reply to Boris Zbarsky [:bz] from comment #2)
> We don't do this because it now requires two hashtable lookups to go from a
> string to a namespace id, instead of one hashtable lookup.

Well, not all hashtable lookups are created equal. I would expect the string-keyed lookup to dominate here, and the atom-keyed lookup to be more or less constant-time (I could fiddle with optimizing the second lookup if we think it's important).

So the real performance question is whether looking up the string in the atom table is significantly slower than looking up the string in hash table we're using on trunk. I don't have enough intuition to say one way or another there.

>  What's the win,
> exactly, and why do we need this for stylo?

Servo uses atomized namespace-uris to represent namespaces (which generally seems like a sane thing to do). With stylo, we're using gecko atoms to back servo atoms, so we need a cheap way to get the atomized namesepace URI from a node without doing it every time.

I could certainly do both here - i.e. keep the hold hashtable setup with the manual strings, and hang an additional atomized version off of it, or alter the hashtable semantics to allow us to perform lookups with strings rather than with atoms. It's just a question of whether it's worth it.

FWIW, Talos shows no regressions on linux64 with 4-5 retriggers on each job.
> I would expect the string-keyed lookup to dominate here, and the atom-keyed lookup to be more or less constant-time

I'd need to measure to know what to expect.  Last I'd measured our hashtables, the actual hashing of the key very much did not dominate things, but maybe the hashtable impls have gotten better.... It used to be a bunch of code running, function call overhead, cache misses, indirect calls, etc, etc.

If servo represents namespaces as atomized strings, what does it do to represent "null namespace", "any namespace", and "unknown namespace"?  Presumably unions or so?
(Assignee)

Comment 5

3 years ago
(In reply to Boris Zbarsky [:bz] from comment #4)
> > I would expect the string-keyed lookup to dominate here, and the atom-keyed lookup to be more or less constant-time
> 
> I'd need to measure to know what to expect.  Last I'd measured our
> hashtables, the actual hashing of the key very much did not dominate things,
> but maybe the hashtable impls have gotten better.... It used to be a bunch
> of code running, function call overhead, cache misses, indirect calls, etc,
> etc.

Ok. I could eliminate the second hashtable and just replace it with a linear scan through the array of atoms, with the most commonly-used atoms being at the front. Would you prefer that?

> If servo represents namespaces as atomized strings, what does it do to
> represent "null namespace", "any namespace", and "unknown namespace"? 
> Presumably unions or so?

Null namespace is the empty string. I don't think there's any general system-wide handling of the latter two cases, but I'd imagine the code uses tagged unions as appropriate.
Flags: needinfo?(bzbarsky)
No, the linear array sounds like it has really bad worst-case behavior...

Have you measured the getElementsByTagNameNS performance with this change?  I'd think that's where any extra overhead would be most obvious, so interested in how it looks.
Flags: needinfo?(bzbarsky)
(Assignee)

Comment 7

3 years ago
From IRC:

<bholley>	bz: my patch makes it about 15% slower
<bholley>	bz: the two hashtable lookups are 2x and 0.3x the original hashtable tookup
<bholley>	bz: which is to say it's much cheaper to run the lookup when we have the atom, but the time to atomize is too much
<bholley>	bz: (assuming we care about this microbenchmark - each call is about 100ns on my machine
<bholley>	bz: the cleanest solution I can think of is to continue storing atoms, but perform lookups on the underlying string
<bholley>	bz: does that sound reasonable to you?
Flags: needinfo?(bzbarsky)
Fwiw, I think a 15% hit on this microbenchmark is probably acceptable.  It's the absolute worst-case scenario for this situation...

I'm not sure what "continue storing atoms, but perform lookups on the underlying string" means.  Store atoms where, and perform which lookups?
Flags: needinfo?(bzbarsky)
(Assignee)

Comment 9

3 years ago
Created attachment 8752416 [details] [diff] [review]
Atomize the namespace manager. v1
(Assignee)

Comment 10

3 years ago
NI bz who's not accepting review requests.
Flags: needinfo?(bzbarsky)
Whiteboard: btpp-active
(Assignee)

Updated

2 years ago
Blocks: 1273771
Comment on attachment 8752416 [details] [diff] [review]
Atomize the namespace manager. v1

>-  REGISTER_NAMESPACE(kXMLNSNameSpaceURI, kNameSpaceID_XMLNS);

kXMLNSNameSpaceURI is then unused and can go, as well as the other k*URI bits here.

>+nsresult nsNameSpaceManager::AddNameSpace(already_AddRefed<nsIAtom> aURI,

This needs to release aURI (e.g. by assigning it to a stack nsCOMPtr) in the failure cases in this method.

>-  if (!mURIArray.AppendElement(uri)) {
>+  mURIArray.AppendElement(Move(aURI));

You should probably keep this a fallible allocation.

r=me with those fixed.
Flags: needinfo?(bzbarsky)
Attachment #8752416 - Flags: review+

Comment 15

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/a412db75b281
Status: NEW → RESOLVED
Last Resolved: 2 years ago
status-firefox49: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla49
(Assignee)

Updated

2 years ago
Flags: needinfo?(bobbyholley)
You need to log in before you can comment on or make changes to this bug.