Closed Bug 277479 Opened 20 years ago Closed 14 years ago

Make atoms hold PRUnichar strings again

Categories

(Core :: XUL, defect)

Product:
Core
Component:
XUL
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: sicking, Assigned: sicking)

References

(Blocks 1 open bug)

Details

Attachments

(4 files, 1 obsolete file)

zero-copy atom lookup from UTF16 strings (for existing atoms)
38.90 KB, patch
benjamin
: review+
brendan
: review+
bzbarsky
: superreview+
Details | Diff | Splinter Review
Patch v1
214.77 KB, patch
Details | Diff | Splinter Review
changes to unichartable files
23.91 KB, patch
Details | Diff | Splinter Review
Complete patch for perf measurement
498.27 KB, patch
Details | Diff | Splinter Review 
We were talking on irc about atoms and the fact that they hold UTF8 strings.
This was originally done in bug 195262 so that we could have 'static atoms'.
I.e. atoms whos string-data are static and thus doesn't need any allocation when
started up.

The downside of this is that we in a lot of places have interaction between
UTF16 strings and atoms. Either comparing an atom to a string, or converting the
atom to a string.

Darin (or was it bsmedberg?) came up with the excellent idea that if we put the
string-data in a separate file, we can preprocess that file and create code that
looks something like:

PRUnichar[] {'s', 't', 'r', 'i', 'n', 'g', '\0'};

This file could then be #included into the real source.

This should be fairly easy considering that we most of the time have atom-tables
as separate files anyway. So we'd just need to preprocess these and modify the
code that include them.

We would also have to go through the changes that were made in bug 195262 to
undo any optimizations that were made for utf8-ness of atoms. I think at least
the attribute-name that were made needs to be undone.

The only real downside with this is that the static stringdata would be bigger,
but I don't think we have so many strings that it'll make a difference. And I
think there'll be some codesize wins due to less utf8<->utf16 conversions.
I find it hard to believe that this is a large win over making our UTF8<->UTF16
code in the atom table code suck less. In fact, I've got a patch that makes the
atom code do a compare-without-copy between UTF16 and UTF8, and beyond that I'd
like to see some numbers before I believe that this is wroth it.
i agree.  

here is a question, why are we using atom's if you still have to do string
operations anywhere outside the atom specifc code (for construction)?
> here is a question, why are we using atom's if you still have to do string
> operations anywhere outside the atom specifc code (for construction)?

doug: consider that the DOM API does not expose nsIAtom, yet our content model
makes extensive use of atoms.  So, there are boundaries between nsAString and
nsIAtom that are frequently crossed.  I'm sure there are other similar examples.
Another example is in XUL where we store attribute-values as atoms, but the API
(Get/SetAttr) uses strings. And we want it to use strings since sometimes we
want to store the value as a string, and sometimes we parse it into a number as
store it as a float or int. (We should do the same in HTML, so it's not XUL
specific).

