Add VM class for Map/LinkedHashMap.

Add VM class for Map/LinkedHashMap.

Introduces a new internal class for the most common case, the default Map.

Passes all functionality tests.
Slow: Dart side simply calls into runtime for now.
Hidden behind "--use_internal_hash_map".

Add copies of hash map tests to exercise this implementation.

R=asiva@google.com

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

[siva, 2014-07-23 22:43:07]

Mostly minor nits...

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
File runtime/lib/linked_hash_map.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:47: return map.Contains(key) ? Bool::True().raw()
: Bool::False().raw();
you could also write this as:

return Bool::Get(map.Contains(key)).raw();

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:88: return map.GetModificationMark(create.raw()
== Bool::True().raw());
I guess this could be:

return map.GetModificationMark(create.value());

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
File runtime/lib/linked_hash_map.dart (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.dart:20: List _toArray() native
"LinkedHashMap_toArray";
blank line here for spacing?

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.dart:62: // The even-indexed entries of toArray are
the values.
Comment states both key and values are even-indexed entries.
values should be odd-indexed entries

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18020: if (a.IsNull() || b.IsNull()) {
why not

if (a.raw() == b.raw()) {
  return true;
} else {
  return Instance::Cast(a).......
}

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18029: }
Need a NoGCScope here right as we have a raw object being used below.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18079: Object& result = Object::Handle(map.GetOrNull(key));
const Object& result ....

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18104: Object& result = Object::Handle(map.GetOrNull(key));
const Object& result ....

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18120: StorePointer(&raw_ptr()->data_, map.Release());
Do we still require to do a map.Initialize() if Length() is 0.

i.e if Clear() is called twice in succession do we need to go over this code
twice?

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18142: Instance& current =
Instance::Handle(Instance::New(object_class));
Would be worth allocating a local variable isolate and using it for the handle
creation and access to object_class();

Isolate* Isolate = Isolate::Current();
const Class& object_class = Class::Handle(isolate, isolate->...);
const Instance& current = Instance::Handle(isolate, ...);

Also instead of creating a new mark object every time should we just
create one per isolate upfront and use it here. Similar to how we have
Object::sentinel_
Object::transition_sentinel_
etc.

Maybe Object::sentinel_ itself could be your mark object ?

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
File runtime/vm/raw_object_snapshot.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2183: if (kind == Snapshot::kFull) {
Do we expect to see hash maps in script snapshots?

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2189: Array& contents = Array::Handle();
Array::Handle(reader->isolate());

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2193:
TypeArguments::Handle(contents.GetTypeArguments());
TypeArguments::Handle(reader->isolate(), ...);

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2201: Snapshot::Kind kind) {
if (kind == Snapshot::kFull) UNREACHABLE() ?
Also what about script snapshots?

[koda, 2014-07-24 19:31:45]

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
File runtime/lib/linked_hash_map.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:47: return map.Contains(key) ? Bool::True().raw()
: Bool::False().raw();
On 2014/07/23 22:43:06, siva wrote:
> you could also write this as:
> 
> return Bool::Get(map.Contains(key)).raw();

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:88: return map.GetModificationMark(create.raw()
== Bool::True().raw());
On 2014/07/23 22:43:06, siva wrote:
> I guess this could be:
> 
> return map.GetModificationMark(create.value());

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
File runtime/lib/linked_hash_map.dart (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.dart:20: List _toArray() native
"LinkedHashMap_toArray";
On 2014/07/23 22:43:06, siva wrote:
> blank line here for spacing?

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/lib/linke...
runtime/lib/linked_hash_map.dart:62: // The even-indexed entries of toArray are
the values.
On 2014/07/23 22:43:06, siva wrote:
> Comment states both key and values are even-indexed entries.
> values should be odd-indexed entries

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18020: if (a.IsNull() || b.IsNull()) {
Because that could give the wrong result for NaN.

I focused on correctness in this CL. We could definitely inline the common
cases, but performance tuning will come later (and probably focus more on the
Dart/intrinsics).

On 2014/07/23 22:43:07, siva wrote:
> why not
> 
> if (a.raw() == b.raw()) {
>   return true;
> } else {
>   return Instance::Cast(a).......
> }

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18029: }
On 2014/07/23 22:43:07, siva wrote:
> Need a NoGCScope here right as we have a raw object being used below.

Although I don't think there was any actual bug, I agree that the code looks
unsafe.

So, for now I'll instead always create the handle (cannot use NoGCScope since
HashCode currently might allocate). Once the TODO has been addressed and we only
have Smis, this will be simple and fast.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18079: Object& result = Object::Handle(map.GetOrNull(key));
On 2014/07/23 22:43:07, siva wrote:
> const Object& result ....

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18104: Object& result = Object::Handle(map.GetOrNull(key));
On 2014/07/23 22:43:06, siva wrote:
> const Object& result ....

Done.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18120: StorePointer(&raw_ptr()->data_, map.Release());
On 2014/07/23 22:43:07, siva wrote:
> Do we still require to do a map.Initialize() if Length() is 0.
> 
> i.e if Clear() is called twice in succession do we need to go over this code
> twice?

No, you are right. Moved everything into the 'if'.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/object...
runtime/vm/object.cc:18142: Instance& current =
Instance::Handle(Instance::New(object_class));
First part done.

As for the marks, we do need more than one. I've added the following comment in
linked_hash_map.dart. Let me know if you still think it needs clarification (a
counter-based solution would be easier to explain, but needs overflow handling).

  // "Modificaton marks" are tokens used to detect concurrent modification.
  // Considering only modifications (M) and iterator creation (I) events, e.g.:
  //   M, M, M, I, I, M, I, M, M, I, I, I, M ...
  // a new mark is allocated at the start of each run of I's and cleared from
the map at
  // the start of each run of M's. Iterators' moveNext check whether the map's
  // mark was changed or cleared since the iterator was created.
  // TODO(koda): Consider a counter instead.

On 2014/07/23 22:43:07, siva wrote:
> Would be worth allocating a local variable isolate and using it for the handle
> creation and access to object_class();
> 
> Isolate* Isolate = Isolate::Current();
> const Class& object_class = Class::Handle(isolate, isolate->...);
> const Instance& current = Instance::Handle(isolate, ...);
> 
> Also instead of creating a new mark object every time should we just
> create one per isolate upfront and use it here. Similar to how we have
> Object::sentinel_
> Object::transition_sentinel_
> etc.
> 
> Maybe Object::sentinel_ itself could be your mark object ?

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
File runtime/vm/raw_object_snapshot.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2183: if (kind == Snapshot::kFull) {
On 2014/07/23 22:43:07, siva wrote:
> Do we expect to see hash maps in script snapshots?

In the future, yes. But not currently, the immutable maps that seed map literals
are not yet VM-internal.

I added the script case and a comment both here and in WriteTo.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2189: Array& contents = Array::Handle();
On 2014/07/23 22:43:07, siva wrote:
> Array::Handle(reader->isolate());

Done, also in GrowableObjectArray above.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2193:
TypeArguments::Handle(contents.GetTypeArguments());
On 2014/07/23 22:43:07, siva wrote:
> TypeArguments::Handle(reader->isolate(), ...);

Done, also in GrowableObjectArray above.

https://chromiumcodereview.appspot.com/380333002/diff/20001/runtime/vm/raw_ob...
runtime/vm/raw_object_snapshot.cc:2201: Snapshot::Kind kind) {
On 2014/07/23 22:43:07, siva wrote:
> if (kind == Snapshot::kFull) UNREACHABLE() ?
> Also what about script snapshots?

See previous comment.

[siva, 2014-07-24 20:24:25]

Did you upload after the changes? I do not see any delta.

[siva, 2014-07-24 20:25:54]

On 2014/07/24 20:24:25, siva wrote:
> Did you upload after the changes? I do not see any delta.

I see it now.

[koda, 2014-07-24 20:28:13]

On 2014/07/24 20:24:25, siva wrote:
> Did you upload after the changes? I do not see any delta.

Patch Set 3 has all the latest changes. I'm not sure why Rietveld doesn't show
the deltas from Set 2... I'll upload again.

[siva, 2014-07-24 20:47:11]

lgtm

https://chromiumcodereview.appspot.com/380333002/diff/60001/runtime/lib/linke...
File runtime/lib/linked_hash_map.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/60001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:93: return FLAG_use_internal_hash_map ?
Bool::True().raw() : Bool::False().raw();
return Bool::Get(FLAG_use_internal_hash_map).raw();

[koda, 2014-07-25 20:03:17]

https://chromiumcodereview.appspot.com/380333002/diff/60001/runtime/lib/linke...
File runtime/lib/linked_hash_map.cc (right):

https://chromiumcodereview.appspot.com/380333002/diff/60001/runtime/lib/linke...
runtime/lib/linked_hash_map.cc:93: return FLAG_use_internal_hash_map ?
Bool::True().raw() : Bool::False().raw();
On 2014/07/24 20:47:11, siva wrote:
> return Bool::Get(FLAG_use_internal_hash_map).raw();

Done.

[koda, 2014-07-25 20:04:22]

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