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> {