Changeset 51671 in webkit for trunk/JavaScriptCore/runtime/JSString.h

Timestamp:

Dec 3, 2009, 6:15:18 PM (15 years ago)

Author:

[email protected]

Message:

​https://bugs.webkit.org/show_bug.cgi?id=32136
Add a rope representation to JSString. Presently JSString always holds its data in UString form.
Instead, allow the result of a string concatenation to be represented in a tree form - with a
variable sized, reference-counted rope node retaining a set of UString::Reps (or other rope nopes).

Reviewed by Oliver "Brraaaaiiiinnnnnzzzzzzzz" Hunt.

Strings must still currently be resolved down to a flat UString representation before being used,
but by holding the string in a rope representation during construction we can avoid copying data
until we know the final size of the string.

~2% progression on SunSpider (~25% on date-format-xparb, ~20% on string-validate-input).

• JavaScriptCore.exp:

• Update exports.

• interpreter/Interpreter.cpp:

(JSC::Interpreter::privateExecute):

• Make use of new JSString::length() method to avoid prematurely resolving ropes.

• jit/JITOpcodes.cpp:

(JSC::JIT::privateCompileCTIMachineTrampolines):

• Switch the string length trampoline to read the length directly from JSString::m_length, rather than from the JSString's UString::Rep's 'len' property.

• jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

• Modify op_add such that addition of two strings, where either or both strings are already in rope representation, produces a rope as a result.

• runtime/JSString.cpp:

(JSC::JSString::Rope::~Rope):
(JSC::copyChars):
(JSC::JSString::resolveRope):
(JSC::JSString::getPrimitiveNumber):
(JSC::JSString::toBoolean):
(JSC::JSString::toNumber):
(JSC::JSString::toString):
(JSC::JSString::toThisString):
(JSC::JSString::getStringPropertyDescriptor):

• runtime/JSString.h:

(JSC::JSString::Rope::Fiber::Fiber):
(JSC::JSString::Rope::Fiber::destroy):
(JSC::JSString::Rope::Fiber::isRope):
(JSC::JSString::Rope::Fiber::rope):
(JSC::JSString::Rope::Fiber::string):
(JSC::JSString::Rope::create):
(JSC::JSString::Rope::initializeFiber):
(JSC::JSString::Rope::ropeLength):
(JSC::JSString::Rope::stringLength):
(JSC::JSString::Rope::fibers):
(JSC::JSString::Rope::Rope):
(JSC::JSString::Rope::operator new):
(JSC::JSString::JSString):
(JSC::JSString::value):
(JSC::JSString::length):
(JSC::JSString::isRope):
(JSC::JSString::rope):
(JSC::JSString::string):
(JSC::JSString::canGetIndex):
(JSC::jsSingleCharacterSubstring):
(JSC::JSString::getIndex):
(JSC::jsSubstring):
(JSC::JSString::getStringPropertySlot):

• Add rope form.

• runtime/Operations.h:

(JSC::jsAdd):
(JSC::concatenateStrings):

• Update string concatenation, and addition of ropes, to produce ropes.

• runtime/StringObject.cpp:

(JSC::StringObject::getOwnPropertyNames):

• Make use of new JSString::length() method to avoid prematurely resolving ropes.

File:

• trunk/JavaScriptCore/runtime/JSString.h (modified) (12 diffs)

trunk/JavaScriptCore/runtime/JSString.h

