Changeset 120149 in webkit for trunk/Source/JavaScriptCore/heap/MarkStack.cpp

Timestamp:

Jun 12, 2012, 7:06:50 PM (13 years ago)

Author:

[email protected]

Message:

GC should be 1.7X faster
​https://bugs.webkit.org/show_bug.cgi?id=88840

Reviewed by Oliver Hunt.

I profiled, and removed anything that showed up as a concurrency
bottleneck. Then, I added 3 threads to our max thread count, since we
can scale up to more threads now.

• heap/BlockAllocator.cpp:

(JSC::BlockAllocator::BlockAllocator):
(JSC::BlockAllocator::~BlockAllocator):
(JSC::BlockAllocator::releaseFreeBlocks):
(JSC::BlockAllocator::waitForRelativeTimeWhileHoldingLock):
(JSC::BlockAllocator::waitForRelativeTime):
(JSC::BlockAllocator::blockFreeingThreadMain):

• heap/BlockAllocator.h:

(BlockAllocator):
(JSC::BlockAllocator::allocate):
(JSC::BlockAllocator::deallocate): Use a spin lock for the common case
where we're just popping a linked list. (A pthread mutex would sleep our
thread even if the lock were only contended for a microsecond.)

Scope the lock to avoid holding it while allocating VM, since that's a
slow activity and it doesn't modify any of our data structures.

We still use a pthread mutex to handle our condition variable since we
have to, and it's not a hot path.

• heap/CopiedSpace.cpp:

(JSC::CopiedSpace::CopiedSpace):
(JSC::CopiedSpace::doneFillingBlock):

• heap/CopiedSpace.h:

(JSC::CopiedSpace::CopiedSpace): Use a spin lock for the to space lock,
since it just guards linked list and hash table manipulation.

• heap/MarkStack.cpp:

(JSC::MarkStackSegmentAllocator::MarkStackSegmentAllocator):
(JSC::MarkStackSegmentAllocator::allocate):
(JSC::MarkStackSegmentAllocator::release):
(JSC::MarkStackSegmentAllocator::shrinkReserve): Use a spin lock, since
we're just managing a linked list.

(JSC::MarkStackArray::donateSomeCellsTo): Changed donation to be proportional
to our current stack size. This fixes cases where we used to donate too
much. Interestingly, donating too much was starving the donor (when it
ran out of work later) *and* the recipient (since it had to wait on a
long donation operation to complete before it could acquire the lock).

In the worst case, we're still guaranteed to donate N cells in roughly log N time.

This change also fixes cases where we used to donate too little, since
we would always keep a fixed minimum number of cells. In the worst case,
with N marking threads, would could have N large object graph roots in
our stack for the duration of GC, and scale to only 1 thread.

It's an interesting observation that a single object in the mark stack
might represent an arbitrarily large object graph -- and only the act
of marking can find out.

(JSC::MarkStackArray::stealSomeCellsFrom): Steal in proportion to idle
threads. Once again, this fixes cases where constants could cause us
to steal too much or too little.

(JSC::SlotVisitor::donateKnownParallel): Always wake up other threads
if they're idle. We can afford to do this because we're conservative
about when we donate.

(JSC::SlotVisitor::drainFromShared):

• heap/MarkStack.h:

(MarkStackSegmentAllocator):
(MarkStackArray):
(JSC):

• heap/SlotVisitor.h: Merged the "should I donate?" decision into a

single function, for simplicity.

• runtime/Options.cpp:

(minimumNumberOfScansBetweenRebalance): Reduced the delay before donation
a lot. We can afford to do this because, in the common case, donation is
a single branch that decides not to donate.

(cpusToUse): Use more CPUs now, since we scale better now.

• runtime/Options.h:

(Options): Removed now-unused variables.

File:

• trunk/Source/JavaScriptCore/heap/MarkStack.cpp (modified) (9 diffs)

trunk/Source/JavaScriptCore/heap/MarkStack.cpp

@@ -47 +47 @@
     : m_nextFreeSegment(0)
 {
+    m_lock.Init();
 }
 
