pldhash is not widely used, desipte being a more efficient hash than plhash/ nsHashtable. I think the reasons are: 1. Lack of a C++ API forces clients to have to learn a non-transparent API 2. It can't own C++ objects, including reference-counted ones. I'm trying to write a wrapper that addresses these issues.

I'm not working on this bug, yet sfraser kindly is. So I think he should take assignment, at least for now. /be

Plus, I'm a C luddite and proud of it. /be

Also, plhash beats plhash in some cases, see http://lxr.mozilla.org/mozilla/source/js/src/jsdhash.h#94 and below. And do not mix up nsHashtable (sic) with plhash, on which it is layered. nsHashtable is much more malloc intensive for common key types than plhash is by default (if not using PLHashAllocOps). Muddling the C++ bloat of nsHashtable with plhash may put people off of using plhash, when it is the best choice. If C++ users can't handle using C from time to time, they need to Get Over It. /be

s/plhash beats plhash/plhash beats pldhash/ /be

I'm too much of a wimp to do this. It's gonna be easier to write a better API over plhash, and try to do fewer allocations than nsHashtable.

I'm actually convinced (luddite tho I may be) that it's possible to switch nsHashtable etc. over to pldhash. Some placement new allocation is required. Anyway, I'm gonna try. It seems very wrong to me to buy off on plhash's malloc happy ways, even if we fix the current extra malloc-happiness in nsHashtable. It also seems wrong to me to do a warren-style jihad thru the tree to change all ns*Hashtable uses. It's all just code, right? :-) /be

Taking from sfraser. /be

nsHashKey is evil. In spite of its bogus vtbl pointer overhead for specialization that is always per-table, not per-key. There are no heterogenous tables in sight, and no one wants them either (proof: check each key subclass's Equals method impl). The problem with moving key specialization dispatching from the key class into the table class is that it combines with the various existing table subclasses, which specialize value type (void*, nsISupports* strong ref, "object" that's cloned and deleted, but not explicitly refcounted). My C++-fu is not up to expressing this kind of key X value specialization matrix in a series of table subtypes or templates. So I'm leaving the virtual methods in nsHashKey (actually, adding a SizeOf one, needed to set PLDHashTable.entrySize). But the win is still there. Patch and bloatblame numbers coming up. /be

Somewhat related: I think pldhash needs an 'entry init' callback. The reason is that the return value from PL_DHashTableOperate(table, key, PL_DHASH_ADD); does not indicate whether space for this entry was just reserved, or whether an existing entry was returned (since PL_DHASH_ENTRY_IS_BUSY(entry) is true in both cases). If I'm trying to store objects inline in the table, I thus cannot tell if I have to call the constructor here or not. So a callback that indicate that space is being allocated for an entry for the first time would be useful. This would balance calls to PLDHashClearEntry. I guess it would be OK to overload PLDHashMoveEntry(), can call it with a NULL from* to indicate entry initialization.

sfraser: the original design zeroed new entry store, and hoped that was enough for callers to distinguish between already-there and just-added after a successful return JS_DHASH_ADD return. Lean and mean. Sufficient? If zeroes could mean either just-added or already-there, what construction is required? /be

> what construction is required? Setting up vtables for classes with virtual methods in the entries, for one. I think you have to call the ctor to get these set up. (I found this out the hard way trying to use nsString in entries). Also, what happens when a newly added entry falls into a space that was previously occupied? Is it zero'd out again? Or left as the ClearEntry callback left it?

Left as the clearEntry callback left it -- hence the "clear" trope. Entry store starts zeroed and should go back to zeroed (except for keyHash, of course). Overloading moveEntry is ugly. I'll add a patch here for an initEntry hook. /be

Sounds good. Looking at your patch.

