Convert HashMap and LinkedHashMap to closed addressing hash tables.

Convert HashMap and LinkedHashMap to closed addressing hash tables.

R=regis@google.com, sgjesse@google.com

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

[Lasse Reichstein Nielsen, 2013-08-13 13:03:33]

I expect to change HashSet and LinkedHashSet too, and remove the old HashTable.

[regis, 2013-08-13 16:51:35]

LGTM

Srdjan could also have a look at performance implications, if any.

https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
File tests/lib/convert/unicode_tests.dart (right):

https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
tests/lib/convert/unicode_tests.dart:37: //const BEE_STRING = "𐐒";
Left over comment?

[Ivan Posva, 2013-08-13 17:31:17]

On 2013/08/13 16:51:35, regis wrote:
> LGTM
> 
> Srdjan could also have a look at performance implications, if any.
> 
>
https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
> File tests/lib/convert/unicode_tests.dart (right):
> 
>
https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
> tests/lib/convert/unicode_tests.dart:37: //const BEE_STRING = "𐐒";
> Left over comment?

Lasse,

Before you go ahead and commit this, can you please give as brief overview of
what you changed and the implication on performance. Ideally with links to
actual runs of the performance harness?

Thanks,
-Ivan

[Lasse Reichstein Nielsen, 2013-08-14 07:31:27]

On 2013/08/13 17:31:17, Ivan Posva wrote:

> 
> Lasse,
> 
> Before you go ahead and commit this, can you please give as brief overview of
> what you changed and the implication on performance. Ideally with links to
> actual runs of the performance harness?

This changes the implementation of HashMap to use a closed addressing hash table
(no probing, but a linked list in each bucket). The existing code was using an
open addressing hash table - entries are put directly into the table with no
entry objects, and if the slot is taken, it probes for an empty slot, and remove
operations stores tombstones to keep slots occupied.

Using entry objects means a larger memory overhead (at least for mostly full
maps - it reduces the memory for sparse maps because an empty entry only takes
one cell, but most maps are at least half full all the time due to the growth
strategy).

Being closed addressing means that you can only collide with objects that hash
to the same bucket. Open addressing allows you to collide with objects that hash
to other buckets - if you have two keys that hash to the same bucket, you will
also add a collision for another bucket. For a 50% full table, that becomes
significant. A class with a not-so-great hash code (and most of them probably
are) will generate more collisions. For a closed-addressing hash table, more
collisions means more elements in one bucket, but also fewer occupied buckets,
so it also helps itself. In an open-addressing hash table, each collision costs,
and the table gets fuller.

Kasper did the closed-addressing implementation of HashMap and did some tests to
see if it was faster than the existing HashMap, and it was. In some cases by
almost an order of magnitude.

For the test Kasper devised, the results are (actual running time, smaller is
better):

Current versions:
$ ./dart-old-hash fastmap_test.dart
HashMap: 1263
LinkedHashMap: 1280

With this CL:
$ ./dart-new-hash fastmap_test.dart
HashMap: 154
LinkedHashMap: 161

Other tests I've made show a performance improvement too, but not as large.

It is not an absolute win, though. I have a test where the existing
implementation is faster too (bigger is better):

$ ./dart-old-hash hash-exp/anagram.dart
HashMap: 16.78 rnds/s
LinkedHashMap: 12.02 rnds/s

[09:08:48]lrn@lrn:~/dart/full/dart/dev (hash-fast-map)
$ ./dart-new-hash hash-exp/anagram.dart
HashMap: 13.24 rnds/s
LinkedHashMap: 10.27 rnds/s

That code uses putIfAbsent for most operations, so it might not be true for
actual user code. 

The new code for HashMap is just *so much simpler* that I think it is better.

[Lasse Reichstein Nielsen, 2013-08-14 07:31:38]

https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
File tests/lib/convert/unicode_tests.dart (right):

