Serialize maps without hashes.

runtime/lib/compact_hash.dart

Index: runtime/lib/compact_hash.dart
diff --git a/runtime/lib/compact_hash.dart b/runtime/lib/compact_hash.dart
index 22af0a23c2c7c48eaf7c5876fa841c9f9de4af0c..ec8f0501c564404ed3ec4806a43e4192a5ed0cf6 100644
--- a/runtime/lib/compact_hash.dart
+++ b/runtime/lib/compact_hash.dart
@@ -13,15 +13,13 @@ abstract class _HashFieldBase {
   // The hash pattern is based on hashCode, but is guaranteed to be non-zero.
   // The length of _index is always a power of two, and there is always at
   // least one unoccupied entry.
+  // NOTE: When maps are deserialized, their _index and _hashMask is regenerated
+  // lazily by _regenerateIndex.
+  // TODO(koda): Consider also using null _index for tiny, linear-search tables.
   Uint32List _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE);
 
-  // Cached in-place mask for the hash pattern component. On 32-bit, the top
-  // bits are wasted to avoid Mint allocation.
-  // TODO(koda): Reclaim the bits by making the compiler treat hash patterns
-  // as unsigned words.
-  int _hashMask = internal.is64Bit ?
-      (1 << (32 - _HashBase._INITIAL_INDEX_BITS)) - 1 :
-      (1 << (30 - _HashBase._INITIAL_INDEX_BITS)) - 1;
+  // Cached in-place mask for the hash pattern component. 
+  int _hashMask = _HashBase._indexSizeToHashMask(_HashBase._INITIAL_INDEX_SIZE);
 
   // Fixed-length list of keys (set) or key/value at even/odd indices (map).
   List _data = new List(_HashBase._INITIAL_INDEX_SIZE);
@@ -67,7 +65,16 @@ abstract class _HashBase {
   // Unused and deleted entries are marked by 0 and 1, respectively.
   static const int _UNUSED_PAIR = 0;
   static const int _DELETED_PAIR = 1;
-  
+
+  // On 32-bit, the top bits are wasted to avoid Mint allocation.
+  // TODO(koda): Reclaim the bits by making the compiler treat hash patterns
+  // as unsigned words.
+  static int _indexSizeToHashMask(int indexSize) {
+    int indexBits = indexSize.bitLength - 1;
+    return internal.is64Bit ? (1 << (32 - indexBits)) - 1 :
+                              (1 << (30 - indexBits)) - 1;
+  }
+
   static int _hashPattern(int fullHash, int hashMask, int size) {
     final int maskedHash = fullHash & hashMask;
     // TODO(koda): Consider keeping bit length and use left shift.
@@ -132,7 +139,8 @@ class _LinkedHashMapMixin<K, V> {
   
   void clear() {
     if (!isEmpty) {
-      _init(_index.length, _hashMask);
+      // Use _data.length, since _index might be null.
+      _init(_data.length, _hashMask);
     }
   }
 
@@ -155,6 +163,20 @@ class _LinkedHashMapMixin<K, V> {
       }
     }
   }
+
+  int _regenerateIndex() {
+    assert(_index == null);
+    _index = new Uint32List(_data.length);
+    assert(_hashMask == 0);
+    _hashMask = _HashBase._indexSizeToHashMask(_index.length);
+    final int tmpUsed = _usedData;
+    _usedData = 0;
+    for (int i = 0; i < tmpUsed; i += 2) {
+      // TODO(koda): Avoid redundant equality tests and stores into _data.
+      this[_data[i]] = _data[i + 1];
+    }
+    return _index.length;

[siva, 2015/06/01 22:19:36]

instead of checking every caller to this function why not just do
if (_index == null) {
  ......
  ......
}
return _index.length;

[koda, 2015/06/01 23:01:01]

Since we don't do partial inlining (right?), that will either add a function
call to all those operations or blow up their code size.

Do you think this is a premature optimization?

[siva, 2015/06/02 00:13:35]

I don't feel strongly about moving the null check into the function but it does
make the code seem verbose at the call sites.

+  }
   
   void _insert(K key, V value, int hashPattern, int i) {
     if (_usedData == _data.length) {
@@ -199,7 +221,7 @@ class _LinkedHashMapMixin<K, V> {
   }
   
   void operator[]=(K key, V value) {
-    final int size = _index.length;
+    final int size = (_index == null) ? _regenerateIndex() : _index.length;
     final int sizeMask = size - 1;
     final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
@@ -213,7 +235,7 @@ class _LinkedHashMapMixin<K, V> {
   }
   
   V putIfAbsent(K key, V ifAbsent()) {
-    final int size = _index.length;
+    final int size = (_index == null) ? _regenerateIndex() : _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
@@ -236,7 +258,7 @@ class _LinkedHashMapMixin<K, V> {
   }
   
   V remove(Object key) {
-    final int size = _index.length;
+    final int size = (_index == null) ? _regenerateIndex() : _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
@@ -266,7 +288,7 @@ class _LinkedHashMapMixin<K, V> {
   
   // If key is absent, return _data (which is never a value).
   Object _getValueOrData(Object key) {
-    final int size = _index.length;
+    final int size = (_index == null) ? _regenerateIndex() : _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);