dart2js: Use frequency of occurence to sort metadata indices.

pkg/compiler/lib/src/js_emitter/metadata_collector.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart2js.js_emitter;
 
+abstract class _MetadataEntry extends jsAst.TokenNumber implements Comparable {
+  jsAst.Expression get entry;
+  int get value;
+  int get _rc;

[karlklose, 2015/05/28 09:39:53]

Could you add comments for this class and _rc?

[herhut, 2015/06/01 12:09:42]

Done.

+
+  markSeen();
+}
+
+class _BoundMetadataEntry extends _MetadataEntry {
+  int _value = -1;
+  int _rc = 0;
+  final jsAst.Expression entry;
+
+  _BoundMetadataEntry(this.entry);
+
+  bool get isFinalized => _value != -1;
+
+  finalize(int value) {
+    assert(!isFinalized);
+    _value = value;
+  }
+
+  int get value {
+    if (!isFinalized) print ("OHA! I have no value!");

[karlklose, 2015/05/28 09:39:53]

Remove/replace debug print.

[herhut, 2015/06/01 12:09:42]

Done.

+    assert(isFinalized);
+    return _value;
+  }
+
+  markSeen() => _rc++;
+
+  int compareTo(_MetadataEntry other) => other._rc - this._rc;
+}
+
+abstract class Placeholder implements jsAst.TokenNumber {
+  bind(_MetadataEntry entry);
+}
+
+class _ForwardingMetadataEntry extends _MetadataEntry implements Placeholder {
+  _MetadataEntry _forwardTo;
+  var debugData;
+  var trace;
+
+  bool get isBound => _forwardTo != null;
+
+  _ForwardingMetadataEntry([this.debugData, this.trace]);
+
+  _MetadataEntry get forwardTo {
+     assert(isBound);
+     return _forwardTo;
+   }
+
+  jsAst.Expression get entry {
+    if (isBound) return forwardTo.entry;
+    return new jsAst.LiteralString('"BOGUS: $debugData"');

[karlklose, 2015/05/28 09:39:53]

assert(isBound) or throw?

[herhut, 2015/06/01 12:09:42]

Done.

+  }
+
+  int get value {
+    if (isBound) return forwardTo.value;
+    return -336699;

[sra1, 2015/05/27 19:38:51]

Should this be
  assert(isBound);
?

[herhut, 2015/06/01 12:09:42]

Done.

+  }
+
+  int get _rc => forwardTo._rc;
+  markSeen() {
+    if (isBound) forwardTo.markSeen();
+  }
+  int compareTo(other) => forwardTo.compareTo(other);
+
+  bind(_MetadataEntry entry) {
+    assert(!isBound);
+    _forwardTo = entry;
+  }
+}
+
+class _MetadataList extends jsAst.TokenExpression {
+  jsAst.Expression _value;
+
+  void setExpression(jsAst.Expression value) {
+    assert(_value == null);
+    _value = value;
+  }
+
+  jsAst.Expression get value {
+    assert(_value != null);
+    return _value;
+  }
+}
+
 class MetadataCollector {
   final Compiler _compiler;
   final Emitter _emitter;
 
-  /// A list of JS expressions that represent metadata, parameter names and
-  /// type variable types.
-  final List<jsAst.Expression> globalMetadata = <jsAst.Expression>[];
+  /// A token for a list of expressions that represent metadata, parameter names
+  /// and type variable types.
+  final _MetadataList _globalMetadata = new _MetadataList();
+
+  jsAst.Expression get globalMetadata => _globalMetadata;
+
+  final jsAst.Expression _globalMetadataToken = new _MetadataList();
 
   /// A map used to canonicalize the entries of globalMetadata.
-  final Map<String, int> _globalMetadataMap = <String, int>{};
+  Map<String, _BoundMetadataEntry> _globalMetadataMap;
 
-  /// A map with lists of JS expressions, one list for each output unit. The
-  /// entries represent types including function types and typedefs.
-  final Map<OutputUnit, List<jsAst.Expression>> types =
-      <OutputUnit, List<jsAst.Expression>>{};
+  /// A map with a token for a lists of JS expressions, one token for each
+  /// output unit. Once finalized, the entries represent types including
+  /// function types and typedefs.
+  Map<OutputUnit, _MetadataList> _typesTokens =
+      new Map<OutputUnit, _MetadataList>();
+
+  jsAst.Expression getTypesForOutputUnit(OutputUnit outputUnit) {
+    return _typesTokens.putIfAbsent(outputUnit, () => new _MetadataList());
+  }
 
   /// A map used to canonicalize the entries of types.
-  final Map<OutputUnit, Map<String, int>> _typesMap =
-      <OutputUnit, Map<String, int>>{};
+  Map<OutputUnit, Map<DartType, _BoundMetadataEntry>> _typesMap =
+      <OutputUnit, Map<DartType, _BoundMetadataEntry>>{};
 
-  MetadataCollector(this._compiler, this._emitter);
+  MetadataCollector(this._compiler, this._emitter) {
+    _globalMetadataMap = new Map<String, _BoundMetadataEntry>();
+  }
 
   JavaScriptBackend get _backend => _compiler.backend;
   TypeVariableHandler get _typeVariableHandler => _backend.typeVariableHandler;
 
   bool _mustEmitMetadataFor(Element element) {
     return _backend.mustRetainMetadata &&
         _backend.referencedFromMirrorSystem(element);
   }
 
   /// The metadata function returns the metadata associated with
@@ skipping 19 matching lines @@
             metadata.add(_emitter.constantReference(constant.value));
           }
         }
       }
       if (metadata.isEmpty) return null;
       return js('function() { return # }',
           new jsAst.ArrayInitializer(metadata));
     });
   }
 
