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

Timestamp:

May 11, 2010, 11:42:46 AM (15 years ago)

Author:

[email protected]

Message:

Start using ropes in String.prototype.replace.

Reviewed by Oliver Hunt and Darin Adler.

1%-1.5% speedup on SunSpider.

• runtime/JSString.cpp:

(JSC::JSString::resolveRope): Updated for RopeImpl refactoring.

(JSC::JSString::replaceCharacter): Added a replaceCharacter function, which creates
a rope for the resulting replacement.

• runtime/JSString.h: A few changes here:

(JSC::):
(JSC::RopeBuilder::RopeIterator::RopeIterator):
(JSC::RopeBuilder::RopeIterator::operator++):
(JSC::RopeBuilder::RopeIterator::operator*):
(JSC::RopeBuilder::RopeIterator::operator!=):
(JSC::RopeBuilder::RopeIterator::WorkItem::WorkItem):
(JSC::RopeBuilder::RopeIterator::WorkItem::operator!=):
(JSC::RopeBuilder::RopeIterator::skipRopes): Created a RopeIterator abstraction.
We use this to do a substring find without having to resolve the rope.
(We could use this iterator when resolving ropes, too, but resolving
ropes backwards is usually more efficient.)

(JSC::RopeBuilder::JSString): Added constructors for 2 & 3 UStrings.

(JSC::RopeBuilder::appendValueInConstructAndIncrementLength):
(JSC::RopeBuilder::size): Updated for RopeImpl refactoring.

• runtime/Operations.h: Updated for RopeImpl refactoring.

(JSC::jsString): Added jsString functions for 2 & 3 UStrings.

• runtime/RopeImpl.cpp:

(JSC::RopeImpl::derefFibersNonRecursive):

• runtime/RopeImpl.h:

(JSC::RopeImpl::initializeFiber):
(JSC::RopeImpl::size):
(JSC::RopeImpl::fibers):
(JSC::RopeImpl::deref):
(JSC::RopeImpl::RopeImpl): A little refactoring to make this patch easier:
Moved statics to the top of the class; put multi-statement functions on
multiple lines; renamed "fiberCount" to "size" to match other collections;
changed the "fibers" accessor to return the fibers buffer, instead of an
item in the buffer, to make iteration easier.

• runtime/StringPrototype.cpp:

(JSC::stringProtoFuncReplace): Don't resolve a rope unless we need to. Do
use our new replaceCharacter function if possible. Do use a rope to
represent splicing three strings together.

File:

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

trunk/JavaScriptCore/runtime/JSString.h

@@ -112 +112 @@
         };
 
+        class RopeIterator {
+            public:
+                RopeIterator() { }
+
+                RopeIterator(RopeImpl::Fiber* fibers, size_t fiberCount)
+                {
+                    ASSERT(fiberCount);
+                    m_workQueue.append(WorkItem(fibers, fiberCount));
+                    skipRopes();
+                }
+
+                RopeIterator& operator++()
+                {
+                    WorkItem& item = m_workQueue.last();
+                    ASSERT(!RopeImpl::isRope(item.fibers[item.i]));
+                    if (++item.i == item.fiberCount)
+                        m_workQueue.removeLast();
+                    skipRopes();
+                    return *this;
+                }
+
+                UStringImpl* operator*()
+                {
+                    WorkItem& item = m_workQueue.last();
+                    RopeImpl::Fiber fiber = item.fibers[item.i];
+                    ASSERT(!RopeImpl::isRope(fiber));
+                    return static_cast<UStringImpl*>(fiber);
+                }
+
+                bool operator!=(const RopeIterator& other) const
+                {
+                    return m_workQueue != other.m_workQueue;
+                }
+
+            private:
+                struct WorkItem {
+                    WorkItem(RopeImpl::Fiber* fibers, size_t fiberCount)
+                        : fibers(fibers)
+                        , fiberCount(fiberCount)
+                        , i(0)
+                    {
+                    }
+
+                    bool operator!=(const WorkItem& other) const
+                    {
+                        return fibers != other.fibers || fiberCount != other.fiberCount || i != other.i;
+                    }
+
+                    RopeImpl::Fiber* fibers;
+                    size_t fiberCount;
+                    size_t i;
+                };
+
+                void skipRopes()
+                {
+                    if (m_workQueue.isEmpty())
+                        return;
+
+                    while (1) {
+                        WorkItem& item = m_workQueue.last();
+                        RopeImpl::Fiber fiber = item.fibers[item.i];
+                        if (!RopeImpl::isRope(fiber))
+                            break;
+                        RopeImpl* rope = static_cast<RopeImpl*>(fiber);
+                        if (++item.i == item.fiberCount)
+                            m_workQueue.removeLast();
+                        m_workQueue.append(WorkItem(rope->fibers(), rope->fiberCount()));
+                    }
+                }
+
+                Vector<WorkItem, 16> m_workQueue;
+        };
+
         ALWAYS_INLINE JSString(JSGlobalData* globalData, const UString& value)
             : JSCell(globalData->stringStructure.get())
