⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 100239 in webkit


Ignore:
Timestamp:
Nov 14, 2011, 10:14:31 PM (15 years ago)
Author:
dslomov@google.com
Message:

Source/WebCore: [V8][Chromium]Serialize dense arrays densly
​https://bugs.webkit.org/show_bug.cgi?id=72198
This patch ensures that:

  • Dense arrays are serialized densly, and not as name-value pairs
  • Sparse arrays are allocated as sparse on deserialization.

The criteria to choose whether to serialize densly or sparsely is the size
of a resulting serialized stream.

Reviewed by David Levin.

Test: fast/dom/Window/window-postmessage-arrays.html

  • bindings/v8/SerializedScriptValue.cpp:

(WebCore::V8ObjectMap::Writer::writeDenseArray):
(WebCore::V8ObjectMap::Writer::writeGenerateFreshSparseArray):
(WebCore::V8ObjectMap::Writer::writeGenerateFreshDenseArray):
(WebCore::V8ObjectMap::Serializer::writeDenseArray):
(WebCore::V8ObjectMap::Serializer::AbstractObjectState::execDepth):
(WebCore::V8ObjectMap::Serializer::AbstractObjectState::serializeProperties):
(WebCore::V8ObjectMap::Serializer::ObjectState::advance):
(WebCore::V8ObjectMap::Serializer::DenseArrayState::DenseArrayState):
(WebCore::V8ObjectMap::Serializer::DenseArrayState::advance):
(WebCore::V8ObjectMap::Serializer::DenseArrayState::objectDone):
(WebCore::V8ObjectMap::Serializer::SparseArrayState::SparseArrayState):
(WebCore::V8ObjectMap::Serializer::SparseArrayState::advance):
(WebCore::V8ObjectMap::Serializer::serializeDensely):
(WebCore::V8ObjectMap::Serializer::startArrayState):
(WebCore::V8ObjectMap::Serializer::startObjectState):
(WebCore::V8ObjectMap::Serializer::doSerialize):
(WebCore::V8ObjectMap::Reader::read):
(WebCore::V8ObjectMap::Deserializer::newSparseArray):
(WebCore::V8ObjectMap::Deserializer::completeSparseArray):
(WebCore::V8ObjectMap::Deserializer::completeDenseArray):

LayoutTests: [V8][Chromium]Serialize dense arrays densly.
​https://bugs.webkit.org/show_bug.cgi?id=72198

Reviewed by David Levin.

  • fast/dom/Window/script-tests/postmessage-clone.js:
  • fast/dom/Window/window-postmessage-arrays-expected.txt: Added.
  • fast/dom/Window/window-postmessage-arrays.html: Added.
Location:
trunk
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r100238 r100239  
     12011-11-14  Dmitry Lomov  <dslomov@google.com>
     2
     3        [V8][Chromium]Serialize dense arrays densly.
     4        https://bugs.webkit.org/show_bug.cgi?id=72198
     5
     6        Reviewed by David Levin.
     7
     8        * fast/dom/Window/script-tests/postmessage-clone.js:
     9        * fast/dom/Window/window-postmessage-arrays-expected.txt: Added.
     10        * fast/dom/Window/window-postmessage-arrays.html: Added.
     11
    1122011-11-14  Peter Kasting  <pkasting@google.com>
    213

  • trunk/LayoutTests/fast/dom/Window/script-tests/postmessage-clone.js

    r91959 r100239  
    9898        'return a;'
    9999    ), false, "evalThunk", function(v) {
    100         doPassFail(v.length === 3, "length correct"); // undefined
     100        doPassFail(v.length === 3 || v.length === 2, "length correct"); // undefined
    101101        doPassFail(v[0] === 0, "index 0 OK"); // mandatory
    102102        doPassFail(v[1].x === 41, "accessor reached"); // mandatory

  • trunk/Source/WebCore/ChangeLog

    r100235 r100239  
     12011-11-14  Dmitry Lomov  <dslomov@google.com>
     2       
     3        [V8][Chromium]Serialize dense arrays densly
     4        https://bugs.webkit.org/show_bug.cgi?id=72198
     5        This patch ensures that:
     6        - Dense arrays are serialized densly, and not as name-value pairs
     7        - Sparse arrays are allocated as sparse on deserialization.
     8        The criteria to choose whether to serialize densly or sparsely is the size
     9        of a resulting serialized stream.
     10
     11        Reviewed by David Levin.
     12
     13        Test: fast/dom/Window/window-postmessage-arrays.html
     14
     15        * bindings/v8/SerializedScriptValue.cpp:
     16        (WebCore::V8ObjectMap::Writer::writeDenseArray):
     17        (WebCore::V8ObjectMap::Writer::writeGenerateFreshSparseArray):
     18        (WebCore::V8ObjectMap::Writer::writeGenerateFreshDenseArray):
     19        (WebCore::V8ObjectMap::Serializer::writeDenseArray):
     20        (WebCore::V8ObjectMap::Serializer::AbstractObjectState::execDepth):
     21        (WebCore::V8ObjectMap::Serializer::AbstractObjectState::serializeProperties):
     22        (WebCore::V8ObjectMap::Serializer::ObjectState::advance):
     23        (WebCore::V8ObjectMap::Serializer::DenseArrayState::DenseArrayState):
     24        (WebCore::V8ObjectMap::Serializer::DenseArrayState::advance):
     25        (WebCore::V8ObjectMap::Serializer::DenseArrayState::objectDone):
     26        (WebCore::V8ObjectMap::Serializer::SparseArrayState::SparseArrayState):
     27        (WebCore::V8ObjectMap::Serializer::SparseArrayState::advance):
     28        (WebCore::V8ObjectMap::Serializer::serializeDensely):
     29        (WebCore::V8ObjectMap::Serializer::startArrayState):
     30        (WebCore::V8ObjectMap::Serializer::startObjectState):
     31        (WebCore::V8ObjectMap::Serializer::doSerialize):
     32        (WebCore::V8ObjectMap::Reader::read):
     33        (WebCore::V8ObjectMap::Deserializer::newSparseArray):
     34        (WebCore::V8ObjectMap::Deserializer::completeSparseArray):
     35        (WebCore::V8ObjectMap::Deserializer::completeDenseArray):
     36
    1372011-11-14  Alexandre Elias  <aelias@google.com>
    238

  • trunk/Source/WebCore/bindings/v8/SerializedScriptValue.cpp

    r99229 r100239  
    190190    FileListTag = 'l', // length:uint32_t, files:RawFile[length] -> FileList (ref)
    191191    ImageDataTag = '#', // width:uint32_t, height:uint32_t, pixelDataLength:uint32_t, data:byte[pixelDataLength] -> ImageData (ref)
    192     ArrayTag = '[', // length:uint32_t -> pops the last array from the open stack;
    193                     //                    fills it with the last length elements pushed on the deserialization stack
    194192    ObjectTag = '{', // numProperties:uint32_t -> pops the last object from the open stack;
    195193                     //                           fills it with the last numProperties name,value pairs pushed onto the deserialization stack
    196194    SparseArrayTag = '@', // numProperties:uint32_t, length:uint32_t -> pops the last object from the open stack;
    197195                          //                                            fills it with the last numProperties name,value pairs pushed onto the deserialization stack
     196    DenseArrayTag = '$', // numProperties:uint32_t, length:uint32_t -> pops the last object from the open stack;
     197                         //                                            fills it with the last length elements and numProperties name,value pairs pushed onto deserialization stack
    198198    RegExpTag = 'R', // pattern:RawString, flags:uint32_t -> RegExp (ref)
    199199    ArrayBufferTag = 'B', // byteLength:uint32_t, data:byte[byteLength] -> ArrayBuffer (ref)
    … …  
    201201    ObjectReferenceTag = '^', // ref:uint32_t -> reference table[ref]
    202202    GenerateFreshObjectTag = 'o', // -> empty object allocated an object ID and pushed onto the open stack (ref)
    203     GenerateFreshArrayTag = 'a', // length:uint32_t -> empty array[length] allocated an object ID and pushed onto the open stack (ref)
     203    GenerateFreshSparseArrayTag = 'a', // length:uint32_t -> empty array[length] allocated an object ID and pushed onto the open stack (ref)
     204    GenerateFreshDenseArrayTag = 'A', // length:uint32_t -> empty array[length] allocated an object ID and pushed onto the open stack (ref)
    204205    ReferenceCountTag = '?', // refTableSize:uint32_t -> If the reference table is not refTableSize big, fails.
    205206    StringObjectTag = 's', //  string:RawString -> new String(string) (ref)
    … …  
    438439    }
    439440
    440     void writeArray(uint32_t length)
    441     {
    442         append(ArrayTag);
    443         doWriteUint32(length);
    444     }
    445 
    446441    void writeObjectReference(uint32_t reference)
    447442    {
    … …  
    463458    }
    464459
     460    void writeDenseArray(uint32_t numProperties, uint32_t length)
     461    {
     462        append(DenseArrayTag);
     463        doWriteUint32(numProperties);
     464        doWriteUint32(length);
     465    }
     466
    465467    Vector<BufferValueType>& data()
    466468    {
    … …  
    480482    }
    481483
    482     void writeGenerateFreshArray(uint32_t length)
    483     {
    484         append(GenerateFreshArrayTag);
     484    void writeGenerateFreshSparseArray(uint32_t length)
     485    {
     486        append(GenerateFreshSparseArrayTag);
    485487        doWriteUint32(length);
    486488    }
     489
     490    void writeGenerateFreshDenseArray(uint32_t length)
     491    {
     492        append(GenerateFreshDenseArrayTag);
     493        doWriteUint32(length);
     494    }
     495
    487496
    488497private:
    … …  
    623632    }
    624633
    625     StateBase* writeArray(uint32_t length, StateBase* state)
    626     {
    627         m_writer.writeArray(length);
    628         return pop(state);
    629     }
    630 
    631634    StateBase* writeObject(uint32_t numProperties, StateBase* state)
    632635    {
    … …  
    640643        return pop(state);
    641644    }
     645
     646    StateBase* writeDenseArray(uint32_t numProperties, uint32_t length, StateBase* state)
     647    {
     648        m_writer.writeDenseArray(numProperties, length);
     649        return pop(state);
     650    }
     651
    642652
    643653private:
    … …  
    700710        }
    701711    };
    702 
    703 #if 0
    704     // Currently unused, see comment in newArrayState.
    705     class ArrayState : public State<v8::Array> {
    706     public:
    707         ArrayState(v8::Handle<v8::Array> array, StateBase* next)
    708             : State<v8::Array>(array, next)
    709             , m_index(-1)
    710         {
    711         }
    712 
    713         virtual StateBase* advance(Serializer& serializer)
    714         {
    715             ++m_index;
    716             for (; m_index < composite()->Length(); ++m_index) {
    717                 v8::Handle<v8::Value> value = composite()->Get(m_index);
    718                 if (StateBase* newState = serializer.checkException(this))
    719                     return newState;
    720                 if (StateBase* newState = serializer.doSerialize(value, this))
    721                     return newState;
    722             }
    723             return serializer.writeArray(composite()->Length(), this);
    724         }
    725 
    726     private:
    727         unsigned m_index;
    728     };
    729 #endif
    730712
    731713    class AbstractObjectState : public State<v8::Object> {
    … …  
    740722        }
    741723
    742         virtual StateBase* advance(Serializer& serializer)
     724        virtual uint32_t execDepth() const { return m_isSerializingAccessor ? 1 : 0; }
     725
     726    protected:
     727        virtual StateBase* objectDone(unsigned numProperties, Serializer&) = 0;
     728
     729        StateBase* serializeProperties(bool ignoreIndexed, Serializer& serializer)
    743730        {
    744731            m_isSerializingAccessor = false;
    745             if (!m_index) {
    746                 m_propertyNames = composite()->GetPropertyNames();
    747                 if (StateBase* newState = serializer.checkException(this))
    748                     return newState;
    749                 if (m_propertyNames.IsEmpty())
    750                     return serializer.reportFailure(this);
    751             }
    752732            while (m_index < m_propertyNames->Length()) {
    753733                bool isAccessor = false;
    … …  
    767747                    if (StateBase* newState = serializer.checkException(this))
    768748                        return newState;
    769                     if (hasStringProperty || hasIndexedProperty)
     749                    if (hasStringProperty || (hasIndexedProperty && !ignoreIndexed))
    770750                        m_propertyName = propertyName;
    771751                    else {
    … …  
    800780        }
    801781
    802         virtual uint32_t execDepth() const { return m_isSerializingAccessor ? 1 : 0; }
    803 
    804     protected:
    805         virtual StateBase* objectDone(unsigned numProperties, Serializer&) = 0;
     782        v8::Local<v8::Array> m_propertyNames;
    806783
    807784    private:
    808         v8::Local<v8::Array> m_propertyNames;
    809785        v8::Local<v8::Value> m_propertyName;
    810786        unsigned m_index;
    … …  
    823799        }
    824800
     801        virtual StateBase* advance(Serializer& serializer)
     802        {
     803            if (m_propertyNames.IsEmpty()) {
     804                m_propertyNames = composite()->GetPropertyNames();
     805                if (StateBase* newState = serializer.checkException(this))
     806                    return newState;
     807                if (m_propertyNames.IsEmpty())
     808                    return serializer.reportFailure(this);
     809            }
     810            return serializeProperties(false, serializer);
     811        }
     812
    825813    protected:
    826814        virtual StateBase* objectDone(unsigned numProperties, Serializer& serializer)
    … …  
    830818    };
    831819
     820    class DenseArrayState : public AbstractObjectState {
     821    public:
     822        DenseArrayState(v8::Handle<v8::Array> array, v8::Handle<v8::Array> propertyNames, StateBase* next)
     823            : AbstractObjectState(array, next)
     824            , m_arrayIndex(0)
     825            , m_arrayLength(array->Length())
     826        {
     827            m_propertyNames = v8::Local<v8::Array>::New(propertyNames);
     828        }
     829
     830        virtual StateBase* advance(Serializer& serializer)
     831        {
     832            while (m_arrayIndex < m_arrayLength) {
     833                v8::Handle<v8::Value> value = composite().As<v8::Array>()->Get(m_arrayIndex);
     834                m_arrayIndex++;
     835                if (StateBase* newState = serializer.checkException(this))
     836                    return newState;
     837                if (StateBase* newState = serializer.doSerialize(value, this))
     838                    return newState;
     839            }
     840            return serializeProperties(true, serializer);
     841        }
     842
     843    protected:
     844        virtual StateBase* objectDone(unsigned numProperties, Serializer& serializer)
     845        {
     846            return serializer.writeDenseArray(numProperties, m_arrayLength, this);
     847        }
     848
     849    private:
     850        uint32_t m_arrayIndex;
     851        uint32_t m_arrayLength;
     852    };
     853
    832854    class SparseArrayState : public AbstractObjectState {
    833855    public:
    834         SparseArrayState(v8::Handle<v8::Array> array, StateBase* next)
     856        SparseArrayState(v8::Handle<v8::Array> array, v8::Handle<v8::Array> propertyNames, StateBase* next)
    835857            : AbstractObjectState(array, next)
    836858        {
     859            m_propertyNames = v8::Local<v8::Array>::New(propertyNames);
     860        }
     861
     862        virtual StateBase* advance(Serializer& serializer)
     863        {
     864            return serializeProperties(false, serializer);
    837865        }
    838866
    … …  
    9951023    }
    9961024
    997     static StateBase* newArrayState(v8::Handle<v8::Array> array, StateBase* next)
    998     {
    999         // FIXME: use plain Array state when we can quickly check that
    1000         // an array is not sparse and has only indexed properties.
    1001         return new SparseArrayState(array, next);
    1002     }
    1003 
    1004     static StateBase* newObjectState(v8::Handle<v8::Object> object, StateBase* next)
    1005     {
     1025    static bool shouldSerializeDensely(uint32_t length, uint32_t propertyCount)
     1026    {
     1027        // Let K be the cost of serializing all property values that are there
     1028        // Cost of serializing sparsely: 5*propertyCount + K (5 bytes per uint32_t key)
     1029        // Cost of serializing densely: K + 1*(length - propertyCount) (1 byte for all properties that are not there)
     1030        // so densely is better than sparsly whenever 6*propertyCount > length
     1031        return 6 * propertyCount >= length;
     1032    }
     1033
     1034    StateBase* startArrayState(v8::Handle<v8::Array> array, StateBase* next)
     1035    {
     1036        v8::Handle<v8::Array> propertyNames = array->GetPropertyNames();
     1037        if (StateBase* newState = checkException(next))
     1038            return newState;
     1039        uint32_t length = array->Length();
     1040
     1041        if (shouldSerializeDensely(length, propertyNames->Length())) {
     1042            m_writer.writeGenerateFreshDenseArray(length);
     1043            return push(new DenseArrayState(array, propertyNames, next));
     1044        }
     1045
     1046        m_writer.writeGenerateFreshSparseArray(length);
     1047        return push(new SparseArrayState(array, propertyNames, next));
     1048    }
     1049
     1050    StateBase* startObjectState(v8::Handle<v8::Object> object, StateBase* next)
     1051    {
     1052        m_writer.writeGenerateFreshObject();
    10061053        // FIXME: check not a wrapper
    1007         return new ObjectState(object, next);
     1054        return push(new ObjectState(object, next));
    10081055    }
    10091056
    … …  
    10831130            writeBooleanObject(value);
    10841131        else if (value->IsArray()) {
    1085             m_writer.writeGenerateFreshArray(value.As<v8::Array>()->Length());
    1086             return push(newArrayState(value.As<v8::Array>(), next));
     1132            return startArrayState(value.As<v8::Array>(), next);
    10871133        } else if (V8File::HasInstance(value))
    10881134            writeFile(value);
    … …  
    11001146            if (isHostObject(jsObject) || jsObject->IsCallable() || value->IsNativeError())
    11011147                return handleError(DataCloneError, next);
    1102             m_writer.writeGenerateFreshObject();
    1103             return push(newObjectState(jsObject, next));
     1148            return startObjectState(jsObject, next);
    11041149        } else
    11051150            return handleError(DataCloneError, next);
    … …  
    11181163    virtual bool tryGetObjectFromObjectReference(uint32_t reference, v8::Handle<v8::Value>*) = 0;
    11191164    virtual bool tryGetTransferredMessagePort(uint32_t index, v8::Handle<v8::Value>*) = 0;
    1120     virtual bool newArray(uint32_t length) = 0;
     1165    virtual bool newSparseArray(uint32_t length) = 0;
     1166    virtual bool newDenseArray(uint32_t length) = 0;
    11211167    virtual bool newObject() = 0;
    1122     virtual bool completeArray(uint32_t length, v8::Handle<v8::Value>*) = 0;
    11231168    virtual bool completeObject(uint32_t numProperties, v8::Handle<v8::Value>*) = 0;
    11241169    virtual bool completeSparseArray(uint32_t numProperties, uint32_t length, v8::Handle<v8::Value>*) = 0;
     1170    virtual bool completeDenseArray(uint32_t numProperties, uint32_t length, v8::Handle<v8::Value>*) = 0;
    11251171};
    11261172
    … …  
    12351281            break;
    12361282
    1237         case ArrayTag: {
    1238             uint32_t length;
    1239             if (!doReadUint32(&length))
    1240                 return false;
    1241             if (!creator.completeArray(length, value))
    1242                 return false;
    1243             break;
    1244         }
    12451283        case RegExpTag:
    12461284            if (!readRegExp(value))
    … …  
    12671305            break;
    12681306        }
     1307        case DenseArrayTag: {
     1308            uint32_t numProperties;
     1309            uint32_t length;
     1310            if (!doReadUint32(&numProperties))
     1311                return false;
     1312            if (!doReadUint32(&length))
     1313                return false;
     1314            if (!creator.completeDenseArray(numProperties, length, value))
     1315                return false;
     1316            break;
     1317        }
    12691318        case ArrayBufferViewTag: {
    12701319            if (m_version <= 0)
    … …  
    12901339            return true;
    12911340        }
    1292         case GenerateFreshArrayTag: {
     1341        case GenerateFreshSparseArrayTag: {
    12931342            if (m_version <= 0)
    12941343                return false;
    … …  
    12961345            if (!doReadUint32(&length))
    12971346                return false;
    1298             if (!creator.newArray(length))
     1347            if (!creator.newSparseArray(length))
     1348                return false;
     1349            return true;
     1350        }
     1351        case GenerateFreshDenseArrayTag: {
     1352            if (m_version <= 0)
     1353                return false;
     1354            uint32_t length;
     1355            if (!doReadUint32(&length))
     1356                return false;
     1357            if (!creator.newDenseArray(length))
    12991358                return false;
    13001359            return true;
    … …  
    17081767    }
    17091768
    1710     virtual bool newArray(uint32_t length)
     1769    virtual bool newSparseArray(uint32_t)
     1770    {
     1771        v8::Local<v8::Array> array = v8::Array::New(0);
     1772        openComposite(array);
     1773        return true;
     1774    }
     1775
     1776    virtual bool newDenseArray(uint32_t length)
    17111777    {
    17121778        v8::Local<v8::Array> array = v8::Array::New(length);
    1713         if (array.IsEmpty())
    1714             return false;
    17151779        openComposite(array);
    17161780        return true;
    … …  
    17821846            array = composite.As<v8::Array>();
    17831847        } else
    1784             array = v8::Array::New(length);
     1848            array = v8::Array::New();
    17851849        if (array.IsEmpty())
    17861850            return false;
    17871851        return initializeObject(array, numProperties, value);
     1852    }
     1853
     1854    virtual bool completeDenseArray(uint32_t numProperties, uint32_t length, v8::Handle<v8::Value>* value)
     1855    {
     1856        v8::Local<v8::Array> array;
     1857        if (m_version > 0) {
     1858            v8::Local<v8::Value> composite;
     1859            if (!closeComposite(&composite))
     1860                return false;
     1861            array = composite.As<v8::Array>();
     1862        }
     1863        if (array.IsEmpty())
     1864            return false;
     1865        if (!initializeObject(array, numProperties, value))
     1866            return false;
     1867        if (length > stackDepth())
     1868            return false;
     1869        for (unsigned i = 0, stackPos = stackDepth() - length; i < length; i++, stackPos++) {
     1870            v8::Local<v8::Value> elem = element(stackPos);
     1871            if (!elem->IsUndefined())
     1872                array->Set(i, elem);
     1873        }
     1874        pop(length);
     1875        return true;
    17881876    }
    17891877
Note: See TracChangeset for help on using the changeset viewer.