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
--- 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);
+ }
+ }
+
+ protected Scope finalizeSingleScope(Scope impScope) {
+ if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP) {
+ WriteableScope finalized = WriteableScope.create(impScope.owner);
- 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, 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;
}
- 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);
+ @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);