Remove hard limit from mirrors accessor caches.

sdk/lib/internal/cache.dart

Index: sdk/lib/internal/cache.dart
diff --git a/sdk/lib/internal/cache.dart b/sdk/lib/internal/cache.dart
new file mode 100644
index 0000000000000000000000000000000000000000..8c98b4eaf4b70fa01e20a3bbd53f00ac7383e144
--- /dev/null
+++ b/sdk/lib/internal/cache.dart
@@ -0,0 +1,148 @@
+// Copyright (c) 2014, 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.
+
+part of dart._internal;
+
+class CacheAssociation<K,V> {

[Ivan Posva, 2014/08/06 23:05:14]

Why <K,V>?

+  K key;
+  V value;
+  bool usedSinceGrowth = false;
+}
+
+/**
+ * A map that will grow as associations are added but will prefer to evict
+ * associations that have not been used since the last growth when needing to
+ * grow again. Implemented as an open addressing hash table.
+ */
+class Cache<K,V> {
+  final CacheAssociation<K,V> _head;
+  List _table;
+  int _shift;
+  int _mask;
+  int _capacity;  // Max number of associations before we start evicting.
+  int _size = 0;  // Current number of associations.
+
+  /**
+   * Create a Cache whose capacity is 75% of 2^shift.
+   */
+  Cache.withInitialShift(int shift)
+  {
+    // The scheme used here for handling collisions relies on there always
+    // being at least one empty slot.
+    if (shift < 1) throw new Exception("Cache requires a shift >= 1");
+    _initWithShift(shift);
+  }
+
+  void _initWithShift(int shift) {
+    this._shift = shift;
+    this._mask = (1 << shift) - 1;
+    this._capacity = (1 << shift) * 3 ~/ 4;
+    this._table = new List(1 << shift);
+    assert(_table.length > _capacity);
+  }
+
+  int _scanFor(K key) {
+    var start = key.hashCode & _mask;
+    var index = start;
+    do {
+      var assoc = _table[index];
+      if (null == assoc || assoc.key == key) {
+        return index;
+      }
+      index = (index + 1) & _mask;
+    } while (index != start);
+    // Should never happen because we start evicting associations before the
+    // table is full.
+    throw new Exception("Internal error: LRUMap table full");

[Ivan Posva, 2014/08/06 23:05:14]

LRUMap?

+  }
+
+  int _scanForEmpty(K key) {
+    var start = key.hashCode & _mask;
+    var index = start;
+    do {
+      if (null == _table[index]) {
+        return index;
+      }
+      index = (index + 1) & _mask;
+    } while (index != start);
+    // Should never happen because we start evicting associations before the
+    // table is full.
+    throw new Exception("Internal error: LRUMap table full");

[Ivan Posva, 2014/08/06 23:05:14]

ditto

+  }
+
+  void _fixCollisionsAfter(start) {
+    var assoc;
+    var index = (start + 1) & _mask;
+    while (null != (assoc = _table[index])) {

[Ivan Posva, 2014/08/06 23:05:14]

Assignment in condition?

[rmacnak, 2014/08/07 20:05:25]

Yes, Dart doesn't have sequence expressions to write

while (assoc = _table[index], assoc != null)

or better yet

[assoc:: table at: index. assoc isNil] whileFalse: [...]

+      var newIndex = _scanFor(assoc.key);
+      if (newIndex != index) {
+        assert(_table[newIndex] == null);
+        _table[newIndex] = assoc;
+        _table[index] = null;
+      }
+      index = (index + 1) & _mask;
+    }
+  }
+
+  void _grow() {
+    var oldTable = _table;
+
+    _initWithShift(_shift + 1);
+
+    for (int oldIndex = 0; oldIndex < oldTable.length; oldIndex++) {
+      var assoc = oldTable[oldIndex];
+      if (assoc != null) {
+        var newIndex = _scanForEmpty(assoc.key);
+        assoc.usedSinceGrowth = false;
+        _table[newIndex] = assoc;
+      }
+    }
+  }
+
+  void _tryToShrinkOtherwiseGrow() {
+    bool needToGrow = true;
+    for (int i = 0; i < _table.length; i++) {
+      var assoc = _table[i];
+      if (null != assoc && !assoc.usedSinceGrowth) {
+        _table[i] = null;
+        _size--;
+        _fixCollisionsAfter(i);
+        needToGrow = false;
+      }
+    }
+    if (needToGrow) _grow();
+  }
+
+  operator []=(K key, V value) {
+    int index = _scanFor(key);
+    var assoc = _table[index];
+    if (null != assoc) {
+      // Existing key, replace value.
+      assert(assoc.key == key);
+      assoc.value = value;
+      assoc.usedSinceGrowth = true;
+    } else {
+      // New key.
+      var newAssoc = new CacheAssociation();
+      if (_size == _capacity) {
+        // No free slots.
+        _tryToShrinkOtherwiseGrow();
+        index = _scanFor(key);

[Ivan Posva, 2014/08/06 23:05:14]

assert(table[index] == null);

+      }
+      newAssoc.key = key;
+      newAssoc.value = value;
+      newAssoc.usedSinceGrowth = true;
+      _table[index] = newAssoc;
+      _size++;
+    }

[Ivan Posva, 2014/08/06 23:05:14]

What is missing here is the deletion of an entry if the value is being set to
null. Alternatively you could put that into _tryToShrinkOtherwiseGrow, by
deleting the associations with null values during that step.

[rmacnak, 2014/08/07 20:05:25]

This doesn't occur in practice, but added the logic to
_tryToShrinkOtherwiseGrow.

+  }
+
+  V operator [](K key) {
+    var index = _scanFor(key);
+    var assoc = _table[index];
+    if (null == assoc) return null;
+    assoc.usedSinceGrowth = true;
+    return assoc.value;
+  }
+}