diff options
author | Robin Burchell <robin.burchell@viroteck.net> | 2015-01-08 01:28:58 +0100 |
---|---|---|
committer | Lars Knoll <lars.knoll@digia.com> | 2015-01-09 11:51:28 +0100 |
commit | 6421f275286b3238fe1a7a5e909225251f3e8dbf (patch) | |
tree | e91388f7e70d3d2c4d3542701bb573988b7a5a10 /src/qml/jsruntime/qv4internalclass.cpp | |
parent | 2a375c3f54da8bbf637880ea89f4e7e9937bdb26 (diff) |
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>
Diffstat (limited to 'src/qml/jsruntime/qv4internalclass.cpp')
-rw-r--r-- | src/qml/jsruntime/qv4internalclass.cpp | 75 |
1 files changed, 41 insertions, 34 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(); } } |