Switch cycle collector to more efficient hashtables

RESOLVED FIXED

Status

()

defect
RESOLVED FIXED
12 years ago
12 years ago

People

(Reporter: graydon, Assigned: peterv)

Tracking

({perf})

Trunk
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(4 attachments, 4 obsolete attachments)

Reporter

Description

12 years ago
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.
Attachment #261636 - Flags: superreview?(dbaron)
Attachment #261636 - Flags: review?(peterv)

Updated

12 years ago
Keywords: perf
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

12 years ago
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.
Reporter

Comment 3

12 years ago
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.
Assignee

Updated

12 years ago
Blocks: 377787
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 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
Attachment #261636 - Flags: superreview?(dbaron) → superreview-
Assignee

Comment 6

12 years ago
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+.
(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.
Assignee

Comment 8

12 years ago
Posted patch v1.1 (obsolete) — Splinter Review
Takes care of the comments and fixes compilation in DEBUG builds.
Assignee: graydon → peterv
Attachment #261636 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #261636 - Flags: review?(peterv)
Assignee

Updated

12 years ago
Attachment #262131 - Flags: superreview?(dbaron)
Attachment #262131 - Flags: superreview?(dbaron) → superreview+
Assignee

Comment 9

12 years ago
Posted patch v1.2Splinter Review
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.
Attachment #262131 - Attachment is obsolete: true
Attachment #262220 - Flags: superreview+
Attachment #262220 - Flags: review+
Assignee

Comment 10

12 years ago
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?
(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.
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.
I'll request reviews once I've actually tested this; my tree is currently rebuilding.
Attachment #262380 - Flags: superreview?(peterv)
Attachment #262380 - Flags: review?(graydon)
Assignee

Updated

12 years ago
Attachment #262380 - Flags: superreview?(peterv) → superreview+
Assignee

Comment 14

12 years ago
(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).
Assignee

Comment 15

12 years ago
Posted patch Don't keep hashes around (obsolete) — Splinter Review
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.
Reporter

Comment 16

12 years ago
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.
Attachment #262380 - Flags: review?(graydon) → review+
Posted patch Don't keep hashes around (obsolete) — Splinter Review
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).
Attachment #262492 - Attachment is obsolete: true
Assignee

Comment 18

12 years ago
Attachment #262567 - Attachment is obsolete: true
Attachment #262630 - Flags: superreview?(dbaron)
Attachment #262630 - Flags: review?(graydon)
Reporter

Comment 19

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

I don't feel strongly about this stuff; whatever works.
Attachment #262630 - Flags: review?(graydon) → review+
Assignee

Comment 20

12 years ago
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 on attachment 262630 [details] [diff] [review]
Don't keep hashes around

sr=dbaron on the nsXPConnect.cpp changes; the others are obsolete.
Attachment #262630 - Flags: superreview?(dbaron) → superreview+
Assignee

Updated

12 years ago
Status: ASSIGNED → RESOLVED
Last Resolved: 12 years ago
Resolution: --- → FIXED

Updated

12 years ago
Flags: in-testsuite-
You need to log in before you can comment on or make changes to this bug.