- Add a WeakTable to the VM. This is used to remember the

runtime/lib/expando_patch.dart

Index: runtime/lib/expando_patch.dart
===================================================================
--- runtime/lib/expando_patch.dart	(revision 24504)
+++ runtime/lib/expando_patch.dart	(working copy)
@@ -3,61 +3,134 @@
 // BSD-style license that can be found in the LICENSE file.
 
 patch class Expando<T> {
-  /* patch */ Expando([this.name]) : _data = new List();
+  /* patch */ Expando([this.name])
+      : _data = new List(_minSize),
+        _used = 0;
 
+  static const _minSize = 8;
+  static final _deletedEntry = new _WeakProperty(null, null);
+
   /* patch */ T operator[](Object object) {
     _checkType(object);
-    var doCompact = false;
-    var result = null;
-    for (int i = 0; i < _data.length; ++i) {
-      var key = _data[i].key;
-      if (identical(key, object)) {
-        result = _data[i].value;
-        break;
+
+    var mask = _size - 1;
+    var idx = object.hashCode & mask;
+    var wp = _data[idx];
+
+    while (wp != null) {
+      if (identical(wp.key, object)) {
+        return wp.value;
+      } else if (wp.key == null) {
+        // This entry has been cleared by the GC.
+        _data[idx] = _deletedEntry;
       }
-      if (key == null) {
-        doCompact = true;
-        _data[i] = null;
-      }
+      idx = (idx + 1) & mask;
+      wp = _data[idx];
     }
-    if (doCompact) {
-      _data = _data.where((e) => (e != null)).toList();
-    }
-    return result;
+
+    return null;
   }
 
   /* patch */ void operator[]=(Object object, T value) {
     _checkType(object);
-    var doCompact = false;
-    int i = 0;
-    for (; i < _data.length; ++i) {
-      var key = _data[i].key;
-      if (identical(key, object)) {
-        break;
+
+    var mask = _size - 1;
+    var idx = object.hashCode & mask;
+    var empty_idx = -1;
+    var wp = _data[idx];
+
+    while (wp != null) {
+      if (identical(wp.key, object)) {
+        if (value != null) {
+          // Update the associated value.
+          wp.value = value;
+        } else {
+          // Mark the entry as deleted.
+          _data[idx] = _deletedEntry;
+        }
+        return;
+      } else if ((empty_idx < 0) && identical(wp, _deletedEntry)) {
+        empty_idx = idx;  // Insert at this location if not found.
+      } else if (wp.key == null) {
+        // This entry has been cleared by the GC.
+        _data[idx] = _deletedEntry;
+        if (empty_idx < 0) {
+          empty_idx = idx;  // Insert at this location if not found.
+        }
       }
-      if (key == null) {
-        doCompact = true;
-        _data[i] = null;
+      idx = (idx + 1) & mask;
+      wp = _data[idx];
+    }
+
+    if (value == null) {
+      // Not entering a null value. We just needed to make sure to find 

[siva, 2013/06/27 22:11:33]

This comment seems incomplete.

[Ivan Posva, 2013/06/27 23:59:12]

Done.

+      return;
+    }
+
+    if (empty_idx >= 0) {
+      // We will be reusing the empty slot below.
+      _used--;
+      idx = empty_idx;
+    }
+
+    if (_used < _limit) {
+      _data[idx] = new _WeakProperty(object, value);
+      _used++;
+      return;
+    }
+
+    // Grow/reallocate if too many slots have been used.
+    _rehash();
+    this[object] = value;  // Recursively add the value.
+  }
+
+  _rehash() {
+    // Determine the population count of the map to allocate an appropriately
+    // sized map below.
+    var count = 0;
+    var old_data = _data;
+    var len = old_data.length;
+    for (var i = 0; i < len; i++) {
+      var entry = old_data[i];
+      if ((entry != null) && (entry.key != null)) {
+        // Only count non-cleared entries.
+        count++;
       }
     }
-    if (i != _data.length && value == null) {
-      doCompact = true;
-      _data[i] = null;
-    } else if (i != _data.length) {
-      _data[i].value = value;
-    } else {
-      _data.add(new _WeakProperty(object, value));
+
+    var new_size = _size;
+    if (count <= (new_size >> 2)) {
+      new_size = new_size >> 1;
+    } else if (count > (new_size >> 1)) {
+      new_size = new_size << 1;
     }
-    if (doCompact) {
-      _data = _data.where((e) => (e != null)).toList();
+    new_size = (new_size < _minSize) ? _minSize : new_size;
+
+    // Reset the mappings to empty so that we can just add the existing
+    // valid entries.
+    _data = new List(new_size);
+    _used = 0;
+
+    for (var i = 0; i < old_data.length; i++) {
+      var entry = old_data[i];
+      if ((entry != null) && (entry.key != null)) {
+        this[entry.key] = entry.value;
+      }
     }
   }
 
   static _checkType(object) {
-    if (object == null || object is bool || object is num || object is String) {
+    if ((object == null) ||
+         (object is bool) ||
+         (object is num) ||
+         (object is String)) {
       throw new ArgumentError(object);
     }
   }
 
+  get _size => _data.length;
+  get _limit => (3 * (_size ~/ 4));
+
   List _data;
+  int _used;  // Number of used (active and deleted) slots.
 }