- Revision
- 183769
- Author
- [email protected]
- Date
- 2015-05-04 13:42:10 -0700 (Mon, 04 May 2015)
Log Message
Optimize WeakBlock's "reap" and "visit" operations.
<https://webkit.org/b/144585>
Reviewed by Geoffrey Garen.
WeakBlock was using Heap::isLive(void*) to determine the liveness of weak pointees.
That function was really written with conservative roots marking in mind, and will do a bunch
of sanity and bounds checks.
For weaks, we know that the pointer will have been a valid cell pointer into a block
of appropriate cell size, so we can skip a lot of the checks.
We now keep a pointer to the MarkedBlock in each WeakBlock. That way we no longer have to do
MarkedBlock::blockFor() for every single cell when iterating.
Note that a WeakBlock's MarkedBlock pointer becomes null when we detach a logically empty
WeakBlock from its WeakSet and transfer ownership to Heap. At that point, the block will never
be pointing to any live cells, and the only operation that will run on the block is sweep().
Finally, MarkedBlock allows liveness queries in three states: Marked, Retired, and Allocated.
In Allocated state, all cells are reported as live. This state will reset to Marked on next GC.
This patch uses that knowledge to avoid branching on the MarkedBlock's state for every cell.
This is a ~3x speedup of visit() and a ~2x speedup of reap() on Dromaeo/dom-modify, netting
what looks like a 1% speedup locally.
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::MarkedBlock): Pass *this to the WeakSet's ctor.
* heap/MarkedBlock.h:
(JSC::MarkedBlock::isMarkedOrNewlyAllocated): Added, stripped-down version of isLive() when the
block's state is known to be either Marked or Retired.
(JSC::MarkedBlock::isAllocated): Added, tells WeakBlock it's okay to skip reap/visit since isLive()
would report that all cells are live anyway.
* heap/WeakBlock.cpp:
(JSC::WeakBlock::create):
(JSC::WeakBlock::WeakBlock): Stash a MarkedBlock* on each WeakBlock.
(JSC::WeakBlock::visit):
(JSC::WeakBlock::reap): Optimized these two to avoid a bunch of pointer arithmetic and branches.
* heap/WeakBlock.h:
(JSC::WeakBlock::disconnectMarkedBlock): Added.
* heap/WeakSet.cpp:
(JSC::WeakSet::sweep): Call the above when removing a WeakBlock from WeakSet and transferring
ownership to Heap until it can die peacefully.
(JSC::WeakSet::addAllocator):
* heap/WeakSet.h:
(JSC::WeakSet::WeakSet): Give WeakSet a MarkedBlock& for passing on to WeakBlocks.
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (183768 => 183769)
--- trunk/Source/_javascript_Core/ChangeLog 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-05-04 20:42:10 UTC (rev 183769)
@@ -1,3 +1,58 @@
+2015-05-04 Andreas Kling <[email protected]>
+
+ Optimize WeakBlock's "reap" and "visit" operations.
+ <https://webkit.org/b/144585>
+
+ Reviewed by Geoffrey Garen.
+
+ WeakBlock was using Heap::isLive(void*) to determine the liveness of weak pointees.
+ That function was really written with conservative roots marking in mind, and will do a bunch
+ of sanity and bounds checks.
+
+ For weaks, we know that the pointer will have been a valid cell pointer into a block
+ of appropriate cell size, so we can skip a lot of the checks.
+
+ We now keep a pointer to the MarkedBlock in each WeakBlock. That way we no longer have to do
+ MarkedBlock::blockFor() for every single cell when iterating.
+
+ Note that a WeakBlock's MarkedBlock pointer becomes null when we detach a logically empty
+ WeakBlock from its WeakSet and transfer ownership to Heap. At that point, the block will never
+ be pointing to any live cells, and the only operation that will run on the block is sweep().
+
+ Finally, MarkedBlock allows liveness queries in three states: Marked, Retired, and Allocated.
+ In Allocated state, all cells are reported as live. This state will reset to Marked on next GC.
+ This patch uses that knowledge to avoid branching on the MarkedBlock's state for every cell.
+
+ This is a ~3x speedup of visit() and a ~2x speedup of reap() on Dromaeo/dom-modify, netting
+ what looks like a 1% speedup locally.
+
+ * heap/MarkedBlock.cpp:
+ (JSC::MarkedBlock::MarkedBlock): Pass *this to the WeakSet's ctor.
+
+ * heap/MarkedBlock.h:
+ (JSC::MarkedBlock::isMarkedOrNewlyAllocated): Added, stripped-down version of isLive() when the
+ block's state is known to be either Marked or Retired.
+
+ (JSC::MarkedBlock::isAllocated): Added, tells WeakBlock it's okay to skip reap/visit since isLive()
+ would report that all cells are live anyway.
+
+ * heap/WeakBlock.cpp:
+ (JSC::WeakBlock::create):
+ (JSC::WeakBlock::WeakBlock): Stash a MarkedBlock* on each WeakBlock.
+
+ (JSC::WeakBlock::visit):
+ (JSC::WeakBlock::reap): Optimized these two to avoid a bunch of pointer arithmetic and branches.
+
+ * heap/WeakBlock.h:
+ (JSC::WeakBlock::disconnectMarkedBlock): Added.
+ * heap/WeakSet.cpp:
+ (JSC::WeakSet::sweep): Call the above when removing a WeakBlock from WeakSet and transferring
+ ownership to Heap until it can die peacefully.
+
+ (JSC::WeakSet::addAllocator):
+ * heap/WeakSet.h:
+ (JSC::WeakSet::WeakSet): Give WeakSet a MarkedBlock& for passing on to WeakBlocks.
+
2015-05-04 Basile Clement <[email protected]>
Allocation sinking is prohibiting the creation of phis between a Phantom object and its materialization
Modified: trunk/Source/_javascript_Core/heap/MarkedBlock.cpp (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/MarkedBlock.cpp 2015-05-04 20:42:10 UTC (rev 183769)
@@ -52,7 +52,7 @@
, m_needsDestruction(needsDestruction)
, m_allocator(allocator)
, m_state(New) // All cells start out unmarked.
- , m_weakSet(allocator->heap()->vm())
+ , m_weakSet(allocator->heap()->vm(), *this)
{
ASSERT(allocator);
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
Modified: trunk/Source/_javascript_Core/heap/MarkedBlock.h (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/MarkedBlock.h 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/MarkedBlock.h 2015-05-04 20:42:10 UTC (rev 183769)
@@ -164,6 +164,7 @@
bool testAndSetMarked(const void*);
bool isLive(const JSCell*);
bool isLiveCell(const void*);
+ bool isMarkedOrNewlyAllocated(const JSCell*);
void setMarked(const void*);
void clearMarked(const void*);
@@ -176,6 +177,7 @@
void setNewlyAllocated(const void*);
void clearNewlyAllocated(const void*);
+ bool isAllocated() const;
bool needsSweeping();
void didRetireBlock(const FreeList&);
void willRemoveBlock();
@@ -410,6 +412,12 @@
return false;
}
+ inline bool MarkedBlock::isMarkedOrNewlyAllocated(const JSCell* cell)
+ {
+ ASSERT(m_state == Retired || m_state == Marked);
+ return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
+ }
+
inline bool MarkedBlock::isLive(const JSCell* cell)
{
switch (m_state) {
@@ -418,7 +426,7 @@
case Retired:
case Marked:
- return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
+ return isMarkedOrNewlyAllocated(cell);
case New:
case FreeListed:
@@ -486,6 +494,11 @@
return m_state == Marked;
}
+ inline bool MarkedBlock::isAllocated() const
+ {
+ return m_state == Allocated;
+ }
+
} // namespace JSC
namespace WTF {
Modified: trunk/Source/_javascript_Core/heap/WeakBlock.cpp (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/WeakBlock.cpp 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/WeakBlock.cpp 2015-05-04 20:42:10 UTC (rev 183769)
@@ -34,9 +34,9 @@
namespace JSC {
-WeakBlock* WeakBlock::create()
+WeakBlock* WeakBlock::create(MarkedBlock& markedBlock)
{
- return new (NotNull, fastMalloc(blockSize)) WeakBlock();
+ return new (NotNull, fastMalloc(blockSize)) WeakBlock(markedBlock);
}
void WeakBlock::destroy(WeakBlock* block)
@@ -45,8 +45,9 @@
fastFree(block);
}
-WeakBlock::WeakBlock()
+WeakBlock::WeakBlock(MarkedBlock& markedBlock)
: DoublyLinkedListNode<WeakBlock>()
+ , m_markedBlock(&markedBlock)
{
for (size_t i = 0; i < weakImplCount(); ++i) {
WeakImpl* weakImpl = &weakImpls()[i];
@@ -98,6 +99,12 @@
if (isEmpty())
return;
+ // If this WeakBlock doesn't belong to a MarkedBlock, we won't even be here.
+ ASSERT(m_markedBlock);
+
+ if (m_markedBlock->isAllocated())
+ return;
+
SlotVisitor& visitor = heapRootVisitor.visitor();
for (size_t i = 0; i < weakImplCount(); ++i) {
@@ -106,7 +113,7 @@
continue;
const JSValue& jsValue = weakImpl->jsValue();
- if (Heap::isLive(jsValue.asCell()))
+ if (m_markedBlock->isMarkedOrNewlyAllocated(jsValue.asCell()))
continue;
WeakHandleOwner* weakHandleOwner = weakImpl->weakHandleOwner();
@@ -126,12 +133,18 @@
if (isEmpty())
return;
+ // If this WeakBlock doesn't belong to a MarkedBlock, we won't even be here.
+ ASSERT(m_markedBlock);
+
+ if (m_markedBlock->isAllocated())
+ return;
+
for (size_t i = 0; i < weakImplCount(); ++i) {
WeakImpl* weakImpl = &weakImpls()[i];
if (weakImpl->state() > WeakImpl::Dead)
continue;
- if (Heap::isLive(weakImpl->jsValue().asCell())) {
+ if (m_markedBlock->isMarkedOrNewlyAllocated(weakImpl->jsValue().asCell())) {
ASSERT(weakImpl->state() == WeakImpl::Live);
continue;
}
Modified: trunk/Source/_javascript_Core/heap/WeakBlock.h (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/WeakBlock.h 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/WeakBlock.h 2015-05-04 20:42:10 UTC (rev 183769)
@@ -36,6 +36,7 @@
class HeapRootVisitor;
class JSValue;
+class MarkedBlock;
class WeakHandleOwner;
class WeakBlock : public DoublyLinkedListNode<WeakBlock> {
@@ -55,7 +56,7 @@
FreeCell* freeList { nullptr };
};
- static WeakBlock* create();
+ static WeakBlock* create(MarkedBlock&);
static void destroy(WeakBlock*);
static WeakImpl* asWeakImpl(FreeCell*);
@@ -70,17 +71,19 @@
void reap();
void lastChanceToFinalize();
+ void disconnectMarkedBlock() { m_markedBlock = nullptr; }
private:
static FreeCell* asFreeCell(WeakImpl*);
- WeakBlock();
+ explicit WeakBlock(MarkedBlock&);
WeakImpl* firstWeakImpl();
void finalize(WeakImpl*);
WeakImpl* weakImpls();
size_t weakImplCount();
void addToFreeList(FreeCell**, WeakImpl*);
+ MarkedBlock* m_markedBlock;
WeakBlock* m_prev;
WeakBlock* m_next;
SweepResult m_sweepResult;
Modified: trunk/Source/_javascript_Core/heap/WeakSet.cpp (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/WeakSet.cpp 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/WeakSet.cpp 2015-05-04 20:42:10 UTC (rev 183769)
@@ -53,6 +53,7 @@
// to the Heap so we don't pin down the entire 64kB MarkedBlock.
m_blocks.remove(block);
heap()->addLogicallyEmptyWeakBlock(block);
+ block->disconnectMarkedBlock();
}
block = nextBlock;
}
@@ -84,7 +85,7 @@
WeakBlock::FreeCell* WeakSet::addAllocator()
{
- WeakBlock* block = WeakBlock::create();
+ WeakBlock* block = WeakBlock::create(m_markedBlock);
heap()->didAllocate(WeakBlock::blockSize);
m_blocks.append(block);
WeakBlock::SweepResult sweepResult = block->takeSweepResult();
Modified: trunk/Source/_javascript_Core/heap/WeakSet.h (183768 => 183769)
--- trunk/Source/_javascript_Core/heap/WeakSet.h 2015-05-04 20:36:31 UTC (rev 183768)
+++ trunk/Source/_javascript_Core/heap/WeakSet.h 2015-05-04 20:42:10 UTC (rev 183769)
@@ -31,6 +31,7 @@
namespace JSC {
class Heap;
+class MarkedBlock;
class WeakImpl;
class WeakSet {
@@ -40,7 +41,7 @@
static WeakImpl* allocate(JSValue, WeakHandleOwner* = 0, void* context = 0);
static void deallocate(WeakImpl*);
- WeakSet(VM*);
+ WeakSet(VM*, MarkedBlock&);
~WeakSet();
void lastChanceToFinalize();
@@ -65,12 +66,14 @@
WeakBlock* m_nextAllocator;
DoublyLinkedList<WeakBlock> m_blocks;
VM* m_vm;
+ MarkedBlock& m_markedBlock;
};
-inline WeakSet::WeakSet(VM* vm)
+inline WeakSet::WeakSet(VM* vm, MarkedBlock& markedBlock)
: m_allocator(0)
, m_nextAllocator(0)
, m_vm(vm)
+ , m_markedBlock(markedBlock)
{
}
