Ignore:
Timestamp:
May 4, 2014, 9:54:19 PM (11 years ago)
Author:
[email protected]
Message:

jsSubstring() should be lazy
​https://bugs.webkit.org/show_bug.cgi?id=132556

Reviewed by Andreas Kling.

Source/JavaScriptCore:
jsSubstring() is now lazy by using a special rope that is a substring instead of a
concatenation. To make this patch super simple, we require that a substring's base is
never a rope. Hence, when resolving a rope, we either go down a non-recursive substring
path, or we go down a concatenation path which may see exactly one level of substrings in
its fibers.

This is up to a 50% speed-up on microbenchmarks and a 10% speed-up on Octane/regexp.

  • heap/MarkedBlock.cpp:

(JSC::MarkedBlock::specializedSweep):

  • runtime/JSString.cpp:

(JSC::JSRopeString::visitFibers):
(JSC::JSRopeString::resolveRope):
(JSC::JSRopeString::resolveRopeSlowCase8):
(JSC::JSRopeString::resolveRopeSlowCase):
(JSC::JSRopeString::outOfMemory):

  • runtime/JSString.h:

(JSC::JSRopeString::finishCreation):
(JSC::JSRopeString::append):
(JSC::JSRopeString::create):
(JSC::JSRopeString::offsetOfFibers):
(JSC::JSRopeString::fiber):
(JSC::JSRopeString::substringBase):
(JSC::JSRopeString::substringOffset):
(JSC::JSRopeString::substringSentinel):
(JSC::JSRopeString::isSubstring):
(JSC::jsSubstring):

  • runtime/RegExpMatchesArray.cpp:

(JSC::RegExpMatchesArray::reifyAllProperties):

  • runtime/StringPrototype.cpp:

(JSC::stringProtoFuncSubstring):

LayoutTests:
These tests get 35-50% faster.

  • js/regress/script-tests/substring-concat-weird.js: Added.

(foo):

  • js/regress/script-tests/substring-concat.js: Added.

(foo):

  • js/regress/script-tests/substring.js: Added.