The fact is that bug 195262 was a perf regression that was never fixed (see
comment 66 and on). It allowed for other optimizations, so it wasn't a bad
checkin, but these optimizations would still be possible with this bug implemented.
There are further optimizations to be done, not the least of which is the one
jst is talking about (though I though that patch already went in?

        Attachment #172113 -
        Flags: review?(bugmail)

    
    

    
  
Hrm, I think this should be producing ".cpp" files instead of ".h".

    
    

    
  
Ok, here are some stats on how many and how big atoms we're creating, and how
we're accessing them. The numbers mean the following:

UTF8 accesses: number of atom-lookups were made using a utf8 string
UTF16 accesses: number of atom-lookups were made using a utf16 string
Static initialized: total number of atoms in atomtables that were initialized
Max allocated: maximum allocated atoms alive at once
deleted: number of atoms that had been deleted at shutdown
preexisting static: number of atoms that already existed when inited a static
static stringsize: total stringsize of static atomtables
alloced stringsize: max stringsize of allocated atoms at once


Open and close the browser with homepage set to http://www.mozilla.org/start/
UTF8 accesses: 9839
UTF16 accesses: 9877
Static initialized: 1700
Max allocated: 1256
deleted: 1376
preexisting static: 533
static stringsize: 12905
alloced stringsize: 15178

Open browser, open prefs and look around, close browser
UTF8 accesses: 11596
UTF16 accesses: 12620
Static initialized: 1712
Max allocated: 1474
deleted: 1651
preexisting static: 545
static stringsize: 12968
alloced stringsize: 18084

Open browser, go to slashdot, close browser
UTF8 accesses: 11178
UTF16 accesses: 10510
Static initialized: 1700
Max allocated: 1272
deleted: 1509
preexisting static: 533
static stringsize: 12905
alloced stringsize: 15343

Open browser, look around in prefs, surf around 5 major pages, close
UTF8 accesses: 26766
UTF16 accesses: 30727
Static initialized: 1712
Max allocated: 1769
deleted: 3041
preexisting static: 545
static stringsize: 12968
alloced stringsize: 21918


Some things to note:
A fair number of static atoms already exist when they are initialized, i.e. the
space has been wasted. This is probably often due to the same atom existing in
another static table.

We look up atoms about as often using a utf8 string as a utf16 one. However I
suspect that in a lot of cases the string has been converted to utf8 before the
lookup.

There is about 13k of stringdata in static tables. This would double with this
bug fixed. Though there seems to be a fair number of duplicates. It might be
worth combining tables that live in the same dll.

    
    

    
  
Ok, more numbers (still no pref numbers though). I changed all callers of
NS_NewAtom/do_GetAtom that coverted the string from UTF8 to UTF16 themselvs and
now got the following numbers:

UTF8 accesses: 1756
UTF16 accesses: 42381
Static initialized: 1755
Max allocated: 1776
deleted: 2709
preexisting static: 590
static stringsize: 13191
alloced stringsize: 21760

Obviously the majority of times we want to access an atom we're doing that using
an UTF16 string. So the question is how big of a speed-hit we're taking from
these conversions, vs, is it worth the additional memorysize.

Actually, one thing I was thinking of is that we could store atoms in UTF8, but
hash them as UTF16. The only hit we'd take then is whenever we're converting
atom->String and not as much string->atom.. Though when we have hash collisions
it'd be somewhat slow to compare the utf8 string in the atom to the utf16 string
we're trying to find the atom for...

    
    

    
  
Wow, the numbers are pretty interesting.

I don't quite understand your last change - I read it as "I converted all the
callers of NS_NewAtom() who were previously converting the pre-atomized string
to UTF16" themselves" - meaning that if you converted them, they are no longer
calling the conversion themselves and are just passing in a UTF8 string.. do you
mean you found callers going the other way?

I still remember there are a number of optimizations (with complex cascading
calls) where a string starts as UTF8, gets converted to UTF16 somewhere in the
DOM (or at least the content sink) and then NS_NewAtom'ed. If the whole call
chain was fixed, you'd be dealing with UTF8 all the way. Also, I'd be curious to
see numbers on GetString() on atoms...hopefully there aren't many callers, but
that's another potential source of unnecessary conversions one way or the other
and there might be more calls than we realize.

    
    

    
  
The change I did was to change code like:

NS_NewAtom(NS_ConvertUCS2toUTF8(start, end - start))

to

NS_NewAtom(Substring(start, end))

I.e. basically removing conversions that happened just outside the atom code
which were offsetting the counting.

Changing the entire parsing callchain would indeed make a big difference.
However I'm not sure if that is possible since I think that our decoders decode
to UCS2. Though i guess all decoders could be changed too. Also, you'd want to
change signatures like GetAttr and SetAttr. We're basically talking about moving
major parts of content and possibly layout over to utf8.

Yes, it'd be very interesting to see how much we call stringfunctions on the
atoms, like ToString, GetUTF8String and Equals. That's the next thing i'm going
to instrument.

    
    

    
  


  
This patch changes the atom table code to look up atoms given a UTF16 string
w/o doing a string copy (as long as the atom already exists, which is by far
the most common case). This patch relies on some lowlevel pldhash facts in how
it treats its keys etc, all fun :)

The nsCRT changes are just putting back the code that was taken out in bug
254252 (grumble), and the nsUTF8Utils.h changes are largely written by bryner,
IIRC.

Here's some perf stats with and w/o these changes:

No nsAtomTable changes:

Atom creation from char* took 21,164,651us
Atom creation from nsAString& took 35,566,118us
Atom creation from PRUnichar* took 35,550,302us

With nsAtomTable changes:

Atom creation from char* took 12,401,233us (1.70 x faster)
Atom creation from nsAString& took 25,122,260us (1.41 x faster)
Atom creation from PRUnichar* took 22,002,715us (1.61 x faster)

    
    

    
  
Oh, and those numbers show the times for looking up 100,000,000 atoms (Linux
x86_64). But I just realized that my test was actually timing looking up atoms
that are *not* in the table. New stats coming up.

    
    

    
  
Looking up an existing atom:

No nsAtomTable changes:

Atom creation from char* took 21,524,788us
Atom creation from nsAString& took 43,231,257us
Atom creation from PRUnichar* took 49,239,990us

With nsAtomTable changes:

Atom creation from char* took 10,803,083us (1.99 x faster)
Atom creation from nsAString& took 25,321,624us (1.70 x faster)
Atom creation from PRUnichar* took 24,047,543us (2.04 x faster)

    
    

    
  
jst: any idea why atom creation from char* would have gotten faster?  i admit
that i haven't looked at the patch.

> But I just realized that my test was actually timing looking up atoms
> that are *not* in the table.

hmm...

> Atom creation from PRUnichar* took 35,550,302us

that's from your first test (no patch)

> Atom creation from PRUnichar* took 49,239,990us

and that's from your second test (still no patch)

i would have expected these to be the opposite.  i wonder why it is that the
test took longer when the atom didn't already exist in the table.

    
    

    
  
Ok, some more stats before I have a look at jsts code.

Using same run as before, I.e. open browser, check around in prefs, open 6
websites (moz.org/start, slashdot, winamp.com, dn.se, cnn.com, cnn article) I
get the following stats:

UTF8 lookups: 1749          (calls to NS_NewAtom, do_GetAtom using utf8 string)
UTF16 lookups: 39611
Static initialized: 1616    (number of atoms in static tables that were inited)
Max allocated: 1801         (max simultanious nonstatic atoms)
deleted: 2749               (total deleted nonstatic/nonpermanent atoms)
preexisting static: 461     (already existing atoms hit while initing static)
static stringsize: 12428    (total stringsize in static inited tables)
alloced stringsize: 21888   (max simultanious stringsize in allocated atoms)
UTF8 accesses: 1660         (using stringdata as utf8 string)
UTF16 accesses: 58324
either accesses: 116552     (see below)

The last number is for cases where it doesn't matter if the stringdata is in
utf16 or utf8 form. Most of the time this is the stylesystem that needs to
compare two atoms in a case insensitive manner. But it is also checking the
first few characters in the string data, like checking if the string in the atom
starts with 'o' 'n'.
Currently we're cheating the case-insensitive compare by not performing a true
utf8-compare, but rather treat the data as ascii. However this doesn't seem to
be a problem on real-world sites.

    
    

    
  
Oh, i should add that the "UTF8 accesses" and "UTF16 accesses" numbers might be
slightly skewed to UTF16s advantage. This is because initially the atoms code
were UTF16, so code was probably written to take this into consideration. Once
alecf switched to UTF8 many callsites were changed, but there are likly a few
that weren't.

This shouldn't be the case with the "UTF8/16 lookups" numbers though. I went
through all callsites of NS_NewAtom and do_GetAtom to try to make them all use
the encoding they prefered.

    
    

    
  
