Ok, I know we tackled a variation of this once in bug 72722.. but I'd like to consider using PLDHashTable instead of PLHashTable for the inner entries of the hashtable. In bug 72722, we tried to contain the hashkey itself in the pldhashtable, and it was way too much work to be worth the time. However, it meant leaving nsHashtable in its super-malloc-happy state where every entry in the hashtable has 2 seperate allocations for the key - one for the nsHashKey derivative, and one for the PLHashTable's little 16-byte PLHashEntry. We're doing a LOT of excess allocations because of this. according to the bloat logs, there are over 100,000 nsHashKeys created in a typical run. Assuming some large portion of those are actually added to a hashtable, that's a lot of extra 16 byte allocations (Which are probably bigger due to malloc overhead) So I've managed to convert nsHashtable over to using PLDHashTable for the inner entries.. not only does this decrease the size of the HashEntry to 12 bytes each, but they are allocated in bulk by pldhash. Anyway, patch forthcoming. I still have to do testing to see how this affects performance, but I think we're going to get a big win in terms of number of allocations, and the heap should be much less fragmented.

it was almost too easy. This patch is totally untested, but it compiles. I hope to have some numbers later today... I'm also sure that there's some typo in here that makes this particular patch just be broken. But maybe I'm just being pessimistic :)

oh, duh assign this back to me.

sure enough, a few typos turned this into a crash-on-startup :) but with two lines tweaked, we're back in business. Looking for reviews....

I don't have time to do a full review, but I saw one thing while glancing over this: + HTHashEntry* he = + NS_STATIC_CAST(HTHashEntry*, + PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_ADD)); - if ((he = *hep) != NULL) { + if (he->key) { you'll need to null check |he| here before using it, PL_DHashTableOperate(..., PL_DHASH_ADD) will return null if OOM.

alecf: who are the high-frequency/call-count consumers of nsHashtable who drove the nsHashKey count above 1e5 on a typical run? Too bad we still have to have nsHashKey separately allocated. Perhaps some (or only one?) of those high-freq/call users should switch from nsHashtable to raw PLDHashTable or to jkeiser's spanky nsDoubleHashtable, nsHashSet, etc. /be

brendan: I'll try a run in spacetrace to see if I can figure out who the high frequency callers are. You're right of course that those callers in particular need to be weaned off nsHashtable.

IIRC from my daze hacking XPCOM, we also use (stack-allocated) nsHashKeys for every lookup, which might drive those numbers up somewhat artificially. Of course, nsStringHashKey or whatever is no doubt allocating three or four copies of the provided string key, etc., so the concern is still likely valid. I just want to make sure that if we find out that 80% of the nsHashKey allocations are on the stack, we don't abandon this righteous course. =)

ok, so a little work in spacetrace revealed a few of the worst nsHashtable offenders: nsCategoryManager::AddCategoryEntry nsBindingManager::SetInsertionParent nsBindingManager::SetContentListFor nsBindingManager::SetBinding nsBindingManager::SetAnonymousNodesFor nsXBLProtoImpl::InitTargetObjects nsXBLBinding::GetInsertionPointsFor nsXULDocument::AddReference That gives us a good start. CC'ing Boris because I'll bet he'd like to see some of this.

(I should add that if I'm reading spacetrace right, these allocations account for roughly 3000 of the ns*Key allocations.. and since we really don't know how many of the nsHashKey allocations for trace-malloc are actually from the stack, we can guess that this is a lower bound of perhaps 3% of the total heap allocations, but with potential to be much more)

filed bug 177545 on the nsBindingManager issues.. feel free to cc yourself over there.

I'll review this tonight. /be

