Changeset 121806 in webkit


Ignore:
Timestamp:
Jul 3, 2012 3:57:00 PM (12 years ago)
Author:
msaboff@apple.com
Message:

Enh: Hash Const JSString in Backing Stores to Save Memory
​https://bugs.webkit.org/show_bug.cgi?id=86024

Reviewed by Oliver Hunt.

During garbage collection, each marking thread keeps a HashMap of
strings. While visiting via MarkStack::copyAndAppend(), we check to
see if the string we are visiting is already in the HashMap. If not
we add it. If so, we change the reference to the current string we're
visiting to the prior string.

To reduce the performance impact of this change, two throttles have
ben added. 1) We only try hash consting if a significant number of new
strings have been created since the last hash const. Currently this is
set at 100 strings. 2) If a string is unique at the end of a marking
it will not be checked during further GC phases. In some cases this
won't catch all duplicates, but we are trying to catch the growth of
duplicate strings.

  • heap/Heap.cpp:

(JSC::Heap::markRoots):

  • heap/MarkStack.cpp:

(JSC::MarkStackThreadSharedData::resetChildren):
(JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
(JSC::MarkStackThreadSharedData::reset):
(JSC::MarkStack::setup): Check to see if enough strings have been created
to hash const.
(JSC::MarkStack::reset): Added call to clear m_uniqueStrings.
(JSC::JSString::tryHashConstLock): New method to lock JSString for
hash consting.
(JSC::JSString::releaseHashConstLock): New unlock method.
(JSC::JSString::shouldTryHashConst): Set of checks to see if we should
try to hash const the string.
(JSC::MarkStack::internalAppend): New method that performs the hash consting.
(JSC::SlotVisitor::copyAndAppend): Changed to call the new hash
consting internalAppend().

  • heap/MarkStack.h:

(MarkStackThreadSharedData):
(MarkStack):

  • runtime/JSGlobalData.cpp:

(JSC::JSGlobalData::JSGlobalData):

  • runtime/JSGlobalData.h:

(JSGlobalData):
(JSC::JSGlobalData::haveEnoughNewStringsToHashConst):
(JSC::JSGlobalData::resetNewStringsSinceLastHashConst):

  • runtime/JSString.h:

(JSString): Changed from using bool flags to using an unsigned
m_flags field. This works better with the weakCompareAndSwap in
JSString::tryHashConstLock(). Changed the 8bitness setting and
checking to use new accessors.
(JSC::JSString::JSString):
(JSC::JSString::finishCreation):
(JSC::JSString::is8Bit): Updated for new m_flags.
(JSC::JSString::setIs8Bit): New setter.
New hash const flags accessors:
(JSC::JSString::isHashConstSingleton):
(JSC::JSString::clearHashConstSingleton):
(JSC::JSString::setHashConstSingleton):
(JSC::JSRopeString::finishCreation):
(JSC::JSRopeString::append):

Location:
trunk/Source/JavaScriptCore
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r121801 r121806  
     12012-07-03  Michael Saboff  <msaboff@apple.com>
     2
     3        Enh: Hash Const JSString in Backing Stores to Save Memory
     4        https://bugs.webkit.org/show_bug.cgi?id=86024
     5
     6        Reviewed by Oliver Hunt.
     7
     8        During garbage collection, each marking thread keeps a HashMap of
     9        strings.  While visiting via MarkStack::copyAndAppend(), we check to
     10        see if the string we are visiting is already in the HashMap.  If not
     11        we add it. If so, we change the reference to the current string we're
     12        visiting to the prior string.
     13
     14        To reduce the performance impact of this change, two throttles have
     15        ben added.  1) We only try hash consting if a significant number of new
     16        strings have been created since the last hash const.  Currently this is
     17        set at 100 strings.  2) If a string is unique at the end of a marking
     18        it will not be checked during further GC phases. In some cases this
     19        won't catch all duplicates, but we are trying to catch the growth of
     20        duplicate strings.
     21
     22        * heap/Heap.cpp:
     23        (JSC::Heap::markRoots):
     24        * heap/MarkStack.cpp:
     25        (JSC::MarkStackThreadSharedData::resetChildren):
     26        (JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
     27        (JSC::MarkStackThreadSharedData::reset):
     28        (JSC::MarkStack::setup): Check to see if enough strings have been created
     29        to hash const.
     30        (JSC::MarkStack::reset): Added call to clear m_uniqueStrings.
     31        (JSC::JSString::tryHashConstLock): New method to lock JSString for
     32        hash consting.
     33        (JSC::JSString::releaseHashConstLock): New unlock method.
     34        (JSC::JSString::shouldTryHashConst): Set of checks to see if we should
     35        try to hash const the string.
     36        (JSC::MarkStack::internalAppend): New method that performs the hash consting.
     37        (JSC::SlotVisitor::copyAndAppend): Changed to call the new hash
     38        consting internalAppend().
     39        * heap/MarkStack.h:
     40        (MarkStackThreadSharedData):
     41        (MarkStack):
     42        * runtime/JSGlobalData.cpp:
     43        (JSC::JSGlobalData::JSGlobalData):
     44        * runtime/JSGlobalData.h:
     45        (JSGlobalData):
     46        (JSC::JSGlobalData::haveEnoughNewStringsToHashConst):
     47        (JSC::JSGlobalData::resetNewStringsSinceLastHashConst):
     48        * runtime/JSString.h:
     49        (JSString): Changed from using bool flags to using an unsigned
     50        m_flags field.  This works better with the weakCompareAndSwap in
     51        JSString::tryHashConstLock(). Changed the 8bitness setting and
     52        checking to use new accessors.
     53        (JSC::JSString::JSString):
     54        (JSC::JSString::finishCreation):
     55        (JSC::JSString::is8Bit): Updated for new m_flags.
     56        (JSC::JSString::setIs8Bit): New setter.
     57        New hash const flags accessors:
     58        (JSC::JSString::isHashConstSingleton):
     59        (JSC::JSString::clearHashConstSingleton):
     60        (JSC::JSString::setHashConstSingleton):
     61        (JSC::JSRopeString::finishCreation):
     62        (JSC::JSRopeString::append):
     63
    1642012-07-03  Tony Chang  <tony@chromium.org>
    265

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

    r121607 r121806  
    455455    m_storageSpace.startedCopying();
    456456    SlotVisitor& visitor = m_slotVisitor;
     457    visitor.setup();
    457458    HeapRootVisitor heapRootVisitor(visitor);
    458459
    … …  
    586587
    587588    visitor.reset();
    588     m_sharedData.reset();
    589589#if ENABLE(PARALLEL_GC)
    590590    m_sharedData.resetChildren();
    591591#endif
     592    m_sharedData.reset();
    592593    m_storageSpace.doneCopying();
    593 
    594594}
    595595

  • trunk/Source/JavaScriptCore/heap/MarkStack.cpp

    r121798 r121806  
    3939#include "UString.h"
    4040#include "WriteBarrier.h"
     41#include <wtf/Atomics.h>
    4142#include <wtf/DataLog.h>
    4243#include <wtf/MainThread.h>
    … …  
    226227{
    227228    for (unsigned i = 0; i < m_markingThreadsMarkStack.size(); ++i)
    228        m_markingThreadsMarkStack[i]->reset();
    229 }   
     229        m_markingThreadsMarkStack[i]->reset();
     230}
    230231
    231232size_t MarkStackThreadSharedData::childVisitCount()
    … …  
    258259    : m_globalData(globalData)
    259260    , m_copiedSpace(&globalData->heap.m_storageSpace)
     261    , m_shouldHashConst(false)
    260262    , m_sharedMarkStack(m_segmentAllocator)
    261263    , m_numberOfActiveParallelMarkers(0)
    … …  
    299301#endif
    300302    m_weakReferenceHarvesters.removeAll();
     303
     304    if (m_shouldHashConst) {
     305        m_globalData->resetNewStringsSinceLastHashConst();
     306        m_shouldHashConst = false;
     307    }
     308}
     309
     310void MarkStack::setup()
     311{
     312    m_shared.m_shouldHashConst = m_shared.m_globalData->haveEnoughNewStringsToHashConst();
     313    m_shouldHashConst = m_shared.m_shouldHashConst;
     314#if ENABLE(PARALLEL_GC)
     315    for (unsigned i = 0; i < m_shared.m_markingThreadsMarkStack.size(); ++i)
     316        m_shared.m_markingThreadsMarkStack[i]->m_shouldHashConst = m_shared.m_shouldHashConst;
     317#endif
    301318}
    302319
    … …  
    310327    m_opaqueRoots.clear();
    311328#endif
     329    if (m_shouldHashConst) {
     330        m_uniqueStrings.clear();
     331        m_shouldHashConst = false;
     332    }
    312333}
    313334
    … …  
    522543}
    523544
     545ALWAYS_INLINE bool JSString::tryHashConstLock()
     546{
     547#if ENABLE(PARALLEL_GC)
     548    unsigned currentFlags = m_flags;
     549    unsigned newFlags = currentFlags | HashConstLock;
     550
     551    if (!WTF::weakCompareAndSwap(&m_flags, currentFlags, newFlags))
     552        return false;
     553
     554    WTF::memoryBarrierAfterLock();
     555    return true;
     556#else
     557    if (isHashConstSingleton())
     558        return false;
     559
     560    m_flags |= HashConstLock;
     561
     562    return true;
     563#endif
     564}
     565
     566ALWAYS_INLINE void JSString::releaseHashConstLock()
     567{
     568#if ENABLE(PARALLEL_GC)
     569    WTF::memoryBarrierBeforeUnlock();
     570#endif
     571    m_flags &= ~HashConstLock;
     572}
     573
     574ALWAYS_INLINE bool JSString::shouldTryHashConst()
     575{
     576    return ((length() > 1) && !isRope() && !isHashConstSingleton());
     577}
     578
     579ALWAYS_INLINE void MarkStack::internalAppend(JSValue* slot)
     580{
     581    // This internalAppend is only intended for visits to object and array backing stores.
     582    // as it can change the JSValue pointed to be the argument when the original JSValue
     583    // is a string that contains the same contents as another string.
     584
     585    ASSERT(slot);
     586    JSValue value = *slot;
     587    ASSERT(value);
     588    if (!value.isCell())
     589        return;
     590
     591    JSCell* cell = value.asCell();
     592
     593    if (m_shouldHashConst && cell->isString()) {
     594        JSString* string = jsCast<JSString*>(cell);
     595        if (string->shouldTryHashConst() && string->tryHashConstLock()) {
     596            UniqueStringMap::AddResult addResult = m_uniqueStrings.add(string->string().impl(), value);
     597            if (addResult.isNewEntry)
     598                string->setHashConstSingleton();
     599            else {
     600                JSValue existingJSValue = addResult.iterator->second;
     601                if (value != existingJSValue)
     602                    jsCast<JSString*>(existingJSValue.asCell())->clearHashConstSingleton();
     603                *slot = existingJSValue;
     604                string->releaseHashConstLock();
     605                return;
     606            }
     607            string->releaseHashConstLock();
     608        }
     609    }
     610
     611    internalAppend(cell);
     612}
     613
    524614void SlotVisitor::copyAndAppend(void** ptr, size_t bytes, JSValue* values, unsigned length)
    525615{
    … …  
    535625            if (!value)
    536626                continue;
    537             internalAppend(value);
     627            internalAppend(&newValues[i]);
    538628        }
    539629

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

    r121798 r121806  
    220220        MarkStackSegmentAllocator m_segmentAllocator;
    221221       
     222        bool m_shouldHashConst;
     223
    222224        Vector<ThreadIdentifier> m_markingThreads;
    223225        Vector<MarkStack*> m_markingThreadsMarkStack;
    … …  
    260262        bool isEmpty() { return m_stack.isEmpty(); }
    261263
     264        void setup();
    262265        void reset();
    263266
    … …  
    293296        void internalAppend(JSCell*);
    294297        void internalAppend(JSValue);
     298        void internalAppend(JSValue*);
    295299       
    296300        JS_EXPORT_PRIVATE void mergeOpaqueRoots();
    … …  
    325329       
    326330        MarkStackThreadSharedData& m_shared;
     331
     332        bool m_shouldHashConst; // Local per-thread copy of shared flag for performance reasons
     333        typedef HashMap<StringImpl*, JSValue> UniqueStringMap;
     334        UniqueStringMap m_uniqueStrings;
    327335
    328336#if ENABLE(OBJECT_MARK_LOGGING)
    … …  
    340348        , m_isInParallelMode(false)
    341349        , m_shared(shared)
     350        , m_shouldHashConst(false)
    342351    {
    343352    }

  • trunk/Source/JavaScriptCore/runtime/JSGlobalData.cpp

    r121798 r121806  
    171171    , m_timeoutCount(512)
    172172#endif
     173    , m_newStringsSinceLastHashConst(0)
    173174#if ENABLE(ASSEMBLER) && (ENABLE(CLASSIC_INTERPRETER) || ENABLE(LLINT))
    174175    , m_canUseAssembler(enableAssembler(executableAllocator))

  • trunk/Source/JavaScriptCore/runtime/JSGlobalData.h

    r121381 r121806  
    396396#endif
    397397
     398        unsigned m_newStringsSinceLastHashConst;
     399
     400        static const unsigned s_minNumberOfNewStringsToHashConst = 100;
     401
     402        bool haveEnoughNewStringsToHashConst() { return m_newStringsSinceLastHashConst > s_minNumberOfNewStringsToHashConst; }
     403        void resetNewStringsSinceLastHashConst() { m_newStringsSinceLastHashConst = 0; }
     404
    398405#define registerTypedArrayFunction(type, capitalizedType) \
    399406        void registerTypedArrayDescriptor(const capitalizedType##Array*, const TypedArrayDescriptor& descriptor) \

  • trunk/Source/JavaScriptCore/runtime/JSString.h

    r119633 r121806  
    6868        friend class SpecializedThunkJIT;
    6969        friend class JSRopeString;
     70        friend class MarkStack;
    7071        friend class SlotVisitor;
    7172        friend struct ThunkHelpers;
    … …  
    7879        JSString(JSGlobalData& globalData, PassRefPtr<StringImpl> value)
    7980            : JSCell(globalData, globalData.stringStructure.get())
     81            , m_flags(0)
    8082            , m_value(value)
    8183        {
    … …  
    8486        JSString(JSGlobalData& globalData)
    8587            : JSCell(globalData, globalData.stringStructure.get())
     88            , m_flags(0)
    8689        {
    8790        }
    … …  
    9295            Base::finishCreation(globalData);
    9396            m_length = length;
    94             m_is8Bit = m_value.impl()->is8Bit();
     97            setIs8Bit(m_value.impl()->is8Bit());
     98            globalData.m_newStringsSinceLastHashConst++;
    9599        }
    96100
    … …  
    100104            Base::finishCreation(globalData);
    101105            m_length = length;
    102             m_is8Bit = m_value.impl()->is8Bit();
     106            setIs8Bit(m_value.impl()->is8Bit());
    103107            Heap::heap(this)->reportExtraMemoryCost(cost);
     108            globalData.m_newStringsSinceLastHashConst++;
    104109        }
    105110
    … …  
    109114            Base::finishCreation(globalData);
    110115            m_length = 0;
    111             m_is8Bit = true;
     116            setIs8Bit(true);
     117            globalData.m_newStringsSinceLastHashConst++;
    112118        }
    113119       
    … …  
    162168    protected:
    163169        bool isRope() const { return m_value.isNull(); }
    164         bool is8Bit() const { return m_is8Bit; }
     170        bool is8Bit() const { return m_flags & Is8Bit; }
     171        void setIs8Bit(bool flag)
     172        {
     173            if (flag)
     174                m_flags |= Is8Bit;
     175            else
     176                m_flags &= ~Is8Bit;
     177        }
     178        bool shouldTryHashConst();
     179        bool isHashConstSingleton() const { return m_flags & IsHashConstSingleton; }
     180        void clearHashConstSingleton() { m_flags &= ~IsHashConstSingleton; }
     181        void setHashConstSingleton() { m_flags |= IsHashConstSingleton; }
     182        bool tryHashConstLock();
     183        void releaseHashConstLock();
     184
     185        unsigned m_flags;
     186       
     187        enum {
     188            HashConstLock = 1u << 2,
     189            IsHashConstSingleton = 1u << 1,
     190            Is8Bit = 1u
     191        };
    165192
    166193        // A string is represented either by a UString or a rope of fibers.
    167         bool m_is8Bit : 1;
    168194        unsigned m_length;
    169195        mutable UString m_value;
    … …  
    232258            Base::finishCreation(globalData);
    233259            m_length = s1->length() + s2->length();
    234             m_is8Bit = (s1->is8Bit() && s2->is8Bit());
     260            setIs8Bit(s1->is8Bit() && s2->is8Bit());
    235261            m_fibers[0].set(globalData, this, s1);
    236262            m_fibers[1].set(globalData, this, s2);
    … …  
    241267            Base::finishCreation(globalData);
    242268            m_length = s1->length() + s2->length() + s3->length();
    243             m_is8Bit = (s1->is8Bit() && s2->is8Bit() &&  s3->is8Bit());
     269            setIs8Bit(s1->is8Bit() && s2->is8Bit() &&  s3->is8Bit());
    244270            m_fibers[0].set(globalData, this, s1);
    245271            m_fibers[1].set(globalData, this, s2);
    … …  
    256282            m_fibers[index].set(globalData, this, jsString);
    257283            m_length += jsString->m_length;
    258             m_is8Bit = m_is8Bit && jsString->m_is8Bit;
     284            setIs8Bit(is8Bit() && jsString->is8Bit());
    259285        }
    260286
Note: See TracChangeset for help on using the changeset viewer.