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

runtime/vm/object.cc

Index: runtime/vm/object.cc
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index f5d5253bcc584f2a42acce3e5bc6e73fe4214da2..ac3fb9aacfdb3f9e33cfd159d6bf766ff51d3242 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -10276,9 +10276,17 @@ RawLibrary* Library::LookupLibrary(const String &url) {
   String& lib_url = String::Handle(zone, String::null());
   GrowableObjectArray& libs = GrowableObjectArray::Handle(
       zone, isolate->object_store()->libraries());
-  for (int i = 0; i < libs.Length(); i++) {
+
+  // Make sure the URL string has an associated hash code
+  // to speed up the repeated equality checks.
+  url.Hash();

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

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.

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

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.

+
+  intptr_t len = libs.Length();
+  for (intptr_t i = 0; i < len; i++) {
     lib ^= libs.At(i);
     lib_url ^= lib.url();
+
+    ASSERT(url.HasHash() && lib_url.HasHash());

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

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:25]

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

[Ivan Posva, 2016/02/05 05:57:41]

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.

     if (lib_url.Equals(url)) {
       return lib.raw();
     }
@@ -10385,6 +10393,7 @@ RawLibrary* Library::GetLibrary(intptr_t index) {
 
 void Library::Register() const {
   ASSERT(Library::LookupLibrary(String::Handle(url())) == Library::null());
+  ASSERT(String::Handle(url()).HasHash());
   ObjectStore* object_store = Isolate::Current()->object_store();
   GrowableObjectArray& libs =
       GrowableObjectArray::Handle(object_store->libraries());
@@ -19589,16 +19598,36 @@ bool String::Equals(const Instance& other) const {
     return true;
   }
 
-  if (!other.IsString() || other.IsNull()) {

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

This removal is not correct. String handles can still contain a null object.

[kasperl, 2016/02/05 05:09:25]

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.

[Ivan Posva, 2016/02/05 05:57:41]

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.

+  if (!other.IsString()) {
     return false;
   }
 
   const String& other_string = String::Cast(other);
-  if (this->HasHash() && other_string.HasHash() &&
-      (this->Hash() != other_string.Hash())) {
-    return false;  // Both sides have a hash code and it does not match.
+  return Equals(other_string);
+}
+
+
+bool String::Equals(const String& str,
+                    intptr_t begin_index,
+                    intptr_t len) const {
+  ASSERT(begin_index >= 0);
+  ASSERT((begin_index == 0) || (begin_index < str.Length()));
+  ASSERT(len >= 0);
+  ASSERT(len <= str.Length());
+  if (len != this->Length()) {
+    return false;  // Lengths don't match.
   }
-  return Equals(other_string, 0, other_string.Length());
+
+  Scanner::CharAtFunc this_char_at_func = this->CharAtFunc();
+  Scanner::CharAtFunc str_char_at_func = str.CharAtFunc();
+  for (intptr_t i = 0; i < len; i++) {
+    if (this_char_at_func(*this, i) !=
+        str_char_at_func(str, begin_index + i)) {
+      return false;
+    }
+  }
+
+  return true;
 }