377606 - Switch cycle collector to more efficient hashtables

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Graydon Hoare :graydon]

Attachment: patch to move cycle collector hashtables to PLDHashTable

This patch replaces some uses of nsTHashtable and friends with PLDHashTable, and  reduces the number of calls into the hashtable. Should shave some time off the collection pauses.

Comment 1

[Brendan Eich [:brendan]]

Comment on attachment 261636 [details] [diff] [review]
patch to move cycle collector hashtables to PLDHashTable


>+    PRBool Get(void *obj, PRUint32 &refcount)
>+    {
>+        ObjRefCount *entry = (ObjRefCount *) PL_DHashTableOperate(mRefCounts, obj, PL_DHASH_LOOKUP);
>+        NS_ASSERTION(entry, "PL_DHASH_LOOKUP returned null");
>+        if (PL_DHASH_ENTRY_IS_LIVE(&(entry->hdr)))

As noted in pl/jsdhash.h, IS_BUSY is the better test -- you can't lookup a removed entry, so it's safe.

>+            return entry->mCount;
>         else
>-            refs = 1;
>-        mRefCounts.Put(obj, refs);
>-    }
>-
>-    PRBool Get(void *obj, PRUint32 &refcount)
>-    {
>-        return mRefCounts.Get(obj, &refcount);
>+            return 0;

Nit: else after return non-sequitur.

>+    PtrInfo *Lookup(void *key)
>+    {
>+        PtrInfo *p = (PtrInfo*) PL_DHashTableOperate(mTab, key, PL_DHASH_LOOKUP);
>+        NS_ASSERTION(p, "GCTable::Lookup() returning null");

LOOKUP can't return null, it's easy to verify this. I raise this only because here, the NS_ASSERTION seems to be future-proofing a bad regression in pldhash (where LOOKUP could return null); but below:

>+        return p;
>+    }
>+
>+    PtrInfo *Add(void *key)
>+    {
>+        PtrInfo *p = (PtrInfo *) PL_DHashTableOperate(mTab, key, PL_DHASH_ADD);
>+        NS_ASSERTION(p, "GCTable::Add() returning null");

NS_ASSERTION is used to assert-botch on OOM. We actually try to unwind OOM and carry on (we do poorly, but we do try). So perhaps one or both of these assertions should go.

My 2 cent drive-by.

/be

Comment 2

[Benjamin Smedberg]

Did this really show up in profiles? Once you get through inlining nsTHashtable it should be roughly eqivalent to direct pldhash usage, unless there's keyclass optimization that can't be performed with the nsTHash hierarchy.

Comment 3

[Graydon Hoare :graydon]

What showed up in profiles was hitting the hashtables, period. That much makes sense because the hashtables contain records for every pointer in the heap. We can't remove that fact, but we can shave time off it. 

There were two obvious problems in the old code: the entries were too big (not related to which hashtable implementation we used) and we made a lot of calls to the hashtable API, some of which can be eliminated if you are using a hashtable that returns cursors to mutable enties rather than mapped values. This patch changes both (as well as ifdef'ing some of the more outrageous debugging code).

I can do before-and-after profiles of each piece if you'd like.

Comment 4

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

Comment on attachment 261636 [details] [diff] [review]
patch to move cycle collector hashtables to PLDHashTable

>+    PLDHashTable *mRefCounts;

If you want, you could use an object instead of a pointer.  (If you then need to null-check a pointer you could ensure the .ops pointer of the table is null if it's uninitialized.)

>     void Ref(void *obj, uint8 flags)

Seems like you could remove the |flags| argument.

>+        ObjRefCount *entry = (ObjRefCount *) PL_DHashTableOperate(mRefCounts, obj, PL_DHASH_ADD);
>+        NS_ASSERTION(entry, "PL_DHASH_ADD returned null");

Maybe also assert that "!entry->key || entry->key == obj" and that "!entry->key == !entry->mCount" ?

>+    PRBool Get(void *obj, PRUint32 &refcount)

You're changing the contents of the method to return the refcount rather than set refcount.  I think that's a good change, but you should also change the signature and the caller. :-)

>+        if (PL_DHASH_ENTRY_IS_LIVE(&(entry->hdr)))
>+            return entry->mCount;
>         else

Brendan would cringe (else-after-return), although I don't mind.

>+            return 0;

nsCycleCollector.cpp in a bit...

Comment 5

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

Comment on attachment 261636 [details] [diff] [review]
patch to move cycle collector hashtables to PLDHashTable

>diff -r 0ea107d8088a xpcom/base/nsCycleCollector.cpp
>+    NodeColor mColor : 2;
>+    // FIXME: mLang expands back to a full word when bug 368774 lands.
>+    PRUint32 mLang : 2;

Rumor has it (ask sicking) that MSVC doesn't pack objects with field widths when they have different types.

>+PRBool 

Declare this as PR_STATIC_CALLBACK(PRBool).  static for the file-scope linkage, and PR_CALLBACK so you, well, why not, it's still there?  (Used to be "so you don't break OS/2".)

>+struct GCTable 
>+{
>+    PLDHashTableOps mOps;

We typically list out the ops in a static const PLDHashTableOps at file scope, but this works fine too.

>+    PLDHashTable *mTab;

Same comment that you could just put the struct here, if you want.

>-public:
>-    
>+public:    

This added a bunch of trailing spaces.

>@@ -896,40 +953,41 @@ struct scanWalker : public GraphWalker

>-            ScanBlackWalker(mGraph, mRuntimes).Walk(p);
>-            pi.mColor = black;
>+            ScanBlackWalker(mGraph, mRuntimes).Walk(NS_CONST_CAST(void*, pi->key));
>+            pi->mColor = black;
>             sCollector->mStats.mSetColorBlack++;

Seems like it would be best to remove the last two lines (assignment to black and mSetColorBlack++) and replace them with an assertion that pi->mColor == black (after ScanBlackWalker().Walk()).  (Mainly for the more accurate stats, but also because the assertion would catch if that weren't actually the case.)

>+    PRBool ShouldVisitNode(PtrInfo const *pi)  
>     { 
>+        return ! mVisited.GetEntry((void *) pi->key);

Maybe use NS_CONST_CAST if that's what you're doing?

sr=dbaron with those comments (and those from the previous comment) addressed

Comment 6

[Peter Van der Beken [:peterv]]

I don't have much else, only that you should probably check the result of PL_DHashTableInit. I'll wait for a new patch before marking r+.

Comment 7

[Jeff Walden [:Waldo]]

(In reply to comment #5)
> Rumor has it (ask sicking) that MSVC doesn't pack objects with field widths
> when they have different types.

See bug 374988 comment 3.

Comment 8

[Peter Van der Beken [:peterv]]

Attachment: v1.1

Takes care of the comments and fixes compilation in DEBUG builds.

Comment 9

[Peter Van der Beken [:peterv]]

Attachment: v1.2

Some whitespace changes and one additional nullcheck in JSObjectRefcounts::Ref. This is basically still graydon's patch, with review comments addressed, so marking this r=peterv.

Comment 10

[Peter Van der Beken [:peterv]]

Attachment: Reduce struct size

I checked in attachment 262220 [details] [diff] [review]. Also checked in this follow up patch to reduce the struct size, gcc on OS X didn't pack it tightly before this change. Tinderbox show a large increase in MH though, not really sure what that is about. Maybe it has something to do with the much larger default size for the hashtables? Or that clearing the hashes now does PL_DHashTableFinish/PL_DHashTableInit instead of just enumerating and removing all the entries like nsTHashtable?

Comment 11

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

(In reply to comment #10)
> Maybe it has something to do with the much larger default size for the
> hashtables?

I applied just the nsXPConnect.cpp part of the patch, and that caused a 3MB MH increase that went away when I reduced OBJ_REFCOUNT_ENTRIES from 100000 to 1000.

Probably the thing to do here is to get some "typical" size numbers for both of these tables and set the initial capacity closer to the low edge of the typical numbers.

Comment 12

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

So I'd note that 100000 is a rather bad number to use, since the default max load of a pldhash is 0.75.  100000 yields a capacity of 133334 which must be rounded up to the nearest power of 2, 262144.

From some quick printfs and opening a bunch of tabs in a single window, I'd suggest maybe dropping the use of the macro that multiplies by 1.333 and passing in 65536 for JSObjectRefcounts and 32768 for GCTable.

I'd also note that we're clearing both tables (which means reallocating the table storage) twice per collection -- once at the beginning and once at the end -- and we're keeping all that table storage around between collections.

I'd also note than on 64-bit platforms, PtrInfo is allocating a field with of 62 for a PRUint32, which is a bit excessive (and triggers a compiler warning)  If you're using PRUint32, you probably just want an explicit field width of 30.

Comment 13

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

Attachment: proposed followup patch

I'll request reviews once I've actually tested this; my tree is currently rebuilding.

Comment 14

[Peter Van der Beken [:peterv]]

(In reply to comment #12)
> I'd also note that we're clearing both tables (which means reallocating the
> table storage) twice per collection -- once at the beginning and once at the
> end -- and we're keeping all that table storage around between collections.

We should probably still do this too (see also the third paragraph in bug 377787, comment 4).

Comment 15

[Peter Van der Beken [:peterv]]

Attachment: Don't keep hashes around

This doesn't keep the hashtables around between cycle collections. I looked into not alloc'ing/freeing the hashtables' storage, just enumerating and removing entries wouldn't be the right approach I think, because that would shrink the storage space.

Comment 16

[Graydon Hoare :graydon]

Comment on attachment 262380 [details] [diff] [review]
proposed followup patch

Arguably this is optimistic: 30 bits may not be sufficient on a really big heap in the future, but that's probably just paranoia on my part. I doubt this code will live long enough to find out either way. Otherwise looks fine.

Comment 17

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

Attachment: Don't keep hashes around

I landed attachment 262380 [details] [diff] [review] on the trunk.

This is attachment 262492 [details] [diff] [review] diffed against trunk after that landing (since attachment 262492 [details] [diff] [review] included most of attachment 262380 [details] [diff] [review]).  I think it's a good idea, except I don't see why Init / InitRefCounts should need to account for the possibility of table.ops being non-null; it should just assert that it's null -- and the callers should be symmetric (nsCycleCollector::Collect should be easy; not sure if there are asymmetries in nsXPConnect).

Comment 18

[Peter Van der Beken [:peterv]]

Attachment: Don't keep hashes around

Comment 19

[Graydon Hoare :graydon]

Comment on attachment 262630 [details] [diff] [review]
Don't keep hashes around

I don't feel strongly about this stuff; whatever works.

Comment 20

[Peter Van der Beken [:peterv]]

Comment on attachment 262630 [details] [diff] [review]
Don't keep hashes around

dbaron: the patch for bug 378514 will make the nsCycleCollector.cpp changes obsolete, but I think we still want the changes for nsXPConnect.cpp.

Comment 21

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

Comment on attachment 262630 [details] [diff] [review]
Don't keep hashes around

sr=dbaron on the nsXPConnect.cpp changes; the others are obsolete.