still pretty interesting numbers.. one thing I did was simply to break in
nsAtom.GetString(nsAString&) at different points during a typical run - it was
interesting to see who was called a lot

    
    

    
  
(In reply to comment #15)
> jst: any idea why atom creation from char* would have gotten faster?  i admit
> that i haven't looked at the patch.

I think that's mostly due to us not wrapping char*'s in nsDependentCString's any
more, which does a strlen() (which we totally don't care about in this code),
plus the object creation on the stack etc.

> > But I just realized that my test was actually timing looking up atoms
> > that are *not* in the table.
> 
> hmm...
> 
> > Atom creation from PRUnichar* took 35,550,302us
> 
> that's from your first test (no patch)
> 
> > Atom creation from PRUnichar* took 49,239,990us
> 
> and that's from your second test (still no patch)
> 
> i would have expected these to be the opposite.  i wonder why it is that the
> test took longer when the atom didn't already exist in the table.

Yeah, that confused me too. I don't know what the deal is there yet. My tests
were run from NS_InitXPCOM2() (in nsXPComInit.cpp), so the atom table might be
empty at that point, so adding to an empty table is cheaper than comparing to an
existing atom maybe?

Others please feel free to run additional tests here...

    
    

    
  
Alec, did you get a feel for which callers use this a lot? One option is
certanly to try to reduce the number of places where we use atoms. Especially
once we get refcounted buffers.

I havn't checked which callsites generate which numbers. I just happened to find
that the stylesystem does a lots of case insensitive compares since I missed to
convert a callsite there which made a huge difference when I changed. This was
nsGenericHTMLElement::HasClass that generated over 80000 calls to get stringdata
(which was case-insensitivly compared to another atom).


wrt jsts patch: IMHO as far as this bug goes, what matters the most is the ratio
in speed between getting an atom using a UTF16 string and a UTF8 string. And
both before and after it seems like that ratio is 2.5. Though there seems to be
some weird stuff going on there since getting an existing atom should resonably
be faster then getting a new one...
Still sounds like a good patch to check in though, if nothing else, it'll let us
compare performance numbers before and after a possible fix for this bug.

    
    

    
  
> i wonder why it is that the
> test took longer when the atom didn't already exist in the table.

typo: i meant "when the atom already existed in the table"

it seems that was apparent from the context, but i just wanted to clarify ;-)

    
    

    
  
I did at the time but it was well over a year ago. I don't remember who the big
culprits were :(

    
    

    
  
In any case, it seems like it might be worth switching back to utf16 atoms. I'll
write up a patch and then we can evaluate perf vs. bloat.
Assignee: benjamin → bugmail

    
    

    
  

      
      
      
      

        Attached patch
          
          
        Patch v1
        — 
          — Splinter Review
      

    


  
This patch implements utf16 atoms. Static atoms are implemented by expanding
the string in the ns*AtomList.h files. This is done by preprocessing
ns*AtomList.unichartable files into ns*AtomList.h using wide-literal.pl.

The wide-literal.pl in this attachment works differently from the one bsmedberg
attached, instead of having a special format for the file, the script now
performs search'n'replace looking for.
WIDE_LITERAL(ident, "string")
and expands it into
WIDE_LITERAL(ident, {'s','t','r','i','n','g','\0'})

(actually, commas isn't used but rather the macro COMMA which is typedefed at
the top of the processed file.)

It is possible to define which macro or macros to expand by putting a
WideLiteralMacros=MACRO1,MACRO2
in the .unichartable file before any macros.

There were a few problems with using this. First off the generated .h file most
of the time had to be exported since it ended up being included by ns*Atoms.h
files which in turn is included by files in random directories.

There were quite a few classes that hadn't moved the static atom list into a
separate file, but rather had the atomnames and data in the .cpp and .h files
directly, in those cases i broke that out into an ns*AtomList file. This is a
good thing to do anyway since it reduces source duplication of the atomname in
3 different places.

Lastly, in a couple of places the textliteral was given as a macro. This was a
big problem in nsDirectoryService where all literals were given as macros.
Unfortunatly I had to make this code not use static atoms, but rather permanent
ones. Alternativly I could replace the macros with the strings, since they are
frozen anyway. Let me know what you think.

I havn't included all .unichartable files in the patch since it would just make
it harder to read. All i've done is to rename the existing .h file to
.unichartable and added a WideLiteralMacro comment. I included one file as an
example.

I need to run performance tests on this. Once that is done we can decide if
this is the way we want to go or not.

        Attachment #172113 -
        Attachment is obsolete: true

    
    

    
  


  
This is just a patch to show the actual changes i made to the atomlist files.
In addition to renaming them to .unichartable of course.

    
    

    
  
I ran Ts and Txul tests locally on my mashine and the results weren't too
uplifting. Txul didn't change at all, it was 203 both before and after. Ts
however changed from ~780 to ~850. The two reasons I can think of for this is
bigger dll files taking longer to load, or because the nsDirectoryService no
longer uses static atoms.

Is anyone interested in running Tp tests? If so I can produce a compleate patch
including all unichartable files...

    
    

    
  
I figured out a way around the nsDirectoryService issue, but it didn't really
help. Startup time is still significanly slower. Anyone have any ideas? I really
doubt that 8k filesize difference would have that big of an impact.
Status: NEW → ASSIGNED

    
    

    
  
Rejoice! I found the Ts problem. I was still using the stub string-hasher in
nsAtomTable which operates on char strings, so in effect I was just hashing on
the first character in each atom. Once I fixed that I got the same times for Ts
as without the patch.

Txul strangly enough didn't seem affected by this fix though. However I am
getting pretty strange Txul times anyway. It's either 234, 219, 203 or 187. No
values inbetween except a 1ms variation sometimes. Don't know what's up with that...

    
    

    
  
Make sure you're not blowing away the XUL cache or something by not quitting
cleanly.. 

So what's the final result? sounds like Ts is unchanged, Txul is erratic and no
data for Tp?

I'd also be curious about memory usage and how it changes (maybe it won't be
significant?)


    
    

    
  
Ok, here's a summary. With some tweaks on top of the patch attach I get the
following:

Ts seems unaffected by this patch. I get ~780ms both before and after.

The Txul data I get is weird. First off I only get the times 234, 219, 203 or
187ms for each individual windowopen. Nothing inbetween. The most common value
is 203 which also is where median usually ends up. This is true both with or
without the patch. Another strange thing is that I got the exact same times when
I had the very suboptimal atom hash function, which should defenetly have
affected Txul (it increased Tp by 10%). So I would say the Txul is inconclusive
but possibly unaffected.

I havn't run Tp tests since I don't have access to them.

The binary size increased by 18230 bytes. This might be possible to reduce by
combining static atom tables (we have 6 separate tables in gklayout.dll,
probably with quite a bit of duplication).

I'd expect runtime allocation size to go up about 20k since that's the current
peak allocation of stringdata in atoms in my testrun (using more and bigger
pages shouldn't increase the number of atoms alive).


It would be excellent if someone was able to run Tp tests or get better Txul data.

    
    

    
  


  
This is a compleate patch that includes removing the old .h files and adding
the new .unichartable files. When and if we land this patch we probably want to
cvs-copy the .h files into .unichartable files to preserve cvshistory

    
    

    
  
Btw, doesn't look like my computer is the only windowsbox that behaves weirdly
when it comes to Txul data. I wonder if it's some sort of time-measuring issue
on windows.

http://build-graphs.mozilla.org/graph/query.cgi?tbox=beast&testname=xulwinopen&autoscale=0&size=&days=100&units=&ltype=steps&points=1&avg=0

    
    

    
  
(In reply to comment #32)
> Btw, doesn't look like my computer is the only windowsbox that behaves weirdly
> when it comes to Txul data. I wonder if it's some sort of time-measuring issue
> on windows.

It may well not be using the hi-performance or multimedia timers, and so is
limited to this lower resolution of the normal system timer (the cannonical
example GetTickCount() is limited to this resolution, as is Date.now() in
SpiderMonkey). The Windows Time Service here claims this has a resolution of
just over 10ms on my system.

    
    

    
  
OK, I just tried that attachment on a simple testcase --
document.images['imageid'] for a document with a bunch of images.  The results are:

Without patch:  70098 hits under nsContentList::NamedItem, of which 21739 are
under AtomImpl::Equals

With patch: 59130 hits under nsContentList::NamedItem, of which 9822 are under
AtomImpl::Equals

So that patch makes AtomImpl::Equals over two times faster, and makes this quite
real-life testcase about 15% faster.

Could we just get this in on trunk?  Either in this bug or in bug 307601?  Who
would need to review this?
Blocks: 307601

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

Benjamin, you want to review?

        Attachment #172366 -
        Flags: superreview?(bzbarsky)

        Attachment #172366 -
        Flags: review?(benjamin)

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

ConvertUTF8CharToUCS4 is an odd name, especially for a class.  I'd call it
UTF8CharEnumerator or something like that (and likewise for the UTF16 one).

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

>+        // Cast away the signedness of *u8 to prevent signextension when
>+        // converting to PRUint32
>+        PRUint32 c8_32 = (const PRUint32)*u8;

Casting to PRUint8 would be better.  If a cast is needed, this one won't help,
since it doesn't change anything (it doesn't change the conversion at all, just
does it on the other side of the equals).  And the const is unnecessary.

>+            PRBool err;
>+            c8_32 = ConvertUTF8ChartoUCS4::NextChar(&u8, u8end, &err);
>+            if (err)
>+              return -1;
>+
>+            PRUint32 c16_32 = ConvertUTF16ChartoUCS4::NextChar(&u16, u16end,
>+                                                               &err);
>+            if (err)
>+              return -1;

I think these error cases should assert somewhere, probably in the character
enumerator's NextChar methods.	I think code like this should generally be
written to expect things that are known to be UTF-8 or UTF-16.

Also, perhaps the value should be something wacky rather than just -1, since -1
implies a certain comparison result?

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

Yes, I'll look at this Monday or Tuesday. I'm technically not an XPCOM peer, so
we should get shaver or darin to MOA this after.

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

>+// An AtomTableEntry can be either a string key to be used with the
>+// atom table, or an actual entry in the atom table. PLDHashTable
>+// reseves the keyHash values 0 and 1 for internal use, which means
>+// that the *PLDHashTable code* will never pass an entry to our
>+// hooks. That means we can use those values to tell if an
>+// AtomTableEntry is a key created by a PLDHashTable code caller, or
>+// an actual live AtomTableEntry used by a PLDHashTable.

I read this comment about 6 times before I understood it. I think it should
more-clearly indicate that the "key" pointer being passed to the matchentry/etc
callbacks is an AtomTableEntry*.

>Index: xpcom/ds/nsCRT.cpp

>+PRUint32 nsCRT::HashCodeAsUTF8(const PRUnichar* str, PRUint32* resultingStrLen)

>+              /*
>+               * Unlike the algorithm in http://www.ietf.org/rfc/rfc2279.txt
>+               *  we must calculate the bytes in left to right order so that
>+               *  our hash result matches what the narrow version would calculate
>+               *  on an already UTF-8 string.
>+               */

Do we know the string lengths before we start? Would it be quicker to hash all
strings from end to front?


>Index: xpcom/string/src/nsReadableUtils.cpp
>===================================================================
>RCS file: /cvsroot/mozilla/xpcom/string/src/nsReadableUtils.cpp,v
>retrieving revision 1.61
>diff -u -9 -p -r1.61 nsReadableUtils.cpp
>--- xpcom/string/src/nsReadableUtils.cpp	24 Jan 2005 16:44:41 -0000	1.61
>+++ xpcom/string/src/nsReadableUtils.cpp	25 Jan 2005 18:26:06 -0000

>-NS_COM const nsAFlatString& EmptyString()
>+NS_COM
>+const nsAFlatString&
>+EmptyString()
>   {
>     static const nsDependentString sEmpty(empty_buffer);
> 
>     return sEmpty;
>   }
> 
>-NS_COM const nsAFlatCString& EmptyCString()
>+NS_COM
>+const nsAFlatCString&
>+EmptyCString()
>   {
>     static const nsDependentCString sEmpty((const char *)empty_buffer);
> 
>     return sEmpty;
>   }
>+
>+NS_COM PRInt32
>+CompareUTF8toUTF16(const nsASingleFragmentCString& aUTF8String,
>+                   const nsASingleFragmentString& aUTF16String)
>+  {
>+    static const PRUint32 NOT_ASCII = PRUint32(~0x7F);
>+
>+    const char *u8, *u8end;
>+    aUTF8String.BeginReading(u8);
>+    aUTF8String.EndReading(u8end);
>+
>+    const PRUnichar *u16, *u16end;
>+    aUTF16String.BeginReading(u16);
>+    aUTF16String.EndReading(u16end);
>+
>+    while (u8 != u8end && u16 != u16end)
>+      {
>+        // Cast away the signedness of *u8 to prevent signextension when
>+        // converting to PRUint32
>+        PRUint32 c8_32 = (const PRUint32)*u8;
>+
>+        if (c8_32 & NOT_ASCII)
>+          {
>+            PRBool err;
>+            c8_32 = ConvertUTF8ChartoUCS4::NextChar(&u8, u8end, &err);
>+            if (err)
>+              return -1;
>+
>+            PRUint32 c16_32 = ConvertUTF16ChartoUCS4::NextChar(&u16, u16end,
>+                                                               &err);
>+            if (err)
>+              return -1;
>+
>+            if (c8_32 != c16_32)
>+              return c8_32 < c16_32 ? -1 : 1;
>+          }
>+        else
>+          {
>+            if (c8_32 != *u16)
>+              return c8_32 > *u16 ? 1 : -1;
>+
>+            ++u8;
>+            ++u16;
>+          }
>+      }
>+
>+    if (u8 != u8end)
>+      {
>+        // We get to the end of the UTF16 string, but no to the end of
>+        // the UTF8 string. The UTF8 string is longer than the UTF16
>+        // string
>+
>+        return 1;
>+      }
>+
>+    if (u16 != u16end)
>+      {
>+        // We get to the end of the UTF8 string, but no to the end of
>+        // the UTF16 string. The UTF16 string is longer than the UTF8
>+        // string
>+
>+        return -1;
>+      }
>+
>+    // The two strings match.
>+
>+    return 0;
>+  }

Why is this inline? If we're going to make EmptyCString inline we should remove
the NS_COM also, I think. Darin should check this last bit.

        Attachment #172366 -
        Flags: review?(benjamin) → review+

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

>Index: xpcom/ds/nsAtomTable.cpp

>+// An AtomTableEntry can be either a string key to be used with the
>+// atom table, or an actual entry in the atom table. PLDHashTable
>+// reseves the keyHash values 0 and 1 for internal use, which means
>+// that the *PLDHashTable code* will never pass an entry to our
>+// hooks.

You mean "never pass an AtomTableEntry* whose keyHash <= 1 to our hooks"?

I'd really like brendan to ok this part, since it involves assumptions about
the guts of PLDHashTable...

>+// Evil? Yes, bit kinda neat too :-)

s/bit/but/  ;)

>+  inline const char* getAtomString() const {
>+    NS_ASSERTION(keyHash > 1, "get() called on non-atom 

Fix the assert text to match the function name?

>+    NS_ASSERTION(keyHash == 0,
>+                 "getUTF8String() called on atom AtomTableEntry!");

How about s/on atom/on non-UTF8/ ?

>+  inline const PRUnichar* getUTF16String() const {
>+    NS_ASSERTION(keyHash == 1,
>+                 "getUTF16String() called on non-atom AtomTableEntry!");

s/on non-atom/on non-UTF16/

> AtomTableGetKey(PLDHashTable *table, PLDHashEntryHdr *entry)
>+  return he;

Should this assert that |!he->IsUTF8String() && !he->IsUTF16String()| ?

>+AtomTableMatchKey(PLDHashTable *table, const PLDHashEntryHdr *entry,
>                   const void *key)
>   const AtomTableEntry *he = NS_STATIC_CAST(const 

And again here.

>+NS_NewAtom(const char* aUTF8String)
>+  AtomTableEntry *he = GetAtomHashEntry(aUTF8String);

We should probably return null if this is null...

And we should assert that it's not a string key AtomTableEntry.

>+NS_NewAtom(const PRUnichar* aUTF16String)
>+NS_NewAtom(const nsAString& aUTF16String)

This latter is the common case, I think, and in that case we're doing a
PromiseFlatString, then wrapping a dependent string around it in the PRUnichar*
version if we miss.  In other words, I think we should have the PRUnichar*
version call the nsAString& version, not the other way around...  Either that
or fix the operator new involved to take a PRUnichar*.	Though I guess if the
common case is that we get a hashtable hit then the current setup is ok.

>+NS_NewPermanentAtom(const char* aUTF8String)
>+  return NS_NewPermanentAtom(NS_ConvertUTF8toUTF16(aUTF8String));

This should use a nsDependentCString, I think...  the nsACString version of
NS_NewPermanentAtom is where we want to end up.

>+NS_NewPermanentAtom(const nsAString& aUTF16String)
>+  return NS_NewPermanentAtom(NS_ConvertUCS2toUTF8(aUTF16String));

s/UCS2/UTF16/

>Index: xpcom/ds/nsCRT.cpp
>+PRUint32 nsCRT::HashCodeAsUTF8(const PRUnichar* str, PRUint32* resultingStrLen)
>+            if ( W < 0xD800 || 0xDFFF < W )
...
>+            else if ( /* 0xD800 <= W1 && */ W <= 0xDBFF )
>+              W1 = W;

What if 0xDBFF < W <= 0xDFFF  ?  Should we throw an error or something?  Or are
we ignoring that range on purpose?  If the latter, please comment to that
effect!

sr=bzbarsky with bsmedberg's and dbaron's comments addressed.

jst, can you get this updated and into the trunk, or should I try to?

        Attachment #172366 -
        Flags: superreview?(bzbarsky)

        Attachment #172366 -
        Flags: superreview+

        Attachment #172366 -
        Flags: review?(brendan)

    
    

    
  
Comment on attachment 172366 [details] [diff] [review]
zero-copy atom lookup from UTF16 strings (for existing atoms)

I have no plans to change the magic meaning of 0 and 1 when used as
jsdhash/pldhash keyHash values, nor should anyone else.  I skimmed the patch,
it looks good modulo bz and benjamin review.

/be

        Attachment #172366 -
        Flags: review?(brendan) → review+
Depends on: 314465

    
    

    
  
I filed bug 314465 for actually getting jst's patch into the tree, since that's independent of this bug (which is about changing how strings are stored in atoms).
Assignee: jonas → nobody
Status: ASSIGNED → NEW
QA Contact: xptoolkit.trees

    
    

    
  
Sicking, what all's been checked in from this bug and what (if anything) still needs to be done? As best I can tell, attachment 172366 [details] [diff] [review] has been checked in.
Assignee: nobody → jonas

    
    

    
  
Yes, that patch has been checked in. However that patch has nothing really to do with this bug per se, so the status of this bug is correct. I.e. there is still no progress.

I still think we should fix it, but I don't have the time to do it anytime soon, and it's certainly not something that we should spend cycles on before the FF3 release.

    
  
Component: XP Toolkit/Widgets: Trees → XUL
QA Contact: xptoolkit.trees → xptoolkit.widgets
Depends on: 534136

    
    

    
  
The remaining stuff was fixed in bug 534136
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: