Changeset 59161 in webkit for trunk/JavaScriptCore/runtime


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

Location:
trunk/JavaScriptCore/runtime
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/JSString.cpp

    r57912 r59161  
    7676            unsigned fiberCountMinusOne = rope->fiberCount() - 1;
    7777            for (unsigned i = 0; i < fiberCountMinusOne; ++i)
    78                 workQueue.append(rope->fibers(i));
    79             currentFiber = rope->fibers(fiberCountMinusOne);
     78                workQueue.append(rope->fibers()[i]);
     79            currentFiber = rope->fibers()[fiberCountMinusOne];
    8080        } else {
    8181            UStringImpl* string = static_cast<UStringImpl*>(currentFiber);
    … …  
    105105}
    106106
     107JSValue JSString::replaceCharacter(ExecState* exec, UChar character, const UString& replacement)
     108{
     109    if (!isRope()) {
     110        size_t matchPosition = m_value.find(character);
     111        if (matchPosition == notFound)
     112            return JSValue(this);
     113        return jsString(exec, m_value.substr(0, matchPosition), replacement, m_value.substr(matchPosition + 1));
     114    }
     115
     116    RopeIterator end;
     117   
     118    // Count total fibers and find matching string.
     119    size_t fiberCount = 0;
     120    UStringImpl* matchString = 0;
     121    size_t matchPosition = notFound;
     122    for (RopeIterator it(m_other.m_fibers, m_fiberCount); it != end; ++it) {
     123        ++fiberCount;
     124        if (matchString)
     125            continue;
     126
     127        UStringImpl* string = *it;
     128        matchPosition = string->find(character);
     129        if (matchPosition == notFound)
     130            continue;
     131        matchString = string;
     132    }
     133
     134    if (!matchString)
     135        return this;
     136
     137    RopeBuilder builder(replacement.size() ? fiberCount + 2 : fiberCount + 1);
     138    if (UNLIKELY(builder.isOutOfMemory()))
     139        return throwOutOfMemoryError(exec);
     140
     141    for (RopeIterator it(m_other.m_fibers, m_fiberCount); it != end; ++it) {
     142        UStringImpl* string = *it;
     143        if (string != matchString) {
     144            builder.append(UString(string));
     145            continue;
     146        }
     147
     148        builder.append(UString(string).substr(0, matchPosition));
     149        if (replacement.size())
     150            builder.append(replacement);
     151        builder.append(UString(string).substr(matchPosition + 1));
     152    }
     153
     154    JSGlobalData* globalData = &exec->globalData();
     155    return JSValue(new (globalData) JSString(globalData, builder.release()));
     156}
     157
    107158JSString* JSString::getIndexSlowCase(ExecState* exec, unsigned i)
    108159{

  • trunk/JavaScriptCore/runtime/JSString.h

    r58286 r59161  
    112112        };
    113113
     114        class RopeIterator {
     115            public:
     116                RopeIterator() { }
     117
     118                RopeIterator(RopeImpl::Fiber* fibers, size_t fiberCount)
     119                {
     120                    ASSERT(fiberCount);
     121                    m_workQueue.append(WorkItem(fibers, fiberCount));
     122                    skipRopes();
     123                }
     124
     125                RopeIterator& operator++()
     126                {
     127                    WorkItem& item = m_workQueue.last();
     128                    ASSERT(!RopeImpl::isRope(item.fibers[item.i]));
     129                    if (++item.i == item.fiberCount)
     130                        m_workQueue.removeLast();
     131                    skipRopes();
     132                    return *this;
     133                }
     134
     135                UStringImpl* operator*()
     136                {
     137                    WorkItem& item = m_workQueue.last();
     138                    RopeImpl::Fiber fiber = item.fibers[item.i];
     139                    ASSERT(!RopeImpl::isRope(fiber));
     140                    return static_cast<UStringImpl*>(fiber);
     141                }
     142
     143                bool operator!=(const RopeIterator& other) const
     144                {
     145                    return m_workQueue != other.m_workQueue;
     146                }
     147
     148            private:
     149                struct WorkItem {
     150                    WorkItem(RopeImpl::Fiber* fibers, size_t fiberCount)
     151                        : fibers(fibers)
     152                        , fiberCount(fiberCount)
     153                        , i(0)
     154                    {
     155                    }
     156
     157                    bool operator!=(const WorkItem& other) const
     158                    {
     159                        return fibers != other.fibers || fiberCount != other.fiberCount || i != other.i;
     160                    }
     161
     162                    RopeImpl::Fiber* fibers;
     163                    size_t fiberCount;
     164                    size_t i;
     165                };
     166
     167                void skipRopes()
     168                {
     169                    if (m_workQueue.isEmpty())
     170                        return;
     171
     172                    while (1) {
     173                        WorkItem& item = m_workQueue.last();
     174                        RopeImpl::Fiber fiber = item.fibers[item.i];
     175                        if (!RopeImpl::isRope(fiber))
     176                            break;
     177                        RopeImpl* rope = static_cast<RopeImpl*>(fiber);
     178                        if (++item.i == item.fiberCount)
     179                            m_workQueue.removeLast();
     180                        m_workQueue.append(WorkItem(rope->fibers(), rope->fiberCount()));
     181                    }
     182                }
     183
     184                Vector<WorkItem, 16> m_workQueue;
     185        };
     186
    114187        ALWAYS_INLINE JSString(JSGlobalData* globalData, const UString& value)
    115188            : JSCell(globalData->stringStructure.get())
    … …  
    131204            ASSERT(!m_value.isNull());
    132205        }
    133         JSString(JSGlobalData* globalData, PassRefPtr<UString::Rep> value, HasOtherOwnerType)
     206        JSString(JSGlobalData* globalData, PassRefPtr<UStringImpl> value, HasOtherOwnerType)
    134207            : JSCell(globalData->stringStructure.get())
    135208            , m_length(value->length())
    … …  
    201274        }
    202275
     276        // This constructor constructs a new string by concatenating u1 & u2.
     277        JSString(JSGlobalData* globalData, const UString& u1, const UString& u2)
     278            : JSCell(globalData->stringStructure.get())
     279            , m_length(u1.size() + u2.size())
     280            , m_fiberCount(2)
     281        {
     282            unsigned index = 0;
     283            appendStringInConstruct(index, u1);
     284            appendStringInConstruct(index, u2);
     285            ASSERT(index <= s_maxInternalRopeLength);
     286        }
     287
     288        // This constructor constructs a new string by concatenating u1, u2 & u3.
     289        JSString(JSGlobalData* globalData, const UString& u1, const UString& u2, const UString& u3)
     290            : JSCell(globalData->stringStructure.get())
     291            , m_length(u1.size() + u2.size() + u3.size())
     292            , m_fiberCount(s_maxInternalRopeLength)
     293        {
     294            unsigned index = 0;
     295            appendStringInConstruct(index, u1);
     296            appendStringInConstruct(index, u2);
     297            appendStringInConstruct(index, u3);
     298            ASSERT(index <= s_maxInternalRopeLength);
     299        }
     300
    203301        JSString(JSGlobalData* globalData, const UString& value, JSStringFinalizerCallback finalizer, void* context)
    204302            : JSCell(globalData->stringStructure.get())
    … …  
    246344        JSString* getIndex(ExecState*, unsigned);
    247345        JSString* getIndexSlowCase(ExecState*, unsigned);
     346
     347        JSValue replaceCharacter(ExecState*, UChar, const UString& replacement);
    248348
    249349        static PassRefPtr<Structure> createStructure(JSValue proto) { return Structure::create(proto, TypeInfo(StringType, OverridesGetOwnPropertySlot | NeedsThisConversion), AnonymousSlotCount); }
    … …  
    283383                ASSERT(asCell(v)->isString());
    284384                JSString* s = static_cast<JSString*>(asCell(v));
    285                 ASSERT(s->fiberCount() == 1);
     385                ASSERT(s->size() == 1);
    286386                appendStringInConstruct(index, s);
    287387                m_length += s->length();
    … …  
    329429        bool isRope() const { return m_fiberCount; }
    330430        UString& string() { ASSERT(!isRope()); return m_value; }
    331         unsigned fiberCount() { return m_fiberCount ? m_fiberCount : 1; }
     431        unsigned size() { return m_fiberCount ? m_fiberCount : 1; }
    332432
    333433        friend JSValue jsString(ExecState* exec, JSString* s1, JSString* s2);
    … …  
    376476        if (c <= 0xFF)
    377477            return globalData->smallStrings.singleCharacterString(globalData, c);
    378         return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, 1))));
     478        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UStringImpl::create(s.rep(), offset, 1))));
    379479    }
    380480
    … …  
    434534                return globalData->smallStrings.singleCharacterString(globalData, c);
    435535        }
    436         return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, length)), JSString::HasOtherOwner));
     536        return fixupVPtr(globalData, new (globalData) JSString(globalData, UString(UStringImpl::create(s.rep(), offset, length)), JSString::HasOtherOwner));
    437537    }
    438538

  • trunk/JavaScriptCore/runtime/Operations.h

    r54925 r59161  
    4747            return throwOutOfMemoryError(exec);
    4848
    49         unsigned fiberCount = s1->fiberCount() + s2->fiberCount();
     49        unsigned fiberCount = s1->size() + s2->size();
    5050        JSGlobalData* globalData = &exec->globalData();
    5151
    … …  
    7272            return throwOutOfMemoryError(exec);
    7373
    74         unsigned fiberCount = 1 + s2->fiberCount();
     74        unsigned fiberCount = 1 + s2->size();
    7575        JSGlobalData* globalData = &exec->globalData();
    7676
    … …  
    9797            return throwOutOfMemoryError(exec);
    9898
    99         unsigned fiberCount = s1->fiberCount() + 1;
     99        unsigned fiberCount = s1->size() + 1;
    100100        JSGlobalData* globalData = &exec->globalData();
    101101
    … …  
    109109        ropeBuilder.append(u2);
    110110        return new (globalData) JSString(globalData, ropeBuilder.release());
     111    }
     112
     113    ALWAYS_INLINE JSValue jsString(ExecState* exec, const UString& u1, const UString& u2)
     114    {
     115        unsigned length1 = u1.size();
     116        if (!length1)
     117            return jsString(exec, u2);
     118        unsigned length2 = u2.size();
     119        if (!length2)
     120            return jsString(exec, u1);
     121        if ((length1 + length2) < length1)
     122            return throwOutOfMemoryError(exec);
     123
     124        JSGlobalData* globalData = &exec->globalData();
     125        return new (globalData) JSString(globalData, u1, u2);
     126    }
     127
     128    ALWAYS_INLINE JSValue jsString(ExecState* exec, const UString& u1, const UString& u2, const UString& u3)
     129    {
     130        unsigned length1 = u1.size();
     131        unsigned length2 = u2.size();
     132        unsigned length3 = u3.size();
     133        if (!length1)
     134            return jsString(exec, u2, u3);
     135        if (!length2)
     136            return jsString(exec, u1, u3);
     137        if (!length3)
     138            return jsString(exec, u1, u2);
     139
     140        if ((length1 + length2) < length1)
     141            return throwOutOfMemoryError(exec);
     142        if ((length1 + length2 + length3) < length3)
     143            return throwOutOfMemoryError(exec);
     144
     145        JSGlobalData* globalData = &exec->globalData();
     146        return new (globalData) JSString(globalData, u1, u2, u3);
    111147    }
    112148
    … …  
    119155            JSValue v = strings[i].jsValue();
    120156            if (LIKELY(v.isString()))
    121                 fiberCount += asString(v)->fiberCount();
     157                fiberCount += asString(v)->size();
    122158            else
    123159                ++fiberCount;
    … …  
    158194        unsigned fiberCount = 0;
    159195        if (LIKELY(thisValue.isString()))
    160             fiberCount += asString(thisValue)->fiberCount();
     196            fiberCount += asString(thisValue)->size();
    161197        else
    162198            ++fiberCount;
    … …  
    164200            JSValue v = args.at(i);
    165201            if (LIKELY(v.isString()))
    166                 fiberCount += asString(v)->fiberCount();
     202                fiberCount += asString(v)->size();
    167203            else
    168204                ++fiberCount;

  • trunk/JavaScriptCore/runtime/RopeImpl.cpp

    r57912 r59161  
    3131void RopeImpl::derefFibersNonRecursive(Vector<RopeImpl*, 32>& workQueue)
    3232{
    33     unsigned length = fiberCount();
    34     for (unsigned i = 0; i < length; ++i) {
    35         Fiber& fiber = fibers(i);
     33    unsigned fiberCount = this->fiberCount();
     34    for (unsigned i = 0; i < fiberCount; ++i) {
     35        Fiber& fiber = m_fibers[i];
    3636        if (isRope(fiber)) {
    3737            RopeImpl* nextRope = static_cast<RopeImpl*>(fiber);

  • trunk/JavaScriptCore/runtime/RopeImpl.h

    r57932 r59161  
    4747    }
    4848
    49     void initializeFiber(unsigned &index, Fiber fiber)
    50     {
    51         m_fibers[index++] = fiber;
    52         fiber->ref();
    53         m_length += fiber->length();
    54     }
    55 
    56     unsigned fiberCount() { return m_fiberCount; }
    57     Fiber& fibers(unsigned index) { return m_fibers[index]; }
    58 
    59     ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & s_refCountMask)) destructNonRecursive(); }
    60 
    6149    static bool isRope(Fiber fiber)
    6250    {
    … …  
    7260    }
    7361
     62    void initializeFiber(unsigned &index, Fiber fiber)
     63    {
     64        m_fibers[index++] = fiber;
     65        fiber->ref();
     66        m_length += fiber->length();
     67    }
     68
     69    unsigned fiberCount() { return m_size; }
     70    Fiber* fibers() { return m_fibers; }
     71
     72    ALWAYS_INLINE void deref()
     73    {
     74        m_refCountAndFlags -= s_refCountIncrement;
     75        if (!(m_refCountAndFlags & s_refCountMask))
     76            destructNonRecursive();
     77    }
     78
    7479private:
    75     RopeImpl(unsigned fiberCount) : StringImplBase(ConstructNonStringImpl), m_fiberCount(fiberCount) {}
     80    RopeImpl(unsigned fiberCount)
     81        : StringImplBase(ConstructNonStringImpl)
     82        , m_size(fiberCount)
     83    {
     84    }
    7685
    7786    void destructNonRecursive();
    … …  
    8089    bool hasOneRef() { return (m_refCountAndFlags & s_refCountMask) == s_refCountIncrement; }
    8190
    82     unsigned m_fiberCount;
     91    unsigned m_size;
    8392    Fiber m_fibers[1];
    8493};

  • trunk/JavaScriptCore/runtime/StringPrototype.cpp

    r57978 r59161  
    289289}
    290290
    291 JSValue jsReplaceRange(ExecState* exec, const UString& source, int rangeStart, int rangeLength, const UString& replacement);
    292 JSValue jsReplaceRange(ExecState* exec, const UString& source, int rangeStart, int rangeLength, const UString& replacement)
    293 {
    294     int replacementLength = replacement.size();
    295     int totalLength = source.size() - rangeLength + replacementLength;
    296     if (totalLength == 0)
    297         return jsString(exec, "");
    298 
    299     UChar* buffer;
    300     PassRefPtr<UStringImpl> impl = UStringImpl::tryCreateUninitialized(totalLength, buffer);
    301     if (!impl)
    302         return throwOutOfMemoryError(exec);
    303 
    304     UStringImpl::copyChars(buffer, source.data(), rangeStart);
    305     UStringImpl::copyChars(buffer + rangeStart, replacement.data(), replacementLength);
    306     int rangeEnd = rangeStart + rangeLength;
    307     UStringImpl::copyChars(buffer + rangeStart + replacementLength, source.data() + rangeEnd, source.size() - rangeEnd);
    308 
    309     return jsString(exec, impl);
    310 }
    311 
    312291JSValue JSC_HOST_CALL stringProtoFuncReplace(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
    313292{
    314293    JSString* sourceVal = thisValue.toThisJSString(exec);
    315     const UString& source = sourceVal->value(exec);
    316 
    317294    JSValue pattern = args.at(0);
    318 
    319295    JSValue replacement = args.at(1);
     296
    320297    UString replacementString;
    321298    CallData callData;
    … …  
    325302
    326303    if (pattern.inherits(&RegExpObject::info)) {
     304        const UString& source = sourceVal->value(exec);
    327305        RegExp* reg = asRegExpObject(pattern)->regExp();
    328306        bool global = reg->global();
    … …  
    443421
    444422    UString patternString = pattern.toString(exec);
     423    if (patternString.size() == 1 && callType == CallTypeNone)
     424        return sourceVal->replaceCharacter(exec, patternString[0], replacementString);
     425   
     426    const UString& source = sourceVal->value(exec);
    445427    unsigned matchPos = source.find(patternString);
    446428
    … …  
    457439        replacementString = call(exec, replacement, callType, callData, exec->globalThisValue(), args).toString(exec);
    458440    }
    459 
    460     int ovector[2] = { matchPos, matchPos + matchLen };
    461     return jsReplaceRange(exec, source, matchPos, matchLen, substituteBackreferences(replacementString, source, ovector, 0));
     441   
     442    size_t matchEnd = matchPos + matchLen;
     443    int ovector[2] = { matchPos, matchEnd };
     444    return jsString(exec, source.substr(0, matchPos), substituteBackreferences(replacementString, source, ovector, 0), source.substr(matchEnd));
    462445}
    463446
Note: See TracChangeset for help on using the changeset viewer.