[dart2js] Speed up FunctionSet.query by organizing nodes by private/public and private by URI.
All nodes that match must be visited and compared to the queried selector. By organizing private nodes by URI the scope of nodes that need to be visited us much smaller.
In a big application this reduced the runtime of phase 2 by ~20s (~180s -> ~160s).
I see no significant memory difference from this change. +.1GB RSS according to DevTools directly after FunctionSets are initialized.
Change-Id: Id9c3a5ae84c7f0aad589cff89d4bec15e97758d8
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/268408
Reviewed-by: Sigmund Cherem <sigmund@google.com>
Commit-Queue: Nate Biggs <natebiggs@google.com>
diff --git a/pkg/compiler/lib/src/universe/function_set.dart b/pkg/compiler/lib/src/universe/function_set.dart
index 17b39ec..c55d88f 100644
--- a/pkg/compiler/lib/src/universe/function_set.dart
+++ b/pkg/compiler/lib/src/universe/function_set.dart
@@ -6,6 +6,7 @@
import '../common/names.dart' show Identifiers, Selectors;
import '../elements/entities.dart';
+import '../elements/names.dart';
import '../inferrer/abstract_value_domain.dart';
import '../util/util.dart' show Hashing, Setlet;
import 'selector.dart' show Selector;
@@ -14,26 +15,25 @@
// too and stricly they aren't functions. Maybe this needs a better
// name -- something like ElementSet seems a bit too generic.
class FunctionSet {
- final Map<String, FunctionSetNode> _nodes;
+ final Map<String, FunctionSetNode> _publicNodes;
+ final Map<Uri, Map<String, FunctionSetNode>> _privateNodes;
factory FunctionSet(Iterable<MemberEntity> liveInstanceMembers) {
- Map<String, FunctionSetNode> nodes = {};
+ Map<String, FunctionSetNode> publicNodes = {};
+ Map<Uri, Map<String, FunctionSetNode>> privateNodes = {};
for (MemberEntity member in liveInstanceMembers) {
String name = member.name!;
- (nodes[name] ??= FunctionSetNode(name)).add(member);
+ if (member.memberName.isPrivate) {
+ final uri = member.memberName.uri!;
+ ((privateNodes[uri] ??= {})[name] ??= FunctionSetNode()).add(member);
+ } else {
+ (publicNodes[name] ??= FunctionSetNode()).add(member);
+ }
}
- return FunctionSet.internal(nodes);
+ return FunctionSet.internal(publicNodes, privateNodes);
}
- FunctionSet.internal(this._nodes);
-
- bool contains(MemberEntity element) {
- assert(element.isInstanceMember);
- assert(!element.isAbstract);
- String name = element.name!;
- FunctionSetNode? node = _nodes[name];
- return (node != null) ? node.contains(element) : false;
- }
+ FunctionSet.internal(this._publicNodes, this._privateNodes);
/// Returns all the functions that may be invoked with the [selector] on a
/// receiver with the given [constraint]. The returned elements may include
@@ -67,12 +67,18 @@
/// 'noSuchMethod' methods where applicable.
FunctionSetQuery query(
Selector selector, AbstractValue? receiver, AbstractValueDomain domain) {
- String name = selector.name;
+ Name name = selector.memberName;
SelectorMask selectorMask = _createSelectorMask(selector, receiver, domain);
SelectorMask noSuchMethodMask =
SelectorMask(Selectors.noSuchMethod_, selectorMask.receiver);
- FunctionSetNode? node = _nodes[name];
- FunctionSetNode? noSuchMethods = _nodes[Identifiers.noSuchMethod_];
+ FunctionSetNode? node;
+ if (name.isPrivate) {
+ final forUri = _privateNodes[name.uri];
+ if (forUri != null) node = forUri[name.text];
+ } else {
+ node = _publicNodes[name.text];
+ }
+ FunctionSetNode? noSuchMethods = _publicNodes[Identifiers.noSuchMethod_];
if (node != null) {
return node.query(selectorMask, domain, noSuchMethods, noSuchMethodMask);
}
@@ -83,12 +89,6 @@
}
return noSuchMethods.query(noSuchMethodMask, domain);
}
-
- void forEach(void action(MemberEntity member)) {
- _nodes.forEach((String name, FunctionSetNode node) {
- node.forEach(action);
- });
- }
}
/// A selector/constraint pair representing the dynamic invocation of [selector]
@@ -105,8 +105,13 @@
String get name => selector.name;
- bool applies(MemberEntity element, AbstractValueDomain domain) {
- if (!selector.appliesUnnamed(element)) return false;
+ /// Check that the mask applies to the element. Skip checking the name since
+ /// this is called from [FunctionSet.query] which implicitly checks the name
+ /// via the Map lookups.
+ bool _applies(MemberEntity element, AbstractValueDomain domain) {
+ if (!selector.appliesStructural(element)) {
+ return false;
+ }
return domain
.isTargetingMember(receiver, element, selector.memberName)
.isPotentiallyTrue;
@@ -133,7 +138,6 @@
/// A node in the [FunctionSet] caching all [FunctionSetQuery] object for
/// selectors with the same [name].
class FunctionSetNode {
- final String name;
final Map<SelectorMask, FunctionSetQuery> cache = {};
// Initially, we keep the elements in a list because it is more
@@ -143,10 +147,9 @@
Iterable<MemberEntity> elements = [];
bool isList = true;
- FunctionSetNode(this.name);
+ FunctionSetNode();
void add(MemberEntity element) {
- assert(element.name == name);
// We try to avoid clearing the cache unless we have to. For that
// reason we keep the explicit contains check even though the add
// method ends up doing the work again (for sets).
@@ -167,7 +170,6 @@
}
void remove(MemberEntity element) {
- assert(element.name == name);
if (isList) {
final list = elements as List<MemberEntity>;
int index = list.indexOf(element);
@@ -189,7 +191,6 @@
}
bool contains(MemberEntity element) {
- assert(element.name == name);
return elements.contains(element);
}
@@ -201,13 +202,12 @@
/// including no such method handling where applicable.
FunctionSetQuery query(SelectorMask selectorMask, AbstractValueDomain domain,
[FunctionSetNode? noSuchMethods, SelectorMask? noSuchMethodMask]) {
- assert(selectorMask.name == name);
FunctionSetQuery? result = cache[selectorMask];
if (result != null) return result;
Setlet<MemberEntity>? functions;
for (MemberEntity element in elements) {
- if (selectorMask.applies(element, domain)) {
+ if (selectorMask._applies(element, domain)) {
// Defer the allocation of the functions set until we are
// sure we need it. This allows us to return immutable empty
// lists when the filtering produced no results.
diff --git a/pkg/compiler/lib/src/universe/selector.dart b/pkg/compiler/lib/src/universe/selector.dart
index df925fc..b4f6902 100644
--- a/pkg/compiler/lib/src/universe/selector.dart
+++ b/pkg/compiler/lib/src/universe/selector.dart
@@ -240,6 +240,11 @@
if (!memberName.matches(element.memberName)) {
return false;
}
+ return appliesStructural(element);
+ }
+
+ bool appliesStructural(MemberEntity element) {
+ assert(name == element.name);
if (element.isSetter) return isSetter;
if (element.isGetter) return isGetter || isCall;
if (element is FieldEntity) {
