72722 - pldhash needs a C++ wrapper, which should be nsHashtable

Status: RESOLVED WONTFIX

(Core :: XPCOM, defect, P3)

Description

[Simon Fraser [no longer active]]

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.

Comment 1

[Brendan Eich [:brendan]]

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

/be

Comment 2

[Brendan Eich [:brendan]]

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

/be

Comment 3

[Brendan Eich [:brendan]]

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

Comment 4

[Brendan Eich [:brendan]]

s/plhash beats plhash/plhash beats pldhash/

/be

Comment 5

[Simon Fraser [no longer active]]

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.

Comment 6

[Brendan Eich [:brendan]]

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

Comment 7

[Brendan Eich [:brendan]]

Taking from sfraser.

/be

Comment 8

[Brendan Eich [:brendan]]

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

Comment 9

[Simon Fraser [no longer active]]

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.

Comment 10

[Brendan Eich [:brendan]]

Attachment: very lightly tested patch!

Comment 11

[Brendan Eich [:brendan]]

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

Comment 12

[Simon Fraser [no longer active]]

> 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?

Comment 13

[Brendan Eich [:brendan]]

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

Comment 14

[Simon Fraser [no longer active]]

Sounds good. Looking at your patch.

Comment 15

[Simon Fraser [no longer active]]

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--) {

Comment 16

[Simon Fraser [no longer active]]

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).

Comment 17

[Chris Waterson]

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.

Comment 18

[Chris Waterson]

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);
}

Comment 19

[Brendan Eich [:brendan]]

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

Comment 20

[Brendan Eich [:brendan]]

Attachment: jsdhash.[ch] patch (sed -f plify_jsdhash.sed in js/src to get xpcom/ds/pldhash.[ch])

Comment 21

[Brendan Eich [:brendan]]

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

Comment 22

[Brendan Eich [:brendan]]

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

Comment 23

[Brendan Eich [:brendan]]

Attachment: better fix (working? my debug build is screwed up otherwise, clobbering; optimized rebuilding now)

Comment 24

[Simon Fraser [no longer active]]

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,            "");

Comment 25

[Simon Fraser [no longer active]]

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.

Comment 26

[Brendan Eich [:brendan]]

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

Comment 27

[Brendan Eich [:brendan]]

Attachment: working patch, please help test and review

Comment 28

[Brendan Eich [:brendan]]

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

Comment 29

[Judson Valeski]

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 :-).

Comment 30

[Brendan Eich [:brendan]]

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

Comment 31

[Scott Collins]

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

Comment 32

[Scott Collins]

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.

Comment 33

[Brendan Eich [:brendan]]

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 [e-mail] 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

Comment 34

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

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?

Comment 35

[Brendan Eich [:brendan]]

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

/be

Comment 36

[Brendan Eich [:brendan]]

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

/be

Comment 37

[Brendan Eich [:brendan]]

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

/be

Comment 38

[rbs]

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...

Comment 39

[Brendan Eich [:brendan]]

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

Comment 40

[Brendan Eich [:brendan]]

I *might* get to this in 0.9.6.

/be

Comment 41

[Brendan Eich [:brendan]]

Moving to 0.9.7, will fix then.

/be

Comment 42

[Alec Flett]

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

Comment 43

[Alec Flett]

Attachment: use nsFixedSizeAllocator for PLHashEntries

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?)

Comment 44

[Alec Flett]

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.

Comment 45

[Brendan Eich [:brendan]]

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 46

[Alec Flett]

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 :)

Comment 47

[Alec Flett]

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

Comment 48

[Brendan Eich [:brendan]]

I'll take a fresh look next week.

/be

Comment 49

[Brendan Eich [:brendan]]

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

/be

Comment 50

[John Keiser (jkeiser)]

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*.

Comment 51

[Brendan Eich [:brendan]]

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

Comment 52

[Alec Flett]

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