177545 - XBL binding manager should use nsDoubleHashtable

Status: RESOLVED FIXED

(Core :: XBL, defect, P1)

Description

[Alec Flett]

Turns out nsBindingManager is one of the worst consumers of nsHashtable - there
are 7 hashtables in this file, mostly mapping nsIContent -> other nsISupports*
objects. It accounts for hundreds of key allocations, and pldhash or jkieser's
nsDoubleHashtable would serve us much better. (this is fallout from bug 177318)

Interestingly, the hashtable member variables are actually pointers to
hashtables, rather than existing inline in the class. It makes me wonder how
often each of these tables exist, and if we should be allocating each of them
seperately, or if they should all just be direct members of nsBindingManager.
I'm going to try to do some analysis before I procede.

Comment 1

[Alec Flett]

ok, I poked at this some more. It looks like XUL documents typically instantiate
every hashtable except mDocumentTable, and HTML document typically instantiate
only mBindingTable, mInsertionParentTable, and mWrapperTable.

In the interest of keeping this lightweight for HTML, I'm going to put
mBindingTable, mInsertionTable, and mWrapperTable inline in the class, and make
the rest be pointers to these tables.

Comment 2

[Brendan Eich [:brendan]]

Most HTML pages don't get XBL bindings applied to them, though -- I hope.  If
so, why worry about HTML?  Shouldn't we optimize for XUL and future XML
languages that we implement and extend with XBL?

/be

Comment 3

[Alec Flett]

brendan: I'm optimizing for HTML because every document has a binding manager -
so I'm trying to keep the binding manager small in the case of HTML. If I
optimize for XUL, then every HTML page will have extra hashtables for XBL bindings.

Comment 4

[Brendan Eich [:brendan]]

Obviously, I was suggesting that not every document needs a binding manager. 
Why can't it be created lazily, so that htmldocs not subject to xbl bindings
have only a pointer's worth of unused overhead?

/be

Comment 5

[Alec Flett]

Attachment: switch to pldhash and nsDoubleHashtable

Here's my first cut at this.. the results are pretty dramatic.

