Changeset 183769 in webkit


Ignore:
Timestamp:
May 4, 2015 1:42:10 PM (9 years ago)
Author:
akling@apple.com
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.

Location:
trunk/Source/JavaScriptCore
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r183763 r183769  
     12015-05-04  Andreas Kling  <akling@apple.com>
     2
     3        Optimize WeakBlock's "reap" and "visit" operations.
     4        <https://webkit.org/b/144585>
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        WeakBlock was using Heap::isLive(void*) to determine the liveness of weak pointees.
     9        That function was really written with conservative roots marking in mind, and will do a bunch
     10        of sanity and bounds checks.
     11
     12        For weaks, we know that the pointer will have been a valid cell pointer into a block
     13        of appropriate cell size, so we can skip a lot of the checks.
     14
     15        We now keep a pointer to the MarkedBlock in each WeakBlock. That way we no longer have to do
     16        MarkedBlock::blockFor() for every single cell when iterating.
     17
     18        Note that a WeakBlock's MarkedBlock pointer becomes null when we detach a logically empty
     19        WeakBlock from its WeakSet and transfer ownership to Heap. At that point, the block will never
     20        be pointing to any live cells, and the only operation that will run on the block is sweep().
     21
     22        Finally, MarkedBlock allows liveness queries in three states: Marked, Retired, and Allocated.
     23        In Allocated state, all cells are reported as live. This state will reset to Marked on next GC.
     24        This patch uses that knowledge to avoid branching on the MarkedBlock's state for every cell.
     25
     26        This is a ~3x speedup of visit() and a ~2x speedup of reap() on Dromaeo/dom-modify, netting
     27        what looks like a 1% speedup locally.
     28
     29        * heap/MarkedBlock.cpp:
     30        (JSC::MarkedBlock::MarkedBlock): Pass *this to the WeakSet's ctor.
     31
     32        * heap/MarkedBlock.h:
     33        (JSC::MarkedBlock::isMarkedOrNewlyAllocated): Added, stripped-down version of isLive() when the
     34        block's state is known to be either Marked or Retired.
     35
     36        (JSC::MarkedBlock::isAllocated): Added, tells WeakBlock it's okay to skip reap/visit since isLive()
     37        would report that all cells are live anyway.
     38
     39        * heap/WeakBlock.cpp:
     40        (JSC::WeakBlock::create):
     41        (JSC::WeakBlock::WeakBlock): Stash a MarkedBlock* on each WeakBlock.
     42
     43        (JSC::WeakBlock::visit):
     44        (JSC::WeakBlock::reap): Optimized these two to avoid a bunch of pointer arithmetic and branches.
     45
     46        * heap/WeakBlock.h:
     47        (JSC::WeakBlock::disconnectMarkedBlock): Added.
     48        * heap/WeakSet.cpp:
     49        (JSC::WeakSet::sweep): Call the above when removing a WeakBlock from WeakSet and transferring
     50        ownership to Heap until it can die peacefully.
     51
     52        (JSC::WeakSet::addAllocator):
     53        * heap/WeakSet.h:
     54        (JSC::WeakSet::WeakSet): Give WeakSet a MarkedBlock& for passing on to WeakBlocks.
     55
    1562015-05-04  Basile Clement  <basile_clement@apple.com>
    257
  • trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp

    r183124 r183769  
    5353    , m_allocator(allocator)
    5454    , m_state(New) // All cells start out unmarked.
    55     , m_weakSet(allocator->heap()->vm())
     55    , m_weakSet(allocator->heap()->vm(), *this)
    5656{
    5757    ASSERT(allocator);
  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r183124 r183769  
    165165        bool isLive(const JSCell*);
    166166        bool isLiveCell(const void*);
     167        bool isMarkedOrNewlyAllocated(const JSCell*);
    167168        void setMarked(const void*);
    168169        void clearMarked(const void*);
     
    177178        void clearNewlyAllocated(const void*);
    178179
     180        bool isAllocated() const;
    179181        bool needsSweeping();
    180182        void didRetireBlock(const FreeList&);
     
    411413    }
    412414
     415    inline bool MarkedBlock::isMarkedOrNewlyAllocated(const JSCell* cell)
     416    {
     417        ASSERT(m_state == Retired || m_state == Marked);
     418        return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
     419    }
     420
    413421    inline bool MarkedBlock::isLive(const JSCell* cell)
    414422    {
     
    419427        case Retired:
    420428        case Marked:
    421             return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
     429            return isMarkedOrNewlyAllocated(cell);
    422430
    423431        case New:
     
    487495    }
    488496
     497    inline bool MarkedBlock::isAllocated() const
     498    {
     499        return m_state == Allocated;
     500    }
     501
    489502} // namespace JSC
    490503
  • trunk/Source/JavaScriptCore/heap/WeakBlock.cpp

    r182347 r183769  
    3535namespace JSC {
    3636
    37 WeakBlock* WeakBlock::create()
     37WeakBlock* WeakBlock::create(MarkedBlock& markedBlock)
    3838{
    39     return new (NotNull, fastMalloc(blockSize)) WeakBlock();
     39    return new (NotNull, fastMalloc(blockSize)) WeakBlock(markedBlock);
    4040}
    4141
     
    4646}
    4747
    48 WeakBlock::WeakBlock()
     48WeakBlock::WeakBlock(MarkedBlock& markedBlock)
    4949    : DoublyLinkedListNode<WeakBlock>()
     50    , m_markedBlock(&markedBlock)
    5051{
    5152    for (size_t i = 0; i < weakImplCount(); ++i) {
     
    99100        return;
    100101
     102    // If this WeakBlock doesn't belong to a MarkedBlock, we won't even be here.
     103    ASSERT(m_markedBlock);
     104
     105    if (m_markedBlock->isAllocated())
     106        return;
     107
    101108    SlotVisitor& visitor = heapRootVisitor.visitor();
    102109
     
    107114
    108115        const JSValue& jsValue = weakImpl->jsValue();
    109         if (Heap::isLive(jsValue.asCell()))
     116        if (m_markedBlock->isMarkedOrNewlyAllocated(jsValue.asCell()))
    110117            continue;
    111118
     
    127134        return;
    128135
     136    // If this WeakBlock doesn't belong to a MarkedBlock, we won't even be here.
     137    ASSERT(m_markedBlock);
     138
     139    if (m_markedBlock->isAllocated())
     140        return;
     141
    129142    for (size_t i = 0; i < weakImplCount(); ++i) {
    130143        WeakImpl* weakImpl = &weakImpls()[i];
     
    132145            continue;
    133146
    134         if (Heap::isLive(weakImpl->jsValue().asCell())) {
     147        if (m_markedBlock->isMarkedOrNewlyAllocated(weakImpl->jsValue().asCell())) {
    135148            ASSERT(weakImpl->state() == WeakImpl::Live);
    136149            continue;
  • trunk/Source/JavaScriptCore/heap/WeakBlock.h

    r182878 r183769  
    3737class HeapRootVisitor;
    3838class JSValue;
     39class MarkedBlock;
    3940class WeakHandleOwner;
    4041
     
    5657    };
    5758
    58     static WeakBlock* create();
     59    static WeakBlock* create(MarkedBlock&);
    5960    static void destroy(WeakBlock*);
    6061
     
    7172
    7273    void lastChanceToFinalize();
     74    void disconnectMarkedBlock() { m_markedBlock = nullptr; }
    7375
    7476private:
    7577    static FreeCell* asFreeCell(WeakImpl*);
    7678
    77     WeakBlock();
     79    explicit WeakBlock(MarkedBlock&);
    7880    WeakImpl* firstWeakImpl();
    7981    void finalize(WeakImpl*);
     
    8284    void addToFreeList(FreeCell**, WeakImpl*);
    8385
     86    MarkedBlock* m_markedBlock;
    8487    WeakBlock* m_prev;
    8588    WeakBlock* m_next;
  • trunk/Source/JavaScriptCore/heap/WeakSet.cpp

    r182347 r183769  
    5454            m_blocks.remove(block);
    5555            heap()->addLogicallyEmptyWeakBlock(block);
     56            block->disconnectMarkedBlock();
    5657        }
    5758        block = nextBlock;
     
    8586WeakBlock::FreeCell* WeakSet::addAllocator()
    8687{
    87     WeakBlock* block = WeakBlock::create();
     88    WeakBlock* block = WeakBlock::create(m_markedBlock);
    8889    heap()->didAllocate(WeakBlock::blockSize);
    8990    m_blocks.append(block);
  • trunk/Source/JavaScriptCore/heap/WeakSet.h

    r156794 r183769  
    3232
    3333class Heap;
     34class MarkedBlock;
    3435class WeakImpl;
    3536
     
    4142    static void deallocate(WeakImpl*);
    4243
    43     WeakSet(VM*);
     44    WeakSet(VM*, MarkedBlock&);
    4445    ~WeakSet();
    4546    void lastChanceToFinalize();
     
    6667    DoublyLinkedList<WeakBlock> m_blocks;
    6768    VM* m_vm;
     69    MarkedBlock& m_markedBlock;
    6870};
    6971
    70 inline WeakSet::WeakSet(VM* vm)
     72inline WeakSet::WeakSet(VM* vm, MarkedBlock& markedBlock)
    7173    : m_allocator(0)
    7274    , m_nextAllocator(0)
    7375    , m_vm(vm)
     76    , m_markedBlock(markedBlock)
    7477{
    7578}
Note: See TracChangeset for help on using the changeset viewer.