Reduce (debug-only) VerifyMaps from O(n^2) to O(n).

runtime/vm/isolate_reload.cc

 // Copyright (c) 2016, 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/isolate_reload.h"
 
 #include "vm/become.h"
 #include "vm/code_generator.h"
 #include "vm/compiler.h"
 #include "vm/dart_api_impl.h"
@@ skipping 197 matching lines @@
 IsolateReloadContext::~IsolateReloadContext() {
 }
 
 
 void IsolateReloadContext::ReportError(const Error& error) {
   has_error_ = true;
   error_ = error.raw();
   if (FLAG_trace_reload) {
     THR_Print("ISO-RELOAD: Error: %s\n", error.ToErrorCString());
   }
-  ServiceEvent service_event(Isolate::Current(), ServiceEvent::kIsolateReload);
+  ServiceEvent service_event(I, ServiceEvent::kIsolateReload);
   service_event.set_reload_error(&error);
   Service::HandleEvent(&service_event);
 }
 
 
 void IsolateReloadContext::ReportError(const String& error_msg) {
   ReportError(LanguageError::Handle(LanguageError::New(error_msg)));
 }
 
 
 void IsolateReloadContext::ReportSuccess() {
-  ServiceEvent service_event(Isolate::Current(), ServiceEvent::kIsolateReload);
+  ServiceEvent service_event(I, ServiceEvent::kIsolateReload);
   Service::HandleEvent(&service_event);
 }
 
 
 void IsolateReloadContext::StartReload() {
   TIMELINE_SCOPE(Reload);
   Thread* thread = Thread::Current();
 
   // Grab root library before calling CheckpointBeforeReload.
   const Library& root_lib = Library::Handle(object_store()->root_library());
@@ skipping 30 matching lines @@
   }
   if (result.IsError()) {
     ReportError(Error::Cast(result));
   }
 }
 
 
 void IsolateReloadContext::RegisterClass(const Class& new_cls) {
   const Class& old_cls = Class::Handle(OldClassOrNull(new_cls));
   if (old_cls.IsNull()) {
-    Isolate::Current()->class_table()->Register(new_cls);
+    I->class_table()->Register(new_cls);
 
     if (FLAG_identity_reload) {
       TIR_Print("Could not find replacement class for %s\n",
                 new_cls.ToCString());
       UNREACHABLE();
     }
 
     // New class maps to itself.
     AddClassMapping(new_cls, new_cls);
     return;
@@ skipping 298 matching lines @@
   GrowableObjectArray& saved_libs = GrowableObjectArray::Handle(
       Z, saved_libraries());
   if (!saved_libs.IsNull()) {
     for (intptr_t i = 0; i < saved_libs.Length(); i++) {
       lib = Library::RawCast(saved_libs.At(i));
       // Restore indexes that were modified in CheckpointLibraries.
       lib.set_index(i);
     }
 
     // Reset the registered libraries to the filtered array.
-    Library::RegisterLibraries(Thread::Current(), saved_libs);
+    Library::RegisterLibraries(thread, saved_libs);
   }
 
   Library& saved_root_lib = Library::Handle(Z, saved_root_library());
   if (!saved_root_lib.IsNull()) {
     object_store()->set_root_library(saved_root_lib);
   }
 
   set_saved_root_library(Library::Handle());
   set_saved_libraries(GrowableObjectArray::Handle());
 }
 
 
 void IsolateReloadContext::Rollback() {
   I->object_store()->set_compile_time_constants(
       Array::Handle(compile_time_constants_));
   RollbackClasses();
   RollbackLibraries();
 }
 
 
 #ifdef DEBUG
 void IsolateReloadContext::VerifyMaps() {
   TIMELINE_SCOPE(VerifyMaps);
   Class& cls = Class::Handle();
   Class& new_cls = Class::Handle();
   Class& cls2 = Class::Handle();
-  Class& new_cls2 = Class::Handle();
 
   // Verify that two old classes aren't both mapped to the same new
-  // class.  This could happen is the IsSameClass function is broken.
+  // class. This could happen is the IsSameClass function is broken.
   UnorderedHashMap<ClassMapTraits> class_map(class_map_storage_);
+  UnorderedHashMap<ClassMapTraits> reverse_class_map(
+      HashTables::New<UnorderedHashMap<ClassMapTraits> >(
+         class_map.NumOccupied()));
   {
     UnorderedHashMap<ClassMapTraits>::Iterator it(&class_map);
     while (it.MoveNext()) {
       const intptr_t entry = it.Current();
       new_cls = Class::RawCast(class_map.GetKey(entry));
       cls = Class::RawCast(class_map.GetPayload(entry, 0));
-      if (new_cls.raw() != cls.raw()) {
-        UnorderedHashMap<ClassMapTraits>::Iterator it2(&class_map);
-        while (it2.MoveNext()) {
-          new_cls2 = Class::RawCast(class_map.GetKey(entry));
-          if (new_cls.raw() == new_cls2.raw()) {
-            cls2 = Class::RawCast(class_map.GetPayload(entry, 0));
-            if (cls.raw() != cls2.raw()) {
-              OS::PrintErr(
-                  "Classes '%s' and '%s' are distinct classes but both map to "
-                  "class '%s'\n",
-                  cls.ToCString(), cls2.ToCString(), new_cls.ToCString());
-              UNREACHABLE();
-            }
-          }
-        }
+      cls2 ^= reverse_class_map.GetOrNull(new_cls);
+      if (!cls2.IsNull()) {
+        OS::PrintErr("Classes '%s' and '%s' are distinct classes but both map "
+                     " to class '%s'\n",
+                     cls.ToCString(), cls2.ToCString(), new_cls.ToCString());
+        UNREACHABLE();
       }
+      bool update = reverse_class_map.UpdateOrInsert(cls, new_cls);
+      ASSERT(!update);
     }
   }
   class_map.Release();
+  reverse_class_map.Release();
 }
 #endif
 
 
 void IsolateReloadContext::Commit() {
   TIMELINE_SCOPE(Commit);
   TIR_Print("---- COMMITTING REVERSE MAP\n");
 
 #ifdef DEBUG
   VerifyMaps();
@@ skipping 492 matching lines @@
         ASSERT(!super_cls.IsNull());
         super_cls.AddDirectSubclass(cls);
       }
     }
   }
 }
 
 #endif  // !PRODUCT
 
 }  // namespace dart