Investigate linker memory consumption

[gzm0]

IMO there are likely a couple of low-hanging fruits in terms of linker memory consumption. Last time I checked, a large portion of memory was taken by :: (List's cons). It would not surprise me if we could reduce memory consumption significantly by using array backed collections.

I'll file this as a follow-up and take a stab.

Originally posted by @gzm0 in #3767 (comment)

[gzm0]

Just TBC: we value speed over memory consumption in the linker in general, so in-scope here are only reductions that do not affect speed.

[gzm0]

I'm looking at heap Dominators for a Scala.js test suite run. Summary is the following

Size [MB]	Perc	What
910	58.0%	StandardLinkerImpl
312	29.9%	├─ LinkerFrontendImpl
38	2.4%	│ ├─ BaseLinker
38	2.4%	│ │ ├─ InfoLoader#cache
240	15.3%	│ ├─ IncOptimizer
32	2.1%	│ ├─ Refiner
32	2.1%	│ │ ├─ InfoLoader#cache
597	38.1%	├─ BasicLinkerBackend
177	11.3%	│ ├─ PrintedModuleSetCache#modules
251	16.0%	│ ├─ Emitter

For Emitter and IncOptimizer expanding the fields of the classes does not give a list summing up to the overall retained size. I need to investigate what this means and how to look at it.

[gzm0]

I have a WIP branch where I attempt to reduce the memory usage of the Emitter by fusing the two last transformation steps (emitting and printing) and caching the result only (remove the intermediate caches).

However, I'm running into issues with VisualVM and my YourKit evaluation has expired. YourKit offers free licenses for OSS projects, given they add a link to YourKit (https://www.yourkit.com/java/profiler/purchase/#os_license). @sjrd, would that be acceptable? If yes, I'd reach out to them.

[sjrd]

Sure, that is acceptable.

[gzm0]

WIP PR for YourKit on scala-js.org: scala-js/scala-js-website#620

I've reached out to sales for licenses for the two of us.

[gzm0]

So far, as part of this effort, we have the following changes targeting the linker backend:

• Fuse emitting and printing of trees in the backend #4917
• Compress SourceMapWriter.Fragment data #4965

After these, the frontend retains 215 MB on the test suite, whereas the backend retains 77 MB. Before going to more extreme measures (like #4963), I'll start focusing on the linker frontend.

All in all, the picture for the frontend is unchanged:

• BaseLinker: 26MB
• Optimizer: 166MB
• Refiner: 21MB

Observations

Optimizer

The optimizer mostly retains IR trees (both original and optimized def). The optimized defs are sometimes significantly larger (I've seen up to 4x).

Over 46% of the retained size of the optimizer goes to data structures (shallow sizes). Top 5:

• 15% scala.collection.concurrent.SNode (25MB)
• 10% scala.collection.immutable.:: (16MB)
• 8% scala.collection.concurrent.CNode (14MB)
• 7% scala.collection.concurrent.BasicNode[] (12MB)
• 6% scala.collection.concurrent.INode (10MB)

BaseLinker / Refiner

The retained sizes goes almost exclusively to the ClassInfoCache.

Inside these, top 5 shallow sizes:

• 31% ReachabilityInfoInClass (8MB)
• 28% :: (7.3MB)
• 9% scala.collection.mutable.HashEntry[] (2.3MB)
• 6% Infos$MethodInfo (1.6MB)
• 5% Infos$ReachabilityInfo (1.2MB)

[gzm0]

Optimizer retained size reduction from 166MB to 144MB.

• Replace (Par)TrieMap with ConcurrentHashMap in IncOptimizer #4974

BaseLinker / Refiner size reduction by 5MB each:

• Optimize memory consumption of Infos #4978

[gzm0]

BaseLinker / Refiner size reduction by ~5MB each:

• Optimize Infos for caching in InfoLoader #4981

[steinybot]

I'm getting OOME's with 10G of memory for fullLinkJS and FewestModules. About 98% of it is from org.scalajs.linker.frontend.modulesplitter.Tagger#allPaths.

Every entry that I looked at in here has a long hierarchy of dynamic dependencies with a lot of duplication although some differences. It seems like the way that this graph is constructed is not very memory efficient. For example:

0 = {Tuple2@24699} (ClassName<web.cps.v2.Checkbox$Group$>,org.scalajs.linker.frontend.modulesplitter.Tagger$Paths@1ffcae8f)
 _1 = {Names$ClassName@24900} ClassName<web.cps.v2.Checkbox$Group$>
 _2 = {Tagger$Paths@24901} org.scalajs.linker.frontend.modulesplitter.Tagger$Paths@1ffcae8f
  direct = {HashSet@24904} size = 0
  dynamic = {HashMap@24905} size = 1
   0 = {Tuple2@24909} (ModuleID(main),org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@28ee42f2)
    _1 = {ModuleSet$ModuleID@24315} ModuleID(main)
    _2 = {Tagger$DynamicPaths@24911} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@28ee42f2
     content = {HashMap@24914} size = 2
      0 = {Tuple2@24918} (ClassName<web.routes.Route$B1PolicyMovePropose$$anon$52>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@68ffc9ab)
       _1 = {Names$ClassName@24922} ClassName<web.routes.Route$B1PolicyMovePropose$$anon$52>
       _2 = {Tagger$DynamicPaths@24923} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@68ffc9ab
        content = {HashMap@24930} size = 1
         0 = {Tuple2@24934} (ClassName<web.views.policy.b1.B1MoveViewEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@7a18bd92)
          _1 = {Names$ClassName@24936} ClassName<web.views.policy.b1.B1MoveViewEntryPoint$$anon$2>
          _2 = {Tagger$DynamicPaths@24937} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@7a18bd92
           content = {HashMap@24940} size = 7
            0 = {Tuple2@24944} (ClassName<web.routes.Route$PolicyHistoryPage$$anon$31>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6cbc81eb)
             _1 = {Names$ClassName@24958} ClassName<web.routes.Route$PolicyHistoryPage$$anon$31>
             _2 = {Tagger$DynamicPaths@24959} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6cbc81eb
              content = {HashMap@24962} size = 1
               0 = {Tuple2@24966} (ClassName<web.pages.policy.a1.A1HistoryPageEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4776d944)
                _1 = {Names$ClassName@24968} ClassName<web.pages.policy.a1.A1HistoryPageEntryPoint$$anon$2>
                _2 = {Tagger$DynamicPaths@24969} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4776d944
                 content = {HashMap@24972} size = 2
                  0 = {Tuple2@24976} (ClassName<web.routes.Route$PolicyEditPage$$anon$35>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@43bbcab2)
                   _1 = {Names$ClassName@24985} ClassName<web.routes.Route$PolicyEditPage$$anon$35>
                   _2 = {Tagger$DynamicPaths@24986} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@43bbcab2
                    content = {HashMap@24989} size = 1
                     0 = {Tuple2@24993} (ClassName<web.pages.policy.a1.A1EditPageEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@13027986)
                      _1 = {Names$ClassName@24995} ClassName<web.pages.policy.a1.A1EditPageEntryPoint$$anon$2>
                      _2 = {Tagger$DynamicPaths@24996} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@13027986
                       content = {HashMap@24999} size = 6
                        0 = {Tuple2@25003} (ClassName<web.routes.Route$PolicyAddressHomePage$$anon$38>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@624f2e5b)
                         _1 = {Names$ClassName@25015} ClassName<web.routes.Route$PolicyAddressHomePage$$anon$38>
                         _2 = {Tagger$DynamicPaths@25016} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@624f2e5b
                          content = {HashMap@25019} size = 1
                           0 = {Tuple2@25023} (ClassName<web.pages.policy.a1.A1AddressPageEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@fc38aa3)
                            _1 = {Names$ClassName@25025} ClassName<web.pages.policy.a1.A1AddressPageEntryPoint$$anon$2>
                            _2 = {Tagger$DynamicPaths@25026} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@fc38aa3
                             content = {HashMap@25029} size = 1
                              0 = {Tuple2@25033} (ClassName<web.routes.Route$MtaAddressFormPage$$anon$29>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@31b82f68)
                               _1 = {Names$ClassName@25035} ClassName<web.routes.Route$MtaAddressFormPage$$anon$29>
                               _2 = {Tagger$DynamicPaths@25036} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@31b82f68
                                content = {HashMap@25039} size = 1
                                 0 = {Tuple2@25043} (ClassName<web.pages.policy.a1.A1ChangeAddressPageEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@2250500b)
                                  _1 = {Names$ClassName@25045} ClassName<web.pages.policy.a1.A1ChangeAddressPageEntryPoint$$anon$2>
                                  _2 = {Tagger$DynamicPaths@25046} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@2250500b
                                   content = {HashMap@25049} size = 1
                                    0 = {Tuple2@25053} (ClassName<web.routes.Route$MemberDashboard$$anon$13>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@2c06c0aa)
                                     _1 = {Names$ClassName@25055} ClassName<web.routes.Route$MemberDashboard$$anon$13>
                                     _2 = {Tagger$DynamicPaths@25056} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@2c06c0aa
                                      content = {HashMap@25059} size = 1
                                       0 = {Tuple2@25063} (ClassName<web.views.MemberDashboardViewEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@3f03d11b)
                                        _1 = {Names$ClassName@25065} ClassName<web.views.MemberDashboardViewEntryPoint$$anon$2>
                                        _2 = {Tagger$DynamicPaths@25066} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@3f03d11b
                                         content = {HashMap@25069} size = 1
                                          0 = {Tuple2@25073} (ClassName<web.routes.Route$QuoteLayout$$anon$1>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4f307afc)
                                           _1 = {Names$ClassName@25075} ClassName<web.routes.Route$QuoteLayout$$anon$1>
                                           _2 = {Tagger$DynamicPaths@25076} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4f307afc
                                            content = {HashMap@25079} size = 1
                                             0 = {Tuple2@25083} (ClassName<web.layouts.QuoteLayoutEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6fc0bb19)
                                              _1 = {Names$ClassName@25085} ClassName<web.layouts.QuoteLayoutEntryPoint$$anon$2>
                                              _2 = {Tagger$DynamicPaths@25086} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6fc0bb19
                                               content = {HashMap@25089} size = 1
                                                0 = {Tuple2@25093} (ClassName<web.routes.Route$SandboxPageIndex$$anon$68>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@755935db)
                                                 _1 = {Names$ClassName@25095} ClassName<web.routes.Route$SandboxPageIndex$$anon$68>
                                                 _2 = {Tagger$DynamicPaths@25096} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@755935db
                                                  content = {HashMap@25099} size = 1
                                                   0 = {Tuple2@25103} (ClassName<web.pages.SandboxPageEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@54f3b962)
                                                    _1 = {Names$ClassName@25105} ClassName<web.pages.SandboxPageEntryPoint$$anon$2>
                                                    _2 = {Tagger$DynamicPaths@25106} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@54f3b962
                                                     content = {HashMap@25109} size = 0
                        1 = {Tuple2@25004} (ClassName<web.routes.Route$PolicyRenewalPage$$anon$32>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@7f3c96fa)
                        2 = {Tuple2@25005} (ClassName<web.routes.Route$ProfileLandingPage$$anon$22>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4581ee3d)
                        3 = {Tuple2@25006} (ClassName<web.routes.Route$PolicyCancelPage$$anon$39>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@45cf6142)
                        4 = {Tuple2@25007} (ClassName<web.routes.Route$DashboardLayout$$anon$11>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@5ee9b256)
                        5 = {Tuple2@25008} (ClassName<web.routes.Route$MtaCoverageFormPage$$anon$28>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@45796437)
                  1 = {Tuple2@24977} (ClassName<web.routes.Route$A1DashboardLayout$$anon$34>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@11056040)
            1 = {Tuple2@24945} (ClassName<web.routes.Route$PolicyAddressChangePage$$anon$30>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@33fda44e)
            2 = {Tuple2@24946} (ClassName<web.routes.Route$MtaAddNamedInsuredPage$$anon$36>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@4faf36be)
            3 = {Tuple2@24947} (ClassName<web.routes.Route$MtaAddInterestPage$$anon$37>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@7064f6f4)
            4 = {Tuple2@24948} (ClassName<web.routes.Route$B1PolicyEditLayout$$anon$46>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@78df82ca)
            5 = {Tuple2@24949} (ClassName<web.routes.Route$A1PolicyEditLayout$$anon$27>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@26de964b)
            6 = {Tuple2@24950} (ClassName<web.routes.Route$A1DashboardLayout$$anon$34>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@10724ee8)
      1 = {Tuple2@24919} (ClassName<web.routes.Route$B1PolicyEditLayout$$anon$46>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@faa0694)
       _1 = {Names$ClassName@24926} ClassName<web.routes.Route$B1PolicyEditLayout$$anon$46>
       _2 = {Tagger$DynamicPaths@24927} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@faa0694
  maxExcludedHopCount = 0

I was trying to fix our module splits by adding more dynamic imports. We have routes which import entry points and then those entry points import the views. It didn't OOM until I added the imports in the entry points (but the splits weren't right). It still doesn't look like I have the imports right (looks like the route is pulling in the layouts) but it shouldn't OOM.

In case it helps:

sbt:goodcover> show client/fullLinkJS/scalaJSLinkerConfig
[info] StandardConfig(
[info]   semantics                  = Semantics(
[info]   asInstanceOfs          = Unchecked,
[info]   arrayIndexOutOfBounds  = Unchecked,
[info]   arrayStores            = Unchecked,
[info]   negativeArraySizes     = Unchecked,
[info]   nullPointers           = Unchecked,
[info]   stringIndexOutOfBounds = Unchecked,
[info]   moduleInit             = Unchecked,
[info]   strictFloats           = true,
[info]   productionMode         = true
[info] ),
[info]   moduleKind                 = ESModule,
[info]   moduleSplitStyle           = FewestModules,
[info]   esFeatures                 = ESFeatures(
[info]   esVersion = ECMAScript 2021 (edition 12),
[info]   useECMAScript2015Semantics = true,
[info]   allowBigIntsForLongs = false,
[info]   avoidClasses = true,
[info]   avoidLetsAndConsts = true
[info] ),
[info]   checkIR                    = true,
[info]   optimizer                  = true,
[info]   jsHeader                   = "",
[info]   parallel                   = true,
[info]   sourceMap                  = true,
[info]   relativizeSourceMapBase    = None,
[info]   outputPatterns             = OutputPatterns(
[info]   jsFile        = %s.js,
[info]   sourceMapFile = %s.js.map,
[info]   moduleName    = ./%s.js,
[info]   jsFileURI     = %s.js,
[info]   sourceMapURI  = %s.js.map,
[info] ),
[info]   minify                     = true,
[info]   closureCompilerIfAvailable = false,
[info]   prettyPrint                = false,
[info]   batchMode                  = false,
[info]   maxConcurrentWrites        = 50,
[info] )