Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Exponential perf degradation during substituteGenerics (NTI) #2689

Open
supersteves opened this issue Oct 27, 2017 · 6 comments
Open

Exponential perf degradation during substituteGenerics (NTI) #2689

supersteves opened this issue Oct 27, 2017 · 6 comments

Comments

@supersteves
Copy link
Contributor

Our moderately sized codebase uses extensive use of the externs attached. Over time, as we've build out these externs, and the corresponding code that uses them, we've seen an exponential degradation in performance, to the point where it's taking literally hours and gigabytes of memory to complete checks-only compilation.

Here's an example stacktrace after pausing in Eclipse once it's taken far too long already:

	ImmutableMap<K,V>.copyOf(Map<? extends K,? extends V>) line: 333	
	FunctionType.normalized(JSTypes, List<JSType>, List<JSType>, JSType, JSType, JSType, JSType, Map<String,JSType>, TypeParameters, boolean, boolean) line: 232	
	FunctionTypeBuilder.buildFunction() line: 191	
	FunctionType.substituteNominalGenerics(Map<String,JSType>) line: 1287	
	FunctionType.substituteGenerics(Map<String,JSType>) line: 1296	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1587	
	JSType$ObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 220	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$NullableObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$ObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 220	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$ObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	FunctionType.substituteNominalGenerics(Map<String,JSType>) line: 1268	
	FunctionType.substituteGenerics(Map<String,JSType>) line: 1296	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1587	
	JSType$UnionType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$UnionType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$UnionType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$UnionType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$ObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1584	
	JSType$NullableObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	FunctionType.substituteNominalGenerics(Map<String,JSType>) line: 1276	
	FunctionType.substituteGenerics(Map<String,JSType>) line: 1296	
	ObjectType.substituteGenerics(Map<String,JSType>) line: 1587	
	JSType$ObjsType(JSType).substituteGenerics(Map<String,JSType>) line: 698	
	Property.substituteGenerics(Map<String,JSType>) line: 218	
	NominalType.getProp(String, RawNominalType$PropAccess) line: 414	
	RawNominalType.getPropFromClass(String, RawNominalType$PropAccess) line: 429	
	RawNominalType.getProp(String, RawNominalType$PropAccess) line: 458	
	RawNominalType.getInstancePropDeclaredType(String) line: 478	
	NominalType.getPropDeclaredType(String) line: 427	
	GlobalTypeInfoCollector.checkSuperProperty(RawNominalType, NominalType, String, Multimap<String,DeclaredFunctionType>, Multimap<String,JSType>) line: 655	
	GlobalTypeInfoCollector.checkAndFreezeNominalType(RawNominalType) line: 532	
	GlobalTypeInfoCollector.process(Node, Node) line: 378	
	PhaseOptimizer$NamedPass.process(Node, Node) line: 304	
	PhaseOptimizer.process(Node, Node) line: 230

The problem appears to be due to some combination of the usages of:

  1. |undefined to allow properties to be optional
  2. Array<...> generic types
  3. The depth of the tree of types being defined in the externs

Performance is improved by breaking up the structure of these externs type trees through changing various arrays to Array<*> and putting in casts at point of use.

I've created a very simple example in the debugger, but it doesn't show any obvious performance problems. Probably it needs a larger real-world codebase, which I can't submit.

Externs in full, attached: externs.js.txt
@supersteves
Copy link
Contributor Author

supersteves commented Oct 27, 2017 •
edited

After changing all references to Highcharts.HighchartsOptions to * in these externs, performs is improved maybe 100x or greater. But still it's a bottleneck; this top-down worst-only CPU profiling shows GlobalTypeInfoCollector taking 66% (16 seconds) of the overall time to compile (checks-only) several hundred files:

