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

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

BUG=http://dartbug.com/18445
R=iposva@google.com

Committed: https://code.google.com/p/dart/source/detail?r=37059

[rmacnak, 2014-05-06 00:26:19]

GetField benchmark goes from 189-196 to 239-252 (25% slower)

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

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dart
File sdk/lib/internal/lru.dart (right):

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:11: LRUAssociation next;
Empty lines between methods please.

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:41: head.insertBetween(head, head);
Tow space indent. This way it looks like part of the initializer list.

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:45: var start = key.hashCode % table.length;
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?

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:49: if (assoc == null || assoc.key == key) {
I don't think this will work that well for capacity of 1.

Please add a test.

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

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dart
File sdk/lib/internal/lru.dart (right):

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:45: var start = key.hashCode % table.length;
On 2014/05/25 20:00:26, Ivan Posva wrote:
> 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?

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.

https://codereview.chromium.org/268783006/diff/20001/sdk/lib/internal/lru.dar...
sdk/lib/internal/lru.dart:49: if (assoc == null || assoc.key == key) {
On 2014/05/25 20:00:26, Ivan Posva wrote:
> I don't think this will work that well for capacity of 1.
> 
> Please add a test.

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.

[Ivan Posva, 2014-06-05 23:41:54]

LGTM -ip

[rmacnak, 2014-06-06 00:45:08]

Committed patchset #3 manually as r37059 (presubmit successful).