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

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 10145 matching lines @@
   ASSERT(Object::library_class() != Class::null());
   RawObject* raw = Object::Allocate(Library::kClassId,
                                     Library::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawLibrary*>(raw);
 }
 
 
 RawLibrary* Library::NewLibraryHelper(const String& url,
                                       bool import_core_lib) {
   const Library& result = Library::Handle(Library::New());

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

You might want to ensure here that url has a hash associated with it.

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

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

   result.StorePointer(&result.raw_ptr()->name_, Symbols::Empty().raw());
   result.StorePointer(&result.raw_ptr()->url_, url.raw());
   result.StorePointer(&result.raw_ptr()->resolved_names_,
                       Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->dictionary_,
                       Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->metadata_,
                       GrowableObjectArray::New(4, Heap::kOld));
   result.StorePointer(&result.raw_ptr()->toplevel_class_, Class::null());
   result.StorePointer(&result.raw_ptr()->patch_classes_,
                       GrowableObjectArray::New(Object::empty_array(),
                                                Heap::kOld));
   result.StorePointer(&result.raw_ptr()->imports_, Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->exports_, Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->loaded_scripts_, Array::null());
   result.StorePointer(&result.raw_ptr()->load_error_, Instance::null());
   result.set_native_entry_resolver(NULL);
   result.set_native_entry_symbol_resolver(NULL);
   result.set_is_in_fullsnapshot(false);
   result.StoreNonPointer(&result.raw_ptr()->corelib_imported_, true);
   result.set_debuggable(false);
   result.set_is_dart_scheme(url.StartsWith(Symbols::DartScheme()));
   result.StoreNonPointer(&result.raw_ptr()->load_state_,
                          RawLibrary::kAllocated);
   result.StoreNonPointer(&result.raw_ptr()->index_, -1);
   const intptr_t kInitialNameCacheSize = 64;
   result.InitResolvedNamesCache(kInitialNameCacheSize);
   result.InitClassDictionary();
   result.InitImportList();
   result.AllocatePrivateKey();

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

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.

   if (import_core_lib) {
     const Library& core_lib = Library::Handle(Library::CoreLibrary());
     ASSERT(!core_lib.IsNull());
     const Namespace& ns = Namespace::Handle(
         Namespace::New(core_lib, Object::null_array(), Object::null_array()));
     result.AddImport(ns);
   }
   return result.raw();
 }
 
@@ skipping 62 matching lines @@
 
 // Returns library with given url in current isolate, or NULL.
 RawLibrary* Library::LookupLibrary(const String &url) {
   Thread* thread = Thread::Current();
   Zone* zone = thread->zone();
   Isolate* isolate = thread->isolate();
   Library& lib = Library::Handle(zone, Library::null());
   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();
     }
   }
   return Library::null();
 }
 
 
 RawError* Library::Patch(const Script& script) const {
   ASSERT(script.kind() == RawScript::kPatchTag);
@@ skipping 28 matching lines @@
     if (lib_key == key) {
       return true;
     }
   }
   return false;
 }
 
 
 void Library::AllocatePrivateKey() const {
   const String& url = String::Handle(this->url());
   intptr_t key_value = url.Hash() & kIntptrMax;

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

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]

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.

   while ((key_value == 0) || Library::IsKeyUsed(key_value)) {
     key_value = (key_value + 1) & kIntptrMax;
   }
   ASSERT(key_value > 0);
   char private_key[32];
   OS::SNPrint(private_key, sizeof(private_key),
               "%c%" Pd "", kPrivateKeySeparator, key_value);
   StorePointer(&raw_ptr()->private_key_, String::New(private_key, Heap::kOld));
 }
 
@@ skipping 37 matching lines @@
     Library& lib = Library::Handle();
     lib ^= libs.At(index);
     return lib.raw();
   }
   return Library::null();
 }
 
 
 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());
   ASSERT(!libs.IsNull());
   set_index(libs.Length());
   libs.Add(*this);
 }
 
 
 RawLibrary* Library::AsyncLibrary() {
@@ skipping 9184 matching lines @@
   return ExternalTwoByteString::GetPeer(*this);
 }
 
 
 bool String::Equals(const Instance& other) const {
   if (this->raw() == other.raw()) {
     // Both handles point to the same raw instance.
     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, 0, other_string.Length());
+  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.
+  }
+
+  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;
+}
+
+
 bool String::Equals(const char* cstr) const {
   ASSERT(cstr != NULL);
   CodePointIterator it(*this);
   intptr_t len = strlen(cstr);
   while (it.Next()) {
     if (*cstr == '\0') {
       // Lengths don't match.
       return false;
     }
     int32_t ch;
@@ skipping 3295 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart