[vm/aot] Improve AOT compilation speed by using better hash codes
This change improves hash code implementations in multiple places in
the compiler. That reduces number of probes during lookups in hash maps
and improves AOT compilation time of large applications.
On a large Flutter app, compiled in release mode for arm64:
Total gen_snapshot time 89.184s -> 60.736s (-31.9%)
Also, this change adds --hash_map_probes_limit=N option which sets
a hard limit for the number of probes in hash maps. This option
makes it easy to find hash maps where there are many collisions
due to poor hash code implementation.
TEST=ci
Issue: https://github.com/dart-lang/sdk/issues/43299
Bug: b/154155290
Change-Id: Ibf6f37d4b9f3bf42dd6731bfb4095a7305b98b2d
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/229240
Reviewed-by: Martin Kustermann <kustermann@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/vm/compiler/aot/precompiler.h b/runtime/vm/compiler/aot/precompiler.h
index 2b74839..4be44f3 100644
--- a/runtime/vm/compiler/aot/precompiler.h
+++ b/runtime/vm/compiler/aot/precompiler.h
@@ -219,7 +219,7 @@
static Value ValueOf(Pair kv) { return kv; }
- static inline uword Hash(Key key) { return key->GetClassId(); }
+ static inline uword Hash(Key key) { return key->CanonicalizeHash(); }
static inline bool IsKeyEqual(Pair pair, Key key) {
return pair->ptr() == key->ptr();
diff --git a/runtime/vm/compiler/runtime_api.cc b/runtime/vm/compiler/runtime_api.cc
index bc2daf8..a0cca50 100644
--- a/runtime/vm/compiler/runtime_api.cc
+++ b/runtime/vm/compiler/runtime_api.cc
@@ -101,6 +101,11 @@
if (obj.IsNull()) {
return kNullIdentityHash;
}
+ // TypeArguments should be handled before Instance as TypeArguments extends
+ // Instance and TypeArguments::CanonicalizeHash just returns 0.
+ if (obj.IsTypeArguments()) {
+ return TypeArguments::Cast(obj).Hash();
+ }
if (obj.IsInstance()) {
return Instance::Cast(obj).CanonicalizeHash();
}
@@ -121,6 +126,10 @@
return obj.GetClassId();
}
+const char* ObjectToCString(const Object& obj) {
+ return obj.ToCString();
+}
+
void SetToNull(Object* obj) {
*obj = Object::null();
}
diff --git a/runtime/vm/compiler/runtime_api.h b/runtime/vm/compiler/runtime_api.h
index 0559b8c..af57f4ef 100644
--- a/runtime/vm/compiler/runtime_api.h
+++ b/runtime/vm/compiler/runtime_api.h
@@ -181,6 +181,9 @@
// or canonical hash.
intptr_t ObjectHash(const Object& obj);
+// Prints the given object into a C string.
+const char* ObjectToCString(const Object& obj);
+
// If the given object represents a Dart integer returns true and sets [value]
// to the value of the integer.
bool HasIntegerValue(const dart::Object& obj, int64_t* value);
diff --git a/runtime/vm/flag_list.h b/runtime/vm/flag_list.h
index 6e885be..3e0ea0f 100644
--- a/runtime/vm/flag_list.h
+++ b/runtime/vm/flag_list.h
@@ -143,6 +143,8 @@
P(marker_tasks, int, 2, \
"The number of tasks to spawn during old gen GC marking (0 means " \
"perform all marking on main thread).") \
+ P(hash_map_probes_limit, int, kMaxInt32, \
+ "Limit number of probes while doing lookups in hash maps.") \
P(max_polymorphic_checks, int, 4, \
"Maximum number of polymorphic check, otherwise it is megamorphic.") \
P(max_equality_polymorphic_checks, int, 32, \
diff --git a/runtime/vm/hash_map.h b/runtime/vm/hash_map.h
index aacbf87..a55f683 100644
--- a/runtime/vm/hash_map.h
+++ b/runtime/vm/hash_map.h
@@ -6,6 +6,7 @@
#define RUNTIME_VM_HASH_MAP_H_
#include "platform/utils.h"
+#include "vm/flags.h"
#include "vm/growable_array.h" // For Malloc, EmptyBase
#include "vm/hash.h"
#include "vm/zone.h"
@@ -132,6 +133,7 @@
uint32_t mask = hash_table_size_ - 1;
uint32_t hash_index = hash & mask;
uint32_t start = hash_index;
+ intptr_t probes = 0;
for (;;) {
uint32_t pair_index = hash_table_[hash_index];
if (pair_index == kEmpty) {
@@ -139,6 +141,7 @@
}
if (pair_index != kDeleted) {
ASSERT(pair_index < pairs_size_);
+ RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
if (KeyValueTrait::IsKeyEqual(pairs_[pair_index], key)) {
return &pairs_[pair_index];
}
@@ -233,6 +236,7 @@
uint32_t mask = hash_table_size_ - 1;
uint32_t hash_index = hash & mask;
uint32_t start = hash_index;
+ intptr_t probes = 0;
for (;;) {
uint32_t pair_index = hash_table_[hash_index];
if ((pair_index == kEmpty) || (pair_index == kDeleted)) {
@@ -241,6 +245,7 @@
next_pair_index_++;
break;
}
+ RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
ASSERT(pair_index < pairs_size_);
hash_index = (hash_index + 1) & mask;
// Hashtable must contain at least one empty marker.
@@ -273,6 +278,7 @@
uint32_t mask = hash_table_size_ - 1;
uint32_t hash_index = hash & mask;
uint32_t start = hash_index;
+ intptr_t probes = 0;
for (;;) {
uint32_t pair_index = hash_table_[hash_index];
if (pair_index == kEmpty) {
@@ -280,6 +286,7 @@
}
if (pair_index != kDeleted) {
ASSERT(pair_index < pairs_size_);
+ RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
if (KeyValueTrait::IsKeyEqual(pairs_[pair_index], key)) {
hash_table_[hash_index] = kDeleted;
pairs_[pair_index] = typename KeyValueTrait::Pair();
diff --git a/runtime/vm/object.h b/runtime/vm/object.h
index 6320a45..99c91df 100644
--- a/runtime/vm/object.h
+++ b/runtime/vm/object.h
@@ -5887,6 +5887,11 @@
return memcmp(untag(), other.untag(), InstanceSize(Length())) == 0;
}
+ uint32_t Hash() const {
+ NoSafepointScope no_safepoint;
+ return HashBytes(Data(), Length());
+ }
+
void PrintToJSONObject(JSONObject* jsobj, bool ref) const;
private:
diff --git a/runtime/vm/program_visitor.cc b/runtime/vm/program_visitor.cc
index b7f31f3..feba7b0 100644
--- a/runtime/vm/program_visitor.cc
+++ b/runtime/vm/program_visitor.cc
@@ -1020,7 +1020,7 @@
static inline uword Hash(Key key) {
ASSERT(!key->IsNull());
- return Utils::WordHash(key->Length());
+ return Utils::WordHash(key->Hash());
}
static inline bool IsKeyEqual(Pair pair, Key key) {
@@ -1070,7 +1070,14 @@
static inline uword Hash(Key key) {
ASSERT(!key->IsNull());
- return Utils::WordHash(key->Length());
+ ASSERT(Thread::Current()->no_safepoint_scope_depth() > 0);
+ const intptr_t len = key->Length();
+ uint32_t hash = Utils::WordHash(len);
+ for (intptr_t i = 0; i < len; ++i) {
+ hash =
+ CombineHashes(hash, Utils::WordHash(static_cast<uword>(key->At(i))));
+ }
+ return hash;
}
static inline bool IsKeyEqual(Pair pair, Key key) {
@@ -1128,6 +1135,9 @@
};
StackZone stack_zone(thread);
+ // ArrayKeyValueTrait::Hash is based on object addresses, so make
+ // sure GC doesn't happen and doesn't move objects.
+ NoSafepointScope no_safepoint;
DedupListsVisitor visitor(thread->zone());
WalkProgram(thread->zone(), thread->isolate_group(), &visitor);
}
