CodeSplitter's not-exclusive CFA computation is quadratic in fragment count

[rhuanhianc]

CodeSplitter.computeNotExclusiveCfaForFragments builds, for every exclusive fragment, a ControlFlowAnalyzer that traverses the run-asyncs of every other fragment — F² traversals.

With 122 split points that is ~15,000 traversals; with 231, ~53,000. On a real application the loop alone is 25.6% of the permutation's CPU, and CodeSplitter is 181s of an 11-minute compile.

The iterations are independent and can run in parallel: the CFA copy constructor deep-copies every mutable set and the traversal only reads the JProgram. Doing so takes CodeSplitter from 181.4s to 71.5s, with byte-identical output.

Note that-XfragmentCountdoes not help here — the merge strategy replaces the F² loop with an O(F) per-run-async CFA loop of roughly the same cost.

[zbynek]

Not related to the issue, but 230 split points is a lot, the overhead of loading small fragements might outweigh the benefits. Maybe you can group related functionality into fewer split points.

[rhuanhianc]

Thanks for the tip @zbynek , you're right, and it's something I'd like to address eventually, It's a large legacy application that accumulated split points over many years, and consolidating them means reworking module boundaries across a lot of code, so it's not something I can do in the short term, that's part of why I started looking at the compiler side instead.

I did try -XfragmentCount 10 to see if merging would speed up the build and it made no difference.

[niloc132]

In my experience, you often can often outright disable split point for applications with huge numbers of split points and see great benefits - usually with more than 50 split points or so the "leftovers" chunk is larger than the "initial" and often as big as most of the individual permutations combined. Since the leftovers has to be downloaded before even one split point can be started, it should really be part of the initial download.

This doesn't diminish your patch, but mostly goes to "if you need this work, you very likely could improve your user experience dramatically at the same time as avoiding the compile time".

[rhuanhianc]

Interesting, I'd tried grouping before; my concern was always fragment size (for comparison, we have projects with up to 500 split points, yeah I' know), but I'd never tried turning splitting off entirely, so I measured both.

Build time

Full 2×2 on our largest module, 231 split points. Cold unit cache on every run, one build at a time, -localWorkers 1:

	splitting on	splitting off	gain from disabling
GWT 2.13.1	11:15	8:24	−25%
2.13.1 + both patches	4:23	3:23	−23%
gain from patches	−61%	−60%

Together: 11:15 → 3:23.

To be clear "both patches" means this PR and the JsInliner memoization one #10394 , and this PR is the smaller half. Of the 412 s saved with splitting on, the inliner accounts for ~312 s and this PR for ~104 s.

Per phase, from JFR:

Phase	stock + split	stock − split	patched + split	patched − split
JsInliner	328 s	324 s	16 s	17 s
CodeSplitter	176 s	absent	72 s	absent
Precompile	78 s	81 s	78 s	82 s
Unify	51 s	52 s	51 s	53 s
Pruner	10.8 s	11.8 s	10.8 s	12.8 s

Output — you were right @niloc132 , and more than I expected

	initial	leftovers	231 exclusive fragments	total
with splitting	11.91 MB	20.59 MB	6.60 MB	39.26 MB
without	38.83 MB	—	—	38.99 MB

Gzipped, the trade is:

	first screen	each screen after
with splitting	6.49 MB	7.5 KB + one blocking round trip
without	7.70 MB	0

[jnehlmeier]

@rhuanhianc Yeah, you really have to be careful with split point design and reevaluate regularly. Splitpointing everything is a real trap. If use use a single GWT-RPC endpoint (command pattern), then everything GWT-RPC related will be in leftovers. If you use external JS libraries in multiple split points (e.g. in multiple menu items) then these JS libraries will end up in leftovers. Same for GWT SDK UI or whatever UI library the application users.

I have a 10 MB application using GWT's activity + places and first I had splitpoints per activity. But over time they become tiny, especially with gzip. So I started grouping activities based on typical user interactions and roles (e.g. user-group-a vs. user-group-b vs. admin sections and menu items often used together for a common user story). At the end I ended up with like 12 split points or so with leftovers significantly reduced in size.

Finding a good balance isn't easy, especially if you also consider mobile with brittle connectivity or the update frequency of the application itself. For example continuous delivery with multiple updates a day/week hurts GWTs caching mechanism quite a bit and with a large application it can be annoying for users.

We also had users here with a lot of split points and they complained about the compiler requiring 64GB memory to complete. Have you also measured the required heap size for your compiles?

[niloc132]

The other thing that many teams miss is that split points operate in two ways - the usual way, where mutually exclusive chunks are taken out after initial split points (and leftovers left in a "first chunk" that has to be downloaded first), and the initial sequence, where each is assumed to come after those before it - no leftovers are possible, code simply moves to the earliest chunk it might belong to.

Most applications have a loading sequence of sorts that can at least use two of these - start the app and ask the user to log in, and load the main part of the app. If there is any more of a linear sequence after that (landing page, portal, etc), those can be specified as well, and keep the initial drops small. This can be mixed with the usual approach, so that after the initial sequence, the app can "fan out" into separate chunks.

This way you download just enough to start the app, then while the user is logging in, start downloading the next chunk without waiting for them to complete, and have it ready to go without the user experiencing the wait.

The configuration property "compiler.splitpoint.initial.sequence" drives this, see https://www.gwtproject.org/doc/latest/DevGuideCodeSplitting.html#sequence

In your particular case, its likely that the leftover 20mb section was loading pretty quickly after the initial chunk (in which case no split points might be best), or there might be a delay until the first action that would trigger one of the other split points (which would suggest grouping many/most of the split points together).

Note also that fragment merging won't improve compile times much (if at all), but will instead produce better output - odds are high you have many sub-1k split points, and it probably doesn't make sense to have any smaller than 10-100kb (better to merge into leftovers via "compiler.splitpoint.leftovermerge.size", or merge with other split points).

--

I'll take a look soon at the various patches, thanks for contributing them. I'm glad JFR is helping.

[rhuanhianc]

@jnehlmeier
We also had users here with a lot of split points and they complained about the compiler requiring 64GB memory to complete. Have you also measured the required heap size for your compiles?

This test took quite a while to complete, but fortunately, I obtained all the results, and they confirm what you said about RAM usage.

In short, without the split, the application used significantly less RAM—managing to generate the output with an Xmx of 3GB—whereas with the split enabled, it throws an OOM error and requires an Xmx of 10GB.

Descending -Xmx ladder on the same module (231 split points), cold unit cache, one build at a time, -localWorkers 1:
I haven't tested it with 9GB—I have a hunch it would work—but the standard for this project was 10GB, so...

	12g	10g	8g	6g	5g	4g	3g	2.5g
splitting off	OK	OK	OK	OK	OK	OK	OK	OOM
splitting on	OK	OK	OOM	—	—	—	—	—

Obs: dropping from 12 GB to 3 GB cost only ~8% in build time (202.7 s → 219.6 s), I believe 4GB is the ideal amount; I'm looking into ways to group the splits based on the tips you shared. In any case, I've already achieved drastic improvements in the application thanks to you.

@niloc132
I'll take a look soon at the various patches, thanks for contributing them. I'm glad JFR is helping.

You have no idea how useful JFR is proving to be, haha—thanks a lot!

Thank you very much once again @niloc132 @zbynek @jnehlmeier