Optimize const construction

tool/input_sdk/private/ddc_runtime/operations.dart

Index: tool/input_sdk/private/ddc_runtime/operations.dart
diff --git a/tool/input_sdk/private/ddc_runtime/operations.dart b/tool/input_sdk/private/ddc_runtime/operations.dart
index b83e85d98550aba6894729bdc11068c0d90363c6..6da7148b9f3eefb897062bef3febb8bf6674e647 100644
--- a/tool/input_sdk/private/ddc_runtime/operations.dart
+++ b/tool/input_sdk/private/ddc_runtime/operations.dart
@@ -417,7 +417,12 @@ multiKeyPutIfAbsent(map, keys, valueFn) => JS('', '''(() => {
   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()');
 
 ///
@@ -429,7 +434,21 @@ final constants = JS('', 'new Map()');
 ///
 @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.
   //
@@ -440,13 +459,49 @@ const_(obj) => JS('', '''(() => {
   // 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