- Revision
- 121806
- Author
- msab...@apple.com
- Date
- 2012-07-03 15:57:00 -0700 (Tue, 03 Jul 2012)
Log 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):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (121805 => 121806)
--- trunk/Source/_javascript_Core/ChangeLog 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/ChangeLog 2012-07-03 22:57:00 UTC (rev 121806)
@@ -1,3 +1,66 @@
+2012-07-03 Michael Saboff <msab...@apple.com>
+
+ 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):
+
2012-07-03 Tony Chang <t...@chromium.org>
[chromium] Unreviewed, update .gitignore to handle VS2010 files.
Modified: trunk/Source/_javascript_Core/heap/Heap.cpp (121805 => 121806)
--- trunk/Source/_javascript_Core/heap/Heap.cpp 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/heap/Heap.cpp 2012-07-03 22:57:00 UTC (rev 121806)
@@ -454,6 +454,7 @@
m_storageSpace.startedCopying();
SlotVisitor& visitor = m_slotVisitor;
+ visitor.setup();
HeapRootVisitor heapRootVisitor(visitor);
{
@@ -585,12 +586,11 @@
#endif
visitor.reset();
- m_sharedData.reset();
#if ENABLE(PARALLEL_GC)
m_sharedData.resetChildren();
#endif
+ m_sharedData.reset();
m_storageSpace.doneCopying();
-
}
size_t Heap::objectCount()
Modified: trunk/Source/_javascript_Core/heap/MarkStack.cpp (121805 => 121806)
--- trunk/Source/_javascript_Core/heap/MarkStack.cpp 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/heap/MarkStack.cpp 2012-07-03 22:57:00 UTC (rev 121806)
@@ -38,6 +38,7 @@
#include "Structure.h"
#include "UString.h"
#include "WriteBarrier.h"
+#include <wtf/Atomics.h>
#include <wtf/DataLog.h>
#include <wtf/MainThread.h>
@@ -225,8 +226,8 @@
void MarkStackThreadSharedData::resetChildren()
{
for (unsigned i = 0; i < m_markingThreadsMarkStack.size(); ++i)
- m_markingThreadsMarkStack[i]->reset();
-}
+ m_markingThreadsMarkStack[i]->reset();
+}
size_t MarkStackThreadSharedData::childVisitCount()
{
@@ -257,6 +258,7 @@
MarkStackThreadSharedData::MarkStackThreadSharedData(JSGlobalData* globalData)
: m_globalData(globalData)
, m_copiedSpace(&globalData->heap.m_storageSpace)
+ , m_shouldHashConst(false)
, m_sharedMarkStack(m_segmentAllocator)
, m_numberOfActiveParallelMarkers(0)
, m_parallelMarkersShouldExit(false)
@@ -298,8 +300,23 @@
ASSERT(m_opaqueRoots.isEmpty());
#endif
m_weakReferenceHarvesters.removeAll();
+
+ if (m_shouldHashConst) {
+ m_globalData->resetNewStringsSinceLastHashConst();
+ m_shouldHashConst = false;
+ }
}
+void MarkStack::setup()
+{
+ m_shared.m_shouldHashConst = m_shared.m_globalData->haveEnoughNewStringsToHashConst();
+ m_shouldHashConst = m_shared.m_shouldHashConst;
+#if ENABLE(PARALLEL_GC)
+ for (unsigned i = 0; i < m_shared.m_markingThreadsMarkStack.size(); ++i)
+ m_shared.m_markingThreadsMarkStack[i]->m_shouldHashConst = m_shared.m_shouldHashConst;
+#endif
+}
+
void MarkStack::reset()
{
m_visitCount = 0;
@@ -309,6 +326,10 @@
#else
m_opaqueRoots.clear();
#endif
+ if (m_shouldHashConst) {
+ m_uniqueStrings.clear();
+ m_shouldHashConst = false;
+ }
}
void MarkStack::append(ConservativeRoots& conservativeRoots)
@@ -521,6 +542,75 @@
return CopiedSpace::allocateFromBlock(m_copyBlock, bytes);
}
+ALWAYS_INLINE bool JSString::tryHashConstLock()
+{
+#if ENABLE(PARALLEL_GC)
+ unsigned currentFlags = m_flags;
+ unsigned newFlags = currentFlags | HashConstLock;
+
+ if (!WTF::weakCompareAndSwap(&m_flags, currentFlags, newFlags))
+ return false;
+
+ WTF::memoryBarrierAfterLock();
+ return true;
+#else
+ if (isHashConstSingleton())
+ return false;
+
+ m_flags |= HashConstLock;
+
+ return true;
+#endif
+}
+
+ALWAYS_INLINE void JSString::releaseHashConstLock()
+{
+#if ENABLE(PARALLEL_GC)
+ WTF::memoryBarrierBeforeUnlock();
+#endif
+ m_flags &= ~HashConstLock;
+}
+
+ALWAYS_INLINE bool JSString::shouldTryHashConst()
+{
+ return ((length() > 1) && !isRope() && !isHashConstSingleton());
+}
+
+ALWAYS_INLINE void MarkStack::internalAppend(JSValue* slot)
+{
+ // This internalAppend is only intended for visits to object and array backing stores.
+ // as it can change the JSValue pointed to be the argument when the original JSValue
+ // is a string that contains the same contents as another string.
+
+ ASSERT(slot);
+ JSValue value = *slot;
+ ASSERT(value);
+ if (!value.isCell())
+ return;
+
+ JSCell* cell = value.asCell();
+
+ if (m_shouldHashConst && cell->isString()) {
+ JSString* string = jsCast<JSString*>(cell);
+ if (string->shouldTryHashConst() && string->tryHashConstLock()) {
+ UniqueStringMap::AddResult addResult = m_uniqueStrings.add(string->string().impl(), value);
+ if (addResult.isNewEntry)
+ string->setHashConstSingleton();
+ else {
+ JSValue existingJSValue = addResult.iterator->second;
+ if (value != existingJSValue)
+ jsCast<JSString*>(existingJSValue.asCell())->clearHashConstSingleton();
+ *slot = existingJSValue;
+ string->releaseHashConstLock();
+ return;
+ }
+ string->releaseHashConstLock();
+ }
+ }
+
+ internalAppend(cell);
+}
+
void SlotVisitor::copyAndAppend(void** ptr, size_t bytes, JSValue* values, unsigned length)
{
void* oldPtr = *ptr;
@@ -534,7 +624,7 @@
newValues[i] = value;
if (!value)
continue;
- internalAppend(value);
+ internalAppend(&newValues[i]);
}
memcpy(newPtr, oldPtr, jsValuesOffset);
Modified: trunk/Source/_javascript_Core/heap/MarkStack.h (121805 => 121806)
--- trunk/Source/_javascript_Core/heap/MarkStack.h 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/heap/MarkStack.h 2012-07-03 22:57:00 UTC (rev 121806)
@@ -219,6 +219,8 @@
MarkStackSegmentAllocator m_segmentAllocator;
+ bool m_shouldHashConst;
+
Vector<ThreadIdentifier> m_markingThreads;
Vector<MarkStack*> m_markingThreadsMarkStack;
@@ -259,6 +261,7 @@
MarkStackThreadSharedData& sharedData() { return m_shared; }
bool isEmpty() { return m_stack.isEmpty(); }
+ void setup();
void reset();
size_t visitCount() const { return m_visitCount; }
@@ -292,6 +295,7 @@
void internalAppend(JSCell*);
void internalAppend(JSValue);
+ void internalAppend(JSValue*);
JS_EXPORT_PRIVATE void mergeOpaqueRoots();
@@ -325,6 +329,10 @@
MarkStackThreadSharedData& m_shared;
+ bool m_shouldHashConst; // Local per-thread copy of shared flag for performance reasons
+ typedef HashMap<StringImpl*, JSValue> UniqueStringMap;
+ UniqueStringMap m_uniqueStrings;
+
#if ENABLE(OBJECT_MARK_LOGGING)
unsigned m_logChildCount;
#endif
@@ -339,6 +347,7 @@
, m_visitCount(0)
, m_isInParallelMode(false)
, m_shared(shared)
+ , m_shouldHashConst(false)
{
}
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp (121805 => 121806)
--- trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalData.cpp 2012-07-03 22:57:00 UTC (rev 121806)
@@ -170,6 +170,7 @@
#if CPU(X86) && ENABLE(JIT)
, m_timeoutCount(512)
#endif
+ , m_newStringsSinceLastHashConst(0)
#if ENABLE(ASSEMBLER) && (ENABLE(CLASSIC_INTERPRETER) || ENABLE(LLINT))
, m_canUseAssembler(enableAssembler(executableAllocator))
#endif
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalData.h (121805 => 121806)
--- trunk/Source/_javascript_Core/runtime/JSGlobalData.h 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalData.h 2012-07-03 22:57:00 UTC (rev 121806)
@@ -395,6 +395,13 @@
unsigned m_timeoutCount;
#endif
+ unsigned m_newStringsSinceLastHashConst;
+
+ static const unsigned s_minNumberOfNewStringsToHashConst = 100;
+
+ bool haveEnoughNewStringsToHashConst() { return m_newStringsSinceLastHashConst > s_minNumberOfNewStringsToHashConst; }
+ void resetNewStringsSinceLastHashConst() { m_newStringsSinceLastHashConst = 0; }
+
#define registerTypedArrayFunction(type, capitalizedType) \
void registerTypedArrayDescriptor(const capitalizedType##Array*, const TypedArrayDescriptor& descriptor) \
{ \
Modified: trunk/Source/_javascript_Core/runtime/JSString.h (121805 => 121806)
--- trunk/Source/_javascript_Core/runtime/JSString.h 2012-07-03 21:56:05 UTC (rev 121805)
+++ trunk/Source/_javascript_Core/runtime/JSString.h 2012-07-03 22:57:00 UTC (rev 121806)
@@ -67,6 +67,7 @@
friend class JSGlobalData;
friend class SpecializedThunkJIT;
friend class JSRopeString;
+ friend class MarkStack;
friend class SlotVisitor;
friend struct ThunkHelpers;
@@ -77,12 +78,14 @@
private:
JSString(JSGlobalData& globalData, PassRefPtr<StringImpl> value)
: JSCell(globalData, globalData.stringStructure.get())
+ , m_flags(0)
, m_value(value)
{
}
JSString(JSGlobalData& globalData)
: JSCell(globalData, globalData.stringStructure.get())
+ , m_flags(0)
{
}
@@ -91,7 +94,8 @@
ASSERT(!m_value.isNull());
Base::finishCreation(globalData);
m_length = length;
- m_is8Bit = m_value.impl()->is8Bit();
+ setIs8Bit(m_value.impl()->is8Bit());
+ globalData.m_newStringsSinceLastHashConst++;
}
void finishCreation(JSGlobalData& globalData, size_t length, size_t cost)
@@ -99,8 +103,9 @@
ASSERT(!m_value.isNull());
Base::finishCreation(globalData);
m_length = length;
- m_is8Bit = m_value.impl()->is8Bit();
+ setIs8Bit(m_value.impl()->is8Bit());
Heap::heap(this)->reportExtraMemoryCost(cost);
+ globalData.m_newStringsSinceLastHashConst++;
}
protected:
@@ -108,7 +113,8 @@
{
Base::finishCreation(globalData);
m_length = 0;
- m_is8Bit = true;
+ setIs8Bit(true);
+ globalData.m_newStringsSinceLastHashConst++;
}
public:
@@ -161,10 +167,30 @@
protected:
bool isRope() const { return m_value.isNull(); }
- bool is8Bit() const { return m_is8Bit; }
+ bool is8Bit() const { return m_flags & Is8Bit; }
+ void setIs8Bit(bool flag)
+ {
+ if (flag)
+ m_flags |= Is8Bit;
+ else
+ m_flags &= ~Is8Bit;
+ }
+ bool shouldTryHashConst();
+ bool isHashConstSingleton() const { return m_flags & IsHashConstSingleton; }
+ void clearHashConstSingleton() { m_flags &= ~IsHashConstSingleton; }
+ void setHashConstSingleton() { m_flags |= IsHashConstSingleton; }
+ bool tryHashConstLock();
+ void releaseHashConstLock();
+ unsigned m_flags;
+
+ enum {
+ HashConstLock = 1u << 2,
+ IsHashConstSingleton = 1u << 1,
+ Is8Bit = 1u
+ };
+
// A string is represented either by a UString or a rope of fibers.
- bool m_is8Bit : 1;
unsigned m_length;
mutable UString m_value;
@@ -231,7 +257,7 @@
{
Base::finishCreation(globalData);
m_length = s1->length() + s2->length();
- m_is8Bit = (s1->is8Bit() && s2->is8Bit());
+ setIs8Bit(s1->is8Bit() && s2->is8Bit());
m_fibers[0].set(globalData, this, s1);
m_fibers[1].set(globalData, this, s2);
}
@@ -240,7 +266,7 @@
{
Base::finishCreation(globalData);
m_length = s1->length() + s2->length() + s3->length();
- m_is8Bit = (s1->is8Bit() && s2->is8Bit() && s3->is8Bit());
+ setIs8Bit(s1->is8Bit() && s2->is8Bit() && s3->is8Bit());
m_fibers[0].set(globalData, this, s1);
m_fibers[1].set(globalData, this, s2);
m_fibers[2].set(globalData, this, s3);
@@ -255,7 +281,7 @@
{
m_fibers[index].set(globalData, this, jsString);
m_length += jsString->m_length;
- m_is8Bit = m_is8Bit && jsString->m_is8Bit;
+ setIs8Bit(is8Bit() && jsString->is8Bit());
}
static JSRopeString* createNull(JSGlobalData& globalData)