@@ -131 +204 @@
             ASSERT(!m_value.isNull());
         }
-        JSString(JSGlobalData* globalData, PassRefPtr<UString::Rep> value, HasOtherOwnerType)
+        JSString(JSGlobalData* globalData, PassRefPtr<UStringImpl> value, HasOtherOwnerType)
             : JSCell(globalData->stringStructure.get())
             , m_length(value->length())
@@ -201 +274 @@
         }
 
+        // This constructor constructs a new string by concatenating u1 & u2.
+        JSString(JSGlobalData* globalData, const UString& u1, const UString& u2)
+            : JSCell(globalData->stringStructure.get())
+            , m_length(u1.size() + u2.size())
+            , m_fiberCount(2)
+        {
+            unsigned index = 0;
+            appendStringInConstruct(index, u1);
+            appendStringInConstruct(index, u2);
+            ASSERT(index <= s_maxInternalRopeLength);
+        }
+
+        // This constructor constructs a new string by concatenating u1, u2 & u3.
+        JSString(JSGlobalData* globalData, const UString& u1, const UString& u2, const UString& u3)
+            : JSCell(globalData->stringStructure.get())
+            , m_length(u1.size() + u2.size() + u3.size())
+            , m_fiberCount(s_maxInternalRopeLength)
+        {
+            unsigned index = 0;
+            appendStringInConstruct(index, u1);
+            appendStringInConstruct(index, u2);
+            appendStringInConstruct(index, u3);
+            ASSERT(index <= s_maxInternalRopeLength);
+        }
+
         JSString(JSGlobalData* globalData, const UString& value, JSStringFinalizerCallback finalizer, void* context)
             : JSCell(globalData->stringStructure.get())
@@ -246 +344 @@
         JSString* getIndex(ExecState*, unsigned);
         JSString* getIndexSlowCase(ExecState*, unsigned);
+
+        JSValue replaceCharacter(ExecState*, UChar, const UString& replacement);
 
         static PassRefPtr<Structure> createStructure(JSValue proto) { return Structure::create(proto, TypeInfo(StringType, OverridesGetOwnPropertySlot | NeedsThisConversion), AnonymousSlotCount); }
@@ -283 +383 @@
                 ASSERT(asCell(v)->isString());
                 JSString* s = static_cast<JSString*>(asCell(v));
-                ASSERT(s->fiberCount() == 1);
+                ASSERT(s->size() == 1);
                 appendStringInConstruct(index, s);
                 m_length += s->length();
@@ -329 +429 @@
         bool isRope() const { return m_fiberCount; }
         UString& string() { ASSERT(!isRope()); return m_value; }
-        unsigned fiberCount() { return m_fiberCount ? m_fiberCount : 1; }
+        unsigned size() { return m_fiberCount ? m_fiberCount : 1; }
 
         friend JSValue jsString(ExecState* exec, JSString* s1, JSString* s2);
@@ -376 +476 @@
         if (c <= 0xFF)
             return globalData->smallStrings.singleCharacterString(globalData, c);
-        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, 1))));
+        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UStringImpl::create(s.rep(), offset, 1))));
     }
 
@@ -434 +534 @@
                 return globalData->smallStrings.singleCharacterString(globalData, c);
         }
-        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, length)), JSString::HasOtherOwner));
+        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UStringImpl::create(s.rep(), offset, length)), JSString::HasOtherOwner));
     }