Remove O(n^2) loop in serialized script value conversions

sdk/lib/html/html_common/conversions.dart

Index: sdk/lib/html/html_common/conversions.dart
diff --git a/sdk/lib/html/html_common/conversions.dart b/sdk/lib/html/html_common/conversions.dart
index de0d423258d971447938882f573cc9e49e86fd09..fa7f43c0e55fff2aa9fd49cc3886c423bd2d4c7d 100644
--- a/sdk/lib/html/html_common/conversions.dart
+++ b/sdk/lib/html/html_common/conversions.dart
@@ -58,21 +58,15 @@ convertNativeToDart_SerializedScriptValue(object) {
  */
 abstract class _StructuredClone {
 
-  // TODO(sra): Replace slots with identity hash table.
-  var values = [];
-  var copies = [];  // initially 'null', 'true' during initial DFS, then a copy.
-
-  int findSlot(value) {
-    int length = values.length;
-    for (int i = 0; i < length; i++) {
-      if (identical(values[i], value)) return i;
-    }
-    values.add(value);
-    copies.add(null);
-    return length;
+  // Keep track of the clones, keyed by the original object. If we're
+  // not copying, these may be the same.
+  var clones = new HashMap.identity();

[sra1, 2016/03/22 00:54:21]

Be careful here.

The implementation of identityHashCode puts a property on the object.
The effect is to modify the data you are serializing.
It might be necessary to change how identity hash codes work.
Is it possible to add a property in such a way that it does not pass through all
the APIs that use structured clones?

[Alan Knight, 2016/03/22 18:00:01]

OK, I moved the code to use an identity map down into the Dartium-specific
version, and left the general/dart2js version as is. So it shares less code but
avoids the issue of polluting JS objects with the identityHash property. It's
only really a performance problem on Dartium, on accepting a structured clone.

+
+  Object findSlot(value) {
+    return clones.putIfAbsent(value, () => null);
   }
-  readSlot(int i) => copies[i];
-  writeSlot(int i, x) { copies[i] = x; }
+  readSlot(Object original) => clones[original];
+  writeSlot(Object original, clone) { clones[original] = clone; }
   cleanupSlots() {}  // Will be needed if we mark objects with a property.
   bool cloneNotRequired(object);
   newJsMap();
@@ -109,11 +103,10 @@ abstract class _StructuredClone {
     if (cloneNotRequired(e)) return e;
 
     if (e is Map) {
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
       copy = newJsMap();
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
       e.forEach((key, value) {
         putIntoMap(copy, key, walk(value));
       });
@@ -126,21 +119,20 @@ abstract class _StructuredClone {
       // to copy anything reachable from the array.  However, the list may have
       // non-native properties or methods from interceptors and such, e.g.
       // an immutability marker. So we  had to stop doing that.
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
-      copy = copyList(e, slot);
+      copy = copyList(e);
       return copy;
     }
 
     throw new UnimplementedError('structured clone of other type');
   }
 
-  copyList(List e, int slot) {
+  copyList(List e) {
     int i = 0;
     int length = e.length;
     var copy = newJsList(length);
-    writeSlot(slot, copy);
+    writeSlot(e, copy);
     for ( ; i < length; i++) {
       copy[i] = walk(e[i]);
     }
@@ -174,26 +166,19 @@ abstract class _StructuredClone {
  */
 abstract class _AcceptStructuredClone {
 
-  // TODO(sra): Replace slots with identity hash table.
-  var values = [];
-  var copies = [];  // initially 'null', 'true' during initial DFS, then a copy.
+  // Keep track of the clones, keyed by the original object. If we're
+  // not copying, these may be the same.
+  var clones = new HashMap.identity();
   bool mustCopy = false;
 
-  int findSlot(value) {
-    int length = values.length;
-    for (int i = 0; i < length; i++) {
-      if (identicalInJs(values[i], value)) return i;
-    }
-    values.add(value);
-    copies.add(null);
-    return length;
+  Object findSlot(value) {
+    return clones.putIfAbsent(value, () => null);
   }
 
   /// Are the two objects identical, but taking into account that two JsObject
   /// wrappers may not be identical, but their underlying Js Object might be.
   bool identicalInJs(a, b);
-  readSlot(int i) => copies[i];
-  writeSlot(int i, x) { copies[i] = x; }
+  writeSlot(original, x) { clones[original] = x; }
 
   /// Iterate over the JS properties.
   forEachJsField(object, action);
@@ -224,26 +209,24 @@ abstract class _AcceptStructuredClone {
     if (isJavaScriptSimpleObject(e)) {
       // TODO(sra): If mustCopy is false, swizzle the prototype for one of a Map
       // implementation that uses the properies as storage.
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
       copy = {};
 
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
       forEachJsField(e, (key, value) => copy[key] = walk(value));
       return copy;
     }
 
     if (isJavaScriptArray(e)) {
-      var slot = findSlot(e);
-      var copy = readSlot(slot);
+      var copy = findSlot(e);
       if (copy != null) return copy;
 
       int length = e.length;
       // Since a JavaScript Array is an instance of Dart List, we can modify it
       // in-place unless we must copy.
       copy = mustCopy ? newDartList(length) : e;
-      writeSlot(slot, copy);
+      writeSlot(e, copy);
 
       for (int i = 0; i < length; i++) {
         copy[i] = walk(e[i]);