--- a/langtools/src/share/classes/com/sun/tools/javac/code/Symbol.java	Wed Jul 29 13:26:26 2009 -0700
+++ b/langtools/src/share/classes/com/sun/tools/javac/code/Symbol.java	Thu Jul 30 10:29:53 2009 +0100
@@ -1197,21 +1197,9 @@
          *  as possible implementations.
          */
         public MethodSymbol implementation(TypeSymbol origin, Types types, boolean checkResult) {
-            for (Type t = origin.type; t.tag == CLASS || t.tag == TYPEVAR; t = types.supertype(t)) {
-                while (t.tag == TYPEVAR)
-                    t = t.getUpperBound();
-                TypeSymbol c = t.tsym;
-                for (Scope.Entry e = c.members().lookup(name);
-                     e.scope != null;
-                     e = e.next()) {
-                    if (e.sym.kind == MTH) {
-                        MethodSymbol m = (MethodSymbol) e.sym;
-                        if (m.overrides(this, origin, types, checkResult) &&
-                            (m.flags() & SYNTHETIC) == 0)
-                            return m;
-                    }
-                }
-            }
+            MethodSymbol res = types.implementation(this, origin, types, checkResult);
+            if (res != null)
+                return res;
             // if origin is derived from a raw type, we might have missed
             // an implementation because we do not know enough about instantiations.
             // in this case continue with the supertype as origin.

--- a/langtools/src/share/classes/com/sun/tools/javac/code/Types.java	Wed Jul 29 13:26:26 2009 -0700
+++ b/langtools/src/share/classes/com/sun/tools/javac/code/Types.java	Thu Jul 30 10:29:53 2009 +0100
@@ -25,10 +25,9 @@
 
 package com.sun.tools.javac.code;
 
+import java.lang.ref.SoftReference;
 import java.util.*;
 
-import com.sun.tools.javac.api.Messages;
-
 import com.sun.tools.javac.util.*;
 import com.sun.tools.javac.util.List;
 
@@ -1442,7 +1441,7 @@
         return (sym.flags() & STATIC) != 0
             ? sym.type
             : memberType.visit(t, sym);
-    }
+        }
     // where
         private SimpleVisitor<Type,Symbol> memberType = new SimpleVisitor<Type,Symbol>() {
 
@@ -1552,7 +1551,7 @@
             return t; /* fast special case */
         else
             return erasure.visit(t, recurse);
-    }
+        }
     // where
         private SimpleVisitor<Type, Boolean> erasure = new SimpleVisitor<Type, Boolean>() {
             public Type visitType(Type t, Boolean recurse) {
@@ -1946,6 +1945,45 @@
             hasSameArgs(t, erasure(s)) || hasSameArgs(erasure(t), s);
     }
 
+    private WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, MethodSymbol>>> implCache_check =
+            new WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, MethodSymbol>>>();
+
+    private WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, MethodSymbol>>> implCache_nocheck =
+            new WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, MethodSymbol>>>();
+
+    public MethodSymbol implementation(MethodSymbol ms, TypeSymbol origin, Types types, boolean checkResult) {
+        Map<MethodSymbol, SoftReference<Map<TypeSymbol, MethodSymbol>>> implCache = checkResult ?
+            implCache_check : implCache_nocheck;
+        SoftReference<Map<TypeSymbol, MethodSymbol>> ref_cache = implCache.get(ms);
+        Map<TypeSymbol, MethodSymbol> cache = ref_cache != null ? ref_cache.get() : null;
+        if (cache == null) {
+            cache = new HashMap<TypeSymbol, MethodSymbol>();
+            implCache.put(ms, new SoftReference<Map<TypeSymbol, MethodSymbol>>(cache));
+        }
+        MethodSymbol impl = cache.get(origin);
+        if (impl == null) {
+            for (Type t = origin.type; t.tag == CLASS || t.tag == TYPEVAR; t = types.supertype(t)) {
+                while (t.tag == TYPEVAR)
+                    t = t.getUpperBound();
+                TypeSymbol c = t.tsym;
+                for (Scope.Entry e = c.members().lookup(ms.name);
+                     e.scope != null;
+                     e = e.next()) {
+                    if (e.sym.kind == Kinds.MTH) {
+                        MethodSymbol m = (MethodSymbol) e.sym;
+                        if (m.overrides(ms, origin, types, checkResult) &&
+                            (m.flags() & SYNTHETIC) == 0) {
+                            impl = m;
+                            cache.put(origin, m);
+                            return impl;
+                        }
+                    }
+                }
+            }
+        }
+        return impl;
+    }
+
     /**
      * Does t have the same arguments as s?  It is assumed that both
      * types are (possibly polymorphic) method types.  Monomorphic