nsDeviceContextMac needs these additional changes: - - PRUnichar* str = (((FontNameKey*)aKey)->mString).ToNewUnicode(); + FontNameKey *fontNameKey = (FontNameKey *)aKey; + PRUnichar* str = nsCRT::strndup(fontNameKey->GetString(), fontNameKey-> GetStringLength()); if (!str) { for (j = j - 1; j >= 0; j--) { @@ -1181,8 +1147,10 @@ int j = info->mCount; + FontNameKey *fontNameKey = (FontNameKey *)aKey; + short fondID = (short) aData; ScriptCode script = ::FontToScript(fondID); if(script == info->mScript) { - PRUnichar* str = (((FontNameKey*)aKey)->mString).ToNewUnicode(); + PRUnichar* str = nsCRT::strndup(fontNameKey->GetString(), fontNameKey-> GetStringLength()); if (!str) { for (j = j - 1; j >= 0; j--) {

Another feature request. It's hard to go between nsSimpleEnumerator-style enumeration (HasMoreElements/ GetNext) and pl(d)hash-style (enumerator with callback.). nsHashTableEnumerator attempts this with a klutzy converter callback, and by copying all the entries into a flat array. However, pldhash internally has a nice linear data structure that is easy to enumerate over, and even passes entry index back to the enum callback. So an additional API call, like: PLDHashEntryHdr * PL_DHashTableGetIndexedEntry(PLDHashTable *table, PRUint32 index) would allow me to easily go between indices and entries. The final icing-on-the-cake would be a call to get the number of live entries: PRUint32 PL_DHashGetNumEntries(PLDHashTable *table). Or is this too all-signing all-dancing for you C luddites? (Yes, I know I can do both of the above with enumeractor calls, and that the first one, at least, implies something about the internal structure of the hash that it can fairly efficiently go between index and entry).

I bugged brendan about this, and came up with a solution that's in bug 68213. It's rough and ready, basically wraps a C++-style enumerator around the raw table. Here's a sketch: class MyCollection { PLDHashTable mTable; struct MyEntry { PLDHashEntryHdr mHdr; ... }; class iterator { protected: PLDHashTable* mTable; MyEntry* mCurrent; friend class MyCollection; // to access ctor iterator(PLDHashTable* aTable, MyEntry* aEntry) : mTable(aTable), mCurrect(aEntry) {} void Prev(); void Next(); public: iterator(const iterator&); iterator& operator=(const iterator&) const; // etc. MyEntry& operator*() { return *mCurrent; } MyEntry* operator->() { return mCurrent; } iterator& operator++() { Next(); return *this; } operator& operator--() { Prev(); return *this; } // post[in|de]crement similar PRBool operator==(const iterator& aOther) const { return aOther.mCurrent == mCurrent; } }; iterator First(); iterator Last(); } iterator MyCollection::First() { MyEntry* limit = NS_REINTERPRET_CAST(MyEntry*, mTable.entryStore); limit += PR_BIT(mTable.sizeLog2); MyEntry* entry = limit; while (++entry < limit) { if (PL_DHASH_ENTRY_IS_LIVE(&entry->mHdr)) break; } return iterator(&mTable, entry); } void MyCollection::Last() { MyEntry* limit = NS_REINTERPRET_CAST(MyEntry*, mTable.entryStore); limit += PR_BIT(mTable.sizeLog2); return iterator(&mTable, limit); } void MyCollection::iterator::Next() { MyEntry* limit = NS_REINTERPRET_CAST(MyEntry*, mTable->entryStore); limit += PR_BIT(mTable->sizeLog2); while (++mCurrent < limit) { if (PL_DHASH_ENTRY_IS_LIVE(&mCurrent->mHdr)) break; } } The PL_DHASH_ENTRY_IS_LIVE() macro is just the ENTRY_IS_LIVE macro from pldhash.c, pulled up to the top level.

Argh! That'll teach my to try to mangle a file. iterator MyCollection::First() { MyEntry* entry = NS_REINTERPRET_CAST(MyEntry*, mTable.entryStore); MyEntry* limit = entry; limit += PR_BIT(mTable.sizeLog2); do { if (PL_DHASH_ENTRY_IS_LIVE(&entry->mHdr)) break; } while (++entry < limit); return iterator(&mTable, entry); }

sfraser: entrySize and entryCount are public (yes, I trust you with sharp tools such as C structs). Patch coming up to make the is-entry-live? macro public, as well as to add a backward-compatible initEntry JSDHashTableOps member. /be

Sorry if my last comment was obscure: entryCount is the live entry count; you can use entryStore (and possibly entrySize) to stride over the table; and with the last patch, you can skip entries for which JS_DHASH_ENTRY_IS_LIVE evaluates to false. Let a thousand iterators bloom. The jsdhash.[ch] patch, in addition to adding the optional initEntry hook, finds the added entry that caused a table growth or compression. The current, top of trunk code skipped this entry in ChangeTable, worried about clearing it if it consumed the last free entry if ChangeTable failed, and re-added it in order to return the correct entry address in case of growth or compression. The patched version uses an in-out param to ChangeTable to find the new entry address given the old one. /be

Apropos entryCount: I was horribly abusing it to delay PL_DHashTableInit from the nsHashtable ctor to first Put -- it conveyed the desired size passed in the aInitSize arg to the ctor. This broke lots of stuff. New patch coming up, it also includes Simon's Mac fixes. /be

This stuff breaks Mac: - nsAutoString times; times.AssignWithConversion("Times"); - nsAutoString timesNewRoman; timesNewRoman.AssignWithConversion("Times New Roman"); - nsAutoString timesRoman; timesRoman.AssignWithConversion("Times Roman"); - nsAutoString arial; arial.AssignWithConversion("Arial"); - nsAutoString helvetica; helvetica.AssignWithConversion("Helvetica"); - nsAutoString courier; courier.AssignWithConversion("Courier"); - nsAutoString courierNew; courierNew.AssignWithConversion("Courier New"); - nsAutoString nullStr; + NS_NAMED_LITERAL_STRING(times, "Times"); + NS_NAMED_LITERAL_STRING(timesNewRoman, "Times New Roman"); + NS_NAMED_LITERAL_STRING(timesRoman, "Times Roman"); + NS_NAMED_LITERAL_STRING(arial, "Arial"); + NS_NAMED_LITERAL_STRING(helvetica, "Helvetica"); + NS_NAMED_LITERAL_STRING(courier, "Courier"); + NS_NAMED_LITERAL_STRING(courierNew, "Courier New"); + NS_NAMED_LITERAL_STRING(nullStr, "");

Last patch, minus the stuff I pasted above, seems to work well. However, it does warning a lot about: pldhash: for the table at address 0x0x080c6f04, the given entrySize of 28 probably favors chaining over double hashing.

That last patch leaks like a sieve, for want of the right static type for the key in each entry, or (equivalently) a clearEntry routine specialized per key. I'm working on the real fix, which squishes out the bogus vtbl pointer per key subtype altogether. Hope to have a patch later today. /be

With this patch, basic smoke tests pass for me. I had to make stored keys (in PLDHashTable entries) "flyweight", with Store, Clear, Wrap and Unwrap virtual methods on the heavier, usually stack-allocated nsHashKey subclasses for stored key setting, clearing, and wrapping by a dummy fat key. The dummy key is used per table to proxy for each flyweight as it needs to have virtual methods called on its key-data. The common patterns in certain methods (Clone, e.g.) suggest using templates. But I'd like to get this patch in, with more testing and measurement of the bloatblame wins. More tomorrow. Comments welcome. /be

r=valeski on the nsStreamConverter* changes if you are able to successfully view a html ftp dir listing (causes this code to be driven). Thanks for cleaning things up in there. Steps: 1. set "network.dir.generate_html" to true. 2. visit an ftp site ("ftp://ftp.mozilla.org") If you can sucessfully view that dir listing in html (not XUL), you've driven this code and it still works :-).

valeski: thanks, that all works great (confirming what I said on irc here, for posterity). Anyone else care to test the patch? Who else should r= which files? Scott, can you sr=? I'm working on the bloatblame numbers still. /be

Sorry for the delay on this. I'm looking at it now (or right after this dentist appointment, anyway); comments by this afternoon.

First, comments on |nsCRT::HashCode|. There's a fine line to walk here. In general, thre are a great many transformations one might want to perform on a string to be used as a key. Case folding is chief among them; but consider also stripping white space, control sequences, canonicalizing URLs etc. Case folding isn't much work, but you have made every caller pay for it on every call. This may be acceptable, though consider that other callers will have gone to some trouble to perform all key transformations in advance. The three choices you might pick among are: force all transformations in advance (the old code); optionally perform the most common transformation inline (your code); provide additional implementations of |HashCode| that do case-folding so only callers who want it pay. Does it matter? Morally, yes, at least to my eye. In performance? Probably not, only measuring would say. Additionally, you'd proabably move the |ToUpper| into the |W <= 0x007F| clause. if ( W <= 0x007F ) { W = nsCRT::ToUpper(W); code_length = 1; } else if ... else ... U = W; Still looking at the rest of the patch.

scc: the old code ripped off the broken nsCRT::HashCode algorithm and inlined a call to nsCRT::ToUpper. That seems wrong, even given the old alg's small code size compared to the UTF-8 one you wrote that fixed all the bad old woes. So the choices are: inline the new alg with ToUpper specialization, add a flag, add a new method that differs only from nsCRT::HashCode in the ToUpper call. I chose to add a flag, and would wager (yes, bet) that the cycle difference is in the noise. But I agree it's something to measure, perhaps just by watching jrgm's numbers. What do you say? I don't think it's a moral issue (right and wrong are unclear -- code space is precious too -- what is the acceptable cost of a human life, er, of a cycle saved in terms of instruction space bytes added?). I put the conditional ToUpper call in the single-PRUnichar path because nsCRT::ToUpper takes a PRUnichar, so must be valid on all values in that type's domain. Further, the old FontAliasKey::HashCode used that overloading of ToUpper, and as erik@netscape.com reminded me, it expected the case-folding to apply to non-ASCII code points too. Were you thinking that I was calling the char-param version of nsCRT::ToUpper? /be /be

scc wants to comment on the C++-allocator fu, but here's the first round of my comments. It appears that wrap and unwrap intentionally don't hold refs on their contents -- is that the case? What happens if you call Unwrap on a non-dummy key? If nothing else, a little bit of documentation for key-class authors would be nice, because this is likely to confuse. nsHashtable.cpp If you're asserting ownership over that file (by moving to 4-space indentation), could you also standardize on |nsHashkey *foo| rather than mixing in |nsHashkey* foo|? -PRUint32 nsCRT::HashCode(const char* str, PRUint32* resultingStrLen) +PRUint32 nsCRT::HashCode(const char* str, PRUint32* resultingStrLen, PRBool aIgnoreCase) The 80th column lies bleeding! - while ( (c = *s++) ) + while ( (c = *s++) ) { + if (aIgnoreCase) + c = nsCRT::ToUpper(char(c)); h = (h>>28) ^ (h<<4) ^ c; + } Is it worth duplicating the while loop for aIgnoreCase to avoid the branch in the loop, or (more likely) does it get lost in the function call cost? +(* PR_CALLBACK PLDHashClearEntry)(PLDHashTable *table, + PLDHashEntryHdr *entry); Bogus indentation in {pl,js}dhash.h. + // XXXbe shouldn't we do this in an Init method that can propagate + // NS_ERROR_OUT_OF_MEMORY? + PR_ASSERT(mLock != nsnull); Uh, "yes". Wanna file a separate bug that requires Init() to be called for all nsHashtables? + // shouldn't be adding an item during enumeration + PR_ASSERT(!mEnumerating); Is this documented anywhere? At least the attribute-affects-style code adds to hash table B while enumerating hash table A, and takes no special care to avoid A == B. (Though I don't think it happens In Real Life, because it's part of stylesheet cloning.) + // if this vertex has already been discovered, we don't want + // to leak it. (non-discovered vertex's get cleaned up when + // they're popped). Lotsa cleanup and better error handling in the stream converter, I notice; nice. I know you're just reformatting, but do you really want the blame for "vertex's"? + if (!entry) { + if (aStatus) + *aStatus = NS_ERROR_OUT_OF_MEMORY; ... + } else if (!aKey->Store((void *) &entry->mKeySpace)) { + // Store must have left mKeySpace in a valid state for Clear. + if (aStatus) + *aStatus = NS_ERROR_OUT_OF_MEMORY; What about: nsresult dummy, *status = aStatus ? aStatus : &dummy; if (!entry) *status = NS_ERROR_OUT_OF_MEMORY; + // XXXbe locking? Should we expose nsHashtable.Lock() so that people can freeze the table during cloning and enumeration operations? -PRIntn PR_CALLBACK -nsSupportsHashtable::EnumerateCopy(PLHashEntry *he, PRIntn i, void *arg) +static PLDHashOperator PR_CALLBACK +_supportsEnumerateCopy(PLDHashTable *table, PLDHashEntryHdr *hdr, + PRUint32 number, void *arg) Isn't _leadingUnderscore verboten? Why not just SupportsEnumerateCopy?

More work needed, ran out of time. I'll have a new patch for next week. /be

This patch is proving painful to keep fresh. I'll come up with a better patch for 0.9.1, or mothball it. /be

Patch is rusting, no time to strip the rust for 0.9.1. /be

Adding the perf keyword, and cc:ing some other people who might be interested as well. The Style System makes _heavy_ use of nsHashtable. Any help here could pay some dividents elsewhere...

I don't like the working patch, because it overcomplicates nsHashKey and its subtypes in order to work around lack of template support. Maybe a portable templates guru can advise me? Anyway, not likely to happen in one milestone. /be

I *might* get to this in 0.9.6. /be

Moving to 0.9.7, will fix then. /be

I have a patch which uses nsFixedSizeAllocator to allocate the PLHashEntrys.. would that be useful here, either as a short-term solution, or as a step towards continuing PLHashTable use? One thought I had on making the nsHashKey subclasses less malloc-happy was to: - have some virtual sizeOf() method, which returned the space needed to clone the key - make Clone() always happen in-place That way the hashtable could allocate the space from a pool, and any other consumers of Clone() could allocate the space themselves with operator new

Here's a small patch which we could check in now, and at least fix some small malloc crazyness. I also added MOZ_COUNT_CTOR/MOZ_COUNT_DTOR to nsFixedSizeAllocator (even if we don't take that patch, can I get an sr= on the MOZ_COUNT_CTOR stuff?)

oh, and ignore that HASH_USE_ARENAS - that was when I was deciding between raw PLArena's and nsFixedSizeAllocator. I've removed the #if's from my tree. Also, it turns out that to get MOZ_COUNT_CTOR(), I have to #include "nsTraceRefCnt.h" to get the xul template builder to build, which is kinda ugly..but what can ya do.

alecf: do you have any measurements using mozilla/tools/trace-malloc or similar? I'm happy to go with your patch if it makes things better without adding too much code. The mPool member adds 8 words to each nsHashtable, OTOH. /be

Comment on attachment 57771 [details] [diff] [review] use nsFixedSizeAllocator for PLHashEntries Now that I understand the virtues of PLDHashTable, I think there's no reason to do this half-assed. Obsoleting my patch :)

so what are the chances of reviving this patch? I like the general concept, even if it does complicate things a bit.

I'll take a fresh look next week. /be

Urgh. Not sure this will happen before 1.0. Feel free to help if you can. /be

I have filed bug 125849 with a PLDHash wrapper; I think the intent there is slightly different from the intent here. I want a few lean, mean classes to wrap PLDHashTable without (much) overhead for the common cases like mapping from string -> nsISupports*, string -> string, string -> void*.

jkeiser shows the way in bug 125849. I'm going to WONTFIX this bug. If we believe that, once bug 125849 is closed, we need a jihad through the tree to convert nsHashtable users to nsDoubleHashtable (or whatever it'll be called), a new bug should be filed. Cc'ing cathleen and dp in case nsHashtable and its malloc-happy key types are showing up on footprint radar, and just so cathleen can track this issue. (Fine point: I'm WONTFIXing the entire summary, including the "which should be nsHashtable" -- obviously, we'll have a C++ wrapper for pldhash shortly in xpcom, thanks to jkeiser. I could INVALIDate, but WONTFIX seems better: it says we choose not to change nsHashtable's API at this late date.) /be

see bug 177318 which I just filed, to take a slightly less ambitious approach on this... I think PLDHashTable can still help us.