google / google/closure-compiler

MaybeReachingVariableUse.flowThrough takes 4secs or 90% of Compiler.optimize ()

Open
#2,215 1 comment 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
JavaScript
Stars
7.7k
Forks
1.2k
Avg merge
2d 12h
Merged PRs (30d)
6

Description

I've finally decided to take a deep look into why it takes 5 seconds for GCC to process some of my JS files ("process" is minify JS using 'simple' optimizations).

It takes roughly 10 secs to process same file 2 times (5 sec per iteration).
File size is 134KB or 4800 lines.

It looks like root cause is in `com.google.javascript.jscomp.MaybeReachingVariableUse.flowThrough` (see profiler picture below).

This happens on the functions like this one:
```
function do_something_in_ctx(ctx) {
var c = ctx;

c.doSomthing("param");
... 4000 of other calls like c.doSomthingOther(); ...
}
```

It appears that code finally goes here:
https://github.com/google/closure-compiler/blob/master/src/com/google/javascript/jscomp/MaybeReachingVariableUse.java#L95
```
/**
* Copy constructor.
*
* @param other The constructed object is a replicated copy of this element.
*/
public ReachingUses(ReachingUses other) {
mayUseMap = HashMultimap.create(other.mayUseMap);
}
```
via this call stack

:96, MaybeReachingVariableUse$ReachingUses (com.google.javascript.jscomp)
flowThrough:146, MaybeReachingVariableUse (com.google.javascript.jscomp)
flowThrough:42, MaybeReachingVariableUse (com.google.javascript.jscomp)
flow:275, DataFlowAnalysis (com.google.javascript.jscomp)
analyze:212, DataFlowAnalysis (com.google.javascript.jscomp)
analyze:180, DataFlowAnalysis (com.google.javascript.jscomp)

In short - that line
https://github.com/google/closure-compiler/blob/master/src/com/google/javascript/jscomp/DataFlowAnalysis.java#L275
in such environment creates 4000 instances of HashMultimap with [0 .. 4000] items each, where each previous map is copied to next one with all the values one-by-one. As far as I understand all instances are stored as member properties of AST nodes.
This approach is both slow and extremely memory consuming (now I understand why GCC needs much memory). Note - current implementation of HashMultimap in copy-constructoror creates new instances of key()/value() Sets even when source is empty. I guess this should be forwarded to guava.

I would say that something needs to be done with that whole algorithm because it is hardly usable in such cases.

Here is a screenshot from NetBeans profiler.
![flowthrough](https://cloud.githubusercontent.com/assets/2301820/21469431/9564dcfe-ca5e-11e6-913f-634b310143fd.png)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.