Implement an LRU cache in dart:_internal and use it for the getter/setter caches in the VM's mirror…

sdk/lib/internal/lru.dart

Index: sdk/lib/internal/lru.dart
diff --git a/sdk/lib/internal/lru.dart b/sdk/lib/internal/lru.dart
new file mode 100644
index 0000000000000000000000000000000000000000..66c5f138236f535057f5192c2162c4c46edf9e0f
--- /dev/null
+++ b/sdk/lib/internal/lru.dart
@@ -0,0 +1,108 @@
+// 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 LRUAssociation<K,V> {
+  K key;
+  V value;
+  LRUAssociation previous;
+  LRUAssociation next;

[Ivan Posva, 2014/05/25 20:00:26]

Empty lines between methods please.

+  void insertBetween(before, after) {
+    after.previous = this;
+    before.next = this;
+    this.next = after;
+    this.previous = before;
+  }
+  void remove() {
+    var after = next;
+    var before = previous;
+    after.previous = before;
+    before.next = after;
+  }
+}
+
+/**
+ * A map with a fixed capacity that evicts associations when capacity is reached
+ * on a least-recently-used basis. Implemented as an open addressing hash table
+ * with doubly-linked entries forming the LRU queue.
+ */
+class LRUMap<K,V> {
+  final LRUAssociation<K,V> head;
+  final List table;
+  final int capacity;
+  int size = 0;
+
+  LRUMap(int capacity)
+      : this.capacity = capacity
+      , this.table = new List(capacity * 4 ~/ 3)
+      , this.head = new LRUAssociation() {
+        head.insertBetween(head, head);

[Ivan Posva, 2014/05/25 20:00:26]

Tow space indent. This way it looks like part of the initializer list.

+  }
+
+  int _scanFor(K key) {
+    var start = key.hashCode % table.length;

[Ivan Posva, 2014/05/25 20:00:26]

How about rounding up the length to the next power of 2 and then just use a mask
here? Or does it become too wasteful then?

[rmacnak, 2014/05/30 21:26:05]

Using a mask instead of modulus is a ~20% improvement. Changed the constructor
to take a shift rather than a capacity. Table size is always a power of 2 and
capacity is 75% of table size.

+    var index = start;
+    do {
+      var assoc = table[index];
+      if (assoc == null || assoc.key == key) {

[Ivan Posva, 2014/05/25 20:00:26]

I don't think this will work that well for capacity of 1.

Please add a test.

[rmacnak, 2014/05/30 21:26:05]

This scheme relies on their always being at least one empty slot. Asserting at
construction that we don't create a LRUMap with the degenerate case
tablesize=capacity=1 (no point in using an LRU of size 1 anyway). Also added
test.

+        return index;
+      }
+      index = (index + 1) % table.length;
+    } while (index != start);
+    // Should never happen because we start evicting associations before the
+    // table is full.
+    throw "LRUMap out of space";
+  }
+
+  void _fixCollisionsAfter(start) {
+    var assoc;
+    var index = (start + 1) % table.length;
+    while ((assoc = table[index]) != null) {
+      var newIndex = _scanFor(assoc.key);
+      table[newIndex] = assoc;
+      table[index] = null;
+      index = (index + 1) % table.length;
+    }
+  }
+
+  operator []=(K key, V value) {
+    int index = _scanFor(key);
+    var assoc = table[index];
+    if (assoc != null) {
+      // Existing key, replace value.
+      assoc.value = value;
+      assoc.remove();
+      assoc.insertBetween(head, head.next);
+    } else {
+      // New key.
+      var newAssoc;
+      if (size == capacity) {
+        // Knock out the oldest association.
+        var lru = head.previous;
+        lru.remove();
+        index = _scanFor(lru.key);
+        _fixCollisionsAfter(index);
+        index = _scanFor(key);
+        newAssoc = lru;  // Recycle the association.
+      } else {
+        newAssoc = new LRUAssociation();
+        size++;
+      }
+      newAssoc.key = key;
+      newAssoc.value = value;
+      newAssoc.insertBetween(head, head.next);
+      table[index] = newAssoc;
+    }
+  }
+
+  V operator [](K key) {
+    var index = _scanFor(key);
+    var assoc = table[index];
+    if (assoc == null) return null;
+    assoc.remove();
+    assoc.insertBetween(head, head.next);
+    return assoc.value;
+  }
+}