New implementation of {,Linked}Hash{Set,Map}.

New implementation of {,Linked}Hash{Set,Map}.

Accepts null keys/entries.
Much faster LinkedHashMap, faster HashSet, slight penalty on HashMap,
possibly due to accepting null keys.
Performance difference depends on table size.

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

[kasperl, 2013-02-05 09:42:00]

On 2013/02/05 09:32:49, Lasse Reichstein Nielsen wrote:

You should upload the new files too.

[Lasse Reichstein Nielsen, 2013-02-05 11:50:09]

Thanks :)
I'll create co19 issue numbers when I'm good to commit.

[erikcorry, 2013-02-05 16:25:05]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:40: _modificationCount++;
You probably want to mask this with something so it does not get too big.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
Seems inconsistent that you don't increment the modification count here, when
you increment it in addAll

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:90: for (int offset = 0; offset <
_table.length; offset += 2) {
+= _entrySize?

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:26: void addAll(Iterable<E> objects) {
I can't see where this increments the modification count.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:52: void retainAll(Iterable objectsToRemove) {
Parameter is misnamed.

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-runtime.st...
File tests/co19/co19-runtime.status (right):

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-runtime.st...
tests/co19/co19-runtime.status:505: # Doesn't expect null to be allowed in Set
or Map keys.
I think fixing these tests would get you better test coverage.

[Lasse Reichstein Nielsen, 2013-02-05 19:47:40]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:40: _modificationCount++;
That could be wrong, if you keep an iterator alive until the counter overflows..
If you overflow a 31-bit smi by incrementing, you're asking for it.
That said, if you keep an iterator alive while doing that, you're definitely
asking for something too.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
The modification count is only for modifications that break iteration. Changing
the value associated to a key don't do that if the key exists already, and if it
doesn't exist, the count is incremented in _put.

But you are right that I shouldn't increment in addAll either.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:90: for (int offset = 0; offset <
_table.length; offset += 2) {
Yes, it's probably more readable, even if we know it's 2 here.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:26: void addAll(Iterable<E> objects) {
True. I was probably assuming that it was done in _put, if necessary. I'll add
it there.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:52: void retainAll(Iterable objectsToRemove) {
Whoops.

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-runtime.st...
File tests/co19/co19-runtime.status (right):

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-runtime.st...
tests/co19/co19-runtime.status:505: # Doesn't expect null to be allowed in Set
or Map keys.
Not really - these are all pretty simple tests that only test that putting
"null" into a map or set will throw. Which it won't any more. Only the last test
(forEach_A01_t07) does something useful.

It's academic anyway, since I can't change co19 tests.

[sra1, 2013-02-06 05:35:21]

I like the approach take here.

However, I'm concerned that this change causes a 29k increase in the size of
swarm:

Before 775076
After  804082

Most of the change in size corresponds to code which sourcemaps attribute to the
following files:
-20408 - sdk/lib/collection/map.dart
-2116 - sdk/lib/collection/set.dart
4414 + sdk/lib/collection/hash_map.dart
4668 + sdk/lib/collection/hash_set.dart
8279 + sdk/lib/collection/linked_hash_map.dart
10563 + sdk/lib/collection/linked_hash_table.dart
23378 + sdk/lib/collection/hash_table.dart

Notice that the DoubleLinkedQueue (used in the old _LinkedHashMapImpl) is not in
the files with savings because it is used elsewhere in swarm.  It would have
been about 4k had it not been used elsewhere.

There is no mystery here.  The CL deletes 586 lines of code and adds 1067,
nearly twice as much.

Is there some way to further factor this CL so that it is less code?

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:139: bool _equals(Object element, Object
other) {
Who overrides this?
Do you plan to use it for an identity hash?

[floitsch, 2013-02-06 10:43:58]

LGTM.
I would prefer not to share the same array for keys and values. It would make it
somehow cleaner and allow the VM to specialize the value-list for a specific
type.
However it would make growing more difficult.

Also: please add the test from:
https://chromiumcodereview.appspot.com/11644072/diff/1/tests/corelib/ordered_...

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:18: _copyEntry(List fromTable, int fromOffset,
int toOffset) {
Add comment that this is just to be more efficient. The base function is good
enough.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:19: _setValue(toOffset, fromTable[fromOffset +
_VALUE_INDEX]);
Don't use '_setValue' it makes it confusing.
_table[toOffset + VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:40: _modificationCount++;
On 2013/02/05 19:47:40, Lasse Reichstein Nielsen wrote:
> That could be wrong, if you keep an iterator alive until the counter
overflows..
> If you overflow a 31-bit smi by incrementing, you're asking for it.
> That said, if you keep an iterator alive while doing that, you're definitely
> asking for something too.

It's 30 bits (1 for tagging, 1 for the sign). That could realistically happen
(add/remove -> 2 operations).
If you are having an iterator alive for all that time you are doing it on
purpose...
So I would prefer a 30-bit mask too.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:42: int offset = _table._remove(object);
modification count here too.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:47: for (Object object in objectsToRemove) {
ditto.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:107: bool containsAll(Collection<E> collection)
{
We should change this to be an Iterable.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:114: Set<E> intersection(Collection<E> other) {
ditto.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:115: Set<E> result = new HashSet<E>();
new Set<E>(). It should be the default Set.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:17: * Table of entries with [_entrySize]
elements per entry.
[_entrySize] slots per entry.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
Make it a do while(true) ?

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:140: return element == other;
In the last implementation we were hitting a lot of polymorphic calls, because
element was the Sentinel (tombstone now) or the actual type.
Now we end up having 3 types: tombstone, Null and the type.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:162: // Less than 25% free or less free
entries than deleted entries.
fewer

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:171: do {
If a table adds and removes elements frequently, it will end up growing for
nothing.
I would say that the while-check should be before the *2.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:203: void _copyEntry(List fromTable, int
fromOffset, int toOffset) {
I don't think there is an implementation that uses the default implementation.
-> remove.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:211: // They only affect the key of an entry.
The remaining fields must be
Not true. The clear method removes everything.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:234: * remaining fileds.
fields

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:19: _setValue(toOffset,
oldTable[fromOffset + _VALUE_INDEX]);
don't use "_setValue".

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:82: Object oldValue = _value(offset);
modification counter.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:62: if (objects is Set || objects is
List) {
I'm not convinced if we should special case, or not just call iterable.length.
Yes. it could be an O(n) operation, but on the other hand growing one by one is
not really optimal either.
(and an iterable that is given away should not assume that it is only called
once. If that's a requirement it has to "toList()" itself).

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:109: void retainMatching(bool test(E
element)) {
removeMatching and retainMatching could share the same code with a simple if
(matches == shouldMatch) {

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:150: Set<E> result = new HashSet<E>();
new Set.
I think it should be the default Set.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_table.dart:74: _modificationCount++;
This is the only place in the linked_hash_table where we update the modification
count. Should we move it out to the sub-classes entirely. Would be more
consistent.
Same for the non-linked version.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_table.dart:145: class
_LinkedHashTableValueIterator<V> implements Iterator<V> {
The Key and Value iterator could share a common super-class and just implement
"_setCurrent(offset)".

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-dart2dart....
File tests/co19/co19-dart2dart.status (right):

https://codereview.chromium.org/12213010/diff/2001/tests/co19/co19-dart2dart....
tests/co19/co19-dart2dart.status:660: LibTest/core/Map/containsKey_A01_t02: Fail
File co19 bug.
(Just a reminder, so you can click on "done").

https://codereview.chromium.org/12213010/diff/2001/tests/corelib/maps_test.dart
File tests/corelib/maps_test.dart (right):

https://codereview.chromium.org/12213010/diff/2001/tests/corelib/maps_test.da...
tests/corelib/maps_test.dart:48: Expect.equals(7, Maps.length(map), "$map");
Revert?

[erikcorry, 2013-02-06 10:57:55]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
On 2013/02/05 19:47:40, Lasse Reichstein Nielsen wrote:
> The modification count is only for modifications that break iteration.
Changing
> the value associated to a key don't do that if the key exists already, and if
it
> doesn't exist, the count is incremented in _put.
> 
> But you are right that I shouldn't increment in addAll either.

You already called _ensureCapacity, which may have reordered all the elements,
but does not increment the counter, so it's a bad idea to rely on _setValue to
do it _only_ if a new key is introduced!

You need more tests.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
On 2013/02/06 10:43:58, floitsch wrote:
> Make it a do while(true) ?

Why?

[floitsch, 2013-02-06 11:45:46]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
On 2013/02/05 19:47:40, Lasse Reichstein Nielsen wrote:
> The modification count is only for modifications that break iteration.
Changing
> the value associated to a key don't do that if the key exists already, and if
it
> doesn't exist, the count is incremented in _put.
> 
> But you are right that I shouldn't increment in addAll either.

I would not make it dependent on the actual outcome. If you do an operation that
could change the map, the iterator should throw.
However. We should provide an "update" method that throws if the element doesn't
exist yet.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
On 2013/02/06 10:57:56, erikcorry wrote:
> On 2013/02/06 10:43:58, floitsch wrote:
> > Make it a do while(true) ?
> 
> Why?

consistency with above.
And in general (without looking at the condition-expression) it produces nicer
control-flow in the ssa-builder.

[erikcorry, 2013-02-06 11:48:41]

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
On 2013/02/06 11:45:46, floitsch wrote:
> On 2013/02/06 10:57:56, erikcorry wrote:
> > On 2013/02/06 10:43:58, floitsch wrote:
> > > Make it a do while(true) ?
> > 
> > Why?
> 
> consistency with above.
> And in general (without looking at the condition-expression) it produces nicer
> control-flow in the ssa-builder.

This must be a German language thing.  You like having to wait to the end of the
construct to understand what it is all about. :-)

[sra1, 2013-02-06 17:01:08]

What is the idiomatic way retrieve an element from a map and return a call-site
specified default value?

Python's dict has an optional argument to get, e.g.

count = histogram.get(key, 0)
histogram.put(key, count + 1)

This is generally useful, but especially so when null can be stored in the map.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
On 2013/02/06 11:48:41, erikcorry wrote:
> On 2013/02/06 11:45:46, floitsch wrote:
> > On 2013/02/06 10:57:56, erikcorry wrote:
> > > On 2013/02/06 10:43:58, floitsch wrote:
> > > > Make it a do while(true) ?
> > > 
> > > Why?
> > 
> > consistency with above.
> > And in general (without looking at the condition-expression) it produces
nicer
> > control-flow in the ssa-builder.
> 
> This must be a German language thing.  You like having to wait to the end of
the
> construct to understand what it is all about. :-)

I like
  for (;;) {...}  

If you know there is something wrong with the ssa graph for any idiomatic loop,
please open a bug against the ssa builder.

[Lasse Reichstein Nielsen, 2013-02-08 13:53:01]

Please take another look at the concurrent-modification handling.

Nicolas: FYI, I added some wrappers in dart2js where it was modifying a
collection while iterating it.

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:18: _copyEntry(List fromTable, int fromOffset,
int toOffset) {
Base function has been reduced to not copying anything extra.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:19: _setValue(toOffset, fromTable[fromOffset +
_VALUE_INDEX]);
On 2013/02/06 10:43:58, floitsch wrote:
> Don't use '_setValue' it makes it confusing.
> _table[toOffset + VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:40: _modificationCount++;
On 2013/02/06 10:43:58, floitsch wrote:
> On 2013/02/05 19:47:40, Lasse Reichstein Nielsen wrote:
> > That could be wrong, if you keep an iterator alive until the counter
> overflows..
> > If you overflow a 31-bit smi by incrementing, you're asking for it.
> > That said, if you keep an iterator alive while doing that, you're definitely
> > asking for something too.
> 
> It's 30 bits (1 for tagging, 1 for the sign). That could realistically happen
> (add/remove -> 2 operations).
> If you are having an iterator alive for all that time you are doing it on
> purpose...
> So I would prefer a 30-bit mask too.

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
I prefer to consider only operations that change the key-set of the map as
modifications. Iteration of a map is usually iteration of the key-set anyway
(Map itself is not Iterable).

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:42: int offset = _table._remove(object);
Added to _remove.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:47: for (Object object in objectsToRemove) {
Et ditto.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:107: bool containsAll(Collection<E> collection)
{
Or a Set. I think I would prefer that for intersection.
Not changing the Set signature it in this CL.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:114: Set<E> intersection(Collection<E> other) {
Same.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:115: Set<E> result = new HashSet<E>();
Let's keep this the same type as the set creating the intersection.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:115: while (true) {
I've changed it to while(true). It is more readable to see up-front that the
loop is infinite. I'd use for(;;) in C, but I hope it won't become idiomatic in
Dart ;)

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:139: bool _equals(Object element, Object
other) {
Exactly.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:140: return element == other;
If that is a problem, maybe it can be avoided by always checking for those
explicitly before doing equals. I think the probeForRead doesn't do that
currently.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:162: // Less than 25% free or less free
entries than deleted entries.
On 2013/02/06 10:43:58, floitsch wrote:
> fewer

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:171: do {
Good point. I've had the same thought too.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:203: void _copyEntry(List fromTable, int
fromOffset, int toOffset) {
It's reduced to doing nothing. That is still correct for HashSet, and you still
need to override it you have more data.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:211: // They only affect the key of an entry.
The remaining fields must be
Whoops, moving _clear below the three methods I actually was talking about.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:234: * remaining fileds.
On 2013/02/06 10:43:58, floitsch wrote:
> fields

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:19: _setValue(toOffset,
oldTable[fromOffset + _VALUE_INDEX]);
On 2013/02/06 10:43:58, floitsch wrote:
> don't use "_setValue".

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:82: Object oldValue = _value(offset);
Done by _remove now.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:62: if (objects is Set || objects is
List) {
I think you are right. Reading objects.length will usually be fast for other
collections (exceptions are adding a .where()-filtered collection or some
special iterable that isn't based on a collection).

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:109: void retainMatching(bool test(E
element)) {
On 2013/02/06 10:43:58, floitsch wrote:
> removeMatching and retainMatching could share the same code with a simple if
> (matches == shouldMatch) {

Done.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:150: Set<E> result = new HashSet<E>();
I'll make it the same typo as this set (which will be LinkedHashSet).

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_table.dart:74: _modificationCount++;
I have moved modification-count into the _put, _remove and _clear methods, so
only methods not working through those need to handle their own modification
count.

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_table.dart:145: class
_LinkedHashTableValueIterator<V> implements Iterator<V> {
On 2013/02/06 10:43:58, floitsch wrote:
> The Key and Value iterator could share a common super-class and just implement
> "_setCurrent(offset)".

Done.

https://codereview.chromium.org/12213010/diff/2001/tests/corelib/maps_test.dart
File tests/corelib/maps_test.dart (right):

https://codereview.chromium.org/12213010/diff/2001/tests/corelib/maps_test.da...
tests/corelib/maps_test.dart:48: Expect.equals(7, Maps.length(map), "$map");
On 2013/02/06 10:43:58, floitsch wrote:
> Revert?

Done.

[floitsch, 2013-02-08 16:48:35]

LGTM except for the _NULL == part.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_s...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_s...
sdk/lib/collection/hash_set.dart:68: _table._recordModification();
shouldn't be necessary. _deleteEntry records the modification.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:10: bool operator ==(Object other) => other
== null || identical(this, other);
that can't happen. other will never be 'null'.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:44: /** Writes key to table. Converts _NULL
marker to null. */
Converts null to _NULL marker.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/linked...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/linked...
sdk/lib/collection/linked_hash_map.dart:74: V value = ifAbsent();
You already changed the _entryCount and _deletedCount. So you must guard the
ifAbsent against throws. (Or delay the update of the variables).

[erikcorry, 2013-02-11 10:18:29]

In an earlier iteration I pointed out a bug that was getting past your tests,
yet you did not add any tests.

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
On 2013/02/08 13:53:01, Lasse Reichstein Nielsen wrote:
> I prefer to consider only operations that change the key-set of the map as
> modifications. Iteration of a map is usually iteration of the key-set anyway
> (Map itself is not Iterable).

If that is the contract with the user, then you need to make sure that it is
reliable.  At the moment if you set an entry using a key that was already there
you won't get a concurrent modification exception _unless_ the fullness of the
table was just below some limit, in which case the table will be expanded and
rebuilt and you will get the exception.

[Lasse Reichstein Nielsen, 2013-02-11 14:07:37]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
Gah! 
Ok. I think I can do something for non-linked sets so that growing won't cause
iteration to fail (basically; caching the table in the iterator). It will be
able to provide stale values then (but that's ok).

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_s...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_s...
sdk/lib/collection/hash_set.dart:68: _table._recordModification();
True.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:10: bool operator ==(Object other) => other
== null || identical(this, other);
Actually, it will never be _NULL.
The incoming value isn't converted to _NULL prematurely. It's only converted to
null when the key is written, and converted back before being used for anything.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:44: /** Writes key to table. Converts _NULL
marker to null. */
On 2013/02/08 16:48:35, floitsch wrote:
> Converts null to _NULL marker.

Done.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/linked...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/linked...
sdk/lib/collection/linked_hash_map.dart:74: V value = ifAbsent();
On 2013/02/08 16:48:35, floitsch wrote:
> You already changed the _entryCount and _deletedCount. So you must guard the
> ifAbsent against throws. (Or delay the update of the variables).

Done.

[floitsch, 2013-02-11 14:09:43]

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:10: bool operator ==(Object other) => other
== null || identical(this, other);
On 2013/02/11 14:07:37, Lasse Reichstein Nielsen wrote:
> Actually, it will never be _NULL.
> The incoming value isn't converted to _NULL prematurely. It's only converted
to
> null when the key is written, and converted back before being used for
anything.

But the spec for x == y already guarantees that if one side is "null" it won't
do the method call.

[erikcorry, 2013-02-11 14:42:05]

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
On 2013/02/11 14:07:37, Lasse Reichstein Nielsen wrote:
> Gah! 
> Ok. I think I can do something for non-linked sets so that growing won't cause
> iteration to fail (basically; caching the table in the iterator). It will be
> able to provide stale values then (but that's ok).

So if you update the values for preexisting keys while iterating do you get the
new values or the old values?  The answer would seem to depend on whether you
are close to the capacity limit.

[Lasse Reichstein Nielsen, 2013-02-12 10:34:47]

PTAL

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

https://codereview.chromium.org/12213010/diff/2001/sdk/lib/collection/hash_ma...
sdk/lib/collection/hash_map.dart:53: _setValue(offset, value);
Yes, That's acceptable. You always get the elements that were in the table
during the entire iteration. Elements added or remove during iteration may or
may not be included as well, and they may be included after they were removed.

In any case, I didn't go for this solution, and instead checks for growing after
adding instead of before. Updating an existing key will not change the
parameters used to determine if it should grow, so it won't.

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12213010/diff/14001/sdk/lib/collection/hash_t...
sdk/lib/collection/hash_table.dart:10: bool operator ==(Object other) => other
== null || identical(this, other);
Doh. So it's not working. More tests needed.

[erikcorry, 2013-02-12 14:31:12]

LGTM

https://codereview.chromium.org/12213010/diff/8024/tests/corelib/hash_map2_te...
File tests/corelib/hash_map2_test.dart (right):

https://codereview.chromium.org/12213010/diff/8024/tests/corelib/hash_map2_te...
tests/corelib/hash_map2_test.dart:1: // Copyright (c) 2011, the Dart project
authors.  Please see the AUTHORS file
2013