changeset 50871:64c880300d9b

8193717: Import resolution performance regression in JDK 9 Summary: Avoiding iteration through all sub-scopes of single import scope when looking up by name by only using those that may contain the given name. Reviewed-by: mcimadamore
author jlahoda
date Tue, 29 May 2018 13:17:03 +0200
parents cbc4fca9171e
children 3831655869bc
files src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacScope.java src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacTrees.java src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Enter.java src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Resolve.java test/langtools/tools/javac/importscope/T8193717.java test/langtools/tools/javac/lib/DPrinter.java
diffstat 7 files changed, 271 insertions(+), 36 deletions(-) [+]
line wrap: on
line diff
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacScope.java	Tue May 29 12:52:08 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacScope.java	Tue May 29 13:17:03 2018 +0200
@@ -31,6 +31,7 @@
 import javax.lang.model.element.TypeElement;
 
 import com.sun.tools.javac.code.Kinds.Kind;
+import com.sun.tools.javac.code.Scope.CompoundScope;
 import com.sun.tools.javac.code.Symbol;
 import com.sun.tools.javac.comp.AttrContext;
 import com.sun.tools.javac.comp.Env;
@@ -63,7 +64,10 @@
             return new JavacScope(env) {
                 @Override @DefinedBy(Api.COMPILER_TREE)
                 public Iterable<? extends Element> getLocalElements() {
-                    return env.toplevel.namedImportScope.getSymbols(VALIDATOR);
+                    CompoundScope result = new CompoundScope(env.toplevel.packge);
+                    result.prependSubScope(env.toplevel.toplevelScope);
+                    result.prependSubScope(env.toplevel.namedImportScope);
+                    return result.getSymbols(VALIDATOR);
                 }
             };
         } else {
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacTrees.java	Tue May 29 12:52:08 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/api/JavacTrees.java	Tue May 29 13:17:03 2018 +0200
@@ -1229,7 +1229,7 @@
         jcCompilationUnit.lineMap = jcCompilationUnit.getLineMap();
         jcCompilationUnit.modle = psym.modle;
         jcCompilationUnit.sourcefile = jfo;
-        jcCompilationUnit.namedImportScope = new NamedImportScope(psym, jcCompilationUnit.toplevelScope);
+        jcCompilationUnit.namedImportScope = new NamedImportScope(psym);
         jcCompilationUnit.packge = psym;
         jcCompilationUnit.starImportScope = new StarImportScope(psym);
         jcCompilationUnit.toplevelScope = WriteableScope.create(psym);
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java	Tue May 29 12:52:08 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java	Tue May 29 13:17:03 2018 +0200
@@ -740,58 +740,91 @@
          * No further changes to class hierarchy or class content will be reflected.
          */
         public void finalizeScope() {
-            for (List<Scope> scopes = this.subScopes; scopes.nonEmpty(); scopes = scopes.tail) {
-                Scope impScope = scopes.head;
+            for (List<Scope> scopes = this.subScopes.toList(); scopes.nonEmpty(); scopes = scopes.tail) {
+                scopes.head = finalizeSingleScope(scopes.head);
+            }
+        }
 
-                if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP) {
-                    WriteableScope finalized = WriteableScope.create(impScope.owner);
+        protected Scope finalizeSingleScope(Scope impScope) {
+            if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP) {
+                WriteableScope finalized = WriteableScope.create(impScope.owner);
 
-                    for (Symbol sym : impScope.getSymbols()) {
-                        finalized.enter(sym);
+                for (Symbol sym : impScope.getSymbols()) {
+                    finalized.enter(sym);
+                }
+
+                finalized.listeners.add(new ScopeListener() {
+                    @Override
+                    public void symbolAdded(Symbol sym, Scope s) {
+                        Assert.error("The scope is sealed.");
                     }
 
-                    finalized.listeners.add(new ScopeListener() {
-                        @Override
-                        public void symbolAdded(Symbol sym, Scope s) {
-                            Assert.error("The scope is sealed.");
-                        }
+                    @Override
+                    public void symbolRemoved(Symbol sym, Scope s) {
+                        Assert.error("The scope is sealed.");
+                    }
+                });
 
-                        @Override
-                        public void symbolRemoved(Symbol sym, Scope s) {
-                            Assert.error("The scope is sealed.");
-                        }
-                    });
+                return finalized;
+            }
 
-                    scopes.head = finalized;
-                }
-            }
+            return impScope;
         }
 
     }
 
     public static class NamedImportScope extends ImportScope {
 
-        public NamedImportScope(Symbol owner, Scope currentFileScope) {
+        /*A cache for quick lookup of Scopes that may contain the given name.
+          ScopeImpl and Entry is not used, as it is maps names to Symbols,
+          but it is necessary to map names to Scopes at this place (so that any
+          changes to the content of the Scopes is reflected when looking up the
+          Symbols.
+         */
+        private final Map<Name, Scope[]> name2Scopes = new HashMap<>();
+
+        public NamedImportScope(Symbol owner) {
             super(owner);
-            prependSubScope(currentFileScope);
         }
 
         public Scope importByName(Types types, Scope origin, Name name, ImportFilter filter, JCImport imp, BiConsumer<JCImport, CompletionFailure> cfHandler) {
-            return appendScope(new FilterImportScope(types, origin, name, filter, imp, cfHandler));
+            return appendScope(new FilterImportScope(types, origin, name, filter, imp, cfHandler), name);
         }
 
         public Scope importType(Scope delegate, Scope origin, Symbol sym) {
-            return appendScope(new SingleEntryScope(delegate.owner, sym, origin));
+            return appendScope(new SingleEntryScope(delegate.owner, sym, origin), sym.name);
         }
 
-        private Scope appendScope(Scope newScope) {
-            List<Scope> existingScopes = this.subScopes.reverse();
-            subScopes = List.of(existingScopes.head);
-            subScopes = subScopes.prepend(newScope);
-            for (Scope s : existingScopes.tail) {
-                subScopes = subScopes.prepend(s);
+        private Scope appendScope(Scope newScope, Name name) {
+            appendSubScope(newScope);
+            Scope[] existing = name2Scopes.get(name);
+            if (existing != null)
+                existing = Arrays.copyOf(existing, existing.length + 1);
+            else
+                existing = new Scope[1];
+            existing[existing.length - 1] = newScope;
+            name2Scopes.put(name, existing);
+            return newScope;
+        }
+
+        @Override
+        public Iterable<Symbol> getSymbolsByName(Name name, Filter<Symbol> sf, LookupKind lookupKind) {
+            Scope[] scopes = name2Scopes.get(name);
+            if (scopes == null)
+                return Collections.emptyList();
+            return () -> Iterators.createCompoundIterator(Arrays.asList(scopes),
+                                                          scope -> scope.getSymbolsByName(name,
+                                                                                          sf,
+                                                                                          lookupKind)
+                                                                        .iterator());
+        }
+        public void finalizeScope() {
+            super.finalizeScope();
+            for (Scope[] scopes : name2Scopes.values()) {
+                for (int i = 0; i < scopes.length; i++) {
+                    scopes[i] = finalizeSingleScope(scopes[i]);
+                }
             }
-            return newScope;
         }
 
         private static class SingleEntryScope extends Scope {
@@ -977,7 +1010,7 @@
      */
     public static class CompoundScope extends Scope implements ScopeListener {
 
-        List<Scope> subScopes = List.nil();
+        ListBuffer<Scope> subScopes = new ListBuffer<>();
         private int mark = 0;
 
         public CompoundScope(Symbol owner) {
@@ -986,7 +1019,16 @@
 
         public void prependSubScope(Scope that) {
            if (that != null) {
-                subScopes = subScopes.prepend(that);
+                subScopes.prepend(that);
+                that.listeners.add(this);
+                mark++;
+                listeners.symbolAdded(null, this);
+           }
+        }
+
+        public void appendSubScope(Scope that) {
+           if (that != null) {
+                subScopes.append(that);
                 that.listeners.add(this);
                 mark++;
                 listeners.symbolAdded(null, this);
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Enter.java	Tue May 29 12:52:08 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Enter.java	Tue May 29 13:17:03 2018 +0200
@@ -215,7 +215,7 @@
         localEnv.toplevel = tree;
         localEnv.enclClass = predefClassDef;
         tree.toplevelScope = WriteableScope.create(tree.packge);
-        tree.namedImportScope = new NamedImportScope(tree.packge, tree.toplevelScope);
+        tree.namedImportScope = new NamedImportScope(tree.packge);
         tree.starImportScope = new StarImportScope(tree.packge);
         localEnv.info.scope = tree.toplevelScope;
         localEnv.info.lint = lint;
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Resolve.java	Tue May 29 12:52:08 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Resolve.java	Tue May 29 13:17:03 2018 +0200
@@ -2305,6 +2305,10 @@
             if (sym.exists()) return sym;
             else bestSoFar = bestOf(bestSoFar, sym);
 
+            sym = findGlobalType(env, env.toplevel.toplevelScope, name, noRecovery);
+            if (sym.exists()) return sym;
+            else bestSoFar = bestOf(bestSoFar, sym);
+
             sym = findGlobalType(env, env.toplevel.packge.members(), name, noRecovery);
             if (sym.exists()) return sym;
             else bestSoFar = bestOf(bestSoFar, sym);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/langtools/tools/javac/importscope/T8193717.java	Tue May 29 13:17:03 2018 +0200
@@ -0,0 +1,184 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * @test
+ * @bug 8193717
+ * @summary Check that code with a lot named imports can compile.
+ * @library /tools/lib
+ * @modules jdk.jdeps/com.sun.tools.classfile
+ *          jdk.compiler/com.sun.tools.javac.api
+ *          jdk.compiler/com.sun.tools.javac.main
+ *          jdk.jdeps/com.sun.tools.javap
+ * @build toolbox.ToolBox toolbox.JavapTask
+ * @run main T8193717
+ */
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.net.URI;
+import java.net.URISyntaxException;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+import javax.tools.ForwardingJavaFileManager;
+import javax.tools.JavaCompiler;
+import javax.tools.JavaFileManager;
+import javax.tools.JavaFileObject;
+import javax.tools.JavaFileObject.Kind;
+import javax.tools.SimpleJavaFileObject;
+import javax.tools.StandardJavaFileManager;
+import javax.tools.StandardLocation;
+import javax.tools.ToolProvider;
+
+import com.sun.tools.classfile.AccessFlags;
+import com.sun.tools.classfile.Attribute;
+import com.sun.tools.classfile.Attributes;
+import com.sun.tools.classfile.ClassFile;
+import com.sun.tools.classfile.ClassWriter;
+import com.sun.tools.classfile.ConstantPool;
+import com.sun.tools.classfile.ConstantPool.CONSTANT_Class_info;
+import com.sun.tools.classfile.ConstantPool.CONSTANT_Utf8_info;
+import com.sun.tools.classfile.ConstantPool.CPInfo;
+import com.sun.tools.classfile.Field;
+import com.sun.tools.classfile.Method;
+
+import toolbox.JavacTask;
+import toolbox.ToolBox;
+
+public class T8193717 {
+    public static void main(String... args) throws IOException {
+        new T8193717().run();
+    }
+
+    private static final int CLASSES = 500000;
+
+    private void run() throws IOException {
+        StringBuilder imports = new StringBuilder();
+        StringBuilder use = new StringBuilder();
+
+        for (int c = 0; c < CLASSES; c++) {
+            String simpleName = getSimpleName(c);
+            String pack = "p";
+            imports.append("import " + pack + "." + simpleName + ";\n");
+            use.append(simpleName + " " + simpleName + ";\n");
+        }
+        String source = imports.toString() + "public class T {\n" + use.toString() + "}";
+        ToolBox tb = new ToolBox();
+        JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
+
+        try (StandardJavaFileManager fm = compiler.getStandardFileManager(null, null, null)) {
+            fm.setLocationFromPaths(StandardLocation.CLASS_OUTPUT, List.of(Paths.get(".")));
+            new JavacTask(tb).sources(source)
+                             .options("-XDshould-stop.at=ATTR") //the source is too big for a classfile
+                             .fileManager(new TestJFM(fm))
+                             .run();
+        }
+    }
+
+    private static String getSimpleName(int c) {
+        return "T" + String.format("%0" + (int) Math.ceil(Math.log10(CLASSES)) + "d", c);
+    }
+
+    private byte[] generateClassFile(String name) throws IOException {
+        ConstantPool cp = new ConstantPool(new CPInfo[] {
+            new CONSTANT_Utf8_info(""),                     //0
+            new CONSTANT_Utf8_info(name.replace(".", "/")), //1
+            new CONSTANT_Class_info(null, 1),               //2
+            new CONSTANT_Utf8_info("java/lang/Object"),     //3
+            new CONSTANT_Class_info(null, 3),               //4
+        });
+        ClassFile cf = new ClassFile(0xCAFEBABE,
+                      0,
+                      51,
+                      cp,
+                      new AccessFlags(AccessFlags.ACC_ABSTRACT |
+                                      AccessFlags.ACC_INTERFACE |
+                                      AccessFlags.ACC_PUBLIC),
+                      2,
+                      4,
+                      new int[0],
+                      new Field[0],
+                      new Method[0],
+                      new Attributes(cp, new Attribute[0]));
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        new ClassWriter().write(cf, baos);
+        return baos.toByteArray();
+    }
+
+    final class TestJFM extends ForwardingJavaFileManager<JavaFileManager> {
+
+        public TestJFM(JavaFileManager fileManager) {
+            super(fileManager);
+        }
+
+        @Override
+        public Iterable<JavaFileObject> list(Location location, String packageName,
+                                             Set<Kind> kinds, boolean recurse) throws IOException {
+            if (location == StandardLocation.CLASS_PATH) {
+                if (packageName.equals("p")) {
+                    try {
+                        List<JavaFileObject> result = new ArrayList<>(CLASSES);
+
+                        for (int c = 0; c < CLASSES; c++) {
+                            result.add(new TestJFO("p." + getSimpleName(c)));
+                        }
+
+                        return result;
+                    } catch (URISyntaxException ex) {
+                        throw new IllegalStateException(ex);
+                    }
+                }
+            }
+            return super.list(location, packageName, kinds, recurse);
+        }
+
+        @Override
+        public String inferBinaryName(Location location, JavaFileObject file) {
+            if (file instanceof TestJFO) {
+                return ((TestJFO) file).name;
+            }
+            return super.inferBinaryName(location, file);
+        }
+
+        private class TestJFO extends SimpleJavaFileObject {
+
+            private final String name;
+
+            public TestJFO(String name) throws URISyntaxException {
+                super(new URI("mem://" + name.replace(".", "/") + ".class"), Kind.CLASS);
+                this.name = name;
+            }
+
+            @Override
+            public InputStream openInputStream() throws IOException {
+                return new ByteArrayInputStream(generateClassFile(name));
+            }
+        }
+
+    }
+}
--- a/test/langtools/tools/javac/lib/DPrinter.java	Tue May 29 12:52:08 2018 +0200
+++ b/test/langtools/tools/javac/lib/DPrinter.java	Tue May 29 13:17:03 2018 +0200
@@ -81,6 +81,7 @@
 import com.sun.tools.javac.util.Assert;
 import com.sun.tools.javac.util.Context;
 import com.sun.tools.javac.util.Convert;
+import com.sun.tools.javac.util.ListBuffer;
 import com.sun.tools.javac.util.Log;
 
 
@@ -405,7 +406,7 @@
             printScope("origin",
                     (Scope) getField(scope, scope.getClass(), "origin"), Details.FULL);
         } else if (scope instanceof CompoundScope) {
-            printList("delegates", (List<?>) getField(scope, CompoundScope.class, "subScopes"));
+            printList("delegates", ((ListBuffer<?>) getField(scope, CompoundScope.class, "subScopes")).toList());
         } else {
             for (Symbol sym : scope.getSymbols()) {
                 printSymbol(sym.name.toString(), sym, Details.SUMMARY);