8230162: ScopeImpl.remove() has O(N) performance
authorjlahoda
Tue, 08 Oct 2019 15:43:38 +0200
changeset 58500 03165abce4cc
parent 58499 d62c7224d5b7
child 58501 6fc4a729763e
8230162: ScopeImpl.remove() has O(N) performance Reviewed-by: jlahoda Contributed-by: bcorso@google.com
src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java
test/langtools/tools/javac/lib/DPrinter.java
test/langtools/tools/javac/scope/RemoveSymbolUnitTest.java
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java	Tue Oct 08 15:48:36 2019 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java	Tue Oct 08 15:43:38 2019 +0200
@@ -389,7 +389,7 @@
                 Entry e = table[hash];
                 Assert.check(e == elems, elems.sym);
                 table[hash] = elems.shadowed;
-                elems = elems.sibling;
+                elems = elems.nextSibling;
             }
             Assert.check(next.shared > 0);
             next.shared--;
@@ -466,15 +466,15 @@
             }
 
             // remove e from elems and sibling list
-            te = elems;
-            if (te == e)
-                elems = e.sibling;
-            else while (true) {
-                if (te.sibling == e) {
-                    te.sibling = e.sibling;
-                    break;
-                }
-                te = te.sibling;
+            if (elems == e) {
+                elems = e.nextSibling;
+                if (elems != null)
+                    elems.prevSibling = null;
+            } else {
+                Assert.check(e.prevSibling != null, e.sym);
+                e.prevSibling.nextSibling = e.nextSibling;
+                if (e.nextSibling != null)
+                    e.nextSibling.prevSibling = e.prevSibling;
             }
 
             removeCount++;
@@ -597,7 +597,7 @@
                 private Symbol doNext() {
                     Symbol sym = (currEntry == null ? null : currEntry.sym);
                     if (currEntry != null) {
-                        currEntry = currEntry.sibling;
+                        currEntry = currEntry.nextSibling;
                     }
                     update();
                     return sym;
@@ -617,7 +617,7 @@
 
                 void skipToNextMatchingEntry() {
                     while (currEntry != null && sf != null && !sf.accepts(currEntry.sym)) {
-                        currEntry = currEntry.sibling;
+                        currEntry = currEntry.nextSibling;
                     }
                 }
             };
@@ -677,7 +677,7 @@
             result.append("Scope[");
             for (ScopeImpl s = this; s != null ; s = s.next) {
                 if (s != this) result.append(" | ");
-                for (Entry e = s.elems; e != null; e = e.sibling) {
+                for (Entry e = s.elems; e != null; e = e.nextSibling) {
                     if (e != s.elems) result.append(", ");
                     result.append(e.sym);
                 }
@@ -702,18 +702,24 @@
 
         /** Next entry in same scope.
          */
-        public Entry sibling;
+        public Entry nextSibling;
+
+        /** Prev entry in same scope.
+         */
+        public Entry prevSibling;
 
         /** The entry's scope.
          *  scope == null   iff   this == sentinel
          */
         public ScopeImpl scope;
 
-        public Entry(Symbol sym, Entry shadowed, Entry sibling, ScopeImpl scope) {
+        public Entry(Symbol sym, Entry shadowed, Entry nextSibling, ScopeImpl scope) {
             this.sym = sym;
             this.shadowed = shadowed;
-            this.sibling = sibling;
+            this.nextSibling = nextSibling;
             this.scope = scope;
+            if (nextSibling != null)
+                nextSibling.prevSibling = this;
         }
 
         /** Return next entry with the same name as this entry, proceeding
--- a/test/langtools/tools/javac/lib/DPrinter.java	Tue Oct 08 15:48:36 2019 +0200
+++ b/test/langtools/tools/javac/lib/DPrinter.java	Tue Oct 08 15:43:38 2019 +0200
@@ -437,7 +437,8 @@
         Scope scope = (Scope) getField(e, e.getClass(), "scope");
         return "(" + sym.name + ":" + sym
                 + ",shdw:" + entryToString(callMethod(e, e.getClass(), "next"), table, true)
-                + ",sibl:" + entryToString(getField(e, e.getClass(), "sibling"), table, true)
+                + ",nextSibling:" + entryToString(getField(e, e.getClass(), "nextSibling"), table, true)
+                + ",prevSibling:" + entryToString(getField(e, e.getClass(), "prevSibling"), table, true)
                 + ((sym.owner != scope.owner)
                     ? (",BOGUS[" + sym.owner + "," + scope.owner + "]")
                     : "")
--- a/test/langtools/tools/javac/scope/RemoveSymbolUnitTest.java	Tue Oct 08 15:48:36 2019 +0200
+++ b/test/langtools/tools/javac/scope/RemoveSymbolUnitTest.java	Tue Oct 08 15:43:38 2019 +0200
@@ -33,8 +33,13 @@
 import com.sun.tools.javac.util.*;
 import com.sun.tools.javac.code.*;
 import com.sun.tools.javac.code.Scope.*;
+import com.sun.tools.javac.code.Symbol;
 import com.sun.tools.javac.code.Symbol.*;
 import com.sun.tools.javac.file.JavacFileManager;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
 
 public class RemoveSymbolUnitTest {
 
@@ -63,36 +68,66 @@
 
         // Try enter and remove in different shuffled combinations.
         // working with fresh scope each time.
-        WriteableScope cs = WriteableScope.create(clazz);
-        cs.enter(v);
-        cs.enter(m);
+        WriteableScope cs = writeableScope(clazz, v, m);
         cs.remove(v);
         Symbol s = cs.findFirst(hasNext);
         if (s != m)
             throw new AssertionError("Wrong symbol");
 
-        cs = WriteableScope.create(clazz);
-        cs.enter(m);
-        cs.enter(v);
+        cs = writeableScope(clazz, m, v);
         cs.remove(v);
         s = cs.findFirst(hasNext);
         if (s != m)
             throw new AssertionError("Wrong symbol");
 
-        cs = WriteableScope.create(clazz);
-        cs.enter(v);
-        cs.enter(m);
+        cs = writeableScope(clazz, v, m);
         cs.remove(m);
         s = cs.findFirst(hasNext);
         if (s != v)
             throw new AssertionError("Wrong symbol");
 
-        cs = WriteableScope.create(clazz);
+        cs = writeableScope(clazz);
         cs.enter(m);
         cs.enter(v);
         cs.remove(m);
         s = cs.findFirst(hasNext);
         if (s != v)
             throw new AssertionError("Wrong symbol");
+
+        // Test multiple removals in the same scope.
+        VarSymbol v1 = new VarSymbol(0, names.fromString("name1"), Type.noType, clazz);
+        VarSymbol v2 = new VarSymbol(0, names.fromString("name2"), Type.noType, clazz);
+        VarSymbol v3 = new VarSymbol(0, names.fromString("name3"), Type.noType, clazz);
+        VarSymbol v4 = new VarSymbol(0, names.fromString("name4"), Type.noType, clazz);
+
+        cs = writeableScope(clazz, v1, v2, v3, v4);
+        cs.remove(v2);
+        assertRemainingSymbols(cs, v1, v3, v4);
+        cs.remove(v3);
+        assertRemainingSymbols(cs, v1, v4);
+        cs.remove(v1);
+        assertRemainingSymbols(cs, v4);
+        cs.remove(v4);
+        assertRemainingSymbols(cs);
+    }
+
+    private WriteableScope writeableScope(ClassSymbol classSymbol, Symbol... symbols) {
+        WriteableScope cs = WriteableScope.create(classSymbol);
+        for (Symbol symbol : symbols) {
+            cs.enter(symbol);
+        }
+        return cs;
+    }
+
+    private void assertRemainingSymbols(WriteableScope cs, Symbol... symbols) {
+      List<Symbol> expectedSymbols = Arrays.asList(symbols);
+      List<Symbol> actualSymbols = new ArrayList<>();
+      cs.getSymbols().forEach(symbol -> actualSymbols.add(symbol));
+      // The symbols are stored in reverse order
+      Collections.reverse(actualSymbols);
+      if (!actualSymbols.equals(expectedSymbols)) {
+          throw new AssertionError(
+              String.format("Wrong symbols: %s. Expected %s", actualSymbols, expectedSymbols));
+      }
     }
 }