Changeset 87522 in webkit


Ignore:
Timestamp:
May 27, 2011 10:39:35 AM (13 years ago)
Author:
ggaren@apple.com
Message:

2011-05-26 Geoffrey Garen <​ggaren@apple.com>

Reviewed by Oliver Hunt.

Optimized ConservativeSet to avoid double-visiting objects
​https://bugs.webkit.org/show_bug.cgi?id=61592


SunSpider thinks this might be a 1% speedup

  • heap/ConservativeRoots.h: (JSC::ConservativeRoots::add): Use testAndClearMarked to avoid double-visiting an object.
  • heap/Heap.h: (JSC::Heap::isMarked): (JSC::Heap::testAndSetMarked): (JSC::Heap::testAndClearMarked): (JSC::Heap::setMarked): Added testAndClearMarked. Changed argument type to void*, since clients want to ask questions about arbitrary pointers into the heap, even when they aren't known to be JSCells.
  • heap/MarkedBlock.h: (JSC::MarkedBlock::testAndClearMarked):
  • heap/MarkedSpace.h: (JSC::MarkedSpace::isMarked): (JSC::MarkedSpace::testAndSetMarked): (JSC::MarkedSpace::testAndClearMarked): (JSC::MarkedSpace::setMarked): (JSC::MarkedSpace::contains): Ditto.
  • wtf/Bitmap.h: (WTF::::testAndClear): New function for ConservativeRoots's inverted marking pass.
