Changeset 130102 in webkit


Ignore:
Timestamp:
Oct 1, 2012, 5:14:33 PM (13 years ago)
Author:
fpizlo@apple.com
Message:

Address a FIXME in JSArray::sort
​https://bugs.webkit.org/show_bug.cgi?id=98080
<rdar://problem/12407844>

Reviewed by Oliver Hunt.

Source/JavaScriptCore:

Get rid of fast sorting of sparse maps. I don't know that it's broken but I do know that we don't
have coverage for it. Then also address the FIXME in JSArray::sort regarding side-effecting
compare functions.

  • runtime/ArrayPrototype.cpp:

(JSC::arrayProtoFuncSort):

  • runtime/JSArray.cpp:

(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::compactForSorting):

  • runtime/JSArray.h:

(JSArray):

  • runtime/JSObject.h:

(JSC::JSObject::hasSparseMap):
(JSObject):

LayoutTests:

  • fast/js/jsc-test-list:
  • fast/js/script-tests/sort-with-side-effecting-comparisons.js: Added.
  • fast/js/sort-with-side-effecting-comparisons-expected.txt: Added.
  • fast/js/sort-with-side-effecting-comparisons.html: Added.
Location:
trunk
Files:
3 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r130100 r130102  
     12012-10-01  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Address a FIXME in JSArray::sort
     4        https://bugs.webkit.org/show_bug.cgi?id=98080
     5        <rdar://problem/12407844>
     6
     7        Reviewed by Oliver Hunt.
     8
     9        * fast/js/jsc-test-list:
     10        * fast/js/script-tests/sort-with-side-effecting-comparisons.js: Added.
     11        * fast/js/sort-with-side-effecting-comparisons-expected.txt: Added.
     12        * fast/js/sort-with-side-effecting-comparisons.html: Added.
     13
    1142012-10-01  Roger Fong  <roger_fong@apple.com>
    215

  • trunk/LayoutTests/fast/js/jsc-test-list

    r129948 r130102  
    298298fast/js/sort-randomly
    299299fast/js/sort-stability
     300fast/js/sort-with-side-effecting-comparisons
    300301fast/js/sparse-array
    301302fast/js/stack-overflow-arrity-catch

  • trunk/Source/JavaScriptCore/ChangeLog

    r130014 r130102  
     12012-10-01  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Address a FIXME in JSArray::sort
     4        https://bugs.webkit.org/show_bug.cgi?id=98080
     5        <rdar://problem/12407844>
     6
     7        Reviewed by Oliver Hunt.
     8
     9        Get rid of fast sorting of sparse maps. I don't know that it's broken but I do know that we don't
     10        have coverage for it. Then also address the FIXME in JSArray::sort regarding side-effecting
     11        compare functions.
     12
     13        * runtime/ArrayPrototype.cpp:
     14        (JSC::arrayProtoFuncSort):
     15        * runtime/JSArray.cpp:
     16        (JSC::JSArray::sortNumeric):
     17        (JSC::JSArray::sort):
     18        (JSC::JSArray::compactForSorting):
     19        * runtime/JSArray.h:
     20        (JSArray):
     21        * runtime/JSObject.h:
     22        (JSC::JSObject::hasSparseMap):
     23        (JSObject):
     24
    1252012-10-01  Jonathan Liu  <net147@gmail.com>
    226

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

    r129676 r130102  
    656656    CallType callType = getCallData(function, callData);
    657657
    658     if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseIndexingMode() && !shouldUseSlowPut(thisObj->structure()->indexingType())) {
     658    if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->hasSparseMap() && !shouldUseSlowPut(thisObj->structure()->indexingType())) {
    659659        if (isNumericCompareFunction(exec, callType, callData))
    660660            asArray(thisObj)->sortNumeric(exec, function, callType, callData);

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

    r129676 r130102  
    602602       
    603603    case ArrayWithArrayStorage: {
    604         unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
     604        unsigned lengthNotIncludingUndefined = compactForSorting();
    605605        ArrayStorage* storage = m_butterfly->arrayStorage();
    606        
    607         if (storage->m_sparseMap.get()) {
    608             throwOutOfMemoryError(exec);
    609             return;
    610         }
     606
     607        ASSERT(!storage->m_sparseMap);
    611608       
    612609        if (!lengthNotIncludingUndefined)
    … …  
    647644       
    648645    case ArrayWithArrayStorage: {
    649         unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
     646        unsigned lengthNotIncludingUndefined = compactForSorting();
    650647        ArrayStorage* storage = m_butterfly->arrayStorage();
    651         if (storage->m_sparseMap.get()) {
    652             throwOutOfMemoryError(exec);
    653             return;
    654         }
     648        ASSERT(!storage->m_sparseMap);
    655649       
    656650        if (!lengthNotIncludingUndefined)
    … …  
    812806       
    813807    case ArrayWithArrayStorage: {
    814         ArrayStorage* storage = m_butterfly->arrayStorage();
    815        
    816808        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
    817809       
    818810        // The maximum tree depth is compiled in - but the caller is clearly up to no good
    819811        // if a larger array is passed.
    820         ASSERT(storage->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
    821         if (storage->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
     812        ASSERT(arrayStorage()->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
     813        if (arrayStorage()->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
    822814            return;
    823815       
    824         unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
    825         unsigned nodeCount = usedVectorLength + (storage->m_sparseMap ? storage->m_sparseMap->size() : 0);
     816        unsigned usedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
     817        ASSERT(!arrayStorage()->m_sparseMap);
     818        unsigned nodeCount = usedVectorLength;
    826819       
    827820        if (!nodeCount)
    … …  
    851844        // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
    852845        for (; numDefined < usedVectorLength; ++numDefined) {
    853             JSValue v = storage->m_vector[numDefined].get();
     846            if (numDefined > arrayStorage()->vectorLength())
     847                break;
     848            JSValue v = arrayStorage()->m_vector[numDefined].get();
    854849            if (!v || v.isUndefined())
    855850                break;
    … …  
    858853        }
    859854        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
    860             JSValue v = storage->m_vector[i].get();
     855            if (i > arrayStorage()->vectorLength())
     856                break;
     857            JSValue v = arrayStorage()->m_vector[i].get();
    861858            if (v) {
    862859                if (v.isUndefined())
    … …  
    872869        unsigned newUsedVectorLength = numDefined + numUndefined;
    873870       
    874         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
    875             newUsedVectorLength += map->size();
    876             if (newUsedVectorLength > storage->vectorLength()) {
    877                 // Check that it is possible to allocate an array large enough to hold all the entries.
    878                 if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
    879                     throwOutOfMemoryError(exec);
    880                     return;
    881                 }
    882                 storage = m_butterfly->arrayStorage();
    883             }
    884            
    885             SparseArrayValueMap::const_iterator end = map->end();
    886             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
    887                 tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
    888                 tree.insert(numDefined);
    889                 ++numDefined;
    890             }
    891            
    892             deallocateSparseIndexMap();
    893         }
    894        
    895         ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
    896        
    897         // FIXME: If the compare function changed the length of the array, the following might be
    898         // modifying the vector incorrectly.
     871        ASSERT(!arrayStorage()->m_sparseMap);
     872       
     873        // The array size may have changed.  Figure out the new bounds.
     874        unsigned newestUsedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
     875       
     876        unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
     877        unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
     878        unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
    899879       
    900880        // Copy the values back into m_storage.
    … …  
    902882        iter.start_iter_least(tree);
    903883        JSGlobalData& globalData = exec->globalData();
    904         for (unsigned i = 0; i < numDefined; ++i) {
    905             storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
     884        for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
     885            arrayStorage()->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
    906886            ++iter;
    907887        }
    908888       
    909889        // Put undefined values back in.
    910         for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
    911             storage->m_vector[i].setUndefined();
    912        
     890        for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)
     891            arrayStorage()->m_vector[i].setUndefined();
     892
    913893        // Ensure that unused values in the vector are zeroed out.
    914         for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
    915             storage->m_vector[i].clear();
    916        
    917         storage->m_numValuesInVector = newUsedVectorLength;
    918        
     894        for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)
     895            arrayStorage()->m_vector[i].clear();
     896       
     897        arrayStorage()->m_numValuesInVector = undefinedElementsThreshold;
     898
    919899        return;
    920900    }
    … …  
    983963}
    984964
    985 unsigned JSArray::compactForSorting(JSGlobalData& globalData)
     965unsigned JSArray::compactForSorting()
    986966{
    987967    ASSERT(!inSparseIndexingMode());
    … …  
    1017997        unsigned newUsedVectorLength = numDefined + numUndefined;
    1018998       
    1019         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
    1020             newUsedVectorLength += map->size();
    1021             if (newUsedVectorLength > storage->vectorLength()) {
    1022                 // Check that it is possible to allocate an array large enough to hold all the entries - if not,
    1023                 // exception is thrown by caller.
    1024                 if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
    1025                     return 0;
    1026                
    1027                 storage = m_butterfly->arrayStorage();
    1028             }
    1029            
    1030             SparseArrayValueMap::const_iterator end = map->end();
    1031             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
    1032                 storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
    1033            
    1034             deallocateSparseIndexMap();
    1035         }
     999        ASSERT(!storage->m_sparseMap);
    10361000       
    10371001        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)

  • trunk/Source/JavaScriptCore/runtime/JSArray.h

    r129676 r130102  
    104104        bool unshiftCountSlowCase(JSGlobalData&, bool, unsigned);
    105105       
    106         unsigned compactForSorting(JSGlobalData&);
     106        unsigned compactForSorting();
    107107    };
    108108

  • trunk/Source/JavaScriptCore/runtime/JSObject.h

    r129691 r130102  
    328328        }
    329329       
     330        bool hasSparseMap()
     331        {
     332            switch (structure()->indexingType()) {
     333            case ALL_BLANK_INDEXING_TYPES:
     334                return false;
     335            case ALL_ARRAY_STORAGE_INDEXING_TYPES:
     336                return m_butterfly->arrayStorage()->m_sparseMap;
     337            default:
     338                ASSERT_NOT_REACHED();
     339                return false;
     340            }
     341        }
     342       
    330343        bool inSparseIndexingMode()
    331344        {
Note: See TracChangeset for help on using the changeset viewer.