Improve performance of Library::LookupLibrary(const String&).

Improve performance of Library::LookupLibrary(const String&).

Make sure that String::Equals(const String&) checks the hash codes
on  the strings if they are available. Before this change, only
String::Equals(const Instance&) would consult the hash codes.

R=iposva@google.com
BUG=

Committed: https://github.com/dart-lang/sdk/commit/42dfb86459d2e7d7b07f5bb1d85a8793b9deff3c

[Ivan Posva, 2016-02-05 04:53:54]

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (left):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#oldcod...
runtime/vm/object.cc:19592: if (!other.IsString() || other.IsNull()) {
This removal is not correct. String handles can still contain a null object.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10166: const Library& result =
Library::Handle(Library::New());
You might want to ensure here that url has a hash associated with it.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10282: url.Hash();
In the past we have had a negative performance impact with aggressively hashing
because to calculate the hash you need to walk through the whole string. While
often enough you will fail early in a string comparison. By all means if the
string already has a hash it is a good early indicator.

Not sure whether strings that make up library URLs behave differently. Most of
them will have a similar prefix, such as "package:", "file:", "html:" or
"dart:". This could mean that the overhead of hashing pays of in this particular
instance.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10289: ASSERT(url.HasHash() && lib_url.HasHash());
How do you guarantee that lib_url has a hash code associated with it? If this
assertion is not triggering then probably because we use the string to first
lookup whether this library is already loaded as part of the loading code,
although that is not necessarily true for all cases.

[kasperl, 2016-02-05 05:09:26]

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (left):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#oldcod...
runtime/vm/object.cc:19592: if (!other.IsString() || other.IsNull()) {
On 2016/02/05 04:53:54, Ivan Posva wrote:
> This removal is not correct. String handles can still contain a null object.

If other.IsString() is true then it can flow through String::Cast, right? In
that case, the Equals(const String&) takes care of the null check. No need to do
it twice.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10166: const Library& result =
Library::Handle(Library::New());
On 2016/02/05 04:53:54, Ivan Posva wrote:
> You might want to ensure here that url has a hash associated with it.

I do that when the library enters the library array (in Library::Register).

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10196: result.AllocatePrivateKey();
The allocation of the private key (which is also linear in the size of the
library array) forces the library url string to get an associated hash code.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10282: url.Hash();
On 2016/02/05 04:53:54, Ivan Posva wrote:
> In the past we have had a negative performance impact with aggressively
hashing
> because to calculate the hash you need to walk through the whole string. While
> often enough you will fail early in a string comparison. By all means if the
> string already has a hash it is a good early indicator.
> 
> Not sure whether strings that make up library URLs behave differently. Most of
> them will have a similar prefix, such as "package:", "file:", "html:" or
> "dart:". This could mean that the overhead of hashing pays of in this
particular
> instance.

The url string will be compared using Equals to a ton of already hashed library
url strings. Once we go to a hash table based implementation of this, we will
also need to hash the url string.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10289: ASSERT(url.HasHash() && lib_url.HasHash());
On 2016/02/05 04:53:54, Ivan Posva wrote:
> How do you guarantee that lib_url has a hash code associated with it? If this
> assertion is not triggering then probably because we use the string to first
> lookup whether this library is already loaded as part of the loading code,
> although that is not necessarily true for all cases.

It's hashed as part of NewLibraryHelper and I check it both here and when the
library is "registered" in the library array.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.h#newcode...
runtime/vm/object.h:8356: if (str.IsNull()) {
This takes care of the null check I removed from String::Equals(const
Instance&).

[kasperl, 2016-02-05 05:14:18]

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10338: intptr_t key_value = url.Hash() & kIntptrMax;
Here's the url.Hash() calll. I wonder why we cannot just use a library's array
index as its private key? Seems so simple that there must be a good reason why
you didn't pick that.

[Ivan Posva, 2016-02-05 05:57:42]

LGTM -ip

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (left):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#oldcod...
runtime/vm/object.cc:19592: if (!other.IsString() || other.IsNull()) {
On 2016/02/05 05:09:25, kasperl wrote:
> On 2016/02/05 04:53:54, Ivan Posva wrote:
> > This removal is not correct. String handles can still contain a null object.
> 
> If other.IsString() is true then it can flow through String::Cast, right? In
> that case, the Equals(const String&) takes care of the null check. No need to
do
> it twice.

Generally you are not supposed to XYZ:Cast() a null object, but in this case it
is fine because by calling obj.IsXYZ() you verified that the C++ vtable is
properly setup already.

Maybe we should update the comment in object.h to clarify the restriction. It is
OK to use the Cast() function always if guarded with a corresponding Is check.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10289: ASSERT(url.HasHash() && lib_url.HasHash());
On 2016/02/05 05:09:25, kasperl wrote:
> On 2016/02/05 04:53:54, Ivan Posva wrote:
> > How do you guarantee that lib_url has a hash code associated with it? If
this
> > assertion is not triggering then probably because we use the string to first
> > lookup whether this library is already loaded as part of the loading code,
> > although that is not necessarily true for all cases.
> 
> It's hashed as part of NewLibraryHelper and I check it both here and when the
> library is "registered" in the library array.

I was wondering about how the hash was being enforced, since I saw the assertion
here and in Register(). I missed the private key generation.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10338: intptr_t key_value = url.Hash() & kIntptrMax;
On 2016/02/05 05:14:18, kasperl wrote:
> Here's the url.Hash() calll. I wonder why we cannot just use a library's array
> index as its private key? Seems so simple that there must be a good reason why
> you didn't pick that.

Side note: We have discussed making the private key less predictable by using
the random number generator. On the other hand library privacy is not a security
mechanism.

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/1666113002/diff/1/runtime/vm/object.h#newcode...
runtime/vm/object.h:8356: if (str.IsNull()) {
On 2016/02/05 05:09:26, kasperl wrote:
> This takes care of the null check I removed from String::Equals(const
> Instance&).

Acknowledged.

[kasperl, 2016-02-05 07:57:32]

Thanks for the review!

[kasperl, 2016-02-05 08:55:07]

Description was changed from

==========
Improve performance of Library::LookupLibrary(const String&).

Make sure that String::Equals(const String&) checks the hash codes
on  the strings if they are available. Before this change, only
String::Equals(const Instance&) would consult the hash codes.

R=iposva@google.com
BUG=
==========

to

==========
Improve performance of Library::LookupLibrary(const String&).

Make sure that String::Equals(const String&) checks the hash codes
on  the strings if they are available. Before this change, only
String::Equals(const Instance&) would consult the hash codes.

R=iposva@google.com
BUG=

Committed:
https://github.com/dart-lang/sdk/commit/42dfb86459d2e7d7b07f5bb1d85a8793b9deff3c
==========

[kasperl, 2016-02-05 08:55:09]

Committed patchset #1 (id:1) manually as
42dfb86459d2e7d7b07f5bb1d85a8793b9deff3c (presubmit successful).