180264 - Templatize nsHashtable for inline allocation of keys

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Benjamin Smedberg]

Would it make sense to optimize nsStringKey to use shared string buffers rather
than individual allocations, using the same methodology as nsSharableString?  I
would like to take a crack at it, unless you (jag,bzbarsky) see any particular
reasons why this couldn't work (threading might be an issue).  I think that it
might save significantly in terms of heap-fragmentation and overall memory
usage.  Bug 119745 has some discussion about optimizing nsStringKey.

Comment 1

[Boris Zbarsky [:bzbarsky]]

I don't really know much about the internals of this stuff.... alecf? Thoughts?

Comment 2

[Alec Flett]

I think this is already fairly well covered with the ownership flag in the key.
If anything, we should be arena-allocating strings that the key owns. 

Its an interesting idea really - we could add a new constructor to nsStringKey
which does arena-allocation of the string, and then pretends like it doesn't own
it. It would be up to consumers to provide the arena, and to release the arena
when the hashtable goes away...

Comment 3

[Benjamin Smedberg]

I have coded a templatized hashtable that can do inline-allocation of hashkeys,
to avoid double allocations.  I have created new class names, because the APIs
are not really compatible with nsHashkey.  Because I can't do a CVS add, there
will be two attachments: one diff for the files already in the trunk, and one
tar for the three new files.

Comment 4

[Benjamin Smedberg]

Attachment: tar of three new files

nsTHashtable.h
nsTHashtableImpl.h
nsTHashtable.cpp

Comment 5

[Benjamin Smedberg]

Attachment: patch for existing files

Comment 6

[Benjamin Smedberg]

Attachment: example of usage

This is a (very simple) working example of the new classes, in
nsPluginHostImpl.cpp

I would love to convert a more-complicated example for testing purposes,
especially one that might have a significant performance win. Suggestions?

Comment 7

[Benjamin Smedberg]

Please note that this code currently builds on linux (gcc) and MSVC, but will
probably not build on other systems without a configure test.

Chris Seawood: is it possible to add a configure test for the following sytax
(see nsTHashtable.h in the attached tar file).  If the compiler does not support
this syntax, we can degrade gracefully by omitting the extern declaration (at
the price of a little code duplication):

extern template myClass<T>;

Comment 8

[John Keiser (jkeiser)]

Reading through those files, I just have a few comments to start with:
(1) PLDHashTable allows you to do some really funky cool stuff with entries that
saves memory (such as allowing an object to *point to* another object which
contains the key and the value) ... 
(2) it might also be nice to not require the user to pass in a "key type" to
Get() and Put() but rather use the native type they mean to use, like nsAString
or void*.  Thus you could do myPtr = hashtable->Get(myStr); instead of creating
intermediate key types all the time.

The enumeration thing is wonderful to have.  The templatization is great
(especially the fact that it works on Windows, which I wasn't able to do
initially in nsDoubleHashtable).  Having it threadsafe would be nice, but we
need to think on that decision more--locks carry significant performance costs,
and in most cases in Mozilla thread safety is not an issue.

I'd love to have something with these traits replace nsDoubleHashtable--one
could make a templatized version that these simpler
nsTHashtable<keytype,valtype> hashtables extended and worked from.

Comment 9

[Benjamin Smedberg]

> (2) it might also be nice to not require the user to pass in a "key type" to
> Get() and Put() but rather use the native type they mean to use, like nsAString
> or void*

I will try that. I was trying to avoid additional template parameters: I think I
can do it if the key classes have typedefs indicating the type that they are
wrapping.  What hashtables do we currently use that have void* keys?  That seems
rather odd to me.

> Having it threadsafe would be nice, but we
> need to think on that decision more--locks carry significant performance costs,

Threadsafety is optional for these classes, via the boolean in the constructor.
 If it is not enabled, there is no real performance overhead.

> (such as allowing an object to *point to* another object which
> contains the key and the value) ... 

This would be a slightly different type, but I'll take a crack at it. I don't
have code in my project that could test it; please show me an example in the
mozilla tree where this is needed, so that I can test it properly.

Comment 10

[Benjamin Smedberg]

Attachment: tar of three new files in xpcom/ds

Tar of new files, version 0.2

Comment 11

[Benjamin Smedberg]

Attachment: Patch -u version 0.2

Comment 12

[Benjamin Smedberg]

