Changeset 91039 in webkit


Ignore:
Timestamp:
Jul 14, 2011 6:40:25 PM (13 years ago)
Author:
commit-queue@webkit.org
Message:

GC allocation fast path has too many operations.
https://bugs.webkit.org/show_bug.cgi?id=64493

Patch by Filip Pizlo <fpizlo@apple.com> on 2011-07-14
Reviewed by Darin Adler.

Changed the timing of the lazy sweep so that it occurs when we land on
a previously-unsweeped block, rather than whenever we land on an unsweeped
cell. After the per-block lazy sweep occurs, the block is turned into a
singly linked list of free cells. The allocation fast path is now just a
load-branch-store to remove a cell from the head of the list.

Additionally, this changes the way new blocks are allocated. Previously,
they would be populated with dummy cells. With this patch, they are
turned into a free list, which means that there will never be destructor
calls for allocations in fresh blocks.

These changes result in a 1.9% speed-up on V8, and a 0.6% speed-up on
SunSpider. There are no observed statistically significant slow-downs
on any individual benchmark.

(JSC::Heap::allocateSlowCase):
(JSC::Heap::collect):
(JSC::Heap::canonicalizeBlocks):
(JSC::Heap::resetAllocator):

  • heap/Heap.h:

(JSC::Heap::forEachProtectedCell):
(JSC::Heap::forEachCell):
(JSC::Heap::forEachBlock):
(JSC::Heap::allocate):

  • heap/MarkedBlock.cpp:

(JSC::MarkedBlock::MarkedBlock):
(JSC::MarkedBlock::lazySweep):
(JSC::MarkedBlock::blessNewBlockForFastPath):
(JSC::MarkedBlock::blessNewBlockForSlowPath):
(JSC::MarkedBlock::canonicalizeBlock):

  • heap/MarkedBlock.h:
  • heap/NewSpace.cpp:

(JSC::NewSpace::addBlock):
(JSC::NewSpace::canonicalizeBlocks):

  • heap/NewSpace.h:

(JSC::NewSpace::allocate):
(JSC::NewSpace::SizeClass::SizeClass):
(JSC::NewSpace::SizeClass::canonicalizeBlock):

  • heap/OldSpace.cpp:

(JSC::OldSpace::addBlock):

