Add a new implementation of HashMap that uses JS objects for its (multiple) hash tables.

Add a new implementation of HashMap that uses JS objects for its (multiple) hash tables.

I'll start refactoring the implementation to make it a bit more
maintainable, but I wanted to get your first impressions.

R=erikcorry@google.com,lrn@google.com,srdjan@google.com
BUG=

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

[kasperl, 2013-03-22 11:34:33]

I've hacked up a silly and small read/write benchmark for maps and for that this
CL gives a 19.7x speedup.

After this change, the code completes 8.4 times faster on dart2js than on the
native Dart VM.

---
class X {
  final int val;
  X(this.val);

  operator ==(other) {
    if (other is !X) return false;
    return val == other.val;
  }

  get hashCode => val.hashCode;

  toString() => 'X($val)';
}

main() {
  var keys = [];
  for (var i = 0; i < 1000; i++) {
    keys.add('key$i$i$i');
    keys.add(i);
  }
  for (var i = 0; i < 50; i++) {
    keys.add(new X(i));
  }

  Map map = new Map();
  var watch = new Stopwatch()..start();
  for (var key in keys) {
    for (int i = 0; i < 10000; i++) {
      map[key];
    }
    for (int i = 0; i < 10000; i++) {
      map[key] = i;
    }
    for (int i = 0; i < 50000; i++) {
      map[key];
    }
  }
  watch.stop();
  print('Elapsed: ${watch.elapsedMilliseconds} ms');
}

[kasperl, 2013-03-22 11:40:35]

After messing a bit with the benchmark to make it more reasonable (don't use
consecutive int keys -- use more object keys with user-defined hashCode) the
results are still pretty promising.

With this CL dart2js becomes almost 5 times faster and ends up being almost 4
times faster than the VM. Not a factor of 20x but still pretty good.

[erikcorry, 2013-03-22 12:59:24]

Looking very promising.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:9: //
BUG(9368): We're currently unable to pass the type arguments to
Perhaps you should just rename JSMap to HashMap until this is fixed.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:76: var hash
= JS('num', 'Number(#)', key.hashCode);
I think you just want to | with 0 here to save creating an object.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:94: _strings
= strings = _newHashTable();
You can close the } here and omit the 'else' for more compactness.  Also below.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:101: if
(value == null) value = _strings;
strings, rather than _strings.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:116: var
rest = _rest;
The NaN case should go into this section, at least if we want to match the VM:

var m = new Map();
m[0/0] = 0;
print(m.length);  // 1
print(m.containsKey(0/0));  // false
m[0/0] = 0;
print(m.length);  // 2
print(m.containsKey(0/0));  // false

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:227: var
names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
Perhaps not in the first version, but it should be possible to just return names
if _nums and _rest are null.  (Remember to set _keys too :-)

https://codereview.chromium.org/12827018/diff/7001/runtime/lib/collection_pat...
File runtime/lib/collection_patch.dart (left):

https://codereview.chromium.org/12827018/diff/7001/runtime/lib/collection_pat...
runtime/lib/collection_patch.dart:6: 
I think Rietveld is screwing with us here.

https://codereview.chromium.org/12827018/diff/7001/runtime/lib/collection_sou...
File runtime/lib/collection_sources.gypi (right):

https://codereview.chromium.org/12827018/diff/7001/runtime/lib/collection_sou...
runtime/lib/collection_sources.gypi:1: # Copyright (c) 2013, the Dart project
authors.  Please see the AUTHORS file
accidental edit

https://codereview.chromium.org/12827018/diff/7001/runtime/vm/bootstrap.cc
File runtime/vm/bootstrap.cc (left):

https://codereview.chromium.org/12827018/diff/7001/runtime/vm/bootstrap.cc#ol...
runtime/vm/bootstrap.cc:46: const char* source = patch ? collection_source_ :
collection_source_;
Strange code is strange.

https://codereview.chromium.org/12827018/diff/7001/tests/corelib/map_test.dart
File tests/corelib/map_test.dart (right):

https://codereview.chromium.org/12827018/diff/7001/tests/corelib/map_test.dar...
tests/corelib/map_test.dart:289: 'constructor',
Please add __proto__, __count__, __parent__, NaN and +-0, perhaps also Infinity
and -Infinity, null and the empty string.

[ahe, 2013-03-22 16:18:31]

I have looked at
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart and the
tests.  Those parts, LGTM.

I would suggest that you test using keys that have bad implementations of
hashCode.  For example, what happens if I have a hashCode implementation like
this:

get hashCode => '${super.hashCode}';