In a short run where I open the browser, (which loads http://www.mozilla.org/)
open the prefs window, hit cancel, then close the product, I see these drops
(in number of objects created, from the XPCOM_BLOAT_LOG stuff)

nsHashKey: 78163->40759
nsHashtable: 927->853
nsHashtableEnumerator: 43->14

I used pldhash directly where I felt it was valuble (object->object tables),
and I used nsDoubleHashtable for other stuff. I might be willing to switch to
nsDoubleHashtable for everything, I'm not sure yet.

So I'd like to get some reviews here. I'd like to land this conversion
seperately from the XUL vs. HTML optimization as well, so lets not dwell on
that for this patch.

Comment 6

[Alec Flett]

Comment on attachment 107058 [details] [diff] [review]
switch to pldhash and nsDoubleHashtable

Requesting a review from brendan and hyatt...

I did some analysis of "Wasted" bytes - basically I ran through the 30 urls on
cowtools, to see how many wasted bytes we had by inlining every table into the
nsBindingManager.. 

I figured that in the simplest case we were to lazily create each 32-byte table
and just store a pointer to each, we would need a 4-byte pointer to point to
the table. In this case an unused table would amount to 28 bytes of wasted
space per table.

in my testing of these 30 urls run in mozilla, I found that we created 248
nsBindingManagers, and wasted 245 tables, (which means on average, we waste
only one hashtable per nsBindingManager.. interesting!) This amounted to a
total waste of 6860 bytes. This really isn't a lot of space considering it is
spread out over 30 web pages.

so I'm not as worried about optimizing for HTML vs. XUL right now. I feel like
the additional complexity might outweigh the savings.

Comment 7

[Alec Flett]

wow, these results are rather staggering. Comparing the bloat logs for the
cowtools runs, I see even better results:
nsHashKey: 706,811 -> 301,708
nsHashtable: 2166 -> 1949
nsHashtableEnumerator: 45->16

all in all this is great stuff. Obviously, the nsHashtable stuff is just
transferred over to PLDHashTable, so the real win here is nsHashKey.

Comment 8

[Alec Flett]

cc'ing some other possible reviewers - bryner and dbaron.. 

Comment 9

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

Comment on attachment 107058 [details] [diff] [review]
switch to pldhash and nsDoubleHashtable

>+{
>+  NS_ASSERTION(aKey, "key must be non-null");
>+  if (!aKey) return;
>+  
>+  ObjectEntry *entry =
>+    NS_STATIC_CAST(ObjectEntry*,
>+                   PL_DHashTableOperate(&table, aKey, PL_DHASH_ADD));
>+
>+  // have an old entry, make sure to release the old value
>+  if (entry->key)
>+    NS_RELEASE(entry->value);
>+  // this is a new entry, so need to make sure the key is addreffed
>+  else
>+    NS_ADDREF(entry->key = aKey);

It might be nice to use nsCOMPtrs, although using nsCOMPtrs with pldhash can be
a little messy because you have to be careful to run constructors and
destructors at the right times, so this is OK.	However, you might want to
comment that the keys are required to be non-null.

>+// helper routine for looking up an existing entry. Note that the
>+// return result is NOT addreffed
>+static nsISupports*
>+LookupObject(PLDHashTable& table, nsISupports* aKey)
>+{
>+  ObjectEntry *entry =
>+    NS_STATIC_CAST(ObjectEntry*,
>+                   PL_DHashTableOperate(&table, aKey, PL_DHASH_LOOKUP));
>+
>+  if (entry->key)

This should be using PL_DHASH_ENTRY_IS_BUSY.

>+static void LazySetObject(PLDHashTable& table, nsISupports* aKey, nsISupports* aValue)

I don't like the name of this function, since it's really
if-null-set-otherwise-remove.  Maybe |SetOrRemoveObject|?

Also, perhaps the creation of the hashtable should be moved
inside the non-null-aValue case, to match what SetContentListFor
did before your patch?

>-PRBool PR_CALLBACK ExecuteDetachedHandler(nsHashKey* aKey, void* aData, void* aClosure)
>+PR_STATIC_CALLBACK(PLDHashOperator)
>+ExecuteDetachedHandler(PLDHashTable* aTable, PLDHashEntryHdr* aHdr, PRUint32 aNumber, void* aClosure)
> {
>-  nsIXBLBinding* binding = (nsIXBLBinding*)aData;
>+  ObjectEntry* entry = NS_STATIC_CAST(ObjectEntry*, aHdr);
>+  nsIXBLBinding* binding = NS_STATIC_CAST(nsIXBLBinding*,entry->value);

Missing space after comma.

>@@ -1032,33 +1105,38 @@ NS_IMETHODIMP
> nsBindingManager::GetLoadingDocListener(const nsCString& aURL, nsIStreamListener** aResult)
> {
>   *aResult = nsnull;
>-  if (!mLoadingDocTable)
>+  if (!mLoadingDocTable.mHashTable.ops)
>     return NS_OK;
> 
>-  nsCStringKey key(aURL);
>-  *aResult = NS_STATIC_CAST(nsIStreamListener*, mLoadingDocTable->Get(&key)); // Addref happens here.
>+  StringToObjectEntry* entry = mLoadingDocTable.GetEntry(aURL);
>+  if (entry) {
>+    *aResult = NS_STATIC_CAST(nsIStreamListener*,entry->GetValue());

again, missing space after comma.

Not sure yet if I've looked at this in enough detail.

Comment 10

[Alec Flett]

Attachment: switch to pldhash v1.01

thanks for the quick review, david.. I've addressed the stuff your brought up
(thanks for catching the PL_DHASH_IS_BUSY thing - doh!)

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 107080 [details] [diff] [review]
switch to pldhash v1.01

>+// not using nsCOMPtrs because in this use of pldhash, proper
>+// management of constructors/destructors would be more work than
>+// manual addref/release management

Is that true?  If you use nsCOMPtr, you have to write the same number of lines
of ClearObjectEntry source, and you can write an InitObjectEntry hook (the only
hook that's optional in PLDHashTableOps so far).  But you don't need to flail
around with ADDREF and RELEASE in the code that adds to the table.  That seems
like a win to me.

>+// helper routine for adding a new entry
>+static void
>+AddObjectEntry(PLDHashTable& table, nsISupports* aKey, nsISupports* aValue)
>+{
>+  NS_ASSERTION(aKey, "key must be non-null");
>+  if (!aKey) return;
>+  
>+  ObjectEntry *entry =
>+    NS_STATIC_CAST(ObjectEntry*,
>+                   PL_DHashTableOperate(&table, aKey, PL_DHASH_ADD));
>+
>+  // have an old entry, make sure to release the old value
>+  if (PL_DHASH_ENTRY_IS_BUSY(entry))

This isn't the right test, you konw the entry is busy after you ADD (either it
was found, or it was just added for you, but in both cases, it's busy).  First,
you need to check for OOM by null-testing entry.  Then, test whether entry->key
is non-null in this if's condition.

>@@ -480,9 +589,10 @@ nsBindingManager::SetBinding(nsIContent*
> NS_IMETHODIMP
> nsBindingManager::GetInsertionParent(nsIContent* aContent, nsIContent** aResult) 
> { 
>-  if (mInsertionParentTable) {
>-    nsISupportsKey key(aContent);
>-    *aResult = NS_STATIC_CAST(nsIContent*, mInsertionParentTable->Get(&key));
>+  if (mInsertionParentTable.ops) {
>+    *aResult = NS_STATIC_CAST(nsIContent*,
>+                              LookupObject(mInsertionParentTable,aContent));

Nit: space after comma (check elsewhere, I haven't).

>@@ -494,25 +604,16 @@ nsBindingManager::GetInsertionParent(nsI
> NS_IMETHODIMP
> nsBindingManager::SetInsertionParent(nsIContent* aContent, nsIContent* aParent)
> {
>-  if (!mInsertionParentTable)
>-    mInsertionParentTable = new nsSupportsHashtable;
>-
>-  nsISupportsKey key(aContent);
>-  if (aParent) {
>-    mInsertionParentTable->Put(&key, aParent);
>-  }
>-  else
>-    mInsertionParentTable->Remove(&key);
>-
>+  LazySetObject(mInsertionParentTable, aContent, aParent);

Er, SetOrRemoveObject, not LazySetObject, right?  Compile before attaching
(test too, so my brain doesn't have to simulate a cpu as well as a compiler
;-).

This method becomes fallible once you check for OOM after PL_DHASH_ADD, so
propagate NS_ERROR_OUT_OF_MEMORY or NS_OK here and elsewhere.

/be

Comment 12

[Alec Flett]

Attachment: switch to pldhash v1.02

oops, heh. here's a working version... it actually compiles and works, imagine
that :)

Anyhow, I decided to go with the clear/initEntry stubs, so that we could use
nsCOMPtrs - the difference was minimal in terms of total code size/complexity,
but brendan was right in that the consumers get much cleaner.

reviews?

Comment 13

[Alec Flett]

Attachment: switch to pldhash v1.02

argh, lets try that again - I forgot to actually regenerate the patch before
attaching it.

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 107814 [details] [diff] [review]
switch to pldhash v1.02

>+//
>+// Generic pldhash table stuff for mapping one nsISupports to another
>+//
>+

Gratuitous/unintended extra newline here?

>+// not using nsCOMPtrs because in this use of pldhash, proper
>+// management of constructors/destructors would be more work than
>+// manual addref/release management

But you are using nsCOMPtrs now!

>+//
>+// Also, these values are never null - a null value implies that this
>+// whole key should be removed (See SetOrRemoveObject)
>+class ObjectEntry : public PLDHashEntryHdr
>+{
>+public:
>+  nsCOMPtr<nsISupports> key;
>+  nsCOMPtr<nsISupports> value;
>+};
>+  nsresult rv;
>+  rv = SetOrRemoveObject(mBindingTable, aContent, aBinding);

Nit: why not initialize rv at its declaration?

>@@ -964,11 +1057,11 @@ nsBindingManager::GetXBLDocumentInfo(con
> NS_IMETHODIMP
> nsBindingManager::PutLoadingDocListener(const nsCString& aURL, nsIStreamListener* aListener)
> {
>-  if (!mLoadingDocTable)
>-    mLoadingDocTable = new nsSupportsHashtable();
>+  if (!mLoadingDocTable.mHashTable.ops)
>+    mLoadingDocTable.Init(16);
> 
>-  nsCStringKey key(aURL);
>-  mLoadingDocTable->Put(&key, aListener);
>+  StringToObjectEntry* entry = mLoadingDocTable.AddEntry(aURL);
>+  entry->SetValue(aListener);

Null-test entry after AddEntry return, fail with OOM if null.

>+PR_STATIC_CALLBACK(PLDHashOperator)
>+MarkForDeath(PLDHashTable* aTable, PLDHashEntryHdr* aHdr, PRUint32 aNumber, void* aClosure)
> {
>+  ObjectEntry* entry = NS_STATIC_CAST(ObjectEntry*, aHdr);
>+  nsIXBLBinding* binding = NS_STATIC_CAST(nsIXBLBinding*, (void*)entry->value.get());

Ick.  How about a GetValue inline method that returns an nsISupports*?

/be

Comment 15

[Brendan Eich [:brendan]]

>+public:
>+  nsCOMPtr<nsISupports> key;
>+  nsCOMPtr<nsISupports> value;
>+};

Forgot to comment here: besides inline GetValue that avoids an ugly
nsCOMPtr::get call and a (void*) old-style cast, you might make these private
and use mKey and mValue names.  Just a thought.

/be

Comment 16

[Alec Flett]

Attachment: switch to pldhash v1.03

nits addressed..

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 107823 [details] [diff] [review]
switch to pldhash v1.03

One last nit: no need for inline before methods defined (body and all, not just
declared) in a class body -- no one does that elsewhere, it's redundant, etc.

hyatt should r=, I'll sr now: sr=[e-mail].

Say, what's the code size change, and what are the latest footprint savings you
measure?

/be

Comment 18

[Alec Flett]

Comment on attachment 107823 [details] [diff] [review]
switch to pldhash v1.03

Requesting a review from hyatt now.

I'll try to get footprint numbers, my guess is that static footprint will go up
slightly.. but you can see in the numbers above that our hashkey usage improves
dramatically!

Comment 19

[Alec Flett]

on my release build, the binary gkcontent.dll did not change in size (currently
at 1420k) - now obviously there is some growth here, but this shows its likely
less than 1k

Comment 20

[Alec Flett]

yeah, this continues to amaze me - I've done these tests over and over, but
still seeing these great results.

so in addition to dropping some 38,000 nsHashKeys (about 291k), the new
hashtables create only 873 ObjectEntrys, and 51 StringToObjectEntrys - a total
of 11k, and that 11k is in the form of pldhashtable objects so the *ObjectEntry
structs are more or less heap-allocated, so the load on the heap should be much
smaller too!

Comment 21

[Alec Flett]

fix is in. thanks everyone for reviews/etc...

Comment 22

[Alec Flett]

looks like this got us an across-the-board Ts/Txul/Tp improvement. It also
reduced our Bl number by some .3.. I'm convince that the "A" number is just
totally random and rarely actually changes :)