Switched Serialization identityMap to use a wrapper, not linear search.

pkg/serialization/lib/src/serialization_helpers.dart

 // Copyright (c) 2012, 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 contains extra functions and classes useful for implementing
  * serialiation. Some or all of these will be removed once the functionality is
  * available in the core library.
  */
 library serialization_helpers;
@@ skipping 162 matching lines @@
 /**
  * This acts as a stand-in for some value that cannot be hashed. We can't
  * just use const Object() because the compiler will fold them together.
  */
 class _Sentinel {
   final _wrappedObject;
   const _Sentinel(this._wrappedObject);
 }
 
 /**
- * This provides an identity map which also allows true, false, and null
- * as valid keys. In the interests of avoiding duplicating map code, and
- * because hashCode for arbitrary objects is currently very slow on the VM,
- * just do a linear lookup.
+ * This is used to provide an identity map. We wrap all the objects in

[Jennifer Messerly, 2013/08/26 21:58:47]

this comment belongs on the IdentityMap type instead?

[Alan Knight, 2013/08/27 18:13:44]

Rephrased and put it on both.

+ * the map in something whose equality is based on identity of the
+ * wrapped objects. It also treats equal primitive values as identical
+ * to conserve space. This is still not particularly efficient, and
+ * should be removed once we have a real identity map.
+ */
+// TODO(alanknight): Replace with a real identityMap. Issue 4161.

[Jennifer Messerly, 2013/08/26 21:58:47]

remove todo? or perhaps change it to:
TODO: implement this without wrappers

(ideally we'd have the ability to provide the equals/hashcode function to the
map w/o requiring every object be wrapped) 

[Alan Knight, 2013/08/27 18:13:44]

Rephrased the TODO. The bug is for the core library to allow maps where you can
provide the equality (and hash?) functions.

+class IdentityMapWrapper {

[Jennifer Messerly, 2013/08/26 21:58:47]

maybe make this class library private to indicate it's an impl detail of
IdentityMap.

Also perhaps rename "IdentityMapKey"?

[Alan Knight, 2013/08/27 18:13:44]

Done.

+  IdentityMapWrapper(this._value);
+  var _value;
+
+  /**
+   * Check if an object is primitive to know if we should compare it using
+   * equality or identity. We don't test null/true/false where it's the same.
+   */
+  _isPrimitive(x) => x is String || x is num;
+
+  operator ==(IdentityMapWrapper w) =>
+      _isPrimitive(_value) ? _value == w._value : identical(_value, w._value);
+  get hashCode => _value.hashCode;
+  get object => _value;
+}
+
+/**
+ * This provides an identity map.
  */
 class IdentityMap<K, V> implements Map<K, V> {

[Jennifer Messerly, 2013/08/26 21:58:47]

I wonder if it's possible and a good idea to extend LinkedHashMap instead of
implementing it, and then use "super" to forward the methods?

[Alan Knight, 2013/08/27 18:13:44]

Possible, and does make the code simpler, but unfortunately never terminated on
dart2js until I realized that in the dartj2s implementation some calls make use
of others in ways they don't on the VM, so you can get multiple levels of
wrapping. But done now.

 
-  final List<K> keys = <K>[];
-  final List<V> values = <V>[];
+  final Map<IdentityMapWrapper, V> map = new Map<IdentityMapWrapper, V>();
 
-  V operator [](Object key) {
-    var index =  _indexOf(key);
-    return (index == -1) ? null : values[index];
+  _wrap(Object key) => new IdentityMapWrapper(key);
+  _unwrap(IdentityMapWrapper wrapper) => wrapper.object;
+
+  Iterable<K> get keys => map.keys.map((x) => _unwrap(x));
+  Iterable<V> get values => map.values;
+
+  void forEach(void f(K key, V value)) {
+    map.keys.forEach((k) => f(_unwrap(k), map[k]));

[Jennifer Messerly, 2013/08/26 21:58:47]

perhaps:

map.forEach((k, v) { f(_unwrap(k), v); });

...to save the extra hash lookup for every element?

[Alan Knight, 2013/08/27 18:13:44]

Done.

   }
 
+  V operator [](K key) => map[_wrap(key)];
+
   void operator []=(K key, V value) {
-    var index = _indexOf(key);
-    if (index == -1) {
-      keys.add(key);
-      values.add(value);
-    } else {
-      values[index] = value;
-    }
+      map[_wrap(key)] = value;
   }
 
-  V putIfAbsent(K key, Function ifAbsent) {
-    var index = _indexOf(key);
-    if (index == -1) {
-      keys.add(key);
-      values.add(ifAbsent());
-      return values.last;
-    } else {
-      return values[index];
-    }
-  }
+  V putIfAbsent(K key, Function ifAbsent) =>
+      map.putIfAbsent(_wrap(key), ifAbsent);
 
-  int _indexOf(Object key) {
-    // Go backwards on the guess that we are most likely to access the most
-    // recently added.
-    // Make strings and primitives unique
-    var compareEquality = isPrimitive(key);
-    for (var i = keys.length - 1; i >= 0; i--) {
-      var equal = compareEquality ? key == keys[i] : identical(key, keys[i]);
-      if (equal) return i;
-    }
-    return -1;
-  }
+  bool containsKey(Object key) => map.containsKey(_wrap(key));
 
-  bool containsKey(Object key) => _indexOf(key) != -1;
-  void forEach(f(K key, V value)) {
-    for (var i = 0; i < keys.length; i++) {
-      f(keys[i], values[i]);
-    }
-  }
-
-  V remove(Object key) {
-    var index = _indexOf(key);
-    if (index == -1) return null;
-    keys.removeAt(index);
-    return values.removeAt(index);
-  }
+  V remove(Object key) => map.remove(_wrap(key));
 
   int get length => keys.length;
-  void clear() {
-    keys.clear();
-    values.clear();
-  }
-  bool get isEmpty => keys.isEmpty;
-  bool get isNotEmpty => !isEmpty;
+  void clear() => map.clear();
+
+  bool get isEmpty => map.isEmpty;
+  bool get isNotEmpty => !map.isEmpty;
 
   // Note that this is doing an equality comparison.
-  bool containsValue(Object x) => values.contains(x);
+  bool containsValue(Object x) => map.containsValue(x);
 
   void addAll(Map<K, V> other) {
     other.forEach((K key, V value) {
       this[key] = value;

[Jennifer Messerly, 2013/08/26 21:58:47]

_wrap?

[Alan Knight, 2013/08/27 18:13:44]

[]= will wrap, so not needed. With subclassing, the whole method isn't needed.

     });
   }
 }