From 238b1cb1cb8915995b6dfe4e404f1771c62b3169 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Fri, 6 Apr 2018 12:49:09 +0200 Subject: Turn Identifier into a simple integer Add a reverse mapping table to the IdentifierHash to avoid having to store a hash value inside the identifier. This makes it possible to then use the identifiers value based and not new them on the heap anymore. Change-Id: If1f177588ea104565c6e3add49c70534a6c7dcb8 Reviewed-by: Simon Hausmann --- src/qml/jsruntime/qv4engine_p.h | 5 +++ src/qml/jsruntime/qv4identifier.cpp | 6 ++-- src/qml/jsruntime/qv4identifier_p.h | 2 +- src/qml/jsruntime/qv4identifiertable.cpp | 60 +++++++++++++++++++++++--------- src/qml/jsruntime/qv4identifiertable_p.h | 5 +-- src/qml/jsruntime/qv4internalclass.cpp | 6 ++-- src/qml/jsruntime/qv4internalclass_p.h | 2 +- 7 files changed, 60 insertions(+), 26 deletions(-) diff --git a/src/qml/jsruntime/qv4engine_p.h b/src/qml/jsruntime/qv4engine_p.h index 4316967484..8e5108b399 100644 --- a/src/qml/jsruntime/qv4engine_p.h +++ b/src/qml/jsruntime/qv4engine_p.h @@ -157,6 +157,11 @@ public: QV8Engine *v8Engine; QJSEngine *publicEngine; +private: + int stringOrSymbolId = 0; +public: + int nextStringOrSymbolId() { return ++stringOrSymbolId; } + enum JSObjects { RootContext, IntegerNull, // Has to come after the RootContext to make the context stack safe diff --git a/src/qml/jsruntime/qv4identifier.cpp b/src/qml/jsruntime/qv4identifier.cpp index 77510d95f6..69d44f89c4 100644 --- a/src/qml/jsruntime/qv4identifier.cpp +++ b/src/qml/jsruntime/qv4identifier.cpp @@ -107,7 +107,7 @@ IdentifierHashEntry *IdentifierHash::addEntry(const Identifier *identifier) const IdentifierHashEntry &e = d->entries[i]; if (!e.identifier) continue; - uint idx = e.identifier->hashValue % newAlloc; + uint idx = e.identifier->id % newAlloc; while (newEntries[idx].identifier) { ++idx; idx %= newAlloc; @@ -119,7 +119,7 @@ IdentifierHashEntry *IdentifierHash::addEntry(const Identifier *identifier) d->alloc = newAlloc; } - uint idx = identifier->hashValue % d->alloc; + uint idx = identifier->id % d->alloc; while (d->entries[idx].identifier) { Q_ASSERT(d->entries[idx].identifier != identifier); ++idx; @@ -136,7 +136,7 @@ const IdentifierHashEntry *IdentifierHash::lookup(const Identifier *identifier) return nullptr; Q_ASSERT(d->entries); - uint idx = identifier->hashValue % d->alloc; + uint idx = identifier->id % d->alloc; while (1) { if (!d->entries[idx].identifier) return nullptr; diff --git a/src/qml/jsruntime/qv4identifier_p.h b/src/qml/jsruntime/qv4identifier_p.h index c0c035479e..f3935950c8 100644 --- a/src/qml/jsruntime/qv4identifier_p.h +++ b/src/qml/jsruntime/qv4identifier_p.h @@ -66,7 +66,7 @@ struct ExecutionEngine; struct Identifier { - uint hashValue; + uint id; }; diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp index 9a86e4259f..cd5a7ebc3e 100644 --- a/src/qml/jsruntime/qv4identifiertable.cpp +++ b/src/qml/jsruntime/qv4identifiertable.cpp @@ -59,16 +59,19 @@ IdentifierTable::IdentifierTable(ExecutionEngine *engine) , numBits(8) { alloc = primeForNumBits(numBits); - entries = (Heap::String **)malloc(alloc*sizeof(Heap::String *)); - memset(entries, 0, alloc*sizeof(Heap::String *)); + entriesByHash = (Heap::String **)malloc(alloc*sizeof(Heap::String *)); + entriesById = (Heap::String **)malloc(alloc*sizeof(Heap::String *)); + memset(entriesByHash, 0, alloc*sizeof(Heap::String *)); + memset(entriesById, 0, alloc*sizeof(Heap::String *)); } IdentifierTable::~IdentifierTable() { for (int i = 0; i < alloc; ++i) - if (entries[i]) - delete entries[i]->identifier; - free(entries); + if (entriesByHash[i]) + delete entriesByHash[i]->identifier; + free(entriesByHash); + free(entriesById); } void IdentifierTable::addEntry(Heap::String *str) @@ -79,7 +82,7 @@ void IdentifierTable::addEntry(Heap::String *str) return; str->identifier = new Identifier; - str->identifier->hashValue = hash; + str->identifier->id = engine->nextStringOrSymbolId(); bool grow = (alloc <= size*2); @@ -89,7 +92,7 @@ void IdentifierTable::addEntry(Heap::String *str) Heap::String **newEntries = (Heap::String **)malloc(newAlloc*sizeof(Heap::String *)); memset(newEntries, 0, newAlloc*sizeof(Heap::String *)); for (int i = 0; i < alloc; ++i) { - Heap::String *e = entries[i]; + Heap::String *e = entriesByHash[i]; if (!e) continue; uint idx = e->stringHash % newAlloc; @@ -99,17 +102,42 @@ void IdentifierTable::addEntry(Heap::String *str) } newEntries[idx] = e; } - free(entries); - entries = newEntries; + free(entriesByHash); + entriesByHash = newEntries; + + newEntries = (Heap::String **)malloc(newAlloc*sizeof(Heap::String *)); + memset(newEntries, 0, newAlloc*sizeof(Heap::String *)); + for (int i = 0; i < alloc; ++i) { + Heap::String *e = entriesById[i]; + if (!e) + continue; + uint idx = e->identifier->id % newAlloc; + while (newEntries[idx]) { + ++idx; + idx %= newAlloc; + } + newEntries[idx] = e; + } + free(entriesById); + entriesById = newEntries; + alloc = newAlloc; } uint idx = hash % alloc; - while (entries[idx]) { + while (entriesByHash[idx]) { + ++idx; + idx %= alloc; + } + entriesByHash[idx] = str; + + idx = str->identifier->id % alloc; + while (entriesById[idx]) { ++idx; idx %= alloc; } - entries[idx] = str; + entriesById[idx] = str; + ++size; } @@ -120,7 +148,7 @@ Heap::String *IdentifierTable::insertString(const QString &s) uint subtype; uint hash = String::createHashValue(s.constData(), s.length(), &subtype); uint idx = hash % alloc; - while (Heap::String *e = entries[idx]) { + while (Heap::String *e = entriesByHash[idx]) { if (e->stringHash == hash && e->toQString() == s) return e; ++idx; @@ -144,7 +172,7 @@ Identifier *IdentifierTable::identifierImpl(const Heap::String *str) return nullptr; uint idx = hash % alloc; - while (Heap::String *e = entries[idx]) { + while (Heap::String *e = entriesByHash[idx]) { if (e->stringHash == hash && e->isEqualTo(str)) { str->identifier = e->identifier; return e->identifier; @@ -162,9 +190,9 @@ Heap::String *IdentifierTable::stringFromIdentifier(const Identifier *i) const if (!i) return nullptr; - uint idx = i->hashValue % alloc; + uint idx = i->id % alloc; while (1) { - Heap::String *e = entries[idx]; + Heap::String *e = entriesById[idx]; Q_ASSERT(e); if (e->identifier == i) return e; @@ -187,7 +215,7 @@ Identifier *IdentifierTable::identifier(const char *s, int len) QLatin1String latin(s, len); uint idx = hash % alloc; - while (Heap::String *e = entries[idx]) { + while (Heap::String *e = entriesByHash[idx]) { if (e->stringHash == hash && e->toQString() == latin) return e->identifier; ++idx; diff --git a/src/qml/jsruntime/qv4identifiertable_p.h b/src/qml/jsruntime/qv4identifiertable_p.h index 2210a866fb..0c8de01f71 100644 --- a/src/qml/jsruntime/qv4identifiertable_p.h +++ b/src/qml/jsruntime/qv4identifiertable_p.h @@ -66,7 +66,8 @@ struct IdentifierTable int alloc; int size; int numBits; - Heap::String **entries; + Heap::String **entriesByHash; + Heap::String **entriesById; void addEntry(Heap::String *str); @@ -95,7 +96,7 @@ public: void mark(MarkStack *markStack) { for (int i = 0; i < alloc; ++i) { - Heap::String *entry = entries[i]; + Heap::String *entry = entriesByHash[i]; if (!entry || entry->isMarked()) continue; entry->setMarkBit(); diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp index 4c7eb7b185..532d35962c 100644 --- a/src/qml/jsruntime/qv4internalclass.cpp +++ b/src/qml/jsruntime/qv4internalclass.cpp @@ -77,7 +77,7 @@ void PropertyHash::addEntry(const PropertyHash::Entry &entry, int classSize) if (classSize < d->size || grow) detach(grow, classSize); - uint idx = entry.identifier->hashValue % d->alloc; + uint idx = entry.identifier->id % d->alloc; while (d->entries[idx].identifier) { ++idx; idx %= d->alloc; @@ -98,7 +98,7 @@ int PropertyHash::removeIdentifier(Identifier *identifier, int classSize) val = e.index; continue; } - uint idx = e.identifier->hashValue % dd->alloc; + uint idx = e.identifier->id % dd->alloc; while (dd->entries[idx].identifier) { ++idx; idx %= dd->alloc; @@ -124,7 +124,7 @@ void PropertyHash::detach(bool grow, int classSize) const Entry &e = d->entries[i]; if (!e.identifier || e.index >= static_cast(classSize)) continue; - uint idx = e.identifier->hashValue % dd->alloc; + uint idx = e.identifier->id % dd->alloc; while (dd->entries[idx].identifier) { ++idx; idx %= dd->alloc; diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h index 0b6f088bd3..11c12d012c 100644 --- a/src/qml/jsruntime/qv4internalclass_p.h +++ b/src/qml/jsruntime/qv4internalclass_p.h @@ -133,7 +133,7 @@ inline uint PropertyHash::lookup(const Identifier *identifier) const { Q_ASSERT(d->entries); - uint idx = identifier->hashValue % d->alloc; + uint idx = identifier->id % d->alloc; while (1) { if (d->entries[idx].identifier == identifier) return d->entries[idx].index; -- cgit v1.2.3