(foo):

  • js/regress/substring-concat-expected.txt: Added.
  • js/regress/substring-concat-weird-expected.txt: Added.
  • js/regress/substring-concat-weird.html: Added.
  • js/regress/substring-concat.html: Added.
  • js/regress/substring-expected.txt: Added.
  • js/regress/substring.html: Added.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/runtime/JSString.cpp

    r167336 r168254  
    8383void JSRopeString::visitFibers(SlotVisitor& visitor)
    8484{
    85     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
    86         visitor.append(&m_fibers[i]);
     85    if (isSubstring()) {
     86        visitor.append(&substringBase());
     87        return;
     88    }
     89    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
     90        visitor.append(&fiber(i));
    8791}
    8892
    … …  
    9094{
    9195    ASSERT(isRope());
    92 
     96   
     97    if (isSubstring()) {
     98        ASSERT(!substringBase()->isRope());
     99        m_value = substringBase()->m_value.substring(substringOffset(), m_length);
     100        substringBase().clear();
     101        return;
     102    }
     103   
    93104    if (is8Bit()) {
    94105        LChar* buffer;
    … …  
    100111            return;
    101112        }
    102 
    103         for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
    104             if (m_fibers[i]->isRope())
     113       
     114        for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
     115            if (fiber(i)->isRope())
    105116                return resolveRopeSlowCase8(buffer);
    106117        }
    107118
    108119        LChar* position = buffer;
    109         for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
    110             StringImpl* string = m_fibers[i]->m_value.impl();
     120        for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
     121            StringImpl* string = fiber(i)->m_value.impl();
    111122            unsigned length = string->length();
    112123            StringImpl::copyChars(position, string->characters8(), length);
    113124            position += length;
    114             m_fibers[i].clear();
     125            fiber(i).clear();
    115126        }
    116127        ASSERT((buffer + m_length) == position);
    … …  
    129140    }
    130141
    131     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
    132         if (m_fibers[i]->isRope())
     142    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
     143        if (fiber(i)->isRope())
    133144            return resolveRopeSlowCase(buffer);
    134145    }
    135146
    136147    UChar* position = buffer;
    137     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
    138         StringImpl* string = m_fibers[i]->m_value.impl();
     148    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
     149        StringImpl* string = fiber(i)->m_value.impl();
    139150        unsigned length = string->length();
    140151        if (string->is8Bit())
    … …  
    143154            StringImpl::copyChars(position, string->characters16(), length);
    144155        position += length;
    145         m_fibers[i].clear();
     156        fiber(i).clear();
    146157    }
    147158    ASSERT((buffer + m_length) == position);
    … …  
    164175    Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // Putting strings into a Vector is only OK because there are no GC points in this method.
    165176   
    166     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
    167         workQueue.append(m_fibers[i].get());
     177    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
     178        workQueue.append(fiber(i).get());
    168179        // Clearing here works only because there are no GC points in this method.
    169         m_fibers[i].clear();
     180        fiber(i).clear();
    170181    }
    171182
    … …  
    173184        JSString* currentFiber = workQueue.last();
    174185        workQueue.removeLast();
    175 
     186       
     187        const LChar* characters;
     188       
    176189        if (currentFiber->isRope()) {
    177190            JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
    178             for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->m_fibers[i]; ++i)
    179                 workQueue.append(currentFiberAsRope->m_fibers[i].get());
    180             continue;
    181         }
    182 
    183         StringImpl* string = static_cast<StringImpl*>(currentFiber->m_value.impl());
    184         unsigned length = string->length();
     191            if (!currentFiberAsRope->isSubstring()) {
     192                for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
     193                    workQueue.append(currentFiberAsRope->fiber(i).get());
     194                continue;
     195            }
     196            ASSERT(!currentFiberAsRope->substringBase()->isRope());
     197            characters =
     198                currentFiberAsRope->substringBase()->m_value.characters8() +
     199                currentFiberAsRope->substringOffset();
     200        } else
     201            characters = currentFiber->m_value.characters8();
     202
     203        unsigned length = currentFiber->length();
    185204        position -= length;
    186         StringImpl::copyChars(position, string->characters8(), length);
     205        StringImpl::copyChars(position, characters, length);
    187206    }
    188207
    … …  
    196215    Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
    197216
    198     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
    199         workQueue.append(m_fibers[i].get());
     217    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
     218        workQueue.append(fiber(i).get());
    200219
    201220    while (!workQueue.isEmpty()) {
    … …  
    205224        if (currentFiber->isRope()) {
    206225            JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
    207             for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->m_fibers[i]; ++i)
    208                 workQueue.append(currentFiberAsRope->m_fibers[i].get());
     226            if (currentFiberAsRope->isSubstring()) {
     227                ASSERT(!currentFiberAsRope->substringBase()->isRope());
     228                StringImpl* string = static_cast<StringImpl*>(
     229                    currentFiberAsRope->substringBase()->m_value.impl());
     230                unsigned offset = currentFiberAsRope->substringOffset();
     231                unsigned length = currentFiberAsRope->length();
     232                position -= length;
     233                if (string->is8Bit())
     234                    StringImpl::copyChars(position, string->characters8() + offset, length);
     235                else
     236                    StringImpl::copyChars(position, string->characters16() + offset, length);
     237                continue;
     238            }
     239            for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
     240                workQueue.append(currentFiberAsRope->fiber(i).get());
    209241            continue;
    210242        }
    … …  
    225257void JSRopeString::outOfMemory(ExecState* exec) const
    226258{
    227     for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
    228         m_fibers[i].clear();
     259    for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
     260        u[i].string.clear();
    229261    ASSERT(isRope());
    230262    ASSERT(m_value.isNull());
Note: See TracChangeset for help on using the changeset viewer.