Location:
trunk/Source/JavaScriptCore
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r91034 r91039  
     12011-07-14  Filip Pizlo  <fpizlo@apple.com>
     2
     3        GC allocation fast path has too many operations.
     4        https://bugs.webkit.org/show_bug.cgi?id=64493
     5
     6        Reviewed by Darin Adler.
     7       
     8        Changed the timing of the lazy sweep so that it occurs when we land on
     9        a previously-unsweeped block, rather than whenever we land on an unsweeped
     10        cell.  After the per-block lazy sweep occurs, the block is turned into a
     11        singly linked list of free cells.  The allocation fast path is now just a
     12        load-branch-store to remove a cell from the head of the list.
     13       
     14        Additionally, this changes the way new blocks are allocated.  Previously,
     15        they would be populated with dummy cells.  With this patch, they are
     16        turned into a free list, which means that there will never be destructor
     17        calls for allocations in fresh blocks.
     18       
     19        These changes result in a 1.9% speed-up on V8, and a 0.6% speed-up on
     20        SunSpider.  There are no observed statistically significant slow-downs
     21        on any individual benchmark.
     22
     23        * JavaScriptCore.exp:
     24        * heap/Heap.cpp:
     25        (JSC::Heap::allocateSlowCase):
     26        (JSC::Heap::collect):
     27        (JSC::Heap::canonicalizeBlocks):
     28        (JSC::Heap::resetAllocator):
     29        * heap/Heap.h:
     30        (JSC::Heap::forEachProtectedCell):
     31        (JSC::Heap::forEachCell):
     32        (JSC::Heap::forEachBlock):
     33        (JSC::Heap::allocate):
     34        * heap/MarkedBlock.cpp:
     35        (JSC::MarkedBlock::MarkedBlock):
     36        (JSC::MarkedBlock::lazySweep):
     37        (JSC::MarkedBlock::blessNewBlockForFastPath):
     38        (JSC::MarkedBlock::blessNewBlockForSlowPath):
     39        (JSC::MarkedBlock::canonicalizeBlock):
     40        * heap/MarkedBlock.h:
     41        * heap/NewSpace.cpp:
     42        (JSC::NewSpace::addBlock):
     43        (JSC::NewSpace::canonicalizeBlocks):
     44        * heap/NewSpace.h:
     45        (JSC::NewSpace::allocate):
     46        (JSC::NewSpace::SizeClass::SizeClass):
     47        (JSC::NewSpace::SizeClass::canonicalizeBlock):
     48        * heap/OldSpace.cpp:
     49        (JSC::OldSpace::addBlock):
     50
    1512011-07-14  Filip Pizlo  <fpizlo@apple.com>
    252
  • trunk/Source/JavaScriptCore/JavaScriptCore.exp

    r90643 r91039  
    225225__ZN3JSC4Heap11objectCountEv
    226226__ZN3JSC4Heap16activityCallbackEv
     227__ZN3JSC4Heap16allocateSlowCaseERNS_8NewSpace9SizeClassE
    227228__ZN3JSC4Heap16objectTypeCountsEv
    228229__ZN3JSC4Heap17collectAllGarbageEv
     
    238239__ZN3JSC4Heap7destroyEv
    239240__ZN3JSC4Heap7protectENS_7JSValueE
    240 __ZN3JSC4Heap8allocateERNS_8NewSpace9SizeClassE
    241241__ZN3JSC4Heap8capacityEv
    242242__ZN3JSC4Heap9unprotectENS_7JSValueE
  • trunk/Source/JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.def

    r89927 r91039  
    5757    ?addStaticGlobals@JSGlobalObject@JSC@@IAEXPAUGlobalPropertyInfo@12@H@Z
    5858    ?allocate@Heap@JSC@@QAEPAXAAUSizeClass@NewSpace@2@@Z
    59     ?allocate@Heap@JSC@@QAEPAXI@Z
    6059    ?allocatePropertyStorage@JSObject@JSC@@QAEXII@Z
     60    ?allocateSlowCase@Heap@JSC@@AAEPAXAAUSizeClass@NewSpace@2@@Z
    6161    ?append@StringBuilder@WTF@@QAEXPBDI@Z
    6262    ?append@StringBuilder@WTF@@QAEXPB_WI@Z
  • trunk/Source/JavaScriptCore/heap/Heap.cpp

    r90865 r91039  
    103103}
    104104
    105 struct ResetAllocator : MarkedBlock::VoidFunctor {
    106     void operator()(MarkedBlock*);
    107 };
    108 
    109 inline void ResetAllocator::operator()(MarkedBlock* block)
    110 {
    111     block->resetAllocator();
    112 }
    113 
    114105struct Sweep : MarkedBlock::VoidFunctor {
    115106    void operator()(MarkedBlock*);
     
    321312}
    322313
    323 void* Heap::allocate(NewSpace::SizeClass& sizeClass)
     314void* Heap::allocateSlowCase(NewSpace::SizeClass& sizeClass)
    324315{
    325316#if COLLECT_ON_EVERY_ALLOCATION
     
    559550    ASSERT(m_isSafeToCollect);
    560551    JAVASCRIPTCORE_GC_BEGIN();
    561 
     552   
     553    canonicalizeBlocks();
     554   
    562555    markRoots();
    563556    m_handleHeap.finalizeWeakHandles();
     
    589582}
    590583
     584void Heap::canonicalizeBlocks()
     585{
     586    m_newSpace.canonicalizeBlocks();
     587}
     588
    591589void Heap::resetAllocator()
    592590{
    593591    m_extraCost = 0;
    594592    m_newSpace.resetAllocator();
    595     forEachBlock<ResetAllocator>();
    596593}
    597594
  • trunk/Source/JavaScriptCore/heap/Heap.h

    r90865 r91039  
    2525#include "HandleHeap.h"
    2626#include "HandleStack.h"
    27 #include "SlotVisitor.h"
     27#include "MarkedBlock.h"
    2828#include "MarkedBlockSet.h"
    2929#include "NewSpace.h"
     30#include "SlotVisitor.h"
    3031#include <wtf/Forward.h>
    3132#include <wtf/HashCountedSet.h>
     
    125126
    126127        bool isValidAllocation(size_t);
    127         void* allocateSlowCase(size_t);
    128128        void reportExtraMemoryCostSlowCase(size_t);
     129        void canonicalizeBlocks();
    129130        void resetAllocator();
    130131
     
    138139
    139140        void* tryAllocate(NewSpace::SizeClass&);
     141        void* allocateSlowCase(NewSpace::SizeClass&);
    140142       
    141143        enum SweepToggle { DoNotSweep, DoSweep };
     
    243245    template<typename Functor> inline typename Functor::ReturnType Heap::forEachProtectedCell(Functor& functor)
    244246    {
     247        canonicalizeBlocks();
    245248        ProtectCountSet::iterator end = m_protectedValues.end();
    246249        for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
     
    259262    template<typename Functor> inline typename Functor::ReturnType Heap::forEachCell(Functor& functor)
    260263    {
     264        canonicalizeBlocks();
    261265        BlockIterator end = m_blocks.set().end();
    262266        for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
     
    273277    template<typename Functor> inline typename Functor::ReturnType Heap::forEachBlock(Functor& functor)
    274278    {
     279        canonicalizeBlocks();
    275280        BlockIterator end = m_blocks.set().end();
    276281        for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
     
    284289        return forEachBlock(functor);
    285290    }
     291   
     292    inline void* Heap::allocate(NewSpace::SizeClass& sizeClass)
     293    {
     294        // This is a light-weight fast path to cover the most common case.
     295        MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell;
     296        if (UNLIKELY(!firstFreeCell))
     297            return allocateSlowCase(sizeClass);
     298       
     299        sizeClass.firstFreeCell = firstFreeCell->next;
     300        return firstFreeCell;
     301    }
    286302
    287303    inline void* Heap::allocate(size_t bytes)
  • trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp

    r88519 r91039  
    5050
    5151MarkedBlock::MarkedBlock(const PageAllocationAligned& allocation, Heap* heap, size_t cellSize)
    52     : m_nextAtom(firstAtom())
    53     , m_inNewSpace(false)
     52    : m_inNewSpace(false)
    5453    , m_allocation(allocation)
    5554    , m_heap(heap)
     
    5756    m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
    5857    m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
    59 
    60     Structure* dummyMarkableCellStructure = heap->globalData()->dummyMarkableCellStructure.get();
    61     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
    62         new (&atoms()[i]) JSCell(*heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
    6358}
    6459
     
    8681}
    8782
     83MarkedBlock::FreeCell* MarkedBlock::lazySweep()
     84{
     85    // This returns a free list that is ordered in reverse through the block.
     86    // This is fine, since the allocation code makes no assumptions about the
     87    // order of the free list.
     88   
     89    FreeCell* result = 0;
     90   
     91    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
     92        if (!m_marks.testAndSet(i)) {
     93            JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]);
     94            cell->~JSCell();
     95            FreeCell* freeCell = reinterpret_cast<FreeCell*>(cell);
     96            freeCell->next = result;
     97            result = freeCell;
     98        }
     99    }
     100   
     101    return result;
     102}
     103
     104MarkedBlock::FreeCell* MarkedBlock::blessNewBlockForFastPath()
     105{
     106    // This returns a free list that is ordered in reverse through the block,
     107    // as in lazySweep() above.
     108   
     109    FreeCell* result = 0;
     110    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
     111        m_marks.set(i);
     112        FreeCell* freeCell = reinterpret_cast<FreeCell*>(&atoms()[i]);
     113        freeCell->next = result;
     114        result = freeCell;
     115    }
     116    return result;
     117}
     118
     119void MarkedBlock::blessNewBlockForSlowPath()
     120{
     121    Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
     122    for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
     123        new (&atoms()[i]) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
     124}
     125
     126void MarkedBlock::canonicalizeBlock(FreeCell* firstFreeCell)
     127{
     128    Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get();
     129   
     130    for (FreeCell* current = firstFreeCell; current;) {
     131        FreeCell* next = current->next;
     132        size_t i = atomNumber(current);
     133       
     134        m_marks.clear(i);
     135        new (static_cast<void*>(current)) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);
     136
     137        current = next;
     138    }
     139}
     140
    88141#if ENABLE(JSC_ZOMBIES)
    89142void MarkedBlock::clearMarks()
  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r89156 r91039  
    4949        static const size_t ownerSetsPerBlock = 8; // ~2% overhead.
    5050
     51        struct FreeCell {
     52            FreeCell* next;
     53        };
     54       
    5155        struct VoidFunctor {
    5256            typedef void ReturnType;
     
    8589
    8690        void* allocate();
    87         void resetAllocator();
    8891        void sweep();
     92       
     93        // This invokes destructors on all cells that are not marked, marks
     94        // them, and returns a linked list of those cells.
     95        FreeCell* lazySweep();
     96       
     97        // These should be called immediately after a block is created.
     98        // Blessing for fast path creates a linked list, while blessing for
     99        // slow path creates dummy cells.
     100        FreeCell* blessNewBlockForFastPath();
     101        void blessNewBlockForSlowPath();
     102       
     103        // This unmarks all cells on the free list, and allocates dummy JSCells
     104        // in their place.
     105        void canonicalizeBlock(FreeCell* firstFreeCell);
    89106       
    90107        bool isEmpty();
     
    119136        size_t ownerSetNumber(const JSCell*);
    120137
    121         size_t m_nextAtom;
    122138        size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
    123139        size_t m_atomsPerCell;
     
    166182    }
    167183
    168     inline void MarkedBlock::resetAllocator()
    169     {
    170         m_nextAtom = firstAtom();
    171     }
    172 
    173184    inline bool MarkedBlock::isEmpty()
    174185    {
     
    236247        }
    237248    }
    238 
    239     inline void* MarkedBlock::allocate()
    240     {
    241         while (m_nextAtom < m_endAtom) {
    242             if (!m_marks.testAndSet(m_nextAtom)) {
    243                 JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[m_nextAtom]);
    244                 m_nextAtom += m_atomsPerCell;
    245                 destructor(cell);
    246                 return cell;
    247             }
    248             m_nextAtom += m_atomsPerCell;
    249         }
    250 
    251         return 0;
    252     }
    253 
     249   
    254250    inline size_t MarkedBlock::ownerSetNumber(const JSCell* cell)
    255251    {
  • trunk/Source/JavaScriptCore/heap/MarkedBlockSet.h

    r88504 r91039  
    2929#include "MarkedBlock.h"
    3030#include "TinyBloomFilter.h"
     31#include <wtf/HashSet.h>
    3132
    3233namespace JSC {
  • trunk/Source/JavaScriptCore/heap/NewSpace.cpp

    r88519 r91039  
    4949    sizeClass.nextBlock = block;
    5050    sizeClass.blockList.append(block);
     51    ASSERT(!sizeClass.currentBlock);
     52    ASSERT(!sizeClass.firstFreeCell);
     53    sizeClass.currentBlock = block;
     54    sizeClass.firstFreeCell = block->blessNewBlockForFastPath();
    5155}
    5256
     
    7074}
    7175
     76void NewSpace::canonicalizeBlocks()
     77{
     78    for (size_t cellSize = preciseStep; cellSize < preciseCutoff; cellSize += preciseStep)
     79        sizeClassFor(cellSize).canonicalizeBlock();
     80
     81    for (size_t cellSize = impreciseStep; cellSize < impreciseCutoff; cellSize += impreciseStep)
     82        sizeClassFor(cellSize).canonicalizeBlock();
     83}
     84
    7285} // namespace JSC
  • trunk/Source/JavaScriptCore/heap/NewSpace.h

    r89077 r91039  
    5151            SizeClass();
    5252            void resetAllocator();
    53 
     53            void canonicalizeBlock();
     54
     55            MarkedBlock::FreeCell* firstFreeCell;
     56            MarkedBlock* currentBlock;
    5457            MarkedBlock* nextBlock;
    5558            DoublyLinkedList<MarkedBlock> blockList;
     
    6568        void addBlock(SizeClass&, MarkedBlock*);
    6669        void removeBlock(MarkedBlock*);
     70       
     71        void canonicalizeBlocks();
    6772
    6873        size_t waterMark();
     
    116121    inline void* NewSpace::allocate(SizeClass& sizeClass)
    117122    {
    118         for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) {
    119             if (void* result = block->allocate())
    120                 return result;
    121 
    122             m_waterMark += block->capacity();
    123         }
    124 
    125         return 0;
     123        MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell;
     124        if (!firstFreeCell) {
     125            // There are two possibilities for why we got here:
     126            // 1) We've exhausted the allocation cache for currentBlock, in which case
     127            //    currentBlock == nextBlock, and we know that there is no reason to
     128            //    repeat a lazy sweep of nextBlock because we won't find anything.
     129            // 2) Allocation caches have been cleared, in which case nextBlock may
     130            //    have (and most likely does have) free cells, so we almost certainly
     131            //    should do a lazySweep for nextBlock. This also implies that
     132            //    currentBlock == 0.
     133           
     134            if (sizeClass.currentBlock) {
     135                ASSERT(sizeClass.currentBlock == sizeClass.nextBlock);
     136                m_waterMark += sizeClass.nextBlock->capacity();
     137                sizeClass.nextBlock = sizeClass.nextBlock->next();
     138                sizeClass.currentBlock = 0;
     139            }
     140           
     141            for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) {
     142                firstFreeCell = block->lazySweep();
     143                if (firstFreeCell) {
     144                    sizeClass.firstFreeCell = firstFreeCell;
     145                    sizeClass.currentBlock = block;
     146                    break;
     147                }
     148               
     149                m_waterMark += block->capacity();
     150            }
     151           
     152            if (!firstFreeCell)
     153                return 0;
     154        }
     155       
     156        ASSERT(firstFreeCell);
     157       
     158        sizeClass.firstFreeCell = firstFreeCell->next;
     159        return firstFreeCell;
    126160    }
    127161
     
    156190
    157191    inline NewSpace::SizeClass::SizeClass()
    158         : nextBlock(0)
     192        : firstFreeCell(0)
     193        , currentBlock(0)
     194        , nextBlock(0)
    159195        , cellSize(0)
    160196    {
     
    165201        nextBlock = blockList.head();
    166202    }
     203   
     204    inline void NewSpace::SizeClass::canonicalizeBlock()
     205    {
     206        if (currentBlock) {
     207            currentBlock->canonicalizeBlock(firstFreeCell);
     208            firstFreeCell = 0;
     209        }
     210       
     211        ASSERT(!firstFreeCell);
     212       
     213        currentBlock = 0;
     214        firstFreeCell = 0;
     215    }
    167216
    168217} // namespace JSC
  • trunk/Source/JavaScriptCore/heap/OldSpace.cpp

    r88519 r91039  
    3737{
    3838    m_blocks.append(block);
     39    block->blessNewBlockForSlowPath();
    3940}
    4041
Note: See TracChangeset for help on using the changeset viewer.