-  List<int> reifyDefaultArguments(FunctionElement function) {
+  List<jsAst.TokenNumber> reifyDefaultArguments(FunctionElement function) {
     FunctionSignature signature = function.functionSignature;
     if (signature.optionalParameterCount == 0) return const [];
-    List<int> defaultValues = <int>[];
+    List<jsAst.TokenNumber> defaultValues = <jsAst.TokenNumber>[];
     for (ParameterElement element in signature.optionalParameters) {
       ConstantExpression constant =
           _backend.constants.getConstantForVariable(element);
-      jsAst.Expression expression = (constant == null)
-          ? null
-          : _emitter.constantReference(constant.value);
-      defaultValues.add(addGlobalMetadata(expression));
+      jsAst.Expression representation = (constant == null)
+          ? new jsAst.LiteralNull()
+          : _emitter.constantReference(constant.value);;
+      defaultValues.add(_addGlobalMetadata(representation));
     }
     return defaultValues;
   }
 
-  int reifyMetadata(MetadataAnnotation annotation) {
+  jsAst.Expression reifyMetadata(MetadataAnnotation annotation) {
     ConstantExpression constant =
         _backend.constants.getConstantForMetadata(annotation);
     if (constant == null) {
       _compiler.internalError(annotation, 'Annotation value is null.');
-      return -1;
+      return null;
     }
-    return addGlobalMetadata(_emitter.constantReference(constant.value));
+    return _addGlobalMetadata(_emitter.constantReference(constant.value));
   }
 
-  int reifyType(DartType type, {bool ignoreTypeVariables: false}) {
+  jsAst.Expression reifyType(DartType type, {ignoreTypeVariables: false}) {
     return reifyTypeForOutputUnit(type,
                                   _compiler.deferredLoadTask.mainOutputUnit,
                                   ignoreTypeVariables: ignoreTypeVariables);
   }
 
-  int reifyTypeForOutputUnit(DartType type, OutputUnit outputUnit,
-                             {bool ignoreTypeVariables: false}) {
-    jsAst.Expression representation =
-        _backend.rti.getTypeRepresentation(
-            type,
-            (variable) {
-              if (ignoreTypeVariables) return new jsAst.LiteralNull();
-              return js.number(
-                  _typeVariableHandler.reifyTypeVariable(
-                      variable.element));
-            },
-            (TypedefType typedef) {
-              return _backend.isAccessibleByReflection(typedef.element);
-            });
+  jsAst.Expression reifyTypeForOutputUnit(DartType type,
+                                          OutputUnit outputUnit,
+                                          {ignoreTypeVariables: false}) {
+    return addTypeInOutputUnit(type, outputUnit,
+                               ignoreTypeVariables: ignoreTypeVariables);
+  }
+
+  jsAst.Expression reifyName(String name) {
+    return _addGlobalMetadata(js.string(name));
+  }
+
+  jsAst.Expression reifyExpression(jsAst.Expression expression) {
+    return _addGlobalMetadata(expression);
+  }
+
+  Placeholder getMetadataPlaceholder([debug]) => new _ForwardingMetadataEntry(debug);

[sra1, 2015/05/27 19:38:50]

line length

[herhut, 2015/06/01 12:09:41]

Done.

+
+  _MetadataEntry _addGlobalMetadata(jsAst.Node node) {
+    String printed = jsAst.prettyPrint(node, _compiler).getText();
+    return _globalMetadataMap.putIfAbsent(printed, () {
+      return new _BoundMetadataEntry(node);
+    });
+  }
+
+  jsAst.Expression _computeTypeRepresentation(DartType type,
+                                              {ignoreTypeVariables: false}) {
+    jsAst.Expression representation = _backend.rti.getTypeRepresentation(
+        type,
+        (variable) {
+          if (ignoreTypeVariables) return new jsAst.LiteralNull();
+          return _typeVariableHandler.reifyTypeVariable(variable.element);
+        },
+        (TypedefType typedef) {
+          return _backend.isAccessibleByReflection(typedef.element);
+        });
 
     if (representation is jsAst.LiteralString) {
       // We don't want the representation to be a string, since we use
       // strings as indicator for non-initialized types in the lazy emitter.
       _compiler.internalError(
           NO_LOCATION_SPANNABLE, 'reified types should not be strings.');
     }
 
-    return addTypeInOutputUnit(representation, outputUnit);
+    return representation;
+
   }
 
-  int reifyName(String name) {
-    return addGlobalMetadata(js('"$name"'));
-  }
-
-  int addGlobalMetadata(jsAst.Expression expression) {
-    // TODO(sigmund): consider adding an effient way to compare expressions
-    String string = jsAst.prettyPrint(expression, _compiler).getText();
-    return _globalMetadataMap.putIfAbsent(string, () {
-      globalMetadata.add(expression);
-      return globalMetadata.length - 1;
+  jsAst.Expression addTypeInOutputUnit(DartType type,
+                                       OutputUnit outputUnit,
+                                       {ignoreTypeVariables: false}) {
+    if (_typesMap[outputUnit] == null) {
+      _typesMap[outputUnit] = new Map<DartType, _BoundMetadataEntry>();
+    }
+    return _typesMap[outputUnit].putIfAbsent(type, () {
+      return new _BoundMetadataEntry(
+          _computeTypeRepresentation(type,
+                                     ignoreTypeVariables: ignoreTypeVariables));
     });
   }
 
-  int addTypeInOutputUnit(jsAst.Expression type, OutputUnit outputUnit) {
-    String string = jsAst.prettyPrint(type, _compiler).getText();
-    if (_typesMap[outputUnit] == null) {
-      _typesMap[outputUnit] = <String, int>{};
-    }
-    return _typesMap[outputUnit].putIfAbsent(string, () {
-
-      if (types[outputUnit] == null) {
-        types[outputUnit] = <jsAst.Expression>[];
-      }
-
-      types[outputUnit].add(type);
-      return types[outputUnit].length - 1;
-    });
-  }
-
-  List<int> computeMetadata(FunctionElement element) {
+  List<jsAst.TokenNumber> computeMetadata(FunctionElement element) {
     return _compiler.withCurrentElement(element, () {
-      if (!_mustEmitMetadataFor(element)) return const <int>[];
-      List<int> metadata = <int>[];
+      if (!_mustEmitMetadataFor(element)) return const <jsAst.TokenNumber>[];
+      List<jsAst.TokenNumber> metadata = <jsAst.TokenNumber>[];
       Link link = element.metadata;
       // TODO(ahe): Why is metadata sometimes null?
       if (link != null) {
         for (; !link.isEmpty; link = link.tail) {
           metadata.add(reifyMetadata(link.head));
         }
       }
       return metadata;
     });
   }
+
+  void countTokensInProgram(jsAst.Program program) {
+    TokenCounter visitor = new TokenCounter();
+    visitor.countTokens(program);
+  }
+
+  void finalizeTokens() {
+    void checkTokensInTypes(OutputUnit outputUnit, entries) {
+      UnBoundDebugger debugger = new UnBoundDebugger(outputUnit);
+      for (_BoundMetadataEntry entry in entries) {
+        if (entry._rc == 0) {

[karlklose, 2015/05/28 09:39:53]

Add/use helper in _BoundMetadataEntry?

[herhut, 2015/06/01 12:09:42]

Done.

+          print("UNUSED ${entry.hashCode}");

[karlklose, 2015/05/28 09:39:53]

Remove debug print?

[herhut, 2015/06/01 12:09:41]

Done.

+          continue;
+        }
+        debugger.findUnboundPlaceholders(entry.entry);
+      }
+    }
+    void countTokensInTypes(Iterable<_BoundMetadataEntry> entries) {
+      TokenCounter counter = new TokenCounter();
+      entries.where((_BoundMetadataEntry e) => e._rc > 0)
+             .map((_BoundMetadataEntry e) => e.entry)
+             .forEach(counter.countTokens);
+    }
+
+     jsAst.ArrayInitializer finalizeMap(Map<dynamic, _BoundMetadataEntry> map) {

[sra1, 2015/05/27 19:38:50]

Indentation

[herhut, 2015/06/01 12:09:42]

Done.

+      bool isUsed(_BoundMetadataEntry entry) => entry._rc > 0;

[karlklose, 2015/05/28 09:39:53]

Move this helper to _BoundMetaDataEntry?

[herhut, 2015/06/01 12:09:42]

Done.

+      List<_BoundMetadataEntry> entries = map.values.where(isUsed).toList();
+      entries.sort();

[sra1, 2015/05/27 19:38:50]

Sort is not stable.
Equivalence classes by reference count will be ordered arbitrarily.

[herhut, 2015/06/01 12:09:41]

True but this is not a regression. The original implementation assigned them
first come first served. At least there is now a place where one could improve
stability.

+
+      int count = 0;
+      for (_BoundMetadataEntry entry in entries) {
+        entry.finalize(count++);
+      }

[sra1, 2015/05/27 20:30:15]

Longer term I think we need to be more sophisticated to control build-to-build
differences.  We could bucket entries by number of digits and then allocate
within the bucket by some deterministic feature-based allocation.  This would
protect the large number of low reference-count entries being moved due to
something being 'promoted' over them by an additional reference or two.

[herhut, 2015/06/01 12:09:42]

Acknowledged.

+
+      List<jsAst.Node> values =
+          entries.map((_BoundMetadataEntry e) => e.entry).toList();
+
+       return new jsAst.ArrayInitializer(values);
+    }
+
+    _globalMetadata.setExpression(finalizeMap(_globalMetadataMap));
+
+    _typesTokens.forEach((OutputUnit outputUnit, _MetadataList token) {
+      Map typesMap = _typesMap[outputUnit];
+      if (typesMap != null) {
+        checkTokensInTypes(outputUnit, typesMap.values);
+        countTokensInTypes(typesMap.values);
+        token.setExpression(finalizeMap(typesMap));
+      } else {
+        token.setExpression(new jsAst.ArrayInitializer([]));
+      }
+    });
+  }
 }
+
+class TokenCounter extends jsAst.BaseVisitor {
+  visitTokenNumber(jsAst.TokenNumber token) {
+    if (token is _MetadataEntry) {
+      token.markSeen();
+    }
+  }
+
+  void countTokens(jsAst.Node node) => node.accept(this);
+}
+
+class UnBoundDebugger extends jsAst.BaseVisitor {
+  OutputUnit outputUnit;
+
+  UnBoundDebugger(this.outputUnit);
+
+  visitTokenNumber(jsAst.TokenNumber token) {
+    if (token is _ForwardingMetadataEntry && !token.isBound) {
+      print("UNBOUND ${outputUnit.name} ${token.debugData} ${token.debugData.hashCode}");

[karlklose, 2015/05/28 09:39:53]

Remove debug print.

[herhut, 2015/06/01 12:09:41]

Turned the entire thing into an assertion.

+    }
+  }
+
+  void findUnboundPlaceholders(jsAst.Node node) => node.accept(this);
+}