More memory efficient use of Lists and Mapss in the analyzer.

[mkustermann]

The analyzer is a heavy user of Lists and Maps in the AST and the Element model.

When running analyzer on flutter for 2 rounds (first warms up the memory store, second uses the cached outlines/... in memory store) the second round (after resolving all files) consumes around 470 MB. Out of that we have

• 24 MB growable list objects (which have non-growable lists as backing stores)
• 16 MB linked hash maps (which have non-growable lists & Uint32List as backing store)
• 99 MB non-growable lists objects
• 38 MB of Uint32List

=> We have 177 MB consumed by List/Map (out of 470 MB in total), i.e. 37%.

Growable lists in particular, they cost 32 bytes for the wrapper and the backing store is grown by 2x and therefore may often have unused space in them.

In almost all cases there's no need to use growable lists in the analyzer. All usages can be replaced by precise-length, non-growable lists. Furthermore, for empty lists, one should use a canonical representation of an empty list instead of having many empty list objects.

The top normal usages of growable lists in analyzer are

ElementLocationImpl package:analyzer/src/dart/element/element.dart
FunctionTypeImpl package:analyzer/src/dart/element/type.dart
ParameterElementImpl package:analyzer/src/dart/element/element.dart
NodeListImpl package:analyzer/src/dart/ast/ast.dart
InterfaceTypeImpl package:analyzer/src/dart/element/type.dart
MethodElementImpl package:analyzer/src/dart/element/element.dart
ClassElementImpl package:analyzer/src/dart/element/element.dart
EvaluationResultImpl package:analyzer/src/dart/constant/evaluation.dart
DefaultParameterElementImpl package:analyzer/src/dart/element/element.dart
PropertyAccessorElementImpl package:analyzer/src/dart/element/element.dart
DefaultFieldFormalParameterElementImpl package:analyzer/src/dart/element/element.dart
ConstructorElementImpl package:analyzer/src/dart/element/element.dart
UnlinkedLibraryImportDirective package:analyzer/src/dart/analysis/unlinked_data.dart
_Hierarchy package:analyzer/src/dart/element/class_hierarchy.dart
Interface package:analyzer/src/dart/element/inheritance_manager3.dart
CompilationUnitElementImpl package:analyzer/src/dart/element/element.dart
...

I've tried to see how much can be gained in cl/256843 and it seems to indicate at least 27 MB can be gained (21 MB removed growable lists, 6 MB in shorter non-growable lists).

The cl/256843 uses const [] in place of empty lists. This is good for memory - though mixing different kinds of lists (e.g. const/non-growable/growable) causes polymorphism and therefore slower code.

So my recommendation would be to enforce invariants: e.g. InterfaceTypeImpl.typeArguments will refer to a non-growable mutable list. That saves memory and will ensure access is not polymorphic.

/cc @scheglov @bwilkerson

[jacob314]

As some context: the CFE applied a similar change last year used for Dart2js.
cl/185825 for CFE)

[scheglov]

I'm not sure how you do these measurements, so I'm using a little expanded script that I used initially to get memory usage statistics for packages/flutter/lib. With CL/256843 I see some improvements, but more modest than you do.

Before:

With all elements resynthesized
                    Class   Instances      MBytes
   _InternalLinkedHashMap      141161        8.62
    _CompactLinkedHashSet        8763        0.53
                    _List      447444       42.68
            _GrowableList      324567        9.90
           _OneByteString      347576       47.76
           _TwoByteString         380       12.06
               _Uint8List       63705       28.68
          _Uint8ArrayView        3574        0.16
              _Uint32List      186359       21.36
         ClassElementImpl        4679        1.00
         FieldElementImpl       20062        3.37
        MethodElementImpl       19205        3.52
         MixinElementImpl          82        0.02
                Reference      283256       12.97
        InterfaceTypeImpl      112309        6.85
  Memory: 335605984

After:

With all elements resynthesized
                    Class   Instances      MBytes
   _InternalLinkedHashMap      141161        8.62
    _CompactLinkedHashSet        8763        0.53
                    _List      454963       42.41
            _GrowableList       47398        1.45
           _OneByteString      347592       47.76
           _TwoByteString         380       12.06
               _Uint8List       63752       28.69
          _Uint8ArrayView        3574        0.16
              _Uint32List      186359       21.36
         ClassElementImpl        4679        1.00
         FieldElementImpl       20062        3.37
        MethodElementImpl       19205        3.52
         MixinElementImpl          82        0.02
                Reference      283256       12.97
        InterfaceTypeImpl      112309        6.85
  Memory: 326432672

The difference is almost entirely in _GrowableList and saves us 8.5 MB, or about 2.5% of the total heap size.

Making InterfaceTypeImpl.typeArguments non-growable, and (most probably) non-modifiable is a good idea.

I will review the CL in details and update / land it.

[mkustermann]

I'm not sure how you do these measurements,

@scheglov see cl/259421 how I run the analyzer and collect the dart vm heap state

[srawlins]

I will review the CL in details and update / land it.

@scheglov I see that @mkustermann CL/256843 as it was just a proof-of-concept, but you mention you may land something similar yourself? Do you know if you landed similar changes, or if this is still very much a pending item?