Comment on attachment 104545 [details] [diff] [review] switch to pldhash v1.01 >@@ -113,14 +112,14 @@ class NS_COM nsHashtable { > protected: > // members > PRLock* mLock; >- PLHashTable mHashtable; >+ PLDHashTable mHashtable; > PRBool mEnumerating; Nit: line 'em up, maybe at next 1-mod-4 column? >@@ -158,7 +157,9 @@ class NS_COM nsObjectHashtable : public > PRBool RemoveAndDelete(nsHashKey *aKey); > > protected: >- static PRIntn PR_CALLBACK CopyElement(PLHashEntry *he, PRIntn i, void *arg); >+ static PLDHashOperator PR_CALLBACK CopyElement(PLDHashTable* table, >+ PLDHashEntryHdr* hdr, >+ PRUintn i, void *arg); PRUint32 i, no? Better match types exactly, in case of 64-bit PRUintn. >@@ -200,7 +201,9 @@ class NS_COM nsSupportsHashtable > > private: > static PRBool PR_CALLBACK ReleaseElement(nsHashKey *, void *, void *); >- static PRIntn PR_CALLBACK EnumerateCopy(PLHashEntry *, PRIntn, void *); >+ static PLDHashOperator PR_CALLBACK EnumerateCopy(PLDHashTable*, >+ PLDHashEntryHdr* hdr, >+ PRUint32 i, void *arg); (That's more like it!) >+PR_STATIC_CALLBACK(PRBool) >+matchKeyEntry(PLDHashTable*, const PLDHashEntryHdr* entry, >+ const void* key) > { >+ const HTHashEntry* hashEntry = >+ NS_STATIC_CAST(const HTHashEntry*, entry); > >+ if (hashEntry->key == key) return PR_TRUE; > >+ if (!hashEntry->key || !key) return PR_FALSE; > >+ const nsHashKey* otherKey = NS_REINTERPRET_CAST(const nsHashKey*, key); >+ return otherKey->Equals(hashEntry->key); > } (I deleted the - lines for clarity.) matchEntry should *never* be called with a null key param, AFAICT. Nor should it be called on an entry with a null key pointer (unless you left an ADDed entry in an uninitialized state). Why is the second if-return necessary? Nit: put the returns on their own lines, consistently, for debugability. >+PR_STATIC_CALLBACK(void) >+clearHashEntry(PLDHashTable* table, PLDHashEntryHdr* entry) > { >- if (flag == HT_FREE_ENTRY) { >- delete (nsHashKey *) (entry->key); >- PR_DELETE(entry); >- } >+ HTHashEntry* hashEntry = NS_STATIC_CAST(HTHashEntry*, entry); >+ >+ // leave it up to the nsHashKey destructor to free the "value" >+ delete hashEntry->key; >+ hashEntry->key = nsnull; Shouldn't you null value? I guess it doesn't matter if you only ever test for null key to decide whether PL_DHASH_ADD found or created an entry, but I'd do it just for sanity's sake, at least #ifdef DEBUG. >+ HTHashEntry* he = NS_STATIC_CAST(HTHashEntry*, hdr); BTW, isn't HashEntry or HTEntry a better name? HTHashEntry seems redundant, although HTEntry is ok if you're worried about HashEntry colliding with some other typename (from what include, tho?). >@@ -227,14 +142,10 @@ nsHashtable::nsHashtable(PRUint32 aInitS > : mLock(NULL), mEnumerating(PR_FALSE) > { > MOZ_COUNT_CTOR(nsHashtable); >- PRStatus status = PL_HashTableInit(&mHashtable, >- aInitSize, >- _hashValue, >- _hashKeyCompare, >- _hashValueCompare, >- &_hashAllocOps, >- NULL); >- PR_ASSERT(status == PR_SUCCESS); >+ >+ PRBool result = PL_DHashTableInit(&mHashtable, &hashtableOps, nsnull, >+ sizeof(HTHashEntry), aInitSize); >+ PR_ASSERT(result); Don't assume malloc won't fail. Ok, so you assert here, but where later do you null test mHashtable.entryStore out the wazoo (don't, I'm just asking to point out the potential problem)? Are we giving up on tolerating malloc failure? The JS engine must, it runs in small-mem embeddings where OOM is not fatal. > void *nsHashtable::Put(nsHashKey *aKey, void *aData) > { > void *res = NULL; >- PLHashNumber hash = aKey->HashCode(); >- PLHashEntry *he; > > if (mLock) PR_Lock(mLock); > > // shouldn't be adding an item during enumeration > PR_ASSERT(!mEnumerating); >- PLHashEntry **hep = PL_HashTableRawLookup(&mHashtable, hash, (void *) aKey); >+ >+ HTHashEntry* he = >+ NS_STATIC_CAST(HTHashEntry*, >+ PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_ADD)); > >- if ((he = *hep) != NULL) { >+ if (he->key) { >+ // existing entry, need to boot the old value > res = he->value; > he->value = aData; > } else { >+ // new entry (leave res == null) > nsHashKey* key = aKey->Clone(); >- if (key) { >- PL_HashTableRawAdd(&mHashtable, hep, hash, >- (void *)key, aData); >- } >- else >- res = NULL; >+ he->key = key; key is used once, so why bother with the formerly useful local variable? >@@ -309,9 +210,15 @@ void *nsHashtable::Get(nsHashKey *aKey) > { > if (mLock) PR_Lock(mLock); > >- void *ret = mEnumerating ? >- PL_HashTableLookupConst(&mHashtable, (void *) aKey) : >- PL_HashTableLookup(&mHashtable, (void *) aKey); >+ HTHashEntry* entry = >+ NS_STATIC_CAST(HTHashEntry*, >+ PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_LOOKUP)); >+ void *ret; >+ if (PL_DHASH_ENTRY_IS_FREE(entry)) >+ ret = nsnull; >+ else >+ ret = entry->value; Nit: void *ret = PL_DHASH_ENTRY_IS_BUSY(entry) ? entry->value : nsnull; >@@ -319,19 +226,26 @@ void *nsHashtable::Get(nsHashKey *aKey) > > void *nsHashtable::Remove(nsHashKey *aKey) > { >- PLHashNumber hash = aKey->HashCode(); >- PLHashEntry *he; > > if (mLock) PR_Lock(mLock); > > // shouldn't be adding an item during enumeration > PR_ASSERT(!mEnumerating); >- PLHashEntry **hep = PL_HashTableRawLookup(&mHashtable, hash, (void *) aKey); >- void *res = NULL; > >- if ((he = *hep) != NULL) { >- res = he->value; >- PL_HashTableRawRemove(&mHashtable, hep, he); >+ >+ // need to see if the entry is actually there, in order to get the >+ // old value for the result >+ HTHashEntry* entry = >+ NS_STATIC_CAST(HTHashEntry*, >+ PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_LOOKUP)); >+ void *res; >+ >+ if (PL_DHASH_ENTRY_IS_FREE(entry)) >+ // value wasn't in the table anyway >+ res = nsnull; >+ else { >+ res = entry->value; >+ PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_REMOVE); Why not save re-hashing and use PL_DHashTableRawRemove? The old code used the equivalent "raw-remove" function in the "hit" case. >@@ -342,19 +256,23 @@ void *nsHashtable::Remove(nsHashKey *aKe > // XXX This method was called _hashEnumerateCopy, but it didn't copy the element! > // I don't know how this was supposed to work since the elements are neither copied > // nor refcounted. >-static PRIntn PR_CALLBACK _hashEnumerateShare(PLHashEntry *he, PRIntn i, void *arg) >+PR_STATIC_CALLBACK(PLDHashOperator) >+hashEnumerateShare(PLDHashTable *table, PLDHashEntryHdr *hdr, >+ PRUint32 i, void *arg) > { > nsHashtable *newHashtable = (nsHashtable *)arg; >- newHashtable->Put((nsHashKey *) he->key, he->value); >- return HT_ENUMERATE_NEXT; >+ HTHashEntry * he = NS_STATIC_CAST(HTHashEntry*,hdr); Nit: space after comma? >@@ -422,14 +342,10 @@ nsHashtable::nsHashtable(nsIObjectInputS > rv = aStream->Read32(&count); > > if (NS_SUCCEEDED(rv)) { >- PRStatus status = PL_HashTableInit(&mHashtable, >- count, >- _hashValue, >- _hashKeyCompare, >- _hashValueCompare, >- &_hashAllocOps, >- NULL); >- if (status != PR_SUCCESS) { >+ PRBool status = >+ PL_DHashTableInit(&mHashtable, &hashtableOps, >+ nsnull, sizeof(HTHashEntry), count); >+ if (!status) { > rv = NS_ERROR_OUT_OF_MEMORY; Here's where you might clear mHashtable.ops or otherwise mark the table as unconstructed. Assuming the rest of the code tests ops before calling PL_DH* functions and macros -- or asserts(ops) at least, for #ifdef DEBUG sanity. >+ HTHashEntry *he = NS_STATIC_CAST(HTHashEntry*, hdr); Nit: use entry or he consistently (see typename nit above). >+ > void* newElement = >- newHashtable->mCloneElementFun((nsHashKey*)he->key, he->value, >+ newHashtable->mCloneElementFun(he->key, he->value, > newHashtable->mCloneElementClosure); > if (newElement == nsnull) >- return HT_ENUMERATE_STOP; >- newHashtable->Put((nsHashKey*)he->key, newElement); Nits: NS_STATIC_CAST(nsHashKey*, ...) instead of (nsHashKey*) ? And so on below. /be

Ugh, I'm being inconsistent in bug comments lately: >Here's where you might clear mHashtable.ops or otherwise mark the table as >unconstructed. Assuming the rest of the code tests ops before calling PL_DH* >functions and macros -- or asserts(ops) at least, for #ifdef DEBUG sanity. The proper concern is OOM in a release build leading to null pointer crashes in pldhash.c code, which does not and should not have to null-defend. Just because we can't signal OOM from constructors, we seem to have to make all methods that are callable on an apparently-successfully-constructed nsHashtable instance test for an OOM during construction. My "or assert(ops)..." nonsense doesn't help release builds, and asserting that a pointer is non-null is vacuous in a debug build, if you're gonna crash anyway and the assertion doesn't tell you more than the crash dump or debugger would. What to do? I wish we could ignore OOM (it does lead to thrashing VM till your process or OS dies, depending on OS quality), but not all embeddings real and contemplated use VM. We need to do something. A better approach might be to move all fallible construction logic into an Init method whose r.v. could be tested, but that's an API change. I don't see an alternative to null-testing before PL_DH* calls in each and every method. Anyone have a better idea? /be

brendan: thanks for the review, I'll have a new patch soon as for the OOM stuff, yeah, I was really uncertain about what to do there because the initialization was in a constructor.. but I guess checking mHashtable.ops before every operation is the best option here.

ok, here's an updated patch. Brendan, the only issue I had left was the comment in PL_DHashRawRemove, say that it doesn't shrink the table if it gets underloaded.. I'm pretty sure this is ok based on my theory that most of our hashtable usage doesn't involve having a lot of mostly empty hashtables that had many elements at one time. Anyway, care to do another review here? I'm pretty sure I've addressed all your comments...

Comment on attachment 106126 [details] [diff] [review] switch to pldhash v1.02 >@@ -158,7 +157,9 @@ class NS_COM nsObjectHashtable : public > PRBool RemoveAndDelete(nsHashKey *aKey); > > protected: >- static PRIntn PR_CALLBACK CopyElement(PLHashEntry *he, PRIntn i, void *arg); >+ static PLDHashOperator PR_CALLBACK CopyElement(PLDHashTable* table, >+ PLDHashEntryHdr* hdr, >+ PRUintn i, void *arg); PRUint32 i, not PRUintn (like the similar function below). > > nsHashtableCloneElementFunc mCloneElementFun; > void* mCloneElementClosure; >@@ -200,7 +201,9 @@ class NS_COM nsSupportsHashtable > > private: > static PRBool PR_CALLBACK ReleaseElement(nsHashKey *, void *, void *); >- static PRIntn PR_CALLBACK EnumerateCopy(PLHashEntry *, PRIntn, void *); >+ static PLDHashOperator PR_CALLBACK EnumerateCopy(PLDHashTable*, >+ PLDHashEntryHdr* hdr, >+ PRUint32 i, void *arg); [ . . . ] >+ if (PL_DHASH_ENTRY_IS_FREE(entry)) >+ // value wasn't in the table anyway >+ res = nsnull; >+ else { >+ res = entry->value; >+ PL_DHashTableRawRemove(&mHashtable, entry); > } > Style nit: brace the two-line (including comment) "then" part above, to match the necessary bracing of the else part, which also appears to have two statements in its block (and does -- this is really to help skim lines with brace-checking glasses on, so that the skimmer doesn't have to strip comments). Looks great otherwise -- sr=brendan@mozilla.org with the PRUint32 fix and with nits picked. /be

Comment on attachment 106126 [details] [diff] [review] switch to pldhash v1.02 The patch looks fine. Can the pldhash callback ever pass a null entry? did you get any numbers on performance and/or footprint? Did you verify that we do reduce allocations as you imply in comment #9?

>Can the pldhash callback ever pass a null entry? No; already addressed for other params in comment #12, just reiterating that free and removed entries are not passed to any callback. >did you get any numbers on performance and/or footprint? Did you verify that >we do reduce allocations as you imply in comment #9? It's be nice to have numbers; this patch has to reduce allocations, thought, because plhash.c mallocs every entry, whereas pldhash.c fuses all entries into one malloc'ed array allocation. /be

I'll gather numbers, either by making a release build or by doing a late-night tinderbox test (i.e. check it in while checkin traffic is low, watch the numbers for a few hours, back it out if the numbers go up)

I think there was a warning introduced here that is given for every file that includes nsHashtable.h: ../../../dist/include/xpcom/nsHashtable.h:91: warning: comma at end of enumerator list

thus far this has had pretty negligable affects on tinderbox. In fact, I'm a little surprised not to see something more dramatic one way or the other. I guess the ns*Keys really are the real issue. But I guess I can't complain, since I had a slight fear this would slow things down.

This change removed a bunch of mallocs, made lookup slighly slower, and therefore was unlikely to slow the whole app down. Reducing mallocs is good. Now we just need to get more high-freq/call-count uses switched to pldhash/nsDoubleHashtable or nsHashSet. Alec, sorry I missed the trailing , in enumerator list (damn ANSI for outlawing that!). Did you fix? /be

oops, this landed, forgot to mark fixed - all in all there was very little change in performance, but I'm certain our heap is in better shape as a result.

wow, I'm a dim bulb today. that's what I get for commenting in bugs while on vacation! actually marking fixed now.