FewestModules OOMs with dynamic dependencies

[gzm0]

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] )

Originally posted by @steinybot in #4906 (comment)

[gzm0]

@steinybot splitting this out, because this is almost certainly an algorithmic issue in the FewestModules analyzer (this is what happens if you build an algorithm yourself 🤷 ).

For starters, I would expect this to also happen in fastOpt (provided you run with FewestModules). Could you check that?

[gzm0]

Also, could you give me a rough ballpark of how many js.importDynamic statements are in your codebase?

[steinybot]

For starters, I would expect this to also happen in fastOpt (provided you run with FewestModules). Could you check that?

Yep it happens with fastOptJS (and of course fastLinkJS) too when using FewestModules.

Also, could you give me a rough ballpark of how many js.importDynamic statements are in your codebase?

There looks to be about 128 uses of js.dynamicImport.

[steinybot]

One thing that looked a little odd is how org.scalajs.linker.frontend.modulesplitter.Tagger#dynamicEdge appends the className onto the pathSteps. That doesn't create a circular path? Or are the pathSteps the full path including the key in allPaths?

For example here is the result of allPaths.get(className) when className = ClassName<web.layouts.PolicyEditLayoutEntryPoint$$anon$2>:

value = {Tagger$Paths@21089} org.scalajs.linker.frontend.modulesplitter.Tagger$Paths@5295e691
 direct = {HashSet@21091} size = 0
 dynamic = {HashMap@21092} size = 1
  0 = {Tuple2@21096} (ModuleID(main),org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@1414637)
   _1 = {ModuleSet$ModuleID@20677} ModuleID(main)
   _2 = {Tagger$DynamicPaths@21098} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@1414637
    content = {HashMap@21101} size = 1
     0 = {Tuple2@21105} (ClassName<web.routes.Route$B1PolicyEditLayout$$anon$46>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@64e17f12)
      _1 = {Names$ClassName@20784} ClassName<web.routes.Route$B1PolicyEditLayout$$anon$46>
      _2 = {Tagger$DynamicPaths@21107} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@64e17f12
       content = {HashMap@21110} size = 1
        0 = {Tuple2@21114} (ClassName<web.layouts.PolicyEditLayoutEntryPoint$$anon$2>,org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6db166f4)
         _1 = {Names$ClassName@20789} ClassName<web.layouts.PolicyEditLayoutEntryPoint$$anon$2>
         _2 = {Tagger$DynamicPaths@21116} org.scalajs.linker.frontend.modulesplitter.Tagger$DynamicPaths@6db166f4
          content = {HashMap@21119} size = 0
 maxExcludedHopCount = 0

[steinybot]

Ah I think this is an issue because it is doing a depth first traversal of the dependencies but it is searching for the shortest paths.

In our case we have a sealed trait web.routes.Route and the companion object contains all the cases (e.g. web.routes.Route$B1PolicyMovePropose). These have a dynamic import on the entry point (e.g. web.views.policy.b1.B1MoveViewEntryPoint). The entry point has another dynamic import on the view (it looks like it is also a static dependency which is kinda wrong but that's why it is missing from the paths shown at the top). Some of these views will then statically refer to other routes that can be navigated to (e.g. web.routes.Route$PolicyHistoryPage). This can continue until it gets to the end of the dependency graph which could be a fairly long number of steps. However, the final number of steps should never be more than 2. If it traversed all of the static dependencies of web.routes.Route before traversing the next level then this wouldn't happen.