48855 - nsAVLTree is a loser way to lookup static names

Status: VERIFIED FIXED

(Core :: DOM: HTML Parser, defect, P3)

Description

[John Bandhauer]

nsAVLTree is used in:
/gfx/src/nsColorNames.cpp
/htmlparser/src/nsHTMLEntities.cpp
/htmlparser/src/nsHTMLTags.cpp
/layout/html/style/src/nsCSSKeywords.cpp
/layout/html/style/src/nsCSSProps.cpp
/layout/mathml/content/src/nsMathMLOperators.cpp

The comparitors do 43,000 case insensitive string compares before the browser 
window shows! Because of bug 48853 this included 43,000 calls to strlen too - 
even though both strings being compared where in nsCStrings.

Of those 43,000 calls about 20,000 were in nsCSSKeywords and represented *only* 
2,000 lookups. Clearly a hashtable is a better way to do these lookups.

I have a nsHashtable wrapper class to fix this problem. It makes the compares 
case insensitive by requiring (and asserting) that the static table contain only 
lowercase and then does *one* call to lowercase a copy of the string being 
looked up - rather than deal with the possible case mismatch in each of multipe 
compares like the nsAVLTree scheme.

I also have a change to the nsCStringKey code to allow for keys added to the 
table that don't own the string buffer. This will allow us to not make a copy of 
the strings in the static table. This saves about 25k for nsCSSKeywords alone. 
This is a bigger win than it would have been since these classes where using 
nsCAutoString in their heap allocated structs and thue wasting even more space.

I'll finish making this general and fix the various uses and attach a patch for 
review before checking it in.

Comment 1

[rbs]

I was having some misgivings about this stuff due these duplicated strings.

Comment 2

[rbs]

What about using PLHashTable. I seem to have read somewhere that nsHashtable has
a certain drawback, and that PLHashTable should be preferred over nsHashTable.

Comment 3

[John Bandhauer]

nsHashtable is built on PLHashtable. The string key scheme in nsHashtable was 
suboptimal. warren improved it.

Comment 4

[John Bandhauer]

Attachment: diffs to use nsStaticNameTable class instead of nsAVLTree

Comment 5

[John Bandhauer]

Attached patch to use nsStaticNameTable instead of nsAVLTree.

This gives about 10% speed up in CSSParserImpl::Parse as mesured in Quantify on 
NT.

The patch looks big because I had to add a field to some tables so that string 
sharing would work. 

I decided to not mess with nsHTMLEntities.cpp because it different enough from 
the other cases to require more customized code. And I left 
nsMathMLOperators.cpp alone too.

I'll try to round up reviewers.

Comment 6

[Warren Harris]

I think nsHashtables are very comparable to PLHashtables now.

Comment 7

[John Bandhauer]

Attachment: diff for nsCSSKeywordList.h only to handle pierre's changes

Comment 8

[John Bandhauer]

My fixes are in.

Comment 9

[bsharma]

updated qa contact.

Comment 10

[rbs]

I recently re-worked nsMathMLOperators as outlined here.
http://groups.google.com/groups?hl=en&lr=&group=netscape.public.mozilla.mathml&s
afe=off&ic=1&th=3a8c2e24a034123b&seekd=935108173#935108173
As a part of that work, I switched to a hashtable too.

Comment 11

[bsharma]

Marking verified as per above developer comments.