Reserve a double slot for accessor properties

Reserve two slots in the internal class for accessor
properties. This opens up reducing the default storage
required per data property to one Value. In practice
this implies cutting the required memory in half.

Change-Id: Ifed897852bbdfd810018f0d6b049fca6690ead2c
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 114 insertions, 43 deletions

diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp
index 761a180722..7c4a8de284 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -151,33 +151,53 @@ InternalClass::InternalClass(const QV4::InternalClass &other)
 {
 }
 
-// ### Should we build this up from the empty class to avoid duplication?
+void InternalClass::changeMember(Object *object, String *string, PropertyAttributes data, uint *index)
+{
+    uint idx;
+    InternalClass *newClass = object->internalClass->changeMember(string, data, &idx);
+    if (index)
+        *index = idx;
+
+    if (newClass->size > object->internalClass->size) {
+        Q_ASSERT(newClass->size == object->internalClass->size + 1);
+        memmove(object->memberData + idx + 2, object->memberData + idx + 1, (object->internalClass->size - idx - 1)*sizeof(Property));
+    } else if (newClass->size < object->internalClass->size) {
+        Q_ASSERT(newClass->size == object->internalClass->size - 1);
+        memmove(object->memberData + idx + 1, object->memberData + idx + 2, (object->internalClass->size - idx - 2)*sizeof(Property));
+    }
+    object->internalClass = newClass;
+}
+
 InternalClass *InternalClass::changeMember(String *string, PropertyAttributes data, uint *index)
 {
-//    qDebug() << "InternalClass::changeMember()" << string->toQString() << hex << (uint)data.m_all;
     data.resolve();
     uint idx = find(string);
+    Q_ASSERT(idx != UINT_MAX);
+
     if (index)
         *index = idx;
 
-    Q_ASSERT(idx != UINT_MAX);
-
     if (data == propertyData.at(idx))
         return this;
 
-
     Transition t = { { string->identifier }, (int)data.flags() };
     QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
     if (tit != transitions.constEnd())
         return tit.value();
 
     // create a new class and add it to the tree
-    InternalClass *newClass = engine->newClass(*this);
-    newClass->propertyData.set(idx, data);
+    InternalClass *newClass = engine->emptyClass->changeVTable(vtable);
+    newClass = newClass->changePrototype(prototype);
+    for (uint i = 0; i < size; ++i) {
+        if (i == idx) {
+            newClass = newClass->addMember(nameMap.at(i), data);
+        } else if (!propertyData.at(i).isEmpty()) {
+            newClass = newClass->addMember(nameMap.at(i), propertyData.at(i));
+        }
+    }
 
     transitions.insert(t, newClass);
     return newClass;
-
 }
 
 InternalClass *InternalClass::create(ExecutionEngine *engine, const ManagedVTable *vtable, Object *proto)
@@ -209,8 +229,10 @@ InternalClass *InternalClass::changePrototype(Object *proto)
     } else {
         newClass = engine->emptyClass->changeVTable(vtable);
         newClass = newClass->changePrototype(proto);
-        for (uint i = 0; i < size; ++i)
-            newClass = newClass->addMember(nameMap.at(i), propertyData.at(i));
+        for (uint i = 0; i < size; ++i) {
+            if (!propertyData.at(i).isEmpty())
+                newClass = newClass->addMember(nameMap.at(i), propertyData.at(i));
+        }
     }
 
     transitions.insert(t, newClass);
@@ -238,14 +260,39 @@ InternalClass *InternalClass::changeVTable(const ManagedVTable *vt)
     } else {
         newClass = engine->emptyClass->changeVTable(vt);
         newClass = newClass->changePrototype(prototype);
-        for (uint i = 0; i < size; ++i)
-            newClass = newClass->addMember(nameMap.at(i), propertyData.at(i));
+        for (uint i = 0; i < size; ++i) {
+            if (!propertyData.at(i).isEmpty())
+                newClass = newClass->addMember(nameMap.at(i), propertyData.at(i));
+        }
     }
 
     transitions.insert(t, newClass);
     return newClass;
 }
 
+void InternalClass::addMember(Object *object, StringRef string, PropertyAttributes data, uint *index)
+{
+    return addMember(object, string.getPointer(), data, index);
+}
+
+void InternalClass::addMember(Object *object, String *string, PropertyAttributes data, uint *index)
+{
+    data.resolve();
+    object->internalClass->engine->identifierTable->identifier(string);
+    if (object->internalClass->propertyTable.lookup(string->identifier) < object->internalClass->size) {
+        changeMember(object, string, data, index);
+        return;
+    }
+
+    uint idx;
+    InternalClass *newClass = object->internalClass->addMemberImpl(string, data, &idx);
+    if (index)
+        *index = idx;
+
+    object->internalClass = newClass;
+}
+
+
 InternalClass *InternalClass::addMember(StringRef string, PropertyAttributes data, uint *index)
 {
     return addMember(string.getPointer(), data, index);
@@ -253,13 +300,17 @@ InternalClass *InternalClass::addMember(StringRef string, PropertyAttributes dat
 
 InternalClass *InternalClass::addMember(String *string, PropertyAttributes data, uint *index)
 {
-//    qDebug() << "InternalClass::addMember()" << string->toQString() << size << hex << (uint)data.m_all << data.type();
     data.resolve();
     engine->identifierTable->identifier(string);
 
     if (propertyTable.lookup(string->identifier) < size)
         return changeMember(string, data, index);
 
+    return addMemberImpl(string, data, index);
+}
+
+InternalClass *InternalClass::addMemberImpl(String *string, PropertyAttributes data, uint *index)
+{
     Transition t = { { string->identifier }, (int)data.flags() };
     QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
 
@@ -270,44 +321,56 @@ InternalClass *InternalClass::addMember(String *string, PropertyAttributes data,
 
     // create a new class and add it to the tree
     InternalClass *newClass = engine->newClass(*this);
-    PropertyHash::Entry e = { string->identifier, size };
-    newClass->propertyTable.addEntry(e, size);
+    PropertyHash::Entry e = { string->identifier, newClass->size };
+    newClass->propertyTable.addEntry(e, newClass->size);
 
     // The incoming string can come from anywhere, so make sure to
     // store a string in the nameMap that's guaranteed to get
     // marked properly during GC.
     String *name = engine->newIdentifier(string->toQString());
-    newClass->nameMap.add(size, name);
-
-    newClass->propertyData.add(size, data);
+    newClass->nameMap.add(newClass->size, name);
+    newClass->propertyData.add(newClass->size, data);
     ++newClass->size;
+    if (data.isAccessor()) {
+        // add a dummy entry, since we need two entries for accessors
+        newClass->propertyTable.addEntry(e, newClass->size);
+        newClass->nameMap.add(newClass->size, 0);
+        newClass->propertyData.add(newClass->size, PropertyAttributes());
+        ++newClass->size;
+    }
+
     transitions.insert(t, newClass);
     return newClass;
 }
 
 void InternalClass::removeMember(Object *object, Identifier *id)
 {
-    uint propIdx = propertyTable.lookup(id);
-    Q_ASSERT(propIdx < size);
+    InternalClass *oldClass = object->internalClass;
+    uint propIdx = oldClass->propertyTable.lookup(id);
+    Q_ASSERT(propIdx < oldClass->size);
 
     Transition t = { { id } , -1 };
-    QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
+    QHash<Transition, InternalClass *>::const_iterator tit = object->internalClass->transitions.constFind(t);
 
-    if (tit != transitions.constEnd()) {
+    if (tit != object->internalClass->transitions.constEnd()) {
         object->internalClass = tit.value();
-        return;
+    } else {
+        // create a new class and add it to the tree
+        InternalClass *newClass = oldClass->engine->emptyClass->changeVTable(oldClass->vtable);
+        newClass = newClass->changePrototype(oldClass->prototype);
+        for (uint i = 0; i < oldClass->size; ++i) {
+            if (i == propIdx)
+                continue;
+            if (!oldClass->propertyData.at(i).isEmpty())
+                newClass = newClass->addMember(oldClass->nameMap.at(i), oldClass->propertyData.at(i));
+        }
+        object->internalClass = newClass;
     }
 
-    // create a new class and add it to the tree
-    object->internalClass = engine->emptyClass->changeVTable(vtable);
-    object->internalClass = object->internalClass->changePrototype(prototype);
-    for (uint i = 0; i < size; ++i) {
-        if (i == propIdx)
-            continue;
-        object->internalClass = object->internalClass->addMember(nameMap.at(i), propertyData.at(i));
-    }
+    // remove the entry in memberdata
+    memmove(object->memberData + propIdx, object->memberData + propIdx + 1, (object->internalClass->size - propIdx)*sizeof(Property));
 
-    transitions.insert(t, object->internalClass);
+    oldClass->transitions.insert(t, object->internalClass);
 }
 
 uint InternalClass::find(const StringRef string)
diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h
index b25b895183..91c6e264db 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -233,10 +233,13 @@ struct InternalClass {
     static InternalClass *create(ExecutionEngine *engine, const ManagedVTable *vtable, Object *proto);
     InternalClass *changePrototype(Object *proto);
     InternalClass *changeVTable(const ManagedVTable *vt);
+    static void addMember(Object *object, StringRef string, PropertyAttributes data, uint *index);
+    static void addMember(Object *object, String *string, PropertyAttributes data, uint *index);
     InternalClass *addMember(StringRef string, PropertyAttributes data, uint *index = 0);
     InternalClass *addMember(String *string, PropertyAttributes data, uint *index = 0);
     InternalClass *changeMember(String *string, PropertyAttributes data, uint *index = 0);
-    void removeMember(Object *object, Identifier *id);
+    static void changeMember(Object *object, String *string, PropertyAttributes data, uint *index = 0);
+    static void removeMember(Object *object, Identifier *id);
     uint find(const StringRef string);
     uint find(const String *s);
 
@@ -247,6 +250,7 @@ struct InternalClass {
     void markObjects();
 
 private:
+    InternalClass *addMemberImpl(String *string, PropertyAttributes data, uint *index);
     friend struct ExecutionEngine;
     InternalClass(ExecutionEngine *engine);
     InternalClass(const InternalClass &other);
diff --git a/src/qml/jsruntime/qv4object.cpp b/src/qml/jsruntime/qv4object.cpp
index de84747221..d0fc30005b 100644
--- a/src/qml/jsruntime/qv4object.cpp
+++ b/src/qml/jsruntime/qv4object.cpp
@@ -240,10 +240,11 @@ void Object::markObjects(Managed *that, ExecutionEngine *e)
 void Object::ensureMemberIndex(uint idx)
 {
     if (idx >= memberDataAlloc) {
-        memberDataAlloc = qMax((uint)8, 2*memberDataAlloc);
-        Property *newMemberData = new Property[memberDataAlloc];
-        memcpy(newMemberData, memberData, sizeof(Property)*idx);
-        memset(newMemberData + idx, 0, sizeof(Property)*(memberDataAlloc - idx));
+        int newAlloc = qMax((uint)8, 2*memberDataAlloc);
+        Property *newMemberData = new Property[newAlloc];
+        memcpy(newMemberData, memberData, sizeof(Property)*memberDataAlloc);
+        memset(newMemberData + memberDataAlloc, 0, sizeof(Property)*(newAlloc - memberDataAlloc));
+        memberDataAlloc = newAlloc;
         if (memberData != inlineProperties)
             delete [] memberData;
         memberData = newMemberData;
@@ -253,12 +254,12 @@ void Object::ensureMemberIndex(uint idx)
 void Object::insertMember(const StringRef s, const Property &p, PropertyAttributes attributes)
 {
     uint idx;
-    internalClass = internalClass->addMember(s.getPointer(), attributes, &idx);
+    InternalClass::addMember(this, s.getPointer(), attributes, &idx);
 
     if (attributes.isAccessor())
         hasAccessorProperty = 1;
 
-    ensureMemberIndex(idx);
+    ensureMemberIndex(internalClass->size);
 
     memberData[idx] = p;
 }
@@ -597,7 +598,11 @@ void Object::advanceIterator(Managed *m, ObjectIterator *it, StringRef name, uin
 
     while (it->memberIndex < o->internalClass->size) {
         String *n = o->internalClass->nameMap.at(it->memberIndex);
-        assert(n);
+        if (!n) {
+            // accessor properties have a dummy entry with n == 0
+            ++it->memberIndex;
+            continue;
+        }
 
         Property *p = o->memberData + it->memberIndex;
         PropertyAttributes a = o->internalClass->propertyData[it->memberIndex];
@@ -841,8 +846,7 @@ bool Object::internalDeleteProperty(const StringRef name)
     uint memberIdx = internalClass->find(name);
     if (memberIdx != UINT_MAX) {
         if (internalClass->propertyData[memberIdx].isConfigurable()) {
-            internalClass->removeMember(this, name->identifier);
-            memmove(memberData + memberIdx, memberData + memberIdx + 1, (internalClass->size - memberIdx)*sizeof(Property));
+            InternalClass::removeMember(this, name->identifier);
             return true;
         }
         if (engine()->currentContext()->strictMode)
@@ -1061,7 +1065,7 @@ bool Object::__defineOwnProperty__(ExecutionContext *ctx, uint index, const Stri
 
     current->merge(cattrs, p, attrs);
     if (!member.isNull()) {
-        internalClass = internalClass->changeMember(member.getPointer(), cattrs);
+        InternalClass::changeMember(this, member.getPointer(), cattrs);
     } else {
         setArrayAttributes(index, cattrs);
     }