Optimize const construction

tool/input_sdk/private/ddc_runtime/operations.dart

 // Copyright (c) 2015, 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.
 
 /// This library defines runtime operations on objects used by the code
 /// generator.
 part of dart._runtime;
 
 _canonicalFieldName(obj, name, args, displayName) => JS('', '''(() => {
   $name = $canonicalMember($obj, $name);
@@ skipping 399 matching lines @@
       $map.set(k, value = new Map());
     }
     $map = value;
   }
   if ($map.has($_value)) return $map.get($_value);
   let value = $valueFn();
   $map.set($_value, value);
   return value;
 })()''');
 
-/// The global constant table. */
+/// The global constant table.
+/// This maps the number of names in the object (n)
+/// to a path of length 2*n of maps indexed by the name and
+/// and value of the field.  The final map is
+/// indexed by runtime type, and contains the canonical
+/// version of the object.
 final constants = JS('', 'new Map()');
 
 ///
 /// Canonicalize a constant object.
 ///
 /// Preconditions:
 /// - `obj` is an objects or array, not a primitive.
 /// - nested values of the object are themselves already canonicalized.
 ///
 @JSExportName('const')
 const_(obj) => JS('', '''(() => {
-  let objectKey = [$getReifiedType($obj)];
+  // TODO(leafp): This table gets quite large in apps.
+  // Keeping the paths is probably expensive.  It would probably
+  // be more space efficient to just use a direct hash table with
+  // an appropriately defined structural equality function.
+  function lookupNonTerminal(map, key) {
+    let result = map.get(key);
+    if (result !== void 0) return result;
+    map.set(key, result = new Map());
+    return result;
+  };
+  let names = $getOwnNamesAndSymbols($obj);
+  let count = names.length;
+  // Index by count.  All of the paths through this map
+  // will have 2*count length.
+  let map = lookupNonTerminal($constants, count);
   // TODO(jmesserly): there's no guarantee in JS that names/symbols are
   // returned in the same order.
   //
   // We could probably get the same order if we're judicious about
   // initializing fields in a consistent order across all const constructors.
   // Alternatively we need a way to sort them to make consistent.
   //
   // Right now we use the (name,value) pairs in sequence, which prevents
   // an object with incorrect field values being returned, but won't
   // canonicalize correctly if key order is different.
-  for (let name of $getOwnNamesAndSymbols($obj)) {
-    objectKey.push(name);
-    objectKey.push($obj[name]);
+  for (let i = 0; i < count; i++) {
+    let name = names[i];
+    map = lookupNonTerminal(map, name);
+    map = lookupNonTerminal(map, $obj[name]);
   }
-  return $multiKeyPutIfAbsent($constants, objectKey, () => $obj);
+  // TODO(leafp): It may be the case that the reified type
+  // is always one of the keys already used above?
+  let type = $getReifiedType($obj);
+  let value = map.get(type);
+  if (value) return value;
+  map.set(type, $obj);
+  return $obj;
 })()''');
 
+/// The global constant list table.
+/// This maps the number of elements in the list (n)
+/// to a path of length n of maps indexed by the value
+/// of the field.  The final map is indexed by the element
+/// type and contains the canonical version of the list.
+final constantLists = JS('', 'new Map()');
+
+///
+/// Canonicalize a constant list
+///
+@JSExportName('constList')
+constList_(elements, elementType) => JS('', '''(() => {
+  function lookupNonTerminal(map, key) {
+    let result = map.get(key);
+    if (result !== void 0) return result;
+    map.set(key, result = new Map());
+    return result;
+  };
+  let count = $elements.length;
+  let map = lookupNonTerminal($constantLists, count);
+  for (let i = 0; i < count; i++) {
+    map = lookupNonTerminal(map, elements[i]);
+  }
+  let value = map.get($elementType);
+  if (value) return value;
+  value = $list($elements, $elementType);
+  map.set($elementType, value);
+  return value;
+})()''');
 
 // The following are helpers for Object methods when the receiver
 // may be null or primitive.  These should only be generated by
 // the compiler.
 hashCode(obj) {
   if (obj == null) return 0;
 
   switch (JS('String', 'typeof #', obj)) {
     case "number":
       return JS('','# & 0x1FFFFFFF', obj);
@@ skipping 71 matching lines @@
     constructor(dartIterator) {
       this.dartIterator = dartIterator;
     }
     next() {
       let i = this.dartIterator;
       let done = !i.moveNext();
       return { done: done, value: done ? void 0 : i.current };
     }
   }
 ''');