@@ -61 +61 @@
 
     class JSString : public JSCell {
+    public:
         friend class JIT;
         friend struct VPtrSet;
 
-    public:
+        // A Rope is a string composed of a set of substrings.
+        class Rope : public RefCounted<Rope> {
+        public:
+            // A Rope is composed from a set of smaller strings called Fibers.
+            // Each Fiber in a rope is either UString::Rep or another Rope.
+            class Fiber {
+            public:
+                Fiber() {}
+                Fiber(UString::Rep* string) : m_value(reinterpret_cast<intptr_t>(string)) {}
+                Fiber(Rope* rope) : m_value(reinterpret_cast<intptr_t>(rope) | 1) {}
+
+                bool isRope() { return m_value & 1; }
+                Rope* rope() { return reinterpret_cast<Rope*>(m_value & ~1); }
+                bool isString() { return !isRope(); }
+                UString::Rep* string() { return reinterpret_cast<UString::Rep*>(m_value); }
+
+            private:
+                intptr_t m_value;
+            };
+
+            // Creates a Rope comprising of 'ropeLength' Fibers.
+            // The Rope is constructed in an uninitialized state - initialize must be called for each Fiber in the Rope.
+            static PassRefPtr<Rope> create(unsigned ropeLength) { return adoptRef(new (ropeLength) Rope(ropeLength)); }
+
+            ~Rope();
+
+            void initializeFiber(unsigned index, UString::Rep* string)
+            {
+                string->ref();
+                m_fibers[index] = Fiber(string);
+                m_stringLength += string->len;
+            }
+            void initializeFiber(unsigned index, Rope* rope)
+            {
+                rope->ref();
+                m_fibers[index] = Fiber(rope);
+                m_stringLength += rope->stringLength();
+            }
+            void initializeFiber(unsigned index, JSString* jsString)
+            {
+                if (jsString->isRope())
+                    initializeFiber(index, jsString->rope());
+                else
+                    initializeFiber(index, jsString->string().rep());
+            }
+
+            unsigned ropeLength() { return m_ropeLength; }
+            unsigned stringLength() { return m_stringLength; }
+            Fiber& fibers(unsigned index) { return m_fibers[index]; }
+
+        private:
+            Rope(unsigned ropeLength) : m_ropeLength(ropeLength), m_stringLength(0) {}
+            void* operator new(size_t, unsigned ropeLength) { return fastMalloc(sizeof(Rope) + (ropeLength - 1) * sizeof(UString::Rep*)); }
+            
+            unsigned m_ropeLength;
+            unsigned m_stringLength;
+            Fiber m_fibers[1];
+        };
+
         JSString(JSGlobalData* globalData, const UString& value)
             : JSCell(globalData->stringStructure.get())
+            , m_length(value.size())
             , m_value(value)
         {
@@ -75 +135 @@
         JSString(JSGlobalData* globalData, const UString& value, HasOtherOwnerType)
             : JSCell(globalData->stringStructure.get())
+            , m_length(value.size())
             , m_value(value)
         {
@@ -80 +141 @@
         JSString(JSGlobalData* globalData, PassRefPtr<UString::Rep> value, HasOtherOwnerType)
             : JSCell(globalData->stringStructure.get())
+            , m_length(value->size())
             , m_value(value)
         {
         }
+        JSString(JSGlobalData* globalData, PassRefPtr<JSString::Rope> rope)
+            : JSCell(globalData->stringStructure.get())
+            , m_length(rope->stringLength())
+            , m_rope(rope)
+        {
+        }
         
-        const UString& value() const { return m_value; }
+        const UString& value() const
+        {
+            if (m_rope)
+                resolveRope();
+            return m_value;
+        }
+        unsigned length() { return m_length; }
+
+        bool isRope() const { return m_rope; }
+        Rope* rope() { ASSERT(isRope()); return m_rope.get(); }
+        UString& string() { ASSERT(!isRope()); return m_value; }
 
         bool getStringPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
@@ -90 +168 @@
         bool getStringPropertyDescriptor(ExecState*, const Identifier& propertyName, PropertyDescriptor&);
 
-        bool canGetIndex(unsigned i) { return i < static_cast<unsigned>(m_value.size()); }
+        bool canGetIndex(unsigned i) { return i < m_length; }
         JSString* getIndex(JSGlobalData*, unsigned);
 
@@ -101 +179 @@
         {
         }
+
+        void resolveRope() const;
 
         virtual JSValue toPrimitive(ExecState*, PreferredPrimitiveType) const;
@@ -118 +198 @@
         virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
 
-        UString m_value;
+        // A string is represented either by a UString or a Rope.
+        unsigned m_length;
+        mutable UString m_value;
+        mutable RefPtr<Rope> m_rope;
     };
 
@@ -147 +230 @@
         if (c <= 0xFF)
             return globalData->smallStrings.singleCharacterString(globalData, c);
-        return new (globalData) JSString(globalData, UString::Rep::create(s.rep(), offset, 1));
+        return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, 1)));
     }
 
@@ -167 +250 @@
     {
         ASSERT(canGetIndex(i));
-        return jsSingleCharacterSubstring(globalData, m_value, i);
+        return jsSingleCharacterSubstring(globalData, value(), i);
     }
 
@@ -195 +278 @@
                 return globalData->smallStrings.singleCharacterString(globalData, c);
         }
-        return new (globalData) JSString(globalData, UString::Rep::create(s.rep(), offset, length));
+        return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, length)));
     }
 
@@ -223 +306 @@
     {
         if (propertyName == exec->propertyNames().length) {
-            slot.setValue(jsNumber(exec, m_value.size()));
+            slot.setValue(jsNumber(exec, m_length));
             return true;
         }
@@ -229 +312 @@
         bool isStrictUInt32;
         unsigned i = propertyName.toStrictUInt32(&isStrictUInt32);
-        if (isStrictUInt32 && i < static_cast<unsigned>(m_value.size())) {
-            slot.setValue(jsSingleCharacterSubstring(exec, m_value, i));
+        if (isStrictUInt32 && i < m_length) {
+            slot.setValue(jsSingleCharacterSubstring(exec, value(), i));
             return true;
         }
@@ -239 +322 @@
     ALWAYS_INLINE bool JSString::getStringPropertySlot(ExecState* exec, unsigned propertyName, PropertySlot& slot)
     {
-        if (propertyName < static_cast<unsigned>(m_value.size())) {
-            slot.setValue(jsSingleCharacterSubstring(exec, m_value, propertyName));
+        if (propertyName < m_length) {
+            slot.setValue(jsSingleCharacterSubstring(exec, value(), propertyName));
             return true;
         }