1272537 - Atomize the namespace manager

Status: RESOLVED FIXED

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

Description

[Bobby Holley (:bholley)]

I'm rather surprised this isn't the case already. In any case, we need this for stylo. I have patches.

Comment 1

[Bobby Holley (:bholley)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=dbb19ed84b22

Comment 2

[Boris Zbarsky [:bzbarsky]]

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?

Comment 3

[Bobby Holley (:bholley)]

(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.

Comment 4

[Boris Zbarsky [:bzbarsky]]

> 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?

Comment 5

[Bobby Holley (:bholley)]

(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.

Comment 6

[Boris Zbarsky [: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.

Comment 7

[Bobby Holley (:bholley)]

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?

Comment 8

[Boris Zbarsky [: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?

Comment 9

[Bobby Holley (:bholley)]

Attachment: Atomize the namespace manager. v1

Comment 10

[Bobby Holley (:bholley)]

NI bz who's not accepting review requests.

Comment 11

[Boris Zbarsky [:bzbarsky]]

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.

Comment 12

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3fe3775d2f5d

Comment 13

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

Backed out for Windows build bustage:

https://hg.mozilla.org/integration/mozilla-inbound/rev/671d2a71f803

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=48d8323378acd8d01fc09de523d3831b4857c39a

Comment 14

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a412db75b281

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/a412db75b281