.................com.google.javascript.jscomp.Compiler.compileModules(Compiler.java:772) [97.2%]
..................com.google.javascript.jscomp.Compiler.stage1Passes(Compiler.java:800) [97.2%]
...................com.google.javascript.jscomp.Compiler.runInCompilerThread(Compiler.java:858) [97.2%]
....................com.google.javascript.jscomp.CompilerExecutor.runInCompilerThread(CompilerExecutor.java:128) [97.2%]
.....................com.google.javascript.jscomp.Compiler$2.call(Compiler.java:801) [97.2%]
......................com.google.javascript.jscomp.Compiler$2.call(Compiler.java:804) [97.2%]
.......................com.google.javascript.jscomp.Compiler.access$000(Compiler.java:101) [97.2%]
........................com.google.javascript.jscomp.Compiler.performChecksAndTranspilation(Compiler.java:870) [97.2%]
.........................com.google.javascript.jscomp.Compiler.check(Compiler.java:1071) [97.2%]
..........................com.google.javascript.jscomp.PhaseOptimizer.process(PhaseOptimizer.java:230) [97.2%]
...........................com.google.javascript.jscomp.PhaseOptimizer$NamedPass.process(PhaseOptimizer.java:304) [97.2%]
............................com.google.javascript.jscomp.GlobalTypeInfoCollector.process(GlobalTypeInfoCollector.java:378) [66.7%]
.............................com.google.javascript.jscomp.GlobalTypeInfoCollector.checkAndFreezeNominalType(GlobalTypeInfoCollector.java:532) [52.3%]
..............................com.google.javascript.jscomp.GlobalTypeInfoCollector.checkSuperProperty(GlobalTypeInfoCollector.java:673) [34.7%]
...............................com.google.javascript.jscomp.GlobalTypeInfoCollector.getPropDefFromClass(GlobalTypeInfoCollector.java:486) [24.6%]
................................com.google.javascript.jscomp.newtypes.NominalType.getPropDeclaredType(NominalType.java:427) [14.5%]
.................................com.google.javascript.jscomp.newtypes.RawNominalType.getInstancePropDeclaredType(RawNominalType.java:478) [14.5%]
..................................com.google.javascript.jscomp.newtypes.RawNominalType.getProp(RawNominalType.java:458) [14.5%]
...................................com.google.javascript.jscomp.newtypes.RawNominalType.getPropFromClass(RawNominalType.java:429) [14.3%]
....................................com.google.javascript.jscomp.newtypes.NominalType.getProp(NominalType.java:414) [14.3%]
.....................................com.google.javascript.jscomp.newtypes.Property.substituteGenerics(Property.java:218) [7.2%]
......................................com.google.javascript.jscomp.newtypes.JSType.substituteGenerics(JSType.java:698) [7.2%]
.......................................com.google.javascript.jscomp.newtypes.ObjectType.substituteGenerics(ObjectType.java:1587) [7.2%]
........................................com.google.javascript.jscomp.newtypes.FunctionType.substituteGenerics(FunctionType.java:1296) [7.2%]
.........................................com.google.javascript.jscomp.newtypes.FunctionType.substituteNominalGenerics(FunctionType.java:1276) [7.2%]
..........................................com.google.javascript.jscomp.newtypes.JSType.substituteGenerics(JSType.java:698) [7.2%]
...........................................com.google.javascript.jscomp.newtypes.ObjectType.substituteGenerics(ObjectType.java:1584) [7.2%]
............................................com.google.javascript.jscomp.newtypes.Property.substituteGenerics(Property.java:220) [4.0%]
.............................................com.google.javascript.jscomp.newtypes.JSType.substituteGenerics(JSType.java:698) [4.0%]
..............................................com.google.javascript.jscomp.newtypes.ObjectType.substituteGenerics(ObjectType.java:1584) [3.9%]
...............................................com.google.javascript.jscomp.newtypes.Property.substituteGenerics(Property.java:220) [2.7%]
................................................com.google.javascript.jscomp.newtypes.JSType.substituteGenerics(JSType.java:698) [2.7%]
.................................................com.google.javascript.jscomp.newtypes.ObjectType.substituteGenerics(ObjectType.java:1584) [2.7%]
..................................................com.google.javascript.jscomp.newtypes.Property.substituteGenerics(Property.java:218) [1.7%]
...................................................com.google.javascript.jscomp.newtypes.JSType.substituteGenerics(JSType.java:698) [1.7%]
....................................................com.google.javascript.jscomp.newtypes.ObjectType.substituteGenerics(ObjectType.java:1584) [1.6%]

Then, replacing Highcharts.PlotOptions also with * reduces this about another 10x to about 2 seconds.

@supersteves
Copy link
Contributor Author

Using yesterday's tip. Same performance issue as last March's version - not a regression.

@dimvar
Copy link
Contributor

dimvar commented Oct 27, 2017

It's probably the issue discussed here: https://groups.google.com/forum/#!searchin/closure-compiler-discuss/NaivePersistentMap%7Csort:date/closure-compiler-discuss/bGWbLpsoVZU/rEElP2goDgAJ

Can you check if using the Clojure data structures fixes it?

@supersteves
Copy link
Contributor Author

Pretty sure I've already got Clojure 1.8 in the classpath, as that post was something I reported a while back and solved. I'll check again.

@supersteves
Copy link
Contributor Author

Definitely not NaivePersistentMap. In the same JVM, Class.forName("clojure.lang.PersistentHashMap"); succeeds.

@dimvar
Copy link
Contributor

dimvar commented Oct 27, 2017

OK, I'll take a look and report back. It may be a few days though.

@dimvar dimvar self-assigned this Oct 27, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@dimvar @supersteves