https://codereview.chromium.org/23056002/diff/1/tests/lib/convert/unicode_tes...
tests/lib/convert/unicode_tests.dart:37: //const BEE_STRING = "𐐒";
Yes. Well spotted.
Probably forgot to save after removing it :)

[Søren Gjesse, 2013-08-14 07:45:06]

lgtm

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:5: patch class HashMap<K, V> {
Base class for HashMap and LinkedHashMap with common stuff. Looks as if a
majority of the operations are the same, and only rely on the buckets holding
_HashMapEntry. Of cause a cast to _LinkedHashMapEntry would be required in a few
places.

Also _modificationCount could be here.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:22: /* patch */ bool containsKey(Object key) {
Maybe have a method (_bucketHead?) for

int hashCode = key.hashCode;
List buckets = _buckets;
int index = hashCode & (buckets.length - 1);
_HashMapEntry entry = buckets[index];

Which is duplicated a number of times.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:24: List buckets = _buckets;
Why the local buckets in all methods?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:149: _modificationCount = (_modificationCount
+ 1) & _MODIFICATION_COUNT_MASK;
method for updating the modification count (duplicated below)?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:157: int newElements = _elementCount + 1;
Why the newElements local?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:358: var _nextEntry;
_LinkedHashMapEntry instead of var here?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:440: var _nextEntry;
_LinkedHashMapEntry instead of var here?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:440: var _nextEntry;
_head and _tail instead of _nextEntry and _previousEntry?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:444: _nextEntry = _previousEntry = this;
Now I see the reason for var and the naming above. It makes the
linking/unlinking code simpler when head and tail are never null. I am fine with
it, but at least it deserves a comment.

https://codereview.chromium.org/23056002/diff/1/sdk/lib/json/json.dart
File sdk/lib/json/json.dart (right):

https://codereview.chromium.org/23056002/diff/1/sdk/lib/json/json.dart#newcod...
sdk/lib/json/json.dart:505: String result = source.substring(start, position);
Why?

[Lasse Reichstein Nielsen, 2013-08-14 08:38:34]

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:5: patch class HashMap<K, V> {
I would love to, but can I do that in a patch file?

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:22: /* patch */ bool containsKey(Object key) {
In some cases the index and hashCode are reused (and buckets as shortcut to
_buckets), so we can't always extract it.
I don't think it's worth it. I can make the code smaller when hashCode and index
are not reused:
 _HashMapEntry entry = _buckets[key.hashCode & (_buckets.length - 1)];

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:24: List buckets = _buckets;
Probably an attempt to help the compiler recognize that it isn't modified. I.e.,
optimization.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:149: _modificationCount = (_modificationCount
+ 1) & _MODIFICATION_COUNT_MASK;
I guess it's inlined for performance (because we can't trust the VM to always
inline it).

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:157: int newElements = _elementCount + 1;
Probably for optimization, instead of risking reading _elementCount back.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:358: var _nextEntry;
No, it may also point to LinkedHashMap.
I can't put an interface on LinkedHashMap in the patch file, so I have to use
"var".

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:440: var _nextEntry;
It may also point to LinkedHashMap.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:440: var _nextEntry;
They have the same name as the fields on _LinkedHashMapEntry so that the code in
[remove] doesn't have to know if next/prev is the HashMap itself.

https://codereview.chromium.org/23056002/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:444: _nextEntry = _previousEntry = this;
Ack, will comment.

https://codereview.chromium.org/23056002/diff/1/sdk/lib/json/json.dart
File sdk/lib/json/json.dart (right):

https://codereview.chromium.org/23056002/diff/1/sdk/lib/json/json.dart#newcod...
sdk/lib/json/json.dart:505: String result = source.substring(start, position);
Needed it for debugging at some point. 
I saw no reason to remove it again. Naming intermediates is good for readability
:)

[Lasse Reichstein Nielsen, 2013-08-29 12:13:45]

Committed patchset #1 manually as r26863 (presubmit successful).