Attachment: Patch version 0.2, example of usage

Sorry for the spam.  I changed some of the signatures, as recommended by
jkeiser.  

I don't especially like nsISupports* const* nsTISupportsHashtable::Get(...)
(and others like it), but I'm not sure I have a better option; I need a way to
indicate that the key was not found.

This patch is getting close, but I want to give the code a workout.  What
hashtables are used frequently and would be candidates for conversion?

Comment 13

[John Keiser (jkeiser)]

I believe when we do this we need to replace nsDoubleHashtable.  It would not do
to have both nsDoubleHashtable and nsTHashtable in the tree.  I prefer
nsTHashtable if it will compile everywhere; but I think we might need a more
general base class, and I think we can do it without having a special key class
(well, you have to have one but if you are using entry classes it becomes a
no-brainer).

In other words, I think the base nsTHashtable should essentially just take an
entry class, and then the specialized ones with the nice Get() and Put() would
subclass it and create their own entry classes hidden from the user.

Any classes that use nsDoubleHashtable are candidates for conversion which
should work the code out.  nsHashtable itself now uses nsDoubleHashtable and
PLDHashTable underneath; if this code can handle everything nsHashtable needs to
underneath, that's a *great* candidate for such a workout.

I'll try and work up an example of this base class I'm talking about this weekend.

BTW, you can download cvsutils and do "cvsdo add filename" to make it possible
to include those files in the diff, even though you don't have write access to
the repository.  http://www.red-bean.com/cvsutils/

Comment 14

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 108546 [details] [diff] [review]
Patch -u version 0.2

>Index: ds/nsCRT.h

>+  // Computes the hashcode for an nsAString and nsACString
>+  static PRUint32 StringHashCode(const nsAString* str);
>+  static PRUint32 CStringHashCode(const nsACString* str);

These are unnecessary.	HashString already exists (for nsAString& and
nsACString&) in nsReadableUtils.h.

Comment 15

[Benjamin Smedberg]

Attachment: patch -u, version 0.3

I think this patch is almost ready for review... can I get someone to alter the
mac build projects? 

As a landing plan, I would like to land this in the trunk first, to see if any
tinderboxes break.  Then the dependent bugs which convert uses of nsHashtable
to this code can be landed.

Comment 16

[Benjamin Smedberg]

Attachment: patch version 0.4 -u

Version 0.4 adds nsClassHashtable, Emacs modelines, fixes whitespace issues
(carriage returns).  Still no Mac project file updates.

Comment 17

[Benjamin Smedberg]

Attachment: patch -u version 0.5

Same as 0.4, with mac build changes (I hope these are correct).

Comment 18

[Benjamin Smedberg]

Comment on attachment 109255 [details] [diff] [review]
patch -u version 0.5

OK, start picking it apart! :)

Comment 19

[Scott Collins]

big patch, this review will take a little time, but I'm looking at it

Comment 20

[Brendan Eich [:brendan]]

Comment on attachment 109255 [details] [diff] [review]
patch -u version 0.5

Drive-by nit-picks (I'm happy that bsmedberg took up the template cause -- that
shows guts and brains, what more could one ask from a Mozilla hacker ;-):

- if(foo) vs. if( foo ) style discordance;

- if(foo) one-line-then-on-same-line; makes it hard to breakpoint the
then-part, and to my eyes is less readable than always putting the then-part on
its own line;

- else after return non-sequitur:

+  if( res & PL_DHASH_STOP )
+    return PL_DHASH_STOP;
+  else
+    return PL_DHASH_NEXT;

More in a bit.

/be

Comment 21

[Benjamin Smedberg]

Attachment: nsTHashtable patch -u version 0.6

Addresses Brendan's nits.  I would love to get this and a few of its dependents
in before 1.3b freeze...

Comment 22

[John Keiser (jkeiser)]

Comment on attachment 110868 [details] [diff] [review]
nsTHashtable patch -u version 0.6

This is great, but has a few things to be dealt with for bloat / codesize
reduction.  I like the formulation of the entry class, especially the fact that
it works on the key type rather than the void*.  Nice touch.  Still, a number
of design and architecture issues to hash out, especially some code
redundancies we can do without.  (We can always do without code redundancy :)

