Roberto Lublinerman has uploaded a new change for review.
https://gwt-review.googlesource.com/2701
Change subject: Make sub/superclass queries in JTypeOracle more efficient.
......................................................................
Make sub/superclass queries in JTypeOracle more efficient.
Assign a unique id to each class during for global optimization, such
that the following invariant holds:
a.id < b.id for b != a and b subclass of a.
forall c.id > a.id, c.id <= max_{b subclass of a}(b.id) . c subclass of a
The aforementioned invariant allows to respond to the query subclass(a,b)
very
cheaply with just two integer comparisons (plus pointer dereferences).
Change-Id: Ibe256bc07834b1518a9e90872fdd655e3e242790
---
M dev/core/src/com/google/gwt/dev/jjs/ast/JClassType.java
M dev/core/src/com/google/gwt/dev/jjs/ast/JTypeOracle.java
2 files changed, 94 insertions(+), 2 deletions(-)
diff --git a/dev/core/src/com/google/gwt/dev/jjs/ast/JClassType.java
b/dev/core/src/com/google/gwt/dev/jjs/ast/JClassType.java
index 6c12533..1217c88 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/ast/JClassType.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/ast/JClassType.java
@@ -40,6 +40,7 @@
private final boolean isAbstract;
private boolean isFinal;
private JClassType superClass;
+ private int classId = -1;
public JClassType(SourceInfo info, String name, boolean isAbstract,
boolean isFinal) {
super(info, name);
@@ -85,6 +86,23 @@
isFinal = true;
}
+
+ /**
+ * Returns a numeric id for the class. The id is only assigned in the
global
+ * optimization phase and should not be used before the global ast is
built.
+ */
+ public int getClassId() {
+ return classId;
+ }
+
+ /**
+ * Set a classid. Only to be used after the global AST is build at the
beginning of the
+ * optimization phase.
+ */
+ public void setClassId(int classId) {
+ this.classId = classId;
+ }
+
/**
* Sets this type's super class.
*/
diff --git a/dev/core/src/com/google/gwt/dev/jjs/ast/JTypeOracle.java
b/dev/core/src/com/google/gwt/dev/jjs/ast/JTypeOracle.java
index 5963dd1..deded26 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/ast/JTypeOracle.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/ast/JTypeOracle.java
@@ -23,7 +23,10 @@
import com.google.gwt.dev.util.collect.IdentitySets;
import com.google.gwt.dev.util.collect.Lists;
import com.google.gwt.dev.util.collect.Maps;
+import com.google.gwt.dev.util.log.speedtracer.CompilerEventType;
+import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger;
+import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
@@ -297,6 +300,13 @@
private final Map<JClassType, Map<String, JMethod>> polyClassMethodMap =
new IdentityHashMap<JClassType, Map<String, JMethod>>();
+
+ /**
+ * The number of declared types.
+ */
+ private int declaredTypesSize;
+
+
public JTypeOracle(JProgram program) {
this.program = program;
}
@@ -481,6 +491,8 @@
jsoSingleImpls.clear();
dualImpls.clear();
+ this.declaredTypesSize = program.getDeclaredTypes().size();
+
for (JDeclaredType type : program.getDeclaredTypes()) {
if (type instanceof JClassType) {
recordSuperSubInfo((JClassType) type);
@@ -488,6 +500,13 @@
recordSuperSubInfo((JInterfaceType) type);
}
}
+
+ /*
+ * Compute efficient representation for hierarchy sub/supertype
queries.
+ */
+ computeIds();
+
+// HierarchyEncoder.compute(program);
/*
* Now that the basic type hierarchy is computed, compute which JSOs
@@ -645,14 +664,14 @@
* Returns true if qType is a subclass of type, directly or indirectly.
*/
public boolean isSubClass(JClassType type, JClassType qType) {
- return get(subClassMap, type).contains(qType);
+ return isSubtype(qType, type);
}
/**
* Returns true if qType is a superclass of type, directly or indirectly.
*/
public boolean isSuperClass(JClassType type, JClassType qType) {
- return get(superClassMap, type).contains(qType);
+ return isSubtype(type, qType);
}
/**
@@ -686,6 +705,8 @@
}
}
}
+
+
public void setInstantiatedTypes(Set<JReferenceType> instantiatedTypes) {
this.instantiatedTypes = instantiatedTypes;
@@ -1011,4 +1032,57 @@
}
}
+ /*
+ * Make sure we recompute class ids when reloading serialized type
oracles.
+ */
+ private void readObject(java.io.ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ in.defaultReadObject();
+ // recompute class hierarchy query data structure;
+ computeIds();
+ }
+
+
+ /**
+ * Compute class ids for efficient lookups.
+ *
+ * A clever encoding of the class hierarchy reduces the cost of one of
the hottest methods
+ * during optimize.
+ *
+ * NOTE: Only encodes the (single inheritance) class hierarchy.
+ *
+ * The encoding preserves the following invariant
+ * A is strict subclass of B <=> id(A) < id(B) ^ id(B) =< max{C
subclass A}(Id(C))
+ *
+ * An easy way to guaranteed this propery is to number sequentially
while traversing the
+ * hierarchy tree in preorder.
+ */
+ private transient int lastClassId = -1;
+ private transient int[] maxDescendants = null;
+
+ boolean isSubtype(JClassType sub, JClassType sup) {
+ int supId = sup.getClassId();
+ int subId = sub.getClassId();
+ return supId < subId &&
+ subId <= maxDescendants[supId];
+ }
+
+ private void computeIds() {
+ SpeedTracerLogger.Event computeHierarchyEvent =
+
SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "pass", "Compute Type
Hierarchy");
+ lastClassId = -1;
+ maxDescendants = new int[declaredTypesSize];
+ computeIdTraversal(javaLangObject);
+ computeHierarchyEvent.end();
+ }
+
+ private void computeIdTraversal(JClassType type) {
+ type.setClassId(++lastClassId);
+ for (JClassType sub : get(subClassMap, type)) {
+ if (sub.getSuperClass() == type) {
+ computeIdTraversal(sub);
+ }
+ }
+ maxDescendants[type.getClassId()] = lastClassId;
+ }
}
--
To view, visit https://gwt-review.googlesource.com/2701
To unsubscribe, visit https://gwt-review.googlesource.com/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ibe256bc07834b1518a9e90872fdd655e3e242790
Gerrit-PatchSet: 1
Gerrit-Project: gwt
Gerrit-Branch: master
Gerrit-Owner: Roberto Lublinerman <[email protected]>
--
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
---
You received this message because you are subscribed to the Google Groups "Google Web Toolkit Contributors" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