Also, could you test maps that has strings, numbers keys, and other object keys.

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:16: var
_strings, _nums, _rest;
Each of these should be on their own line, and each deserve a comment.

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:32: var
strings = _strings;
Would this work:

var strings = JS('JavaScriptIndexingBehavior', '#', _strings);
return (strings != null) && strings[key] != null;

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:35: return
JS('bool', '# != null', probe);
Why not simply:

return probe != null;

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:45: var
bucket = JS('var', '#[#]', rest, hash);
Do you know if open addressing would be better in this case?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:47: int
bucketLength = JS('int', '#.length', bucket);
Could you tell compiler that bucket is a List and avoid using JS here? It should
even hoist out the length check in that case, right?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:59: return
_computeKeys().any((each) => this[each] == value);
This looks slow.  Wouldn't this always be faster:

for (var key in _computeKeys()) {
  if (this[key] == value) return true;
}
return false;

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:67: return
JS('bool', '# === #', probe, strings) ? null : probe;
You're using _strings as a sentinel object?  Comment would be nice.

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:76: var hash
= JS('num', 'Number(#)', key.hashCode);
Shouldn't you throw some kind of exception if hashCode isn't an int?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:96: _keys =
null;
This might be more readable:

addedNewKey = true;

And then at the end of this method:

if (addedNewKey) {
  _keys = null;
}

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:117: var
hash = JS('num', 'Number(#)', key.hashCode);
Exception?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:200: throw
new ConcurrentModificationError(this);
This means there are situations where a concurrent modification occurs, but you
allow it.  For example, you may replace values for existing keys.  This is fine
by me, but rather hard to specify correctly, so I hope the specification is
clear about this.

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:227: var
names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
There is a comment in the emitter about an Opera bug for this method.  Is it
safe to use now?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:227: var
names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
If the type of the JS expression is '=List' can't you just use plain Dart code
for the rest?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:237: var
names = JS('var', 'Object.getOwnPropertyNames(#)', nums);
Use =List?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:240: num key
= JS('num', 'Number(#[#])', names, i);
A comment explaining why Number is necessary would be great.

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:247: var
names = JS('var', 'Object.getOwnPropertyNames(#)', rest);
Use =List?

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:266:
JS('void', 'delete #[#]', table, temporaryKey);
Add a comment explaining the purpose of <non-identifier-key> and delete.  I
think it looks like black magic to people that aren't intimately familiar with
map transitions in V8.

[kasperl, 2013-03-22 16:27:31]

As I mentioned to Erik, this definitely needs a bit of refactoring and some more
comments. Thanks for taking a look!

[kasperl, 2013-03-22 16:28:51]

... and I actually do have a few tests cooking with weird objects that return
"__proto__" as their hashCode, etc.

[Ivan Posva, 2013-03-22 16:32:47]

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/collection/hash_ma...
File sdk/lib/collection/hash_map.dart (right):

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:26: external factory HashMap();
Why stop here? There are plenty of other opportunities below. The way it is
structured even after your half-way ripping it apart is that you need to have
this internal _hashTable object even if you did not really need it.

[kasperl, 2013-03-22 16:36:01]

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/collection/hash_ma...
File sdk/lib/collection/hash_map.dart (right):

https://codereview.chromium.org/12827018/diff/7001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:26: external factory HashMap();
On 2013/03/22 16:32:47, Ivan Posva wrote:
> Why stop here? There are plenty of other opportunities below. The way it is
> structured even after your half-way ripping it apart is that you need to have
> this internal _hashTable object even if you did not really need it.

I need to have this _internal hashTable object even when I don't really need it?
I don't understand that?

[sra1, 2013-03-22 18:27:42]

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:76: var hash
= JS('num', 'Number(#)', key.hashCode);
On 2013/03/22 12:59:24, erikcorry wrote:
> I think you just want to | with 0 here to save creating an object.

If the hashCode is already a number,  Number(x) will return the argument.
If the hashcode is crazy, it will be parsed, possibly to a boxed double,
possibly to NaN.

If you going to assume an int, it might be best to force a SMI,
e.g. hashCode & 0x3fffffff

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:76: var hash
= JS('num', 'Number(#)', key.hashCode);
containsKey and [] are inconsistent here.
Since small static methods are inlined, use

static _computeHash(key) => JS('num', 'Number(#)', key.hashCode);

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:223: List
result = new List(_length);
List<K>, for when that works.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:223: List
result = new List(_length);
Perhaps this should be a growable list - see comment on toList()

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:227: var
names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
On 2013/03/22 12:59:24, erikcorry wrote:
> Perhaps not in the first version, but it should be possible to just return
names
> if _nums and _rest are null.  (Remember to set _keys too :-)

