Skip to content

Commit 60a952e

Browse files
rmacnak-googlermacnak-google
committed
[vm] Avoid superlinear time canonicalizing deep constants.
Bug: #37523 Change-Id: Ia3c2514891e2e3f07d1b3266b019b142413918d3 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/109318 Reviewed-by: Siva Annamalai <[email protected]> Reviewed-by: Alexander Markov <[email protected]>
1 parent 730d2c6 commit 60a952e

13 files changed

+40592
-61
lines changed

‎pkg/vm/lib/bytecode/object_table.dart‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1190,6 +1190,7 @@ class _ConstObjectHandle extends ObjectHandle {
11901190
ConstTag tag;
11911191
dynamic value;
11921192
ObjectHandle type;
1193+
int _hashCode = 0;
11931194

11941195
_ConstObjectHandle._empty();
11951196

@@ -1356,34 +1357,41 @@ class _ConstObjectHandle extends ObjectHandle {
13561357

13571358
@override
13581359
int get hashCode {
1360+
if (_hashCode != 0) {
1361+
return _hashCode;
1362+
}
13591363
switch (tag) {
13601364
case ConstTag.kInt:
13611365
case ConstTag.kDouble:
13621366
case ConstTag.kBool:
13631367
case ConstTag.kTearOff:
13641368
case ConstTag.kSymbol:
1365-
return value.hashCode;
1369+
return _hashCode = value.hashCode;
13661370
case ConstTag.kInstance:
13671371
{
13681372
final fieldValues = value as Map<ObjectHandle, ObjectHandle>;
1369-
return _combineHashes(type.hashCode, mapHashCode(fieldValues));
1373+
return _hashCode =
1374+
_combineHashes(type.hashCode, mapHashCode(fieldValues));
13701375
}
13711376
break;
13721377
case ConstTag.kList:
13731378
{
13741379
final elems = value as List<ObjectHandle>;
1375-
return _combineHashes(type.hashCode, listHashCode(elems));
1380+
return _hashCode = _combineHashes(type.hashCode, listHashCode(elems));
13761381
}
13771382
break;
13781383
case ConstTag.kTearOffInstantiation:
1379-
return _combineHashes(value.hashCode, type.hashCode);
1384+
return _hashCode = _combineHashes(value.hashCode, type.hashCode);
13801385
default:
13811386
throw 'Unexpected constant tag: $tag';
13821387
}
13831388
}
13841389

13851390
@override
13861391
bool operator ==(other) {
1392+
if (identical(this, other)) {
1393+
return true;
1394+
}
13871395
if (other is _ConstObjectHandle && this.tag == other.tag) {
13881396
switch (tag) {
13891397
case ConstTag.kInt:

‎runtime/vm/class_finalizer.cc‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1576,13 +1576,13 @@ void ClassFinalizer::RemapClassIds(intptr_t* old_to_new_cid) {
15761576
// * RawType::hash_
15771577
// * RawTypeParameter::hash_
15781578
// * RawTypeArguments::hash_
1579+
// * RawInstance (weak table)
1580+
// * RawArray (weak table)
15791581
//
15801582
// No caching of canonical hash codes (i.e. it gets re-computed every time)
15811583
// happens for:
15821584
//
15831585
// * RawTypeRef (computed via RawTypeRef::type_->type_class_id)
1584-
// * RawInstance (computed via size & fields)
1585-
// * RawArray (computed via type arguments & array entries)
15861586
//
15871587
// Usages of canonical hash codes are:
15881588
//

‎runtime/vm/heap/heap.cc‎

Lines changed: 3 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -829,16 +829,9 @@ int64_t Heap::PeerCount() const {
829829
return new_weak_tables_[kPeers]->count() + old_weak_tables_[kPeers]->count();
830830
}
831831

832-
#if !defined(HASH_IN_OBJECT_HEADER)
833-
int64_t Heap::HashCount() const {
834-
return new_weak_tables_[kHashes]->count() +
835-
old_weak_tables_[kHashes]->count();
836-
}
837-
#endif
838-
839-
int64_t Heap::ObjectIdCount() const {
840-
return new_weak_tables_[kObjectIds]->count() +
841-
old_weak_tables_[kObjectIds]->count();
832+
void Heap::ResetCanonicalHashTable() {
833+
new_weak_tables_[kCanonicalHashes]->Reset();
834+
old_weak_tables_[kCanonicalHashes]->Reset();
842835
}
843836

844837
void Heap::ResetObjectIdTable() {

‎runtime/vm/heap/heap.h‎

Lines changed: 12 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -40,8 +40,9 @@ class Heap {
4040
enum WeakSelector {
4141
kPeers = 0,
4242
#if !defined(HASH_IN_OBJECT_HEADER)
43-
kHashes,
43+
kIdentityHashes,
4444
#endif
45+
kCanonicalHashes,
4546
kObjectIds,
4647
kNumWeakSelectors
4748
};
@@ -208,13 +209,20 @@ class Heap {
208209
// Associate an identity hashCode with an object. An non-existent hashCode
209210
// is equal to 0.
210211
void SetHash(RawObject* raw_obj, intptr_t hash) {
211-
SetWeakEntry(raw_obj, kHashes, hash);
212+
SetWeakEntry(raw_obj, kIdentityHashes, hash);
212213
}
213214
intptr_t GetHash(RawObject* raw_obj) const {
214-
return GetWeakEntry(raw_obj, kHashes);
215+
return GetWeakEntry(raw_obj, kIdentityHashes);
215216
}
216217
#endif
217-
int64_t HashCount() const;
218+
219+
void SetCanonicalHash(RawObject* raw_obj, intptr_t hash) {
220+
SetWeakEntry(raw_obj, kCanonicalHashes, hash);
221+
}
222+
intptr_t GetCanonicalHash(RawObject* raw_obj) const {
223+
return GetWeakEntry(raw_obj, kCanonicalHashes);
224+
}
225+
void ResetCanonicalHashTable();
218226

219227
// Associate an id with an object (used when serializing an object).
220228
// A non-existant id is equal to 0.
@@ -226,7 +234,6 @@ class Heap {
226234
ASSERT(Thread::Current()->IsMutatorThread());
227235
return GetWeakEntry(raw_obj, kObjectIds);
228236
}
229-
int64_t ObjectIdCount() const;
230237
void ResetObjectIdTable();
231238

232239
// Used by the GC algorithms to propagate weak entries.

‎runtime/vm/isolate.cc‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -215,9 +215,12 @@ void Isolate::ValidateClassTable() {
215215
#endif // DEBUG
216216

217217
void Isolate::RehashConstants() {
218-
StackZone stack_zone(Thread::Current());
218+
Thread* thread = Thread::Current();
219+
StackZone stack_zone(thread);
219220
Zone* zone = stack_zone.GetZone();
220221

222+
thread->heap()->ResetCanonicalHashTable();
223+
221224
Class& cls = Class::Handle(zone);
222225
intptr_t top = class_table()->NumCids();
223226
for (intptr_t cid = kInstanceCid; cid < top; cid++) {

‎runtime/vm/isolate_reload_test.cc‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2939,6 +2939,39 @@ TEST_CASE(IsolateReload_ShapeChangeRetainsHash) {
29392939
EXPECT_STREQ("true", SimpleInvokeStr(lib, "main"));
29402940
}
29412941

2942+
TEST_CASE(IsolateReload_ShapeChangeRetainsHash_Const) {
2943+
const char* kScript =
2944+
"class A {\n"
2945+
" final x;\n"
2946+
" const A(this.x);\n"
2947+
"}\n"
2948+
"var a, hash1, hash2;\n"
2949+
"main() {\n"
2950+
" a = const A(1);\n"
2951+
" hash1 = a.hashCode;\n"
2952+
" return 'okay';\n"
2953+
"}\n";
2954+
2955+
Dart_Handle lib = TestCase::LoadTestScript(kScript, NULL);
2956+
EXPECT_VALID(lib);
2957+
EXPECT_STREQ("okay", SimpleInvokeStr(lib, "main"));
2958+
2959+
const char* kReloadScript =
2960+
"class A {\n"
2961+
" final x, y, z;\n"
2962+
" const A(this.x, this.y, this.z);\n"
2963+
"}\n"
2964+
"var a, hash1, hash2;\n"
2965+
"main() {\n"
2966+
" hash2 = a.hashCode;\n"
2967+
" return (hash1 == hash2).toString();\n"
2968+
"}\n";
2969+
2970+
lib = TestCase::ReloadTestScript(kReloadScript);
2971+
EXPECT_VALID(lib);
2972+
EXPECT_STREQ("true", SimpleInvokeStr(lib, "main"));
2973+
}
2974+
29422975
TEST_CASE(IsolateReload_StaticTearOffRetainsHash) {
29432976
const char* kScript =
29442977
"foo() {}\n"

‎runtime/vm/object.cc‎

Lines changed: 23 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4925,7 +4925,10 @@ void Class::RehashConstants(Zone* zone) const {
49254925
while (it.MoveNext()) {
49264926
constant ^= set.GetKey(it.Current());
49274927
ASSERT(!constant.IsNull());
4928-
ASSERT(constant.IsCanonical());
4928+
// Shape changes lose the canonical bit because they may result/ in merging
4929+
// constants. E.g., [x1, y1], [x1, y2] -> [x1].
4930+
DEBUG_ASSERT(constant.IsCanonical() ||
4931+
Isolate::Current()->HasAttemptedReload());
49294932
InsertCanonicalConstant(zone, constant);
49304933
}
49314934
set.Release();
@@ -16490,18 +16493,25 @@ uint32_t Instance::CanonicalizeHash() const {
1649016493
if (IsNull()) {
1649116494
return 2011;
1649216495
}
16493-
NoSafepointScope no_safepoint;
16496+
Thread* thread = Thread::Current();
16497+
uint32_t hash = thread->heap()->GetCanonicalHash(raw());
16498+
if (hash != 0) {
16499+
return hash;
16500+
}
16501+
NoSafepointScope no_safepoint(thread);
1649416502
const intptr_t instance_size = SizeFromClass();
1649516503
ASSERT(instance_size != 0);
16496-
uint32_t hash = instance_size / kWordSize;
16504+
hash = instance_size / kWordSize;
1649716505
uword this_addr = reinterpret_cast<uword>(this->raw_ptr());
1649816506
Instance& member = Instance::Handle();
1649916507
for (intptr_t offset = Instance::NextFieldOffset(); offset < instance_size;
1650016508
offset += kWordSize) {
1650116509
member ^= *reinterpret_cast<RawObject**>(this_addr + offset);
1650216510
hash = CombineHashes(hash, member.CanonicalizeHash());
1650316511
}
16504-
return FinalizeHash(hash, String::kHashBits);
16512+
hash = FinalizeHash(hash, String::kHashBits);
16513+
thread->heap()->SetCanonicalHash(raw(), hash);
16514+
return hash;
1650516515
}
1650616516

1650716517
#if defined(DEBUG)
@@ -20727,19 +20737,25 @@ bool Array::CanonicalizeEquals(const Instance& other) const {
2072720737
}
2072820738

2072920739
uint32_t Array::CanonicalizeHash() const {
20730-
NoSafepointScope no_safepoint;
2073120740
intptr_t len = Length();
2073220741
if (len == 0) {
2073320742
return 1;
2073420743
}
20735-
uint32_t hash = len;
20744+
Thread* thread = Thread::Current();
20745+
uint32_t hash = thread->heap()->GetCanonicalHash(raw());
20746+
if (hash != 0) {
20747+
return hash;
20748+
}
20749+
hash = len;
2073620750
Instance& member = Instance::Handle(GetTypeArguments());
2073720751
hash = CombineHashes(hash, member.CanonicalizeHash());
2073820752
for (intptr_t i = 0; i < len; i++) {
2073920753
member ^= At(i);
2074020754
hash = CombineHashes(hash, member.CanonicalizeHash());
2074120755
}
20742-
return FinalizeHash(hash, kHashBits);
20756+
hash = FinalizeHash(hash, kHashBits);
20757+
thread->heap()->SetCanonicalHash(raw(), hash);
20758+
return hash;
2074320759
}
2074420760

2074520761
RawArray* Array::New(intptr_t len, Heap::Space space) {

‎runtime/vm/raw_object.h‎

Lines changed: 4 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -358,6 +358,10 @@ class RawObject {
358358
return IsFreeListElement() || IsForwardingCorpse();
359359
}
360360

361+
intptr_t GetClassId() const {
362+
uint32_t tags = ptr()->tags_;
363+
return ClassIdTag::decode(tags);
364+
}
361365
intptr_t GetClassIdMayBeSmi() const {
362366
return IsHeapObject() ? GetClassId() : static_cast<intptr_t>(kSmiCid);
363367
}
@@ -504,11 +508,6 @@ class RawObject {
504508

505509
intptr_t HeapSizeFromClass() const;
506510

507-
intptr_t GetClassId() const {
508-
uint32_t tags = ptr()->tags_;
509-
return ClassIdTag::decode(tags);
510-
}
511-
512511
void SetClassId(intptr_t new_cid) {
513512
uint32_t tags = ptr()->tags_;
514513
ptr()->tags_ = ClassIdTag::update(new_cid, tags);
@@ -660,12 +659,7 @@ class RawObject {
660659
friend class StoreBufferUpdateVisitor; // RememberCard
661660
void RememberCard(RawObject* const* slot);
662661

663-
friend class Api;
664-
friend class ApiMessageReader; // GetClassId
665-
friend class Serializer; // GetClassId
666662
friend class Array;
667-
friend class Become; // GetClassId
668-
friend class CompactorTask; // GetClassId
669663
friend class ByteBuffer;
670664
friend class CidRewriteVisitor;
671665
friend class Closure;
@@ -681,25 +675,15 @@ class RawObject {
681675
friend class ForwardList;
682676
friend class GrowableObjectArray; // StorePointer
683677
friend class Heap;
684-
friend class HeapMapAsJSONVisitor;
685678
friend class ClassStatsVisitor;
686679
template <bool>
687680
friend class MarkingVisitorBase;
688681
friend class Mint;
689682
friend class Object;
690683
friend class OneByteString; // StoreSmi
691-
friend class RawCode;
692-
friend class RawExternalTypedData;
693-
friend class RawInstructions;
694684
friend class RawInstance;
695-
friend class RawString;
696-
friend class RawTypedData;
697-
friend class RawTypedDataView;
698685
friend class Scavenger;
699686
friend class ScavengerVisitor;
700-
friend class SizeExcludingClassVisitor; // GetClassId
701-
friend class InstanceAccumulator; // GetClassId
702-
friend class RetainingPathVisitor; // GetClassId
703687
friend class ImageReader; // tags_ check
704688
friend class ImageWriter;
705689
friend class AssemblyImageWriter;
@@ -708,29 +692,17 @@ class RawObject {
708692
friend class Deserializer;
709693
friend class SnapshotWriter;
710694
friend class String;
711-
friend class Type; // GetClassId
712-
friend class TypedDataBase; // GetClassId
713-
friend class TypedData; // GetClassId
714-
friend class TypedDataView; // GetClassId
715695
friend class WeakProperty; // StorePointer
716696
friend class Instance; // StorePointer
717697
friend class StackFrame; // GetCodeObject assertion.
718698
friend class CodeLookupTableBuilder; // profiler
719-
friend class NativeEntry; // GetClassId
720-
friend class WritePointerVisitor; // GetClassId
721699
friend class Interpreter;
722700
friend class InterpreterHelpers;
723701
friend class Simulator;
724702
friend class SimulatorHelpers;
725703
friend class ObjectLocator;
726-
friend class InstanceMorpher; // GetClassId
727-
friend class VerifyCanonicalVisitor;
728-
friend class ObjectGraph::Stack; // GetClassId
729-
friend class Precompiler; // GetClassId
730-
friend class ObjectOffsetTrait; // GetClassId
731704
friend class WriteBarrierUpdateVisitor; // CheckHeapPointerStore
732705
friend class OffsetsTable;
733-
friend class RawTransferableTypedData; // GetClassId
734706

735707
DISALLOW_ALLOCATION();
736708
DISALLOW_IMPLICIT_CONSTRUCTORS(RawObject);

0 commit comments

Comments
 (0)