Canonicalize generic types in an isolate specific hash table

- Canonicalize generic types in a global isolate hash
  table, this ensures that we do not linearly walk through
  a large type list in the class calling the expensive
  'Type::Equals' method (some applications have close to
  1304 generic types in them)

- Use the stand hash table implementation for TypeArguments
  canonicalization instead of a custom hash table

R=johnmccutchan@google.com, regis@google.com, rmacnak@google.com

Committed: https://github.com/dart-lang/sdk/commit/5de775a823c6cdd5a1386044eed47da32d84d74d

[regis, 2016-05-10 18:14:25]

regis@google.com changed reviewers:
+ regis@google.com

[regis, 2016-05-10 18:14:26]

I am pretty sure that you traverse the type arguments of recursive types several
times. You end up overwriting the store hash with a version that was not used to
canonicalize the type arguments, resulting in the assert fault. You should check
that the hash is not already set before setting it again.

The hash is uint32, but you use a Smi, which is kind of a waste on 64-bit
platforms. Also, I am not sure what will happen if the hash happens to be 0.

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h#...
runtime/vm/object.h:8546: if (result != 0) {
What if the hash is 0?

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h#...
runtime/vm/object.h:8573: StoreSmi(&raw_ptr()->hash_, Smi::New(value));
What if the value does not fit in a Smi?

[siva, 2016-05-13 21:19:52]

Description was changed from

==========
Save hash value of Type and TypeArguments object, in order to avoid
recomputation.
==========

to

==========
- Canonicalize generic types in a global isolate hash
  table, this ensures that we do not linearly walk through
  a large type list in the class calling the expensive
  'Type::Equals' method (some applications have close to
  1304 generic types in them)
    
- Use the stand hash table implementation for TypeArguments
  canonicalization instead of a custom hash table
==========

[siva, 2016-05-13 23:16:12]

asiva@google.com changed reviewers:
+ rmacnak@google.com

[siva, 2016-05-13 23:16:13]

Addressed your comments and added the isolate canonicalize table.

PTAL

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h#...
runtime/vm/object.h:8546: if (result != 0) {
On 2016/05/10 18:14:26, regis wrote:
> What if the hash is 0?

I have fixed this similar to the StringHasher to return 1 if the has ever
becomes 0.

https://chromiumcodereview.appspot.com/1965493004/diff/1/runtime/vm/object.h#...
runtime/vm/object.h:8573: StoreSmi(&raw_ptr()->hash_, Smi::New(value));
On 2016/05/10 18:14:26, regis wrote:
> What if the value does not fit in a Smi?

I have fixed this similar to the StringHasher by having a max hash bits which is
30 as it should be Smi consistently on all platforms where a snapshot can be
read

[Cutch, 2016-05-16 17:01:56]

johnmccutchan@google.com changed reviewers:
+ johnmccutchan@google.com

[Cutch, 2016-05-16 17:01:57]

LGTM w.r.t. reload support. Currently we copy the canonical types from the old
classes to the new classes so a global table should be fine too.

Some other DBC nits.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3654: types = canonical_type();
Maybe rename variable to "type" to match the accessor plurality.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:20950: return (hash == 0) ? 1 : hash;
Couldn't the masking off of high bits and handling the 0 casebe inside
FinalizeHash?

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1569: static const intptr_t kHashBits = 30;
should this constant `kHashBits` sit somewhere higher up the class hierarchy? It
should be used by all hashes right? Maybe globals.h

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1716: ASSERT(sizeof(RawTypeArguments) == (sizeof(RawObject)
+ (3 * kWordSize)));
Should this "3" be a named constant with an ASSERT some place when we access
types() ?

[rmacnak, 2016-05-16 19:37:03]

lgtm

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3681: if (types.IsNull() || !types.IsArray()) {
Never an array anymore.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1569: static const intptr_t kHashBits = 30;
On 2016/05/16 17:01:57, Cutch wrote:
> should this constant `kHashBits` sit somewhere higher up the class hierarchy?
It
> should be used by all hashes right? Maybe globals.h

"so that we consistently use a 32bit Smi representation"
->
so hashes in a snapshot taken on a 64-bit machine stay in Smi range when loaded
on 32-bit machine.

[regis, 2016-05-16 20:17:48]

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3642: intptr_t Class::FindCanonicalTypeIndex(const
AbstractType& needle) const {
This function should not be required anymore.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3658: const intptr_t len = Array::Cast(types).Length();
I thought the point of this cl was to remove the array of canonical types in
each class and replace them all by a global array in the object store.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3672: RawAbstractType*
Class::CanonicalTypeFromIndex(intptr_t idx) const {
Still required?

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:5113: // Canonicalization of a recursive type may change
its hash, so recompute.
To be exact, the comment should say:
Canonicalization of a type argument of a recursive type argument vector may
change the hash of the vector, so recompute.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:8609: if (IsNull()) return 0;
Thinking aloud here. Is it OK to return 0? 0 means no computed hash yet.
Wouldn't 1 be better, so that Hash() is not called again? I guess you have no
place to store it anyway, so it does not matter. Never mind.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/type...
File runtime/vm/type_table.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/type...
runtime/vm/type_table.h:79: // Traits for looking up Canonical TypeArguments
based on it's hash.
its

[siva, 2016-05-16 23:24:25]

Addressed all comments, PTAL.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3642: intptr_t Class::FindCanonicalTypeIndex(const
AbstractType& needle) const {
On 2016/05/16 20:17:48, regis wrote:
> This function should not be required anymore.

This function is not required anymore, removed it.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3654: types = canonical_type();
On 2016/05/16 17:01:57, Cutch wrote:
> Maybe rename variable to "type" to match the accessor plurality.

This function is not used anymore and has been removed.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3658: const intptr_t len = Array::Cast(types).Length();
On 2016/05/16 20:17:48, regis wrote:
> I thought the point of this cl was to remove the array of canonical types in
> each class and replace them all by a global array in the object store.

Yes, this function has been removed.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3672: RawAbstractType*
Class::CanonicalTypeFromIndex(intptr_t idx) const {
On 2016/05/16 20:17:48, regis wrote:
> Still required?

This function is also not required and has been removed.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:3681: if (types.IsNull() || !types.IsArray()) {
On 2016/05/16 19:37:02, rmacnak wrote:
> Never an array anymore.

This function has been removed.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:5113: // Canonicalization of a recursive type may change
its hash, so recompute.
On 2016/05/16 20:17:48, regis wrote:
> To be exact, the comment should say:
> Canonicalization of a type argument of a recursive type argument vector may
> change the hash of the vector, so recompute.

Done.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.cc:20950: return (hash == 0) ? 1 : hash;
On 2016/05/16 17:01:57, Cutch wrote:
> Couldn't the masking off of high bits and handling the 0 casebe inside
> FinalizeHash? 

Done.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1569: static const intptr_t kHashBits = 30;
On 2016/05/16 19:37:02, rmacnak wrote:
> On 2016/05/16 17:01:57, Cutch wrote:
> > should this constant `kHashBits` sit somewhere higher up the class
hierarchy?
> It
> > should be used by all hashes right? Maybe globals.h
> 
> "so that we consistently use a 32bit Smi representation"
> ->
> so hashes in a snapshot taken on a 64-bit machine stay in Smi range when
loaded
> on 32-bit machine.

Done.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1569: static const intptr_t kHashBits = 30;
On 2016/05/16 17:01:57, Cutch wrote:
> should this constant `kHashBits` sit somewhere higher up the class hierarchy?
It
> should be used by all hashes right? Maybe globals.h

I am thinking it is specific to hashes in classes which use Smi as the hash
value, there are some hashes which are intptr_t values and in there this does
not make sense, heance I retained it as a value specific to the class.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:1716: ASSERT(sizeof(RawTypeArguments) == (sizeof(RawObject)
+ (3 * kWordSize)));
On 2016/05/16 17:01:57, Cutch wrote:
> Should this "3" be a named constant with an ASSERT some place when we access
> types() ?

made a named constant, the ASSERT captures any issues that may arise when a
field is added to RawTypeArgument without adjusting this constant.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/obje...
runtime/vm/object.h:8609: if (IsNull()) return 0;
On 2016/05/16 20:17:48, regis wrote:
> Thinking aloud here. Is it OK to return 0? 0 means no computed hash yet.
> Wouldn't 1 be better, so that Hash() is not called again? I guess you have no
> place to store it anyway, so it does not matter. Never mind.

Acknowledged.

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/type...
File runtime/vm/type_table.h (right):

https://chromiumcodereview.appspot.com/1965493004/diff/100001/runtime/vm/type...
runtime/vm/type_table.h:79: // Traits for looking up Canonical TypeArguments
based on it's hash.
On 2016/05/16 20:17:48, regis wrote:
> its

Done.

[regis, 2016-05-17 16:55:31]

LGTM

https://chromiumcodereview.appspot.com/1965493004/diff/120001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/120001/runtime/vm/obje...
runtime/vm/object.cc:17055: return FinalizeHash(result, Type::kHashBits);
This is the only place where you qualify kHashBits. You could actually remove
the multiple declarations of it except in Type and use Type::kHashBits
everywhere, even in TypeArguments.

[siva, 2016-05-17 21:25:53]

https://chromiumcodereview.appspot.com/1965493004/diff/120001/runtime/vm/obje...
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/1965493004/diff/120001/runtime/vm/obje...
runtime/vm/object.cc:17055: return FinalizeHash(result, Type::kHashBits);
On 2016/05/17 16:55:30, regis wrote:
> This is the only place where you qualify kHashBits. You could actually remove
> the multiple declarations of it except in Type and use Type::kHashBits
> everywhere, even in TypeArguments.

Moved kHashBits to AbstractType as discussed offline and removed from all the
derived classes.

[siva, 2016-05-17 21:35:27]

Description was changed from

==========
- Canonicalize generic types in a global isolate hash
  table, this ensures that we do not linearly walk through
  a large type list in the class calling the expensive
  'Type::Equals' method (some applications have close to
  1304 generic types in them)
    
- Use the stand hash table implementation for TypeArguments
  canonicalization instead of a custom hash table
==========

to

==========
- Canonicalize generic types in a global isolate hash
  table, this ensures that we do not linearly walk through
  a large type list in the class calling the expensive
  'Type::Equals' method (some applications have close to
  1304 generic types in them)

- Use the stand hash table implementation for TypeArguments
  canonicalization instead of a custom hash table

R=johnmccutchan@google.com, regis@google.com, rmacnak@google.com

Committed:
https://github.com/dart-lang/sdk/commit/5de775a823c6cdd5a1386044eed47da32d84d74d
==========

[siva, 2016-05-17 21:35:29]

Committed patchset #10 (id:180001) manually as
5de775a823c6cdd5a1386044eed47da32d84d74d (presubmit successful).