Switched Serialization identityMap to use a wrapper, not linear search.

Switched Serialization identityMap to use a wrapper, not linear search.

R=jmesserly@google.com

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

[Alan Knight, 2013-08-26 21:06:58]

With fast expandos in the VM, the linear search hack for an identity map in
serialization can be replaced with a wrapper-based hack to compare based on
identity. Code is slightly smaller, and on a simple benchmark of a linked list
of 10,000 cells with an extra string field, it's about 10x faster on dart2js and
more than 20x on the VM.

[Jennifer Messerly, 2013-08-26 21:58:47]

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
File pkg/serialization/lib/src/serialization_helpers.dart (right):

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:183: * This is used to
provide an identity map. We wrap all the objects in
this comment belongs on the IdentityMap type instead?

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:189: // TODO(alanknight):
Replace with a real identityMap. Issue 4161.
remove todo? or perhaps change it to:
TODO: implement this without wrappers

(ideally we'd have the ability to provide the equals/hashcode function to the
map w/o requiring every object be wrapped)

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:190: class
IdentityMapWrapper {
maybe make this class library private to indicate it's an impl detail of
IdentityMap.

Also perhaps rename "IdentityMapKey"?

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:209: class IdentityMap<K,
V> implements Map<K, V> {
I wonder if it's possible and a good idea to extend LinkedHashMap instead of
implementing it, and then use "super" to forward the methods?

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:220: map.keys.forEach((k)
=> f(_unwrap(k), map[k]));
perhaps:

map.forEach((k, v) { f(_unwrap(k), v); });

...to save the extra hash lookup for every element?

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:247: this[key] = value;
_wrap?

[Alan Knight, 2013-08-27 18:13:44]

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
File pkg/serialization/lib/src/serialization_helpers.dart (right):

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:183: * This is used to
provide an identity map. We wrap all the objects in
On 2013/08/26 21:58:47, John Messerly wrote:
> this comment belongs on the IdentityMap type instead?

Rephrased and put it on both.

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:189: // TODO(alanknight):
Replace with a real identityMap. Issue 4161.
On 2013/08/26 21:58:47, John Messerly wrote:
> remove todo? or perhaps change it to:
> TODO: implement this without wrappers
> 
> (ideally we'd have the ability to provide the equals/hashcode function to the
> map w/o requiring every object be wrapped) 

Rephrased the TODO. The bug is for the core library to allow maps where you can
provide the equality (and hash?) functions.

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:190: class
IdentityMapWrapper {
On 2013/08/26 21:58:47, John Messerly wrote:
> maybe make this class library private to indicate it's an impl detail of
> IdentityMap.
> 
> Also perhaps rename "IdentityMapKey"?

Done.

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:209: class IdentityMap<K,
V> implements Map<K, V> {
On 2013/08/26 21:58:47, John Messerly wrote:
> I wonder if it's possible and a good idea to extend LinkedHashMap instead of
> implementing it, and then use "super" to forward the methods?

Possible, and does make the code simpler, but unfortunately never terminated on
dart2js until I realized that in the dartj2s implementation some calls make use
of others in ways they don't on the VM, so you can get multiple levels of
wrapping. But done now.

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:220: map.keys.forEach((k)
=> f(_unwrap(k), map[k]));
On 2013/08/26 21:58:47, John Messerly wrote:
> perhaps:
> 
> map.forEach((k, v) { f(_unwrap(k), v); });
> 
> ...to save the extra hash lookup for every element?

Done.

https://codereview.chromium.org/23467002/diff/1/pkg/serialization/lib/src/ser...
pkg/serialization/lib/src/serialization_helpers.dart:247: this[key] = value;
On 2013/08/26 21:58:47, John Messerly wrote:
> _wrap?

[]= will wrap, so not needed. With subclassing, the whole method isn't needed.

[Jennifer Messerly, 2013-08-27 18:30:58]

lgtm!

[Alan Knight, 2013-08-27 19:08:03]

Committed patchset #2 manually as r26737 (presubmit successful).