Location:
trunk/Source/JavaScriptCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r87520 r87522  
     12011-05-26  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Reviewed by Oliver Hunt.
     4
     5        Optimized ConservativeSet to avoid double-visiting objects
     6        https://bugs.webkit.org/show_bug.cgi?id=61592
     7       
     8        SunSpider thinks this might be a 1% speedup
     9
     10        * heap/ConservativeRoots.h:
     11        (JSC::ConservativeRoots::add): Use testAndClearMarked to avoid double-visiting
     12        an object.
     13
     14        * heap/Heap.h:
     15        (JSC::Heap::isMarked):
     16        (JSC::Heap::testAndSetMarked):
     17        (JSC::Heap::testAndClearMarked):
     18        (JSC::Heap::setMarked): Added testAndClearMarked. Changed argument type
     19        to void*, since clients want to ask questions about arbitrary pointers
     20        into the heap, even when they aren't known to be JSCells.
     21
     22        * heap/MarkedBlock.h:
     23        (JSC::MarkedBlock::testAndClearMarked):
     24        * heap/MarkedSpace.h:
     25        (JSC::MarkedSpace::isMarked):
     26        (JSC::MarkedSpace::testAndSetMarked):
     27        (JSC::MarkedSpace::testAndClearMarked):
     28        (JSC::MarkedSpace::setMarked):
     29        (JSC::MarkedSpace::contains): Ditto.
     30
     31        * wtf/Bitmap.h:
     32        (WTF::::testAndClear): New function for ConservativeRoots's inverted
     33        marking pass.
     34
    1352011-05-27  Stephanie Lewis  <slewis@apple.com>
    236

  • trunk/Source/JavaScriptCore/heap/ConservativeRoots.h

    r83506 r87522  
    3535class JSCell;
    3636class Heap;
    37 
    38 // May contain duplicates.
    3937
    4038class ConservativeRoots {
    … …  
    8179        return;
    8280
     81    // The conservative set inverts the typical meaning of mark bits: We only
     82    // visit marked pointers, and our visit clears the mark bit. This efficiently
     83    // sifts out pointers to dead objects and duplicate pointers.
     84    if (!m_heap->testAndClearMarked(p))
     85        return;
     86
    8387    if (m_size == m_capacity)
    8488        grow();
    8589
    86     m_roots[m_size++] = reinterpret_cast<JSCell*>(p);
     90    m_roots[m_size++] = static_cast<JSCell*>(p);
    8791}
    8892

  • trunk/Source/JavaScriptCore/heap/Heap.h

    r87441 r87522  
    5959        static Heap* heap(JSCell*);
    6060
    61         static bool isMarked(const JSCell*);
    62         static bool testAndSetMarked(const JSCell*);
    63         static void setMarked(JSCell*);
     61        static bool isMarked(const void*);
     62        static bool testAndSetMarked(const void*);
     63        static bool testAndClearMarked(const void*);
     64        static void setMarked(const void*);
    6465
    6566        static void writeBarrier(const JSCell*, JSValue);
    … …  
    155156    }
    156157
    157     inline bool Heap::isMarked(const JSCell* cell)
     158    inline bool Heap::isMarked(const void* cell)
    158159    {
    159160        return MarkedSpace::isMarked(cell);
    160161    }
    161162
    162     inline bool Heap::testAndSetMarked(const JSCell* cell)
     163    inline bool Heap::testAndSetMarked(const void* cell)
    163164    {
    164165        return MarkedSpace::testAndSetMarked(cell);
    165166    }
    166167
    167     inline void Heap::setMarked(JSCell* cell)
     168    inline bool Heap::testAndClearMarked(const void* cell)
     169    {
     170        return MarkedSpace::testAndClearMarked(cell);
     171    }
     172
     173    inline void Heap::setMarked(const void* cell)
    168174    {
    169175        MarkedSpace::setMarked(cell);

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r87441 r87522  
    6868        size_t capacity();
    6969
    70         bool contains(const void*);
    7170        size_t atomNumber(const void*);
    7271        bool isMarked(const void*);
    7372        bool testAndSetMarked(const void*);
     73        bool testAndClearMarked(const void*);
    7474        void setMarked(const void*);
    7575       
    … …  
    161161    }
    162162
    163     inline bool MarkedBlock::contains(const void* p)
    164     {
    165         ASSERT(p && isAtomAligned(p) && atomNumber(p) < atomsPerBlock);
    166 
    167         // Even though we physically contain p, we only logically contain p if p
    168         // points to a live cell. (Claiming to contain a dead cell would trick the
    169         // conservative garbage collector into resurrecting the cell in a zombie state.)
    170         return isMarked(p);
    171     }
    172 
    173163    inline size_t MarkedBlock::atomNumber(const void* p)
    174164    {
    … …  
    184174    {
    185175        return m_marks.testAndSet(atomNumber(p));
     176    }
     177
     178    inline bool MarkedBlock::testAndClearMarked(const void* p)
     179    {
     180        return m_marks.testAndClear(atomNumber(p));
    186181    }
    187182

  • trunk/Source/JavaScriptCore/heap/MarkedSpace.h

    r87441 r87522  
    5353        static Heap* heap(JSCell*);
    5454
    55         static bool isMarked(const JSCell*);
    56         static bool testAndSetMarked(const JSCell*);
    57         static void setMarked(const JSCell*);
     55        static bool isMarked(const void*);
     56        static bool testAndSetMarked(const void*);
     57        static bool testAndClearMarked(const void*);
     58        static void setMarked(const void*);
    5859
    5960        MarkedSpace(JSGlobalData*);
    … …  
    124125    }
    125126
    126     inline bool MarkedSpace::isMarked(const JSCell* cell)
     127    inline bool MarkedSpace::isMarked(const void* cell)
    127128    {
    128129        return MarkedBlock::blockFor(cell)->isMarked(cell);
    129130    }
    130131
    131     inline bool MarkedSpace::testAndSetMarked(const JSCell* cell)
     132    inline bool MarkedSpace::testAndSetMarked(const void* cell)
    132133    {
    133134        return MarkedBlock::blockFor(cell)->testAndSetMarked(cell);
    134135    }
    135136
    136     inline void MarkedSpace::setMarked(const JSCell* cell)
     137    inline bool MarkedSpace::testAndClearMarked(const void* cell)
     138    {
     139        return MarkedBlock::blockFor(cell)->testAndClearMarked(cell);
     140    }
     141
     142    inline void MarkedSpace::setMarked(const void* cell)
    137143    {
    138144        MarkedBlock::blockFor(cell)->setMarked(cell);
    … …  
    147153        if (!block || !m_blocks.contains(block))
    148154            return false;
    149 
    150         return block->contains(x);
     155           
     156        return true;
    151157    }
    152158

  • trunk/Source/JavaScriptCore/wtf/Bitmap.h

    r79126 r87522  
    3838    void set(size_t);
    3939    bool testAndSet(size_t);
     40    bool testAndClear(size_t);
    4041    size_t nextPossiblyUnset(size_t) const;
    4142    void clear(size_t);
    … …  
    8586    bool result = bits[index] & mask;
    8687    bits[index] |= mask;
     88    return result;
     89}
     90
     91template<size_t size>
     92inline bool Bitmap<size>::testAndClear(size_t n)
     93{
     94    WordType mask = one << (n % wordSize);
     95    size_t index = n / wordSize;
     96    bool result = bits[index] & mask;
     97    bits[index] &= ~mask;
    8798    return result;
    8899}
Note: See TracChangeset for help on using the changeset viewer.