Changeset 51671 in webkit for trunk/JavaScriptCore/runtime


Ignore:
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).

  • 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.
Location:
trunk/JavaScriptCore/runtime
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/JSString.cpp

    r49365 r51671  
    3131namespace JSC {
    3232
     33JSString::Rope::~Rope()
     34{
     35    for (unsigned i = 0; i < m_ropeLength; ++i) {
     36        Fiber& fiber = m_fibers[i];
     37        if (fiber.isRope())
     38            fiber.rope()->deref();
     39        else
     40            fiber.string()->deref();
     41    }
     42}
     43
     44#define ROPE_COPY_CHARS_INLINE_CUTOFF 20
     45
     46static inline void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
     47{
     48#ifdef ROPE_COPY_CHARS_INLINE_CUTOFF
     49    if (numCharacters <= ROPE_COPY_CHARS_INLINE_CUTOFF) {
     50        for (unsigned i = 0; i < numCharacters; ++i)
     51            destination[i] = source[i];
     52        return;
     53    }
     54#endif
     55    memcpy(destination, source, numCharacters * sizeof(UChar));
     56}
     57
     58// Overview: this methods converts a JSString from holding a string in rope form
     59// down to a simple UString representation.  It does so by building up the string
     60// backwards, since we want to avoid recursion, we expect that the tree structure
     61// representing the rope is likely imbalanced with more nodes down the left side
     62// (since appending to the string is likely more common) - and as such resolving
     63// in this fashion should minimize work queue size.  (If we built the queue forwards
     64// we would likely have to place all of the constituent UString::Reps into the
     65// Vector before performing any concatenation, but by working backwards we likely
     66// only fill the queue with the number of substrings at any given level in a
     67// rope-of-ropes.)
     68void JSString::resolveRope() const
     69{
     70    ASSERT(isRope());
     71
     72    // Allocate the buffer to hold the final string, position initially points to the end.
     73    UChar* buffer = static_cast<UChar*>(fastMalloc(m_length * sizeof(UChar)));
     74    UChar* position = buffer + m_length;
     75
     76    // Start with the current Rope.
     77    Vector<Rope::Fiber, 32> workQueue;
     78    Rope* rope = m_rope.get();
     79    while (true) {
     80        // Copy the contents of the current rope into the workQueue, with the last item in 'currentFiber'
     81        // (we will be working backwards over the rope).
     82        unsigned ropeLengthMinusOne = rope->ropeLength() - 1;
     83        for (unsigned i = 0; i < ropeLengthMinusOne; ++i)
     84            workQueue.append(rope->fibers(i));
     85        Rope::Fiber currentFiber = rope->fibers(ropeLengthMinusOne);
     86
     87        // Spin backwards over the workQueue (starting with currentFiber),
     88        // writing the strings into the buffer.
     89        while (currentFiber.isString()) {
     90            UString::Rep* string = currentFiber.string();
     91            unsigned length = string->len;
     92            position -= length;
     93            copyChars(position, string->data(), length);
     94
     95            // Was this the last item in the work queue?
     96            if (workQueue.isEmpty())
     97                goto breakOutOfTwoLoops;
     98            // No! - set the next item up to process.
     99            currentFiber = workQueue.last();
     100            workQueue.removeLast();
     101        }
     102
     103        // If we get here we fell out of the loop concatenating strings - currentFiber is a rope.
     104        // set the 'rope' variable, and continue around the loop.
     105        ASSERT(currentFiber.isRope());
     106        rope = currentFiber.rope();
     107    }
     108breakOutOfTwoLoops:
     109
     110    // Create a string from the UChar buffer, clear the rope RefPtr.
     111    ASSERT(buffer == position);
     112    m_value = UString::Rep::create(buffer, m_length, false);
     113    m_rope.clear();
     114
     115    ASSERT(!isRope());
     116}
     117
    33118JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
    34119{
    … …  
    36121}
    37122
    38 bool JSString::getPrimitiveNumber(ExecState*, double& number, JSValue& value)
    39 {
    40     value = this;
    41     number = m_value.toDouble();
     123bool JSString::getPrimitiveNumber(ExecState*, double& number, JSValue& result)
     124{
     125    result = this;
     126    number = value().toDouble();
    42127    return false;
    43128}
    … …  
    45130bool JSString::toBoolean(ExecState*) const
    46131{
    47     return !m_value.isEmpty();
     132    return m_length;
    48133}
    49134
    50135double JSString::toNumber(ExecState*) const
    51136{
    52     return m_value.toDouble();
     137    return value().toDouble();
    53138}
    54139
    55140UString JSString::toString(ExecState*) const
    56141{
    57     return m_value;
     142    return value();
    58143}
    59144
    60145UString JSString::toThisString(ExecState*) const
    61146{
    62     return m_value;
     147    return value();
    63148}
    64149
    … …  
    107192{
    108193    if (propertyName == exec->propertyNames().length) {
    109         descriptor.setDescriptor(jsNumber(exec, m_value.size()), DontEnum | DontDelete | ReadOnly);
     194        descriptor.setDescriptor(jsNumber(exec, m_length), DontEnum | DontDelete | ReadOnly);
    110195        return true;
    111196    }
    … …  
    113198    bool isStrictUInt32;
    114199    unsigned i = propertyName.toStrictUInt32(&isStrictUInt32);
    115     if (isStrictUInt32 && i < static_cast<unsigned>(m_value.size())) {
    116         descriptor.setDescriptor(jsSingleCharacterSubstring(exec, m_value, i), DontDelete | ReadOnly);
     200    if (isStrictUInt32 && i < m_length) {
     201        descriptor.setDescriptor(jsSingleCharacterSubstring(exec, value(), i), DontDelete | ReadOnly);
    117202        return true;
    118203    }

  • trunk/JavaScriptCore/runtime/JSString.h

    r49649 r51671  
    6161
    6262    class JSString : public JSCell {
     63    public:
    6364        friend class JIT;
    6465        friend struct VPtrSet;
    6566
    66     public:
     67        // A Rope is a string composed of a set of substrings.
     68        class Rope : public RefCounted<Rope> {
     69        public:
     70            // A Rope is composed from a set of smaller strings called Fibers.
     71            // Each Fiber in a rope is either UString::Rep or another Rope.
     72            class Fiber {
     73            public:
     74                Fiber() {}
     75                Fiber(UString::Rep* string) : m_value(reinterpret_cast<intptr_t>(string)) {}
     76                Fiber(Rope* rope) : m_value(reinterpret_cast<intptr_t>(rope) | 1) {}
     77
     78                bool isRope() { return m_value & 1; }
     79                Rope* rope() { return reinterpret_cast<Rope*>(m_value & ~1); }
     80                bool isString() { return !isRope(); }
     81                UString::Rep* string() { return reinterpret_cast<UString::Rep*>(m_value); }
     82
     83            private:
     84                intptr_t m_value;
     85            };
     86
     87            // Creates a Rope comprising of 'ropeLength' Fibers.
     88            // The Rope is constructed in an uninitialized state - initialize must be called for each Fiber in the Rope.
     89            static PassRefPtr<Rope> create(unsigned ropeLength) { return adoptRef(new (ropeLength) Rope(ropeLength)); }
     90
     91            ~Rope();
     92
     93            void initializeFiber(unsigned index, UString::Rep* string)
     94            {
     95                string->ref();
     96                m_fibers[index] = Fiber(string);
     97                m_stringLength += string->len;
     98            }
     99            void initializeFiber(unsigned index, Rope* rope)
     100            {
     101                rope->ref();
     102                m_fibers[index] = Fiber(rope);
     103                m_stringLength += rope->stringLength();
     104            }
     105            void initializeFiber(unsigned index, JSString* jsString)
     106            {
     107                if (jsString->isRope())
     108                    initializeFiber(index, jsString->rope());
     109                else
     110                    initializeFiber(index, jsString->string().rep());
     111            }
     112
     113            unsigned ropeLength() { return m_ropeLength; }
     114            unsigned stringLength() { return m_stringLength; }
     115            Fiber& fibers(unsigned index) { return m_fibers[index]; }
     116
     117        private:
     118            Rope(unsigned ropeLength) : m_ropeLength(ropeLength), m_stringLength(0) {}
     119            void* operator new(size_t, unsigned ropeLength) { return fastMalloc(sizeof(Rope) + (ropeLength - 1) * sizeof(UString::Rep*)); }
     120           
     121            unsigned m_ropeLength;
     122            unsigned m_stringLength;
     123            Fiber m_fibers[1];
     124        };
     125
    67126        JSString(JSGlobalData* globalData, const UString& value)
    68127            : JSCell(globalData->stringStructure.get())
     128            , m_length(value.size())
    69129            , m_value(value)
    70130        {
    … …  
    75135        JSString(JSGlobalData* globalData, const UString& value, HasOtherOwnerType)
    76136            : JSCell(globalData->stringStructure.get())
     137            , m_length(value.size())
    77138            , m_value(value)
    78139        {
    … …  
    80141        JSString(JSGlobalData* globalData, PassRefPtr<UString::Rep> value, HasOtherOwnerType)
    81142            : JSCell(globalData->stringStructure.get())
     143            , m_length(value->size())
    82144            , m_value(value)
    83145        {
    84146        }
     147        JSString(JSGlobalData* globalData, PassRefPtr<JSString::Rope> rope)
     148            : JSCell(globalData->stringStructure.get())
     149            , m_length(rope->stringLength())
     150            , m_rope(rope)
     151        {
     152        }
    85153       
    86         const UString& value() const { return m_value; }
     154        const UString& value() const
     155        {
     156            if (m_rope)
     157                resolveRope();
     158            return m_value;
     159        }
     160        unsigned length() { return m_length; }
     161
     162        bool isRope() const { return m_rope; }
     163        Rope* rope() { ASSERT(isRope()); return m_rope.get(); }
     164        UString& string() { ASSERT(!isRope()); return m_value; }
    87165
    88166        bool getStringPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
    … …  
    90168        bool getStringPropertyDescriptor(ExecState*, const Identifier& propertyName, PropertyDescriptor&);
    91169
    92         bool canGetIndex(unsigned i) { return i < static_cast<unsigned>(m_value.size()); }
     170        bool canGetIndex(unsigned i) { return i < m_length; }
    93171        JSString* getIndex(JSGlobalData*, unsigned);
    94172
    … …  
    101179        {
    102180        }
     181
     182        void resolveRope() const;
    103183
    104184        virtual JSValue toPrimitive(ExecState*, PreferredPrimitiveType) const;
    … …  
    118198        virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
    119199
    120         UString m_value;
     200        // A string is represented either by a UString or a Rope.
     201        unsigned m_length;
     202        mutable UString m_value;
     203        mutable RefPtr<Rope> m_rope;
    121204    };
    122205
    … …  
    147230        if (c <= 0xFF)
    148231            return globalData->smallStrings.singleCharacterString(globalData, c);
    149         return new (globalData) JSString(globalData, UString::Rep::create(s.rep(), offset, 1));
     232        return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, 1)));
    150233    }
    151234
    … …  
    167250    {
    168251        ASSERT(canGetIndex(i));
    169         return jsSingleCharacterSubstring(globalData, m_value, i);
     252        return jsSingleCharacterSubstring(globalData, value(), i);
    170253    }
    171254
    … …  
    195278                return globalData->smallStrings.singleCharacterString(globalData, c);
    196279        }
    197         return new (globalData) JSString(globalData, UString::Rep::create(s.rep(), offset, length));
     280        return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, length)));
    198281    }
    199282
    … …  
    223306    {
    224307        if (propertyName == exec->propertyNames().length) {
    225             slot.setValue(jsNumber(exec, m_value.size()));
     308            slot.setValue(jsNumber(exec, m_length));
    226309            return true;
    227310        }
    … …  
    229312        bool isStrictUInt32;
    230313        unsigned i = propertyName.toStrictUInt32(&isStrictUInt32);
    231         if (isStrictUInt32 && i < static_cast<unsigned>(m_value.size())) {
    232             slot.setValue(jsSingleCharacterSubstring(exec, m_value, i));
     314        if (isStrictUInt32 && i < m_length) {
     315            slot.setValue(jsSingleCharacterSubstring(exec, value(), i));
    233316            return true;
    234317        }
    … …  
    239322    ALWAYS_INLINE bool JSString::getStringPropertySlot(ExecState* exec, unsigned propertyName, PropertySlot& slot)
    240323    {
    241         if (propertyName < static_cast<unsigned>(m_value.size())) {
    242             slot.setValue(jsSingleCharacterSubstring(exec, m_value, propertyName));
     324        if (propertyName < m_length) {
     325            slot.setValue(jsSingleCharacterSubstring(exec, value(), propertyName));
    243326            return true;
    244327        }

  • trunk/JavaScriptCore/runtime/Operations.h

    r50704 r51671  
    205205        bool leftIsString = v1.isString();
    206206        if (leftIsString && v2.isString()) {
     207            if (asString(v1)->isRope() || asString(v2)->isRope()) {
     208                RefPtr<JSString::Rope> rope = JSString::Rope::create(2);
     209                rope->initializeFiber(0, asString(v1));
     210                rope->initializeFiber(1, asString(v2));
     211                JSGlobalData* globalData = &callFrame->globalData();
     212                return new (globalData) JSString(globalData, rope.release());
     213            }
     214
    207215            RefPtr<UString::Rep> value = concatenate(asString(v1)->value().rep(), asString(v2)->value().rep());
    208216            if (!value)
    … …  
    299307        ASSERT(count >= 3);
    300308
    301         // Estimate the amount of space required to hold the entire string.  If all
    302         // arguments are strings, we can easily calculate the exact amount of space
    303         // required.  For any other arguments, for now let's assume they may require
    304         // 11 UChars of storage.  This is enouch to hold any int, and likely is also
    305         // reasonable for the other immediates.  We may want to come back and tune
    306         // this value at some point.
    307         unsigned bufferSize = 0;
     309        RefPtr<JSString::Rope> rope = JSString::Rope::create(count);
     310
    308311        for (unsigned i = 0; i < count; ++i) {
    309312            JSValue v = strings[i].jsValue();
    310313            if (LIKELY(v.isString()))
    311                 bufferSize += asString(v)->value().size();
     314                rope->initializeFiber(i, asString(v));
    312315            else
    313                 bufferSize += 11;
    314         }
    315 
    316         // Allocate an output string to store the result.
    317         // If the first argument is a String, and if it has the capacity (or can grow
    318         // its capacity) to hold the entire result then use this as a base to concatenate
    319         // onto.  Otherwise, allocate a new empty output buffer.
    320         JSValue firstValue = strings[0].jsValue();
    321         RefPtr<UString::Rep> resultRep;
    322         if (firstValue.isString() && (resultRep = asString(firstValue)->value().rep())->reserveCapacity(bufferSize)) {
    323             // We're going to concatenate onto the first string - remove it from the list of items to be appended.
    324             ++strings;
    325             --count;
    326         } else
    327             resultRep = UString::Rep::createEmptyBuffer(bufferSize);
    328         UString result(resultRep);
    329 
    330         // Loop over the operands, writing them into the output buffer.
    331         for (unsigned i = 0; i < count; ++i) {
    332             JSValue v = strings[i].jsValue();
    333             if (LIKELY(v.isString()))
    334                 result.append(asString(v)->value());
    335             else
    336                 result.append(v.toString(callFrame));
    337         }
    338 
    339         return jsString(callFrame, result);
    340     }
    341 
     316                rope->initializeFiber(i, v.toString(callFrame).rep());
     317        }
     318
     319        JSGlobalData* globalData = &callFrame->globalData();
     320        return new (globalData) JSString(globalData, rope.release());
     321    }
    342322} // namespace JSC
    343323

  • trunk/JavaScriptCore/runtime/StringObject.cpp

    r48836 r51671  
    8585void StringObject::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
    8686{
    87     int size = internalValue()->value().size();
     87    int size = internalValue()->length();
    8888    for (int i = 0; i < size; ++i)
    8989        propertyNames.add(Identifier(exec, UString::from(i)));
Note: See TracChangeset for help on using the changeset viewer.