Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
11474056:
Store canonical type argments in a hash table instead of linear list. (Closed)
|
Created:
8 years ago by Florian Schneider Modified:
8 years ago CC:
reviews_dartlang.org, vm-dev_dartlang.org Visibility:
Public. |
DescriptionStore canonical type argments in a hash table instead of linear list.
The code closely follows the symbol table implementation, but adjusted
for use with TypeArguments objects.
Committed: https://code.google.com/p/dart/source/detail?r=16117
Patch Set 1 #
Total comments: 26
Patch Set 2 : addressed comments #
Total comments: 19
Patch Set 3 : #
Total comments: 13
Patch Set 4 : addessed comments #Messages
Total messages: 14 (0 generated)
https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode576 runtime/vm/object.cc:576: // canonical_type_arguments_ are NULL terminated. Comment out of date. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2715 runtime/vm/object.cc:2715: return NULL; This seems very unconnected to the change at hand? https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode1... runtime/vm/object.cc:10075: const char* characters = ToCString(); This seems very fragile to me and as you are not caching this anywhere making this rather expensive. Consider an alternative hash function which relies on the participating class ids? Regis?
https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode576 runtime/vm/object.cc:576: // canonical_type_arguments_ are NULL terminated. Fix comment: Smi terminated. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode577 runtime/vm/object.cc:577: const intptr_t kInitialCanonicalTypeArgumentsSize = 4; Seems too small as initial size. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2840 runtime/vm/object.cc:2840: // Last element of the array is the number of used elements. Pass isolate as first argument (as done in other places in this code). https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2842 runtime/vm/object.cc:2842: intptr_t new_table_size = table_size * 2; Can you check on dart2js, checked mode, how much the table grows. The growth policy seems aggressive for large tables. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2852 runtime/vm/object.cc:2852: intptr_t index = hash % new_table_size; new_table_size should be power of 2 for performance reasons. Maybe add an assert? https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2872 runtime/vm/object.cc:2872: Isolate* isolate) { 'isolate' as first argument. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2877 runtime/vm/object.cc:2877: dart::Smi& used = Smi::Handle(isolate); s/dart::Smi/Smi/ I do not think there is a conflicting Smi definition around. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2893 runtime/vm/object.cc:2893: Isolate* isolate) { ditto
https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode1... runtime/vm/object.cc:10075: const char* characters = ToCString(); On 2012/12/10 20:07:52, Ivan Posva wrote: > This seems very fragile to me and as you are not caching this anywhere making > this rather expensive. Consider an alternative hash function which relies on the > participating class ids? Regis? Yes, for efficiency, the hash of a TypeArguments vector should depend on the hash of its constituent element types. Each element type is either a Type or a TypeParameter. A Type has a type class (class id is an integer) and a type argument vector. A type parameter refers to a class (integer class id) and has an index (integer); its name is not relevant here. So the hash can be calculated from integers only. This should be much more efficient than computing the name. Now, you need to pay attention to malformed types, but we do not canonicalize them, if I remember correctly. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.h#newcode989 runtime/vm/object.h:989: intptr_t Hash() const; You should add a Hash() to AbstractType as well (and to Type and TypeParameter), since the hash of this vector depends on the hash of its type elements.
Updated with comments addressed. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode576 runtime/vm/object.cc:576: // canonical_type_arguments_ are NULL terminated. On 2012/12/10 21:19:37, srdjan wrote: > Fix comment: Smi terminated. Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode576 runtime/vm/object.cc:576: // canonical_type_arguments_ are NULL terminated. On 2012/12/10 20:07:52, Ivan Posva wrote: > Comment out of date. Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode576 runtime/vm/object.cc:576: // canonical_type_arguments_ are NULL terminated. On 2012/12/10 20:07:52, Ivan Posva wrote: > Comment out of date. Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode577 runtime/vm/object.cc:577: const intptr_t kInitialCanonicalTypeArgumentsSize = 4; On 2012/12/10 21:19:37, srdjan wrote: > Seems too small as initial size. I don't want to wast space for programs that don't use type arguments. For HelloWorld, the table never grows beyond 4. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2715 runtime/vm/object.cc:2715: return NULL; On 2012/12/10 20:07:52, Ivan Posva wrote: > This seems very unconnected to the change at hand? I think it still makes sense, but I can put it into a separate CL if necessary. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2840 runtime/vm/object.cc:2840: // Last element of the array is the number of used elements. On 2012/12/10 21:19:37, srdjan wrote: > Pass isolate as first argument (as done in other places in this code). Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2842 runtime/vm/object.cc:2842: intptr_t new_table_size = table_size * 2; On 2012/12/10 21:19:37, srdjan wrote: > Can you check on dart2js, checked mode, how much the table grows. The growth > policy seems aggressive for large tables. The max table size in dart2js is 1024 with ~50% occupation. I don't think that this is too much. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2852 runtime/vm/object.cc:2852: intptr_t index = hash % new_table_size; On 2012/12/10 21:19:37, srdjan wrote: > new_table_size should be power of 2 for performance reasons. Maybe add an > assert? Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2872 runtime/vm/object.cc:2872: Isolate* isolate) { On 2012/12/10 21:19:37, srdjan wrote: > 'isolate' as first argument. Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2877 runtime/vm/object.cc:2877: dart::Smi& used = Smi::Handle(isolate); On 2012/12/10 21:19:37, srdjan wrote: > s/dart::Smi/Smi/ I do not think there is a conflicting Smi definition around. Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode2893 runtime/vm/object.cc:2893: Isolate* isolate) { On 2012/12/10 21:19:37, srdjan wrote: > ditto Done. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.cc#newcode1... runtime/vm/object.cc:10075: const char* characters = ToCString(); On 2012/12/11 01:37:15, regis wrote: > On 2012/12/10 20:07:52, Ivan Posva wrote: > > This seems very fragile to me and as you are not caching this anywhere making > > this rather expensive. Consider an alternative hash function which relies on > the > > participating class ids? Regis? > > Yes, for efficiency, the hash of a TypeArguments vector should depend on the > hash of its constituent element types. Each element type is either a Type or a > TypeParameter. A Type has a type class (class id is an integer) and a type > argument vector. A type parameter refers to a class (integer class id) and has > an index (integer); its name is not relevant here. So the hash can be calculated > from integers only. This should be much more efficient than computing the name. > > Now, you need to pay attention to malformed types, but we do not canonicalize > them, if I remember correctly. Done. Added ::Hash() for Type, TypeParameter and AbstractTypeArguments based on class-ids. Malformed type are not equal to any other type, so their hash code can be anything. I doubt that they are important for performance though. https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/1/runtime/vm/object.h#newcode989 runtime/vm/object.h:989: intptr_t Hash() const; On 2012/12/11 01:37:15, regis wrote: > You should add a Hash() to AbstractType as well (and to Type and TypeParameter), > since the hash of this vector depends on the hash of its type elements. Done.
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:2874: intptr_t index = static_cast<uword>(hash) % new_table_size; Since you know you have a power of two. Please do a & mask. You can precalculate the mask before entering the loop. This should avoid two things: Having to static_cast to uword and a lengthy division. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:2919: intptr_t index = static_cast<uword>(hash) % table_size; ditto: power of two assertion, & mask, uword cast. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h#newcod... runtime/vm/object.h:922: virtual uword Hash() const; Hash is not an address, please use intptr_t. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h#newcod... runtime/vm/object.h:3254: virtual uword Hash() const; ditto https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h#newcod... runtime/vm/object.h:3368: virtual uword Hash() const; ditto https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h#newcod... runtime/vm/object.h:3468: virtual uword Hash() const; ditto
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.h#newcod... runtime/vm/object.h:922: virtual uword Hash() const; On 2012/12/11 14:54:52, Ivan Posva wrote: > Hash is not an address, please use intptr_t. I think uword is appropiate also for things like sizes, array length, table indices. Since intptr_t can be negative, I need a explicit cast every time I use the hash for indexing. I think intptr_t is less safe because of the required cast or relying on the hash computation to never produce a negative value. Otherwise, I can choose to make the hash unsigned by type and no static_cast etc. is needed.
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:2519: result += AbstractType::Handle(TypeAt(i)).Hash(); You should move the Handle out of the loop, not to create a Handle per iteration. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9092: uword Type::Hash() const { ASSERT(IsFinalized()); https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9095: result += Class::Handle(type_class()).id(); A malformed type may not have a type_class. You will assert fault if you try to get to it. You should return immediately if it is malformed, since it will not get canonicalized anyway. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9242: uword TypeParameter::Hash() const { ASSERT(IsFinalized()); https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9246: result ^= String::Handle(name()).Hash(); You do not need the name. It is only used for error reporting and debugging purpose after parsing. It is redundant with the index.
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:2519: result += AbstractType::Handle(TypeAt(i)).Hash(); On 2012/12/11 19:04:04, regis wrote: > You should move the Handle out of the loop, not to create a Handle per > iteration. Thanks. Done. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9092: uword Type::Hash() const { On 2012/12/11 19:04:04, regis wrote: > ASSERT(IsFinalized()); Done. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9095: result += Class::Handle(type_class()).id(); On 2012/12/11 19:04:04, regis wrote: > A malformed type may not have a type_class. You will assert fault if you try to > get to it. You should return immediately if it is malformed, since it will not > get canonicalized anyway. Done. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9242: uword TypeParameter::Hash() const { On 2012/12/11 19:04:04, regis wrote: > ASSERT(IsFinalized()); Done. https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9246: result ^= String::Handle(name()).Hash(); On 2012/12/11 19:04:04, regis wrote: > You do not need the name. It is only used for error reporting and debugging > purpose after parsing. It is redundant with the index. Ok, then I'd like to remove from TypeParameter::Equals as well. For Hash() I used the attributes that are tested in Equals. If it's only used for debugging/printing and does not matter for equality, then it can be safely removed in both places.
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9246: result ^= String::Handle(name()).Hash(); On 2012/12/12 14:58:40, Florian Schneider wrote: > On 2012/12/11 19:04:04, regis wrote: > > You do not need the name. It is only used for error reporting and debugging > > purpose after parsing. It is redundant with the index. > > Ok, then I'd like to remove from TypeParameter::Equals as well. For Hash() I > used the attributes that are tested in Equals. If it's only used for > debugging/printing and does not matter for equality, then it can be safely > removed in both places. Yes, it is safe, because Equals returns false if one TypeParameter is finalized while the other is not. It is therefore OK to compare the indices (adjusted or not) and ignore the names in Equals.
Hopefully last round of comments. -Ivan https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2738: return NULL; Please leave this as it was. All other abstract classes keep returning the name. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2862: static void GrowCanonicalTypeArguments(Isolate* isolate, const Array& table) { Do not pass Isolate as a parameter unless it is a very frequently called function as it pollutes the API. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2893: static void InsertIntoCanonicalTypeArguments(Isolate* isolate, ditto https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2916: Isolate* isolate, ditto https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2945: TypeArguments& self = TypeArguments::Handle(isolate, this->raw()); Why do you need to allocate a new handle here? this is a handle already. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2954: result ^= this->raw(); if (this->IsNew()) { result ^= Object::Clone(...); } else { result ^= this->raw(); } ASSERT(...); InsertIntoCanonicalTypeArguments(...); https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:9209: return true; Thanks for simplifying this. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.h#newco... runtime/vm/object.h:922: virtual uword Hash() const; intptr_t
https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/5001/runtime/vm/object.cc#newco... runtime/vm/object.cc:9246: result ^= String::Handle(name()).Hash(); On 2012/12/12 18:36:48, regis wrote: > On 2012/12/12 14:58:40, Florian Schneider wrote: > > On 2012/12/11 19:04:04, regis wrote: > > > You do not need the name. It is only used for error reporting and debugging > > > purpose after parsing. It is redundant with the index. > > > > Ok, then I'd like to remove from TypeParameter::Equals as well. For Hash() I > > used the attributes that are tested in Equals. If it's only used for > > debugging/printing and does not matter for equality, then it can be safely > > removed in both places. > > Yes, it is safe, because Equals returns false if one TypeParameter is finalized > while the other is not. It is therefore OK to compare the indices (adjusted or > not) and ignore the names in Equals. Done. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2738: return NULL; On 2012/12/12 21:25:10, Ivan Posva wrote: > Please leave this as it was. All other abstract classes keep returning the name. Fine. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2916: Isolate* isolate, On 2012/12/12 21:25:10, Ivan Posva wrote: > ditto This is frequently called in checked mode. The two other functions here are also local helpers for TypeArguments::Canonicalize, so I'm not worried about pollution here. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2945: TypeArguments& self = TypeArguments::Handle(isolate, this->raw()); On 2012/12/12 21:25:10, Ivan Posva wrote: > Why do you need to allocate a new handle here? this is a handle already. Done. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.cc#newc... runtime/vm/object.cc:2954: result ^= this->raw(); On 2012/12/12 21:25:10, Ivan Posva wrote: > if (this->IsNew()) { > result ^= Object::Clone(...); > } else { > result ^= this->raw(); > } > ASSERT(...); > InsertIntoCanonicalTypeArguments(...); Done. https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.h File runtime/vm/object.h (right): https://codereview.chromium.org/11474056/diff/10001/runtime/vm/object.h#newco... runtime/vm/object.h:922: virtual uword Hash() const; On 2012/12/12 21:25:10, Ivan Posva wrote: > intptr_t Done.
LGTM -ip
Message was sent while issue was closed.
On 2012/12/13 14:59:11, Ivan Posva wrote: > LGTM -ip Thanks! Landing. |