getOwnPropertyNames returns List<dynamic>, not List<K>.
But perhaps it could be upgraded to List<K> and used as the allocation for
result.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:258: }
assert(index == _length);

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:264: var
temporaryKey = '<non-identifier-key>';
Add a comment - this is slightly obscure and seeking and implementation
dependent effect.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:291: }
toList() can return the computed keys, provided _map._keys is reset to null to
avoid sharing.  This will avoid a copy for map.keys.toList(growable: ?)

To get this to work without copying you will need to either create _keys with
the requested type (growable vs fixed) or change the type after _keys is
created.

I think the common case will be .toList() (i.e. growable).  For this reason, I
think that the _keys should be computed as a growable list that has an initial
size.  I believe we really do need a constructor for that in the core library.

[kasperl, 2013-04-02 10:33:37]

I've refactored the code quite a bit and changed the implementation to be patch
methods for a shared HashMap class. Also, I've tried limiting the number of uses
of JS a bit, but I've kept the ones I need to avoid too many weird bailout cases
and unncessary bounds checks.

I've added tests for NaN and fixed the implementation to deal correctly with
them.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:76: var hash
= JS('num', 'Number(#)', key.hashCode);
On 2013/03/22 12:59:24, erikcorry wrote:
> I think you just want to | with 0 here to save creating an object.

Done.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:94: _strings
= strings = _newHashTable();
On 2013/03/22 12:59:24, erikcorry wrote:
> You can close the } here and omit the 'else' for more compactness.  Also
below.

Done.

https://codereview.chromium.org/12827018/diff/3002/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:101: if
(value == null) value = _strings;
On 2013/03/22 12:59:24, erikcorry wrote:
> strings, rather than _strings.

Done.

[erikcorry, 2013-04-02 11:20:09]

LGTM

Do we have a test that tests things still work with massive hashCode clashes?

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:136: return
JS('var', '#.splice(#, 2)[1]', bucket, index);
Should you be checking for zero length array here?  I think the current
implementation works, but if you add a lot of entries to the map and then remove
them all again you will end up keeping the big dictionary object of _rest big,
containing lots of number->zerolengtharray entries.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:161: int
index = 0;
I wonder if this could be profitably (ie smaller code size) be refactored as:

getKeys(_strings, (key) => result[index++] = key);
getKeys(_nums, (key) => result[index++] = JS('num', '+#', key));
getKeys(_rest, (key) {
  // Stuff with buckets.
})

Alternative, partially contradictory proposal:  Try this first for moar speed:

if (_nums == null && _rest == null && _strings != null) return JS('List',
'Object.getOwnPropertyNames(#)', _strings);

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:244: return
key is num && JS('bool', '# === #', key, key);
This line deserves a comment.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:259: return
JS('bool', '# != null', entry);
Surprised this needs JS.

[kasperl, 2013-04-02 11:42:07]

Thanks for the review. I'll work on this some more when I start dealing with
LinkedHashMap too.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
(right):

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:136: return
JS('var', '#.splice(#, 2)[1]', bucket, index);
On 2013/04/02 11:20:09, erikcorry wrote:
> Should you be checking for zero length array here?  I think the current
> implementation works, but if you add a lot of entries to the map and then
remove
> them all again you will end up keeping the big dictionary object of _rest big,
> containing lots of number->zerolengtharray entries.

Added TODO.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:161: int
index = 0;
On 2013/04/02 11:20:09, erikcorry wrote:
> I wonder if this could be profitably (ie smaller code size) be refactored as:
> 
> getKeys(_strings, (key) => result[index++] = key);
> getKeys(_nums, (key) => result[index++] = JS('num', '+#', key));
> getKeys(_rest, (key) {
>   // Stuff with buckets.
> })
> 
> Alternative, partially contradictory proposal:  Try this first for moar speed:
> 
> if (_nums == null && _rest == null && _strings != null) return JS('List',
> 'Object.getOwnPropertyNames(#)', _strings); 

I'll work on this in another CL.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:244: return
key is num && JS('bool', '# === #', key, key);
On 2013/04/02 11:20:09, erikcorry wrote:
> This line deserves a comment.

Done.

https://codereview.chromium.org/12827018/diff/14001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart:259: return
JS('bool', '# != null', entry);
On 2013/04/02 11:20:09, erikcorry wrote:
> Surprised this needs JS.

You're right. Not needed.

[kasperl, 2013-04-02 11:51:58]

Committed patchset #6 manually as r20770 (presubmit successful).