Replace InternalClass transitions hash with a sorted vector.

In a reasonable test application, there were some 1697 transition entries. Out
of these, 1663 of them had only a single item. The remainder, with the exception
of three, had <10 items. Only one of these had a count of >50 items (86).

As can be seen, most of the time, transitions is usually quite sparsely
populated, so using a hash is a large amount of overhead considering there's
just a few elements. For the times when it isn't, the vector being sorted
should help take care of that.

Since transitions are never removed, we can use a similar trick to
ba690fb73864915b4a35bbec5b7dc134ff1dafd0 and use a sorted vector to store them.

Compared to the hash approach, this saved ~412kb according to malloc_stats on a
reasonably comprehensive test application. Coincidentally, this also improved
v8bench for me by ~10%.

Note that this undoes 132cdfa69cae45d0c02ea715ce58722bbcd57e73, but the
expectation is that the fewer allocations done by using a vector will outweigh
the need to reserve any specific allocation initially.

Change-Id: Iec57a7db7e9a60347c9683b1cb1598f6d9c866f7
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

2 files changed, 47 insertions, 36 deletions

diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp
index c226ceade9..8c44d65426 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -40,14 +40,6 @@
 
 QT_BEGIN_NAMESPACE
 
-uint QV4::qHash(const QV4::InternalClassTransition &t, uint)
-{
-    if (t.flags & QV4::InternalClassTransition::VTableChange)
-        // INT_MAX is prime, so this should give a decent distribution of keys
-        return (uint)((quintptr)t.vtable * INT_MAX);
-    return t.id->hashValue ^ t.flags;
-}
-
 using namespace QV4;
 
 static const uchar prime_deltas[] = {
@@ -125,7 +117,6 @@ InternalClass::InternalClass(ExecutionEngine *engine)
     , m_frozen(0)
     , size(0)
 {
-    transitions.reserve(17);
 }
 
 
@@ -136,12 +127,10 @@ InternalClass::InternalClass(const QV4::InternalClass &other)
     , propertyTable(other.propertyTable)
     , nameMap(other.nameMap)
     , propertyData(other.propertyData)
-    , transitions()
     , m_sealed(0)
     , m_frozen(0)
     , size(other.size)
 {
-    transitions.reserve(17);
 }
 
 void InternalClass::changeMember(Object *object, String *string, PropertyAttributes data, uint *index)
@@ -161,6 +150,17 @@ void InternalClass::changeMember(Object *object, String *string, PropertyAttribu
     object->setInternalClass(newClass);
 }
 
+InternalClassTransition &InternalClass::lookupOrInsertTransition(const InternalClassTransition &t)
+{
+    std::vector<Transition>::iterator it = std::lower_bound(transitions.begin(), transitions.end(), t);
+    if (it != transitions.end() && *it == t) {
+        return *it;
+    } else {
+        it = transitions.insert(it, t);
+        return *it;
+    }
+}
+
 InternalClass *InternalClass::changeMember(Identifier *identifier, PropertyAttributes data, uint *index)
 {
     data.resolve();
@@ -173,10 +173,10 @@ InternalClass *InternalClass::changeMember(Identifier *identifier, PropertyAttri
     if (data == propertyData.at(idx))
         return this;
 
-    Transition t = { { identifier }, (int)data.flags() };
-    QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
-    if (tit != transitions.constEnd())
-        return tit.value();
+    Transition temp = { { identifier }, 0, (int)data.flags() };
+    Transition &t = lookupOrInsertTransition(temp);
+    if (t.lookup)
+        return t.lookup;
 
     // create a new class and add it to the tree
     InternalClass *newClass = engine->emptyClass->changeVTable(vtable);
@@ -188,7 +188,7 @@ InternalClass *InternalClass::changeMember(Identifier *identifier, PropertyAttri
         }
     }
 
-    transitions.insert(t, newClass);
+    t.lookup = newClass;
     return newClass;
 }
 
@@ -202,13 +202,14 @@ InternalClass *InternalClass::changeVTable(const ManagedVTable *vt)
     if (vtable == vt)
         return this;
 
-    Transition t;
-    t.vtable = vt;
-    t.flags = Transition::VTableChange;
+    Transition temp;
+    temp.vtable = vt;
+    temp.lookup = 0;
+    temp.flags = Transition::VTableChange;
 
-    QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
-    if (tit != transitions.constEnd())
-        return tit.value();
+    Transition &t = lookupOrInsertTransition(temp);
+    if (t.lookup)
+        return t.lookup;
 
     // create a new class and add it to the tree
     InternalClass *newClass;
@@ -223,7 +224,7 @@ InternalClass *InternalClass::changeVTable(const ManagedVTable *vt)
         }
     }
 
-    transitions.insert(t, newClass);
+    t.lookup = newClass;
     return newClass;
 }
 
@@ -262,13 +263,14 @@ InternalClass *InternalClass::addMember(Identifier *identifier, PropertyAttribut
 
 InternalClass *InternalClass::addMemberImpl(Identifier *identifier, PropertyAttributes data, uint *index)
 {
-    Transition t = { { identifier }, (int)data.flags() };
-    QHash<Transition, InternalClass *>::const_iterator tit = transitions.constFind(t);
+    Transition temp = { { identifier }, 0, (int)data.flags() };
+    Transition &t = lookupOrInsertTransition(temp);
 
     if (index)
         *index = size;
-    if (tit != transitions.constEnd())
-        return tit.value();
+
+    if (t.lookup)
+        return t.lookup;
 
     // create a new class and add it to the tree
     InternalClass *newClass = engine->newClass(*this);
@@ -286,7 +288,7 @@ InternalClass *InternalClass::addMemberImpl(Identifier *identifier, PropertyAttr
         ++newClass->size;
     }
 
-    transitions.insert(t, newClass);
+    t.lookup = newClass;
     return newClass;
 }
 
@@ -296,11 +298,11 @@ void InternalClass::removeMember(Object *object, Identifier *id)
     uint propIdx = oldClass->propertyTable.lookup(id);
     Q_ASSERT(propIdx < oldClass->size);
 
-    Transition t = { { id } , -1 };
-    QHash<Transition, InternalClass *>::const_iterator tit = object->internalClass()->transitions.constFind(t);
+    Transition t = { { id }, 0, -1 };
+    t = object->internalClass()->lookupOrInsertTransition(t); // take a copy
 
-    if (tit != object->internalClass()->transitions.constEnd()) {
-        object->setInternalClass(tit.value());
+    if (t.lookup) {
+        object->setInternalClass(t.lookup);
     } else {
         // create a new class and add it to the tree
         InternalClass *newClass = oldClass->engine->emptyClass->changeVTable(oldClass->vtable);
@@ -316,7 +318,8 @@ void InternalClass::removeMember(Object *object, Identifier *id)
     // remove the entry in memberdata
     memmove(object->memberData()->data + propIdx, object->memberData()->data + propIdx + 1, (object->internalClass()->size - propIdx)*sizeof(Value));
 
-    oldClass->transitions.insert(t, object->internalClass());
+    t.lookup = object->internalClass();
+    oldClass->lookupOrInsertTransition(t);
 }
 
 uint InternalClass::find(const String *string)
@@ -397,7 +400,11 @@ void InternalClass::destroy()
             destroyStack.append(next->m_sealed);
         if (next->m_frozen)
             destroyStack.append(next->m_frozen);
-        destroyStack.append(next->transitions.values());
+
+        for (size_t i = 0; i < transitions.size(); ++i) {
+            destroyStack.append(next->transitions.at(i).lookup);
+        }
+
         next->transitions.clear();
     }
 }
diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h
index 4367f6576d..5973ca2c7c 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -193,6 +193,7 @@ struct InternalClassTransition
         Identifier *id;
         const ManagedVTable *vtable;
     };
+    InternalClass *lookup;
     int flags;
     enum {
         // range 0-0xff is reserved for attribute changes
@@ -201,8 +202,10 @@ struct InternalClassTransition
 
     bool operator==(const InternalClassTransition &other) const
     { return id == other.id && flags == other.flags; }
+
+    bool operator<(const InternalClassTransition &other) const
+    { return id < other.id; }
 };
-uint qHash(const QV4::InternalClassTransition &t, uint = 0);
 
 struct InternalClass : public QQmlJS::Managed {
     ExecutionEngine *engine;
@@ -213,7 +216,8 @@ struct InternalClass : public QQmlJS::Managed {
     SharedInternalClassData<PropertyAttributes> propertyData;
 
     typedef InternalClassTransition Transition;
-    QHash<Transition, InternalClass *> transitions; // id to next class, positive means add, negative delete
+    std::vector<Transition> transitions;
+    InternalClassTransition &lookupOrInsertTransition(const InternalClassTransition &t);
 
     InternalClass *m_sealed;
     InternalClass *m_frozen;