GENERALLY:
- name arguments with "aArg" instead of "arg".	For example, RemoveEntry(const
KeyType& aKey) instead of "key"
- Locking should be handled as much as possible in nsTHashtable, so that
everything doesn't have to be redone in subclasses like nsInterfaceHashtable. 
For example, GetEntry() and PutEntry() should do the locking, not the Put() and
Get() implementations of subclasses.
- nsClassHashtable and nsInterfaceHashtable really disturb me.	They are almost
100% the same as nsDataHashtable, with just a few changes in the entry class. 
Perhaps it would be possible to make an nsDataHashtableSuper<EntryClass> that
looked for entry->mValue to do its deeds, and pass in nsDataHashtableET,
nsClassHashtableET and nsInterfaceET, respectively.  It could even be a
typedef.  The consumer wouldn't know the difference but the code would all be
in one place.  The entries themselves could almost certainly extend from each
other--Interface and Class could extend Data, if it turns out to be a useful
savings.  nsInterfaceHashtable would need to override Get(), of course, to
provide that extra AddRef.


+++
+++ mozilla/xpcom/ds/nsTHashtable.h 
+++

>  // GetHashFunc(): returns a hash function for KeyType
>  typedef PRUint32 (*HashFuncType)(const KeyType&);
>  static HashFuncType GetHashFunc();

This would be done more easily with a simple PRUint32 GetHashCode(const
KeyType&) instead of grabbing a hash function and going to all that trouble. 
If the function wants to directly call an existing C function it can certainly
do that, and even do it inline so that it's not any different perf-wise.  And
people who do not call another function can hash inline, even.

Also, it should return PLDHashNumber, not PRUint32, even though that's what it
is, because that's the way it's done in PLDHashTable.  Same everywhere this
happens.

>   // placement new -- just put me where you want me!
>   void* operator new(size_t ignored, void* placement);

Is it really necessary for classes to override this?  If not, best make a
comment that it is completely optional.

> if( PL_DHashTableInit( NS_CONST_CAST(PLDHashTable*,&mTable), &sOps, nsnull, sizeof(EntryType), PL_DHASH_MIN_SIZE ) )
>   return PR_TRUE; // succeeded!

The whole EnsureInit() thing bothers me somewhat, but *this* bothers me a lot. 
We lose the initSize information here; and furthermore, it means that we keep
trying to initialize the hashtable even if it failed the first time (which is
unlikely anyway).  Extra code and potentially strange resuls in low-memory
conditions--i.e. operations fail at first and then succeed when memory was
freed up elsewhere.

I'd prefer:
(a) don't try to initialize the hashtable in EnsureInit (preferred)
(b) require Init() to be called (I understand why one would not want to do
this, and EnsureInit() is ok)

> template<class EntryType>
> PLDHashTableOps nsTHashtable<EntryType>::sOps = 

Aha!  This is probably the secret to making this work that I didn't see back
then.  Cool :)

>  // this is unusual but legal... will it break stupid compilers?
>  ((EntryType*) from)->~EntryType();

It's already working in nsDoubleHashtable, so it should be fine.

+++
+++ mozilla/xpcom/ds/nsTHashtable.cpp 
+++

>  /* instantiate common nsInterfaceHashtable uses */

I think it would be best to comment out any that are not currently actually
used, and put a comment in saying to uncomment them as they get used.  Same in
other places you do the same thing, such as nsInterfaceHashtable.h.

+++
+++ mozilla/xpcom/ds/nsHashKeys.h
+++

> class NS_COM nsISupportsHashKey ...
> static PRUint32 s_Hash( const KeyType& key ) { return NS_PTR_TO_INT32(key); }

To make it a good hash key you need to >>2 ... many architectures have the low
2 bits *always* 0.

> nsISupportsHashKey( nsISupports* key ) : mpISupports( key ) { mpISupports->AddRef(); }
> nsISupportsHashKey( const nsISupportsHashKey& toCopy ) : mpISupports( toCopy.mpISupports ) { mpISupports->AddRef(); }
> ~nsISupportsHashKey() { if( mpISupports ) mpISupports->Release(); }

NS_ADDREF and NS_IF_RELEASE are the preferred way to do this.

> class NS_COM nsIDHashKey

I am dubious as to the generality of this.  Is it used in more than one place,
or more than one module at least?  It might be better placed in the module
where it will be used.

+++
+++ mozilla/xpcom/ds/nsInterfaceHashtable.h
+++