@@ -57 +58 @@
 {
     {
-        MutexLocker locker(m_lock);
+        SpinLockHolder locker(&m_lock);
         if (m_nextFreeSegment) {
             MarkStackSegment* result = m_nextFreeSegment;
@@ -70 +71 @@
 void MarkStackSegmentAllocator::release(MarkStackSegment* segment)
 {
-    MutexLocker locker(m_lock);
+    SpinLockHolder locker(&m_lock);
     segment->m_previous = m_nextFreeSegment;
     m_nextFreeSegment = segment;
@@ -79 +80 @@
     MarkStackSegment* segments;
     {
-        MutexLocker locker(m_lock);
+        SpinLockHolder locker(&m_lock);
         segments = m_nextFreeSegment;
         m_nextFreeSegment = 0;
@@ -143 +144 @@
 }
 
-bool MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
-{
+void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
+{
+    // Try to donate about 1 / 2 of our cells. To reduce copying costs,
+    // we prefer donating whole segments over donating individual cells,
+    // even if this skews away from our 1 / 2 target.
+
     ASSERT(m_segmentCapacity == other.m_segmentCapacity);
+
+    size_t segmentsToDonate = (m_numberOfPreviousSegments + 2 - 1) / 2; // Round up to donate 1 / 1 previous segments.
+
+    if (!segmentsToDonate) {
+        size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
+        while (cellsToDonate--) {
+            ASSERT(m_top);
+            other.append(removeLast());
+        }
+        return;
+    }
+
     validatePrevious();
     other.validatePrevious();
-        
-    // Fast check: see if the other mark stack already has enough segments.
-    if (other.m_numberOfPreviousSegments + 1 >= Options::maximumNumberOfSharedSegments)
-        return false;
-        
-    size_t numberOfCellsToKeep = Options::minimumNumberOfCellsToKeep;
-    ASSERT(m_top > numberOfCellsToKeep || m_topSegment->m_previous);
-        
-    // Looks like we should donate! Give the other mark stack all of our
-    // previous segments, and then top it off.
+
     MarkStackSegment* previous = m_topSegment->m_previous;
-    while (previous) {
+    while (segmentsToDonate--) {
+        ASSERT(previous);
         ASSERT(m_numberOfPreviousSegments);
 
@@ -171 +180 @@
         other.m_numberOfPreviousSegments++;
     }
-    ASSERT(!m_numberOfPreviousSegments);
-    m_topSegment->m_previous = 0;
+    m_topSegment->m_previous = previous;
+
     validatePrevious();
     other.validatePrevious();
-        
-    // Now top off. We want to keep at a minimum numberOfCellsToKeep, but if
-    // we really have a lot of work, we give up half.
-    if (m_top > numberOfCellsToKeep * 2)
-        numberOfCellsToKeep = m_top / 2;
-    while (m_top > numberOfCellsToKeep)
-        other.append(removeLast());
-        
-    return true;
-}
-
-void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other)
-{
+}
+
+void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
+{
+    // Try to steal 1 / Nth of the shared array, where N is the number of idle threads.
+    // To reduce copying costs, we prefer stealing a whole segment over stealing
+    // individual cells, even if this skews away from our 1 / N target.
+
     ASSERT(m_segmentCapacity == other.m_segmentCapacity);
     validatePrevious();
@@ -212 +216 @@
         return;
     }
-        
-    // Otherwise drain 1/Nth of the shared array where N is the number of
-    // workers, or Options::minimumNumberOfCellsToKeep, whichever is bigger.
-    size_t numberOfCellsToSteal = std::max((size_t)Options::minimumNumberOfCellsToKeep, other.size() / Options::numberOfGCMarkers);
+
+    size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount; // Round up to steal 1 / 1.
     while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
         append(other.removeLast());
@@ -344 +346 @@
 }
 
-void SlotVisitor::donateSlow()
-{
-    // Refuse to donate if shared has more entries than I do.
-    if (m_shared.m_sharedMarkStack.size() > m_stack.size())
-        return;
-    MutexLocker locker(m_shared.m_markingLock);
-    if (m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack)) {
-        // Only wake up threads if the shared stack is big enough; otherwise assume that
-        // it's more profitable for us to just scan this ourselves later.
-        if (m_shared.m_sharedMarkStack.size() >= Options::sharedStackWakeupThreshold)
-            m_shared.m_markingCondition.broadcast();
-    }
+void SlotVisitor::donateKnownParallel()
+{
+    // NOTE: Because we re-try often, we can afford to be conservative, and
+    // assume that donating is not profitable.
+
+    // Avoid locking when a thread reaches a dead end in the object graph.
+    if (m_stack.size() < 2)
+        return;
+
+    // If there's already some shared work queued up, be conservative and assume
+    // that donating more is not profitable.
+    if (m_shared.m_sharedMarkStack.size())
+        return;
+
+    // If we're contending on the lock, be conservative and assume that another
+    // thread is already donating.
+    MutexTryLocker locker(m_shared.m_markingLock);
+    if (!locker.locked())
+        return;
+
+    // Otherwise, assume that a thread will go idle soon, and donate.
+    m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack);
+
+    if (m_shared.m_numberOfActiveParallelMarkers < Options::numberOfGCMarkers)
+        m_shared.m_markingCondition.broadcast();
 }
 
@@ -455 +470 @@
             }
            
-            m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack);
+            size_t idleThreadCount = Options::numberOfGCMarkers - m_shared.m_numberOfActiveParallelMarkers;
+            m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack, idleThreadCount);
             m_shared.m_numberOfActiveParallelMarkers++;
         }