Simplify the FunctionSet implementation and remove a slightly broken optimization from SelectorMap.
This saves around 70 ms when compiling swarm, so it's not a big deal performance-wise
but the code is much simpler.
R=ngeoffray@google.com
BUG=
Review URL: https://codereview.chromium.org//12261005
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart@18444 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/sdk/lib/_internal/compiler/implementation/universe/function_set.dart b/sdk/lib/_internal/compiler/implementation/universe/function_set.dart
index 7e119da..6afdf09 100644
--- a/sdk/lib/_internal/compiler/implementation/universe/function_set.dart
+++ b/sdk/lib/_internal/compiler/implementation/universe/function_set.dart
@@ -7,51 +7,47 @@
// TODO(kasperl): This actually holds getters and setters just fine
// too and stricly they aren't functions. Maybe this needs a better
// name -- something like ElementSet seems a bit too generic.
-class FunctionSet extends PartialTypeTree {
+class FunctionSet {
+ final Compiler compiler;
+ final Map<SourceString, FunctionSetNode> nodes =
+ new Map<SourceString, FunctionSetNode>();
+ FunctionSet(this.compiler);
- FunctionSet(Compiler compiler) : super(compiler);
-
- FunctionSetNode newSpecializedNode(ClassElement type)
- => new FunctionSetNode(type);
-
- // TODO(kasperl): Allow static members too?
void add(Element element) {
assert(element.isMember());
- FunctionSetNode node = findNode(element.getEnclosingClass(), true);
- node.membersByName[element.name] = element;
+ SourceString name = element.name;
+ FunctionSetNode node = nodes.putIfAbsent(
+ name, () => new FunctionSetNode(name));
+ node.add(element);
}
- // TODO(kasperl): Allow static members too?
void remove(Element element) {
assert(element.isMember());
- FunctionSetNode node = findNode(element.getEnclosingClass(), false);
- if (node != null) node.membersByName.remove(element.name);
+ SourceString name = element.name;
+ FunctionSetNode node = nodes[name];
+ if (node != null) {
+ node.remove(element);
+ }
}
- // TODO(kasperl): Allow static members too?
bool contains(Element element) {
assert(element.isMember());
- FunctionSetNode node = findNode(element.getEnclosingClass(), false);
+ SourceString name = element.name;
+ FunctionSetNode node = nodes[name];
return (node != null)
- ? node.membersByName.containsKey(element.name)
+ ? node.contains(element)
: false;
}
- bool shouldVisitAll(Selector selector) {
- // TODO(kasperl): For now, we use a different implementation for
- // filtering if the tree contains interface subtypes.
- return containsInterfaceSubtypes
- && (selector.typeKind == TypedSelectorKind.INTERFACE
- || selector.typeKind == TypedSelectorKind.UNKNOWN);
- }
-
/**
* Returns all elements that may be invoked with the given [selector].
*/
- Set<Element> filterBySelector(Selector selector) {
- return shouldVisitAll(selector)
- ? filterAllBySelector(selector)
- : filterHierarchyBySelector(selector);
+ Iterable<Element> filterBySelector(Selector selector) {
+ SourceString name = selector.name;
+ FunctionSetNode node = nodes[name];
+ return (node != null)
+ ? node.filter(selector, compiler)
+ : const <Element>[];
}
/**
@@ -59,86 +55,92 @@
* [selector].
*/
bool hasAnyElementMatchingSelector(Selector selector) {
- return shouldVisitAll(selector)
- ? hasAnyInAll(selector)
- : hasAnyInHierarchy(selector);
+ return !filterBySelector(selector).isEmpty;
}
- Set<Element> filterAllBySelector(Selector selector) {
- Set<Element> result = new Set<Element>();
- if (root == null) return result;
- root.visitRecursively((FunctionSetNode node) {
- Element member = node.membersByName[selector.name];
- // Since we're running through the entire tree we have to use
- // the applies method that takes types into account.
- if (member != null && selector.appliesUnnamed(member, compiler)) {
- result.add(member);
- }
- return true;
- });
- return result;
- }
-
- Set<Element> filterHierarchyBySelector(Selector selector) {
- Set<Element> result = new Set<Element>();
- if (root == null) return result;
- visitHierarchy(selectorType(selector), (FunctionSetNode node) {
- Element member = node.membersByName[selector.name];
- if (member != null && selector.appliesUntyped(member, compiler)) {
- result.add(member);
- }
- return true;
- });
- return result;
- }
-
- bool hasAnyInAll(Selector selector) {
- bool result = false;
- if (root == null) return result;
- root.visitRecursively((FunctionSetNode node) {
- Element member = node.membersByName[selector.name];
- // Since we're running through the entire tree we have to use
- // the applies method that takes types into account.
- if (member != null && selector.appliesUnnamed(member, compiler)) {
- result = true;
- // End the traversal.
- return false;
- }
- return true;
- });
- return result;
- }
-
- bool hasAnyInHierarchy(Selector selector) {
- bool result = false;
- if (root == null) return result;
- visitHierarchy(selectorType(selector), (FunctionSetNode node) {
- Element member = node.membersByName[selector.name];
- if (member != null && selector.appliesUntyped(member, compiler)) {
- result = true;
- // End the traversal.
- return false;
- }
- return true;
- });
- return result;
- }
-
- void forEach(Function f) {
- if (root == null) return;
- root.visitRecursively((FunctionSetNode node) {
- node.membersByName.forEach(
- (SourceString _, Element element) => f(element));
- return true;
+ void forEach(Function action) {
+ nodes.forEach((SourceString name, FunctionSetNode node) {
+ node.forEach(action);
});
}
}
-class FunctionSetNode extends PartialTypeTreeNode {
+class FunctionSetNode {
+ final SourceString name;
+ final Map<Selector, List<Element>> cache = new Map<Selector, List<Element>>();
- final Map<SourceString, Element> membersByName;
+ // Initially, we keep the elements in a list because it is more
+ // compact than a hash set. Once we get enough elements, we change
+ // the representation to be a set to get faster contains checks.
+ static const int MAX_ELEMENTS_IN_LIST = 8;
+ Collection<Element> elements = <Element>[];
+ bool isList = true;
- FunctionSetNode(ClassElement type) : super(type),
- membersByName = new Map<SourceString, Element>();
+ FunctionSetNode(this.name);
+ void add(Element 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).
+ if (!elements.contains(element)) {
+ if (isList && elements.length >= MAX_ELEMENTS_IN_LIST) {
+ elements = elements.toSet();
+ isList = false;
+ }
+ elements.add(element);
+ cache.clear();
+ }
+ }
+
+ void remove(Element element) {
+ assert(element.name == name);
+ if (isList) {
+ List list = elements;
+ int index = list.indexOf(element);
+ if (index < 0) return;
+ Element last = list.removeLast();
+ if (index != list.length) {
+ list[index] = last;
+ }
+ cache.clear();
+ } else {
+ Set set = elements;
+ if (set.remove(element)) {
+ // To avoid wobbling between the two representations, we do
+ // not transition back to the list representation even if we
+ // end up with few enough elements at this point.
+ cache.clear();
+ }
+ }
+ }
+
+ bool contains(Element element) {
+ assert(element.name == name);
+ return elements.contains(element);
+ }
+
+ void forEach(Function action) {
+ elements.forEach(action);
+ }
+
+ Iterable<Element> filter(Selector selector, Compiler compiler) {
+ assert(selector.name == name);
+ List<Element> result = cache[selector];
+ if (result != null) return result;
+ for (Element element in elements) {
+ if (selector.appliesUnnamed(element, compiler)) {
+ if (result == null) {
+ // Defer the allocation of the resulting list until we are
+ // sure we need it. This allows us to return immutable empty
+ // lists when the filtering produced no results.
+ result = <Element>[];
+ }
+ result.add(element);
+ }
+ }
+ if (result == null) result = const <Element>[];
+ cache[selector] = result;
+ return result;
+ }
}
diff --git a/sdk/lib/_internal/compiler/implementation/universe/partial_type_tree.dart b/sdk/lib/_internal/compiler/implementation/universe/partial_type_tree.dart
index 53be749..b0ed8dc 100644
--- a/sdk/lib/_internal/compiler/implementation/universe/partial_type_tree.dart
+++ b/sdk/lib/_internal/compiler/implementation/universe/partial_type_tree.dart
@@ -5,62 +5,18 @@
part of universe;
abstract class PartialTypeTree {
-
final Compiler compiler;
PartialTypeTreeNode root;
- final Map<ClassElement, PartialTypeTreeNode> nodes =
- new Map<ClassElement, PartialTypeTreeNode>();
-
- // TODO(kasperl): For now, we keep track of whether or not the tree
- // contains two classes with a subtype relationship that isn't a
- // subclass relationship.
- bool containsInterfaceSubtypes = false;
-
- final Set<ClassElement> unseenInterfaceSubtypes =
- new Set<ClassElement>();
-
PartialTypeTree(this.compiler);
- PartialTypeTreeNode newSpecializedNode(ClassElement type);
+ PartialTypeTreeNode newNode(ClassElement type);
- PartialTypeTreeNode newNode(ClassElement type) {
- PartialTypeTreeNode node = newSpecializedNode(type);
- nodes[type] = node;
- if (containsInterfaceSubtypes) return node;
-
- // Check if the implied interface of the new class is implemented
- // by another class that is already in the tree.
- if (unseenInterfaceSubtypes.contains(type)) {
- containsInterfaceSubtypes = true;
- unseenInterfaceSubtypes.clear();
- return node;
- }
-
- // Run through all the implied interfaces the class that we're
- // adding implements and see if any of them are already in the
- // tree. If so, we have a tree with interface subtypes. If not,
- // keep track of them so we can deal with it if the interface is
- // added to the tree later.
- for (Link link = type.interfaces; !link.isEmpty; link = link.tail) {
- InterfaceType superType = link.head;
- ClassElement superTypeElement = superType.element;
- if (nodes.containsKey(superTypeElement)) {
- containsInterfaceSubtypes = true;
- unseenInterfaceSubtypes.clear();
- break;
- } else {
- unseenInterfaceSubtypes.add(superTypeElement);
- }
- }
- return node;
- }
-
- // TODO(kasperl): Move this to the Selector class?
/**
* Returns a [ClassElement] that is an upper bound of the receiver type on
* [selector].
*/
+ // TODO(kasperl): Move this to the Selector class?
ClassElement selectorType(Selector selector) {
// TODO(ngeoffray): Should the tree be specialized with DartType?
DartType type = selector.receiverType;
diff --git a/sdk/lib/_internal/compiler/implementation/universe/selector_map.dart b/sdk/lib/_internal/compiler/implementation/universe/selector_map.dart
index cf98a10..36b51399 100644
--- a/sdk/lib/_internal/compiler/implementation/universe/selector_map.dart
+++ b/sdk/lib/_internal/compiler/implementation/universe/selector_map.dart
@@ -4,12 +4,13 @@
part of universe;
+// TODO(kasperl): It seems possible to rewrite this class to be more
+// like the FunctionSet abstraction which is a lot simpler.
class SelectorMap<T> extends PartialTypeTree {
SelectorMap(Compiler compiler) : super(compiler);
- SelectorMapNode<T> newSpecializedNode(ClassElement type)
- => new SelectorMapNode<T>(type);
+ SelectorMapNode<T> newNode(ClassElement type) => new SelectorMapNode<T>(type);
T operator [](Selector selector) {
SelectorMapNode<T> node = findNode(selectorType(selector), false);
@@ -23,32 +24,29 @@
return null;
}
+ // TODO(kasperl): Do we need to support removing selectors by
+ // passing null as the value?
void operator []=(Selector selector, T value) {
- SelectorMapNode<T> node = findNode(selectorType(selector), true);
- Link<SelectorValue<T>> selectors = node.selectorsByName[selector.name];
- if (selectors == null) {
- // No existing selectors with the given name. Create a new
- // linked list.
- SelectorValue<T> head = new SelectorValue<T>(selector, value);
- node.selectorsByName[selector.name] =
- new Link<SelectorValue<T>>().prepend(head);
- } else {
- // Run through the linked list of selectors with the same name. If
- // we find one that matches, we update the value in the mapping.
- for (Link link = selectors; !link.isEmpty; link = link.tail) {
- SelectorValue<T> existing = link.head;
- // It is safe to ignore the type here, because all selector
- // mappings that are stored in a single node have the same type.
- if (existing.selector.equalsUntyped(selector)) {
- existing.value = value;
- return;
- }
+ ClassElement type = selectorType(selector);
+ SelectorMapNode<T> node = findNode(type, true);
+ SourceString name = selector.name;
+ Link<SelectorValue<T>> selectors = node.selectorsByName.putIfAbsent(
+ name, () => const Link());
+ // Run through the linked list of selectors with the same name. If
+ // we find one that matches, we update the value in the mapping.
+ for (Link link = selectors; !link.isEmpty; link = link.tail) {
+ SelectorValue<T> existing = link.head;
+ // It is safe to ignore the type here, because all selector
+ // mappings that are stored in a single node have the same type.
+ if (existing.selector.equalsUntyped(selector)) {
+ existing.value = value;
+ return;
}
- // We could not find an existing mapping for the selector, so
- // we add a new one to the existing linked list.
- SelectorValue<T> head = new SelectorValue<T>(selector, value);
- node.selectorsByName[selector.name] = selectors.prepend(head);
}
+ // We could not find an existing mapping for the selector, so
+ // we add a new one to the existing linked list.
+ SelectorValue<T> head = new SelectorValue<T>(selector, value);
+ node.selectorsByName[name] = selectors.prepend(head);
}
// TODO(kasperl): Share code with the [] operator?
@@ -72,13 +70,10 @@
void visitMatching(Element member, bool visit(Selector selector, T value)) {
assert(member.isMember());
if (root == null) return;
- // TODO(kasperl): For now, we use a different implementation for
- // visiting if the tree contains interface subtypes.
- if (containsInterfaceSubtypes) {
- visitAllMatching(member, visit);
- } else {
- visitHierarchyMatching(member, visit);
- }
+ // TODO(kasperl): Use visitHierachyMatching when possible. It is
+ // currently broken in subtle ways when it comes to finding typed
+ // selectors where we only know the interface of the receiver.
+ visitAllMatching(member, visit);
}
void visitAllMatching(Element member, bool visit(selector, value)) {
@@ -116,12 +111,9 @@
}
class SelectorMapNode<T> extends PartialTypeTreeNode {
-
- final Map<SourceString, Link<SelectorValue<T>>> selectorsByName;
-
- SelectorMapNode(ClassElement type) : super(type),
- selectorsByName = new Map<SourceString, Link<SelectorValue<T>>>();
-
+ final Map<SourceString, Link<SelectorValue<T>>> selectorsByName =
+ new Map<SourceString, Link<SelectorValue<T>>>();
+ SelectorMapNode(ClassElement type) : super(type);
}
class SelectorValue<T> {