> template<class KeyClass,class Interface>
> class nsInterfaceHashtableET : private PLDHashEntryHdr 

I think you could save some code here if you had the actual KeyClass extend
PLDHashEntryHdr and had this class extend *that*.  Think of the KeyClass as an
actual entry struct (which it actually is).  Doing this has the added benefit
of making it so that KeyClass and EntryStruct template requirements don't have
to be specified separately, *and* (perhaps more importantly) it becomes
incredibly easy to create a hash set by just doing (for example)
nsTHashTable<nsCStringKeyClass>.

>  KeyClass mKeyClass;

It's a key, not a key class :)	KeyClass mKey; would be fine.

> template<class KeyClass,class Interface>
> class nsInterfaceHashtable
> : private nsTHashtable< nsInterfaceHashtableET<KeyClass,Interface> >

It seems to me that this deserves a has-a relationship, not an is-a
relationship.

> struct s_EnumArgs
> { EnumFunction func; void* userArg; };

This is entirely copied from nsTHashtable, as is which is the *parent class*. 
Perhaps you are too aggressively privatizing and need to do some (at least)
protected inheritance.

>  typedef PLDHashOperator
>    (*PR_CALLBACK EnumReadFunction)( const KeyType&,
>                                 Interface* already_addrefed, void* userArg);

This should not be already addrefed.  That works totally differently from all
other xpcom functions; it requires the called function to release it, AFAICT.

Comment 23

[Benjamin Smedberg]

> - Locking should be handled as much as possible in nsTHashtable, so that
> For example, GetEntry() and PutEntry() should do the locking, not the Put() and

GetEntry and PutEntry are inherently non-threadsafe, because they return a
pointer to a struct that might change location, so the threadlocks need to occur
at the outermost data level.

> - nsClassHashtable and nsInterfaceHashtable really disturb me.	They are 

I will work at combining the code where possible.  Simple inheritence is
limited, because the functions have differing signatures (part of their
reason-for-being).

>>  // placement new -- just put me where you want me!
>>  void* operator new(size_t ignored, void* placement);
> Is it really necessary for classes to override this?
Yes

> The whole EnsureInit() thing bothers me somewhat, but *this* bothers me a lot. 

OK, I'm abandoning EnsureInit() and requiring an Init() call, to stay consistent
with other parts of the codebase.

> I think it would be best to comment out any that are not currently actually
> used, and put a comment in saying to uncomment them as they get used.  Same in

I'll leave in the ones I'm going to use imminently (see the dependent bugs), and
remove the others.  I'll also write a comment about how to add more (you have to
add them to the header, the cpp file, and dlldeps).

> +++ mozilla/xpcom/ds/nsHashKeys.h
>>class NS_COM nsISupportsHashKey ...
>>static PRUint32 s_Hash( const KeyType& key ) { return NS_PTR_TO_INT32(key); }
> To make it a good hash key you need to >>2 ... many architectures have the low
> 2 bits *always* 0.

as you wish... I was just copying from nsSupportsKey

>>class NS_COM nsIDHashKey
> I am dubious as to the generality of this.  Is it used in more than one place,
> or more than one module at least?  It might be better placed in the module
> where it will be used.

I would prefer it in nsCRT, because it uses the same algorithm as the
neighboring hash functions, and has approximately the same generality; I will
relocate it if you insist.

> I think you could save some code here if you had the actual KeyClass extend
> PLDHashEntryHdr and had this class extend *that*.  Think of the KeyClass as an

Excellent! I love logical class hierarchies.

> incredibly easy to create a hash set by just doing (for example)
> nsTHashTable<nsCStringKeyClass>

Does "hash set" mean "hashtable with just keys?"

>>struct s_EnumArgs
>>{ EnumFunction func; void* userArg; };
> This is entirely copied from nsTHashtable, as is which is the *parent class*. 
> Perhaps you are too aggressively privatizing and need to do some (at least)
> protected inheritance.
Unfortunately, no.  EnumFunction is a different signature in the derived class.

>> typedef PLDHashOperator
>>   (*PR_CALLBACK EnumReadFunction)( const KeyType&,
>>                                Interface* already_addrefed, void* userArg);
> This should not be already addrefed.  That works totally differently from all
> other xpcom functions; it requires the called function to release it, AFAICT.

I asked scc about this a while back, and I'm pretty sure it's correct. It is an
XPCOM getter. If you don't addref, you've broken threadsafety.

Thanks for the comments/suggestions; a new patch will come forth shortly ;)

Comment 24

[John Keiser (jkeiser)]

> GetEntry and PutEntry are inherently non-threadsafe, because they return a
> pointer to a struct that might change location, so the threadlocks need to
> occur at the outermost data level.

Makes sense.  Combining classes should be enough to deal with the huge amount of
locking code, anyway.

> I will work at combining the code where possible.  Simple inheritence is
> limited, because the functions have differing signatures (part of their
> reason-for-being).

Actually, the signatures are the same, except that Class and Interface do
pointer-to-type rather than type; that could easily be accounted for when
talking to the parent class.  Just checked, and constructor, destructor, Get,
Put, Remove, EnumFunction, EnumReadFunction, Enumerate, EnumerateRead, and Reset
all follow this convention.

Oh, I just noticed, Clear() is a better name than Reset() in general--I see
nsHashtable did that, but nsVoidArray and even pldhash do Clear().  We may as
well make our syntax consistent while we're doing this.

> > Is it really necessary for classes to override this?
> Yes

More explanation is necessary, because I am *not* overriding it in
nsDoubleHashtable and placement new is working just fine.

> OK, I'm abandoning EnsureInit() and requiring an Init() call, to stay
> consistent with other parts of the codebase.

The more I think of EnsureInit, the more I like the idea, just once the
hashtable fails to initialize, it should *stay* failed.  Your call in the end; I
can see pros and cons either way.

> I would prefer it in nsCRT, because it uses the same algorithm as the
> neighboring hash functions, and has approximately the same generality; I will
> relocate it if you insist.

Well, nsCRT.h is not the place for ID hashing functions anyway (the string hash
functions are there because it does other string stuff, not because it's a
repository for hashing functions), but the simplest way to deal with that is to
make the hash function a part of nsIDKey itself (especially when you make
HashKey() a direct function in the key class).  I suppose it won't take too long
to compile, so putting it in nsHashKeys doesn't hurt.

> Does "hash set" mean "hashtable with just keys?"

Yep.  See xpcom/ds/nsHashSets.h.  I have had occasion to use them in
nsHTMLSelectElement.h.  The major point is you have a set of things and your
main operation will be to test whether the set contains a particular member. 
You might want to add an Exists() method to easily support this.

> I asked scc about this a while back, and I'm pretty sure it's correct. It is
> an XPCOM getter. If you don't addref, you've broken threadsafety.

As discussed on IRC, we either need to do *both* addref and release in the enum
function or do neither (and lock the hashtable during the operation).

Thanks!

Comment 25

[Benjamin Smedberg]

Attachment: nsTHashtable patch -u version 0.7

Wooooee.   Have at it. It's all doxygenated, for good measure.	It compiles in
win MSVC 6, linux gcc 3.2, and I'm pretty sure it also compiles in gcc 2.95,
but I don't have one right now.

I removed the non-const enumerators, because of our discussion on IRC about the
problems and how they probably won't be needed.

I required the Init() call.

I changed most function signatures to "aKey" per your request, but I didn't
change the function signatures of PLDHash callbacks (for consistency's sake
with the existing declarations).

There are lots of typedef typename redundancies in the classes, but these were
required to get both MSVC and gcc to compile the functions cleanly... they
don't like inheriting names from base templates to derived templates in
function signatures.

Comment 26

[Benjamin Smedberg]

Comment on attachment 111125 [details] [diff] [review]
nsTHashtable patch -u version 0.7

I realized that the "nsCOMPtr voodoo" in nsISupportsHashKey is incorrect and
really does return a reference to a stack object.  Cleanup coming shortly.

Comment 27

[Benjamin Smedberg]

Attachment: nsTHashtable patch -u -N version 0.8

I had to do some work with the typedefs KeyType and KeyTypePointer to get the
keys to pass correctly. KeyType is a simple type (PRUint32) when it can be
passed directly, and a const-reference (const nsAString&) when it can't.  This
solves passing nsISupports* as a reference, which can't be done with nsCOMPtr. 
I also changed the root nsTHashtable to use KeyTypePointer, because it is
potentially more flexible.

This patch does not do hash sets (mainly to avoid the extra review time), but
it is trivial once this gets in.

Comment 28

[John Keiser (jkeiser)]

Comment on attachment 111246 [details] [diff] [review]
nsTHashtable patch -u -N version 0.8

1. NS_ABORT_IF_FALSE ... use NS_ASSERTION like everywhere else, there's no
reason we want to specifically abort (even though we *don't* abort).

The Interface / ClassHashtable refactor is quite nice, thanks :)

2. >   if( mTable.entrySize )
> {
>     NS_ERROR("nsTHashtable::Init() should not be called twice.");
>   }

I think you meant to return PR_FALSE; here ...

3. scc or jag needs to comment on the use of nsSharableString vs. nsString in
the string keys.

STYLE

Now on to the Mozilla style bugs:

http://www.johnkeiser.com/cgi-bin/jst-review-cgi.pl?patch_file=&patch_url=http%
3A%2F%2Fbugzilla.mozilla.org%2Fattachment.cgi%3Fid%3D111246&patch_text=&reason_
type=%21&reason_type=A&reason_type=B&reason_type=E&reason_type=F&reason_type=L&
reason_type=N&reason_type=O&reason_type=P&reason_type=Q&reason_type=R&reason_ty
pe=S&reason_type=W&reason_type=X&reason_type=%7B

1. All over the place you are doing if( ) ... if ( ) is the accepted motif. 
Same with the for loop.

2. There are a *lot* of over-80-char lines in there, please make them small ...
some are totally infeasible, but if you have (for example) a list of arguments
with a comma, that is a good start.

3. > template<class KeyClass,class DataType,class UserDataType>
> PRBool nsBaseHashtable<KeyClass,DataType,UserDataType>::Init( PRUint32 initSize, PRBool threadSafe )

Method names go at the beginning of the line: you can either put PRBool on its
own line (my preference), or at the end of the previous line.

4. > : KeyClass( toCopy ),

Operator at the beginning of the line.	This one is legitimate.

5. Excessive spacing.  You are putting spaces right after ( and right before )
where in most cases that is not the accepted style (only when it gets really
out of hand like nested templates do we do stuff like that).  Please fix that. 
nsVoidArray.cpp/.h is a good guide for this.

I don't see any other semantic issues, I'll r= with that.

Comment 29

[Benjamin Smedberg]

Attachment: nsTHashtable patch -u -N version 0.9

Fixed jkeiser's style nits. Changed nsC?StringHashKey to nsString from
nsSharableString, because its smaller and no user at the moment needs the
sharable.  If it would be useful later, it's a one-line change, or we can
create a new KeyClass.

(I used NS_ABORT_IF_FALSE because the header file says that NS_ASSERTION is
obsolete... I must learn not to believe everything I read.)

Comment 30

[Benjamin Smedberg]

nsPluginHostImpl.cpp changed during this process, so there are some changes in
the extern declarations:

we won't need nsDataHashtable<nsCStringHashKey,PRUint32>

nsDataHashtable<nsUint32HashKey,PRUint32> will be changed to
nsDataHashtable<nsUint32HashKey,PRInt32>

I'm not uploading a new patch (yet).  This one should be good enough for review.

Comment 31

[John Keiser (jkeiser)]

Comment on attachment 111405 [details] [diff] [review]
nsTHashtable patch -u -N version 0.9

r=jkeiser, thanks many times over :)

Comment 32

[Benjamin Smedberg]

Comment on attachment 111405 [details] [diff] [review]
nsTHashtable patch -u -N version 0.9

Changing sr request to alecf (though scc, if you have time please look at it!).

Comment 33

[Alec Flett]

Comment on attachment 111405 [details] [diff] [review]
nsTHashtable patch -u -N version 0.9

this looks great!
only issue is the nsHashAutoPtr stuff - why can't we use nsAutoPtr here? (and
if I have to ask.. it belongs in a comment..)

either use nsAutoPtr or explain what we're waiting for, and sr=alecf

Comment 34

[Benjamin Smedberg]

Attachment: nsTHashtable final... class-hash uses nsAutoPtr

alecf: when I started this patch nsAutoPtr was still "in process." Final patch
for checkin.

Carrying over r/sr

Comment 35

[John Keiser (jkeiser)]

Fix checked in, for good or ill.

Comment 36

[Darin Fisher]

so, Zdiff:+12384 (on beast)... not a big problem given that nsTHashtable and
friends are meant to replace nsHashtable and friends?  but, when will the
conversion happen?  can nsHashtable be (easily) implemented in terms of
nsTHashtable?

Comment 37

[Benjamin Smedberg]

The actual codesize increase on win32 is ~2k bytes (1k per template
instantiation). The other 9k is in the DLL export section! And I bet that other
DLLs importing these symbols would have a similar 9k in their import table.
Unless someone can figure out how to eliminate the 9k dllexport table, we should
axe dynamic linking of the the hash-templates on win32.

Codesize increase on linux is ~3.6k (1.8k per template instantiation).

Comment 38

[Cathleen]

patch increased 4k in libxpcom.so  anyway to optimize it better?

  libxpcom.so
  	Total:	      +4196 (+4200/-4)
  	Code:	      +4028 (+4032/-4)
  	Data:	       +168 (+168/+0)
  	      +3644 (+3644/+0)	W (CODE)
  		      +3644 (+3644/+0)	UNDEF:libxpcom.so:W
  			       +164	nsInterfaceHashtable<nsStringHashKey,
nsISupports>::Get(nsAString const &, nsISupports **) const
  			       +148	nsBaseHashtable<nsUint32HashKey, int, int>::Get(unsigned int,
int *) const
  			       +140	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::Get(nsAString const &, nsISupports **) const
  			       +140	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::Put(nsAString const &, nsISupports *)
  			       +140	nsBaseHashtable<nsUint32HashKey, int, int>::Put(unsigned int, int)
  			       +136	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_MatchEntry(PLDHashTable *, PLDHashEntryHdr const *,
void const *)
  			       +112	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::Init(unsigned int, int)
  			       +112	nsBaseHashtable<nsUint32HashKey, int, int>::Init(unsigned int, int)
  			       +104	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::EnumerateRead(PLDHashOperator (*)(nsAString const &,
nsCOMPtr<nsISupports>, void *), void *) const
  			       +104	nsBaseHashtable<nsUint32HashKey, int,
int>::EnumerateRead(PLDHashOperator (*)(unsigned int, int, void *), void *) const
  			        +92	nsBaseHashtable<nsUint32HashKey, int, int>::Remove(unsigned int)
  			        +88	nsBaseHashtableET<nsStringHashKey, nsCOMPtr<nsISupports>
>::~nsBaseHashtableET(void)
  			        +88	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::Init(unsigned int)
  			        +88	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::Init(unsigned int)
  			        +84	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::Remove(nsAString const &)
  			        +84	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::~nsBaseHashtable(void)
  			        +84	nsBaseHashtable<nsUint32HashKey, int, int>::~nsBaseHashtable(void)
  			        +80	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::Clear(void)
  			        +80	nsBaseHashtable<nsUint32HashKey, int, int>::Clear(void)
  			        +76	nsBaseHashtableET<nsStringHashKey, nsCOMPtr<nsISupports>
>::nsBaseHashtableET(nsBaseHashtableET<nsStringHashKey, nsCOMPtr<nsISupports> >
const &)
  			        +72	nsInterfaceHashtable<nsStringHashKey,
nsISupports>::~nsInterfaceHashtable(void)
  			        +68	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::s_EnumReadStub(PLDHashTable *, PLDHashEntryHdr *, unsigned int,
void *)
  			        +68	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::~nsTHashtable(void)
  			        +68	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::~nsTHashtable(void)
  			        +64	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_CopyEntry(PLDHashTable *, PLDHashEntryHdr const *,
PLDHashEntryHdr *)
  			        +64	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_CopyEntry(PLDHashTable *, PLDHashEntryHdr const *, PLDHashEntryHdr *)
  			        +60	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::EnumerateEntries(PLDHashOperator
(*)(nsBaseHashtableET<nsStringHashKey, nsCOMPtr<nsISupports> > *, void *), void *)
  			        +60	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::EnumerateEntries(PLDHashOperator (*)(nsBaseHashtableET<nsUint32HashKey, int>
*, void *), void *)
  			        +52	nsBaseHashtableET<nsStringHashKey, nsCOMPtr<nsISupports>
>::nsBaseHashtableET(nsAString const *)
  			        +48	nsBaseHashtableET<nsUint32HashKey, int>::~nsBaseHashtableET(void)
  			        +48	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::Clear(void)
  			        +48	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_InitEntry(PLDHashTable *, PLDHashEntryHdr *, void
const *)
  			        +48	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int> >::Clear(void)
  			        +48	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_InitEntry(PLDHashTable *, PLDHashEntryHdr *, void const *)
  			        +40	nsBaseHashtable<nsStringHashKey, nsCOMPtr<nsISupports>,
nsISupports *>::nsBaseHashtable(void)
  			        +40	nsBaseHashtable<nsUint32HashKey, int, int>::nsBaseHashtable(void)
  			        +40	nsInterfaceHashtable<nsStringHashKey,
nsISupports>::nsInterfaceHashtable(void)
  			        +40	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::GetEntry(nsAString const *) const
  			        +40	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::PutEntry(nsAString const *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::RemoveEntry(nsAString const *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_ClearEntry(PLDHashTable *, PLDHashEntryHdr *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_HashKey(PLDHashTable *, void const *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::GetEntry(unsigned int const *) const
  			        +40	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::PutEntry(unsigned int const *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::RemoveEntry(unsigned int const *)
  			        +40	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_ClearEntry(PLDHashTable *, PLDHashEntryHdr *)
  			        +32	nsBaseHashtable<nsUint32HashKey, int,
int>::s_EnumReadStub(PLDHashTable *, PLDHashEntryHdr *, unsigned int, void *)
  			        +24	nsBaseHashtableET<nsUint32HashKey,
int>::nsBaseHashtableET(nsBaseHashtableET<nsUint32HashKey, int> const &)
  			        +24	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_MatchEntry(PLDHashTable *, PLDHashEntryHdr const *, void const *)
  			        +20	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_EnumStub(PLDHashTable *, PLDHashEntryHdr *,
unsigned int, void *)
  			        +20	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_EnumStub(PLDHashTable *, PLDHashEntryHdr *, unsigned int, void *)
  			        +16	nsBaseHashtableET<nsUint32HashKey,
int>::nsBaseHashtableET(unsigned int const *)
  			        +16	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::nsTHashtable(void)
  			        +16	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::nsTHashtable(void)
  			        +12	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::s_GetKey(PLDHashTable *, PLDHashEntryHdr *)
  			        +12	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_GetKey(PLDHashTable *, PLDHashEntryHdr *)
  			        +12	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int>
>::s_HashKey(PLDHashTable *, void const *)
  	       +384 (+388/-4)	T (CODE)
  		       +384 (+388/-4)	UNDEF:libxpcom.so:T
  			       +288	__static_initialization_and_destruction_0
  			        +64	nsIDHashKey::HashKey(nsID const *)
  			        +24	global constructors keyed to
PL_DHashStubEnumRemove(PLDHashTable *, PLDHashEntryHdr *, unsigned int, void *)
  			        +12	PL_DHashStubEnumRemove(PLDHashTable *, PLDHashEntryHdr *,
unsigned int, void *)
  			         -4	XPT_Do8
  	       +132 (+132/+0)	B (DATA)
  		       +132 (+132/+0)	UNDEF:libxpcom.so:B
  			        +64	nsTHashtable<nsBaseHashtableET<nsUint32HashKey, int> >::sOps
  			        +36	nsTHashtable<nsBaseHashtableET<nsStringHashKey,
nsCOMPtr<nsISupports> > >::sOps
  			        +24	gDebugLog
  			         +4	_.tmp_0.1656
  			         +4	_.tmp_1.1657
  	        +32 (+32/+0)	R (DATA)
  		        +32 (+32/+0)	UNDEF:libxpcom.so:R
  			        +32	str.1830
  	         +4 (+4/+0)	? (DATA)
  		         +4 (+4/+0)	UNDEF:libxpcom.so:?
  			         +4	__CTOR_LIST__

Comment 39

[Boris Zbarsky [:bzbarsky]]

Cathleen, see comment 36.

Comment 40

[Benjamin Smedberg]

Bug 200709 has cleanup of this bug.

1) nsUint32HashKey was declared incorrectly.
2) removal of dynamic linking.

The hashtable templates do have a codesize cost, but I don't think this cost is
significantly more than using pldhash directly. As I do code conversions from
nsDoubleHashtable I will run codesighs tests to make sure.

Comment 41

[Benjamin Smedberg]

*** Bug 161220 has been marked as a duplicate of this bug. ***