Speedup function profile by using a hash table instead of a linear scan

runtime/vm/profiler_service.cc

 // Copyright (c) 2015, 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/profiler_service.h"
 
 #include "vm/growable_array.h"
+#include "vm/hash_map.h"
 #include "vm/log.h"
 #include "vm/native_symbol.h"
 #include "vm/object.h"
 #include "vm/os.h"
 #include "vm/profiler.h"
 #include "vm/reusable_handles.h"
 #include "vm/scope_timer.h"
 
 namespace dart {
 
 DECLARE_FLAG(int, max_profile_depth);
 DECLARE_FLAG(int, profile_period);
 
 DEFINE_FLAG(bool, trace_profiler, false, "Trace profiler.");

[Ivan Posva, 2016/03/23 15:14:39]

Please move these flags into the common flags file and set them appropriately.
For example verbose only in debug builds.

[Cutch, 2016/03/23 19:34:21]

Done.

+DEFINE_FLAG(bool, trace_profiler_verbose, false, "Verbose trace profiler.");
 
 #ifndef PRODUCT
 
 class DeoptimizedCodeSet : public ZoneAllocated {
  public:
   explicit DeoptimizedCodeSet(Isolate* isolate)
       : previous_(
             GrowableObjectArray::ZoneHandle(isolate->deoptimized_code_array())),
         current_(GrowableObjectArray::ZoneHandle(
             previous_.IsNull() ? GrowableObjectArray::null() :
@@ skipping 122 matching lines @@
   TickSourcePosition(token_position, false);
 }
 
 
 void ProfileFunction::TickSourcePosition(TokenPosition token_position,
                                          bool exclusive) {
   intptr_t i = 0;
   for (; i < source_position_ticks_.length(); i++) {
     ProfileFunctionSourcePosition& position = source_position_ticks_[i];
     if (position.token_pos().value() == token_position.value()) {
-      if (FLAG_trace_profiler) {
+      if (FLAG_trace_profiler_verbose) {
         OS::Print("Ticking source position %s %s\n",
                   exclusive ? "exclusive" : "inclusive",
                   token_position.ToCString());
       }
       // Found existing position, tick it.
       position.Tick(exclusive);
       return;
     }
     if (position.token_pos().value() > token_position.value()) {
       break;
     }
   }
 
   // Add new one, sorted by token position value.
   ProfileFunctionSourcePosition pfsp(token_position);
-  if (FLAG_trace_profiler) {
+  if (FLAG_trace_profiler_verbose) {
     OS::Print("Ticking source position %s %s\n",
               exclusive ? "exclusive" : "inclusive",
               token_position.ToCString());
   }
   pfsp.Tick(exclusive);
 
   if (i < source_position_ticks_.length()) {
     source_position_ticks_.InsertAt(i, pfsp);
   } else {
     source_position_ticks_.Add(pfsp);
@@ skipping 317 matching lines @@
       ticks.AddValueF("%" Pd "", entry.inclusive_ticks());
     }
   }
 }
 
 
 class ProfileFunctionTable : public ZoneAllocated {
  public:
   ProfileFunctionTable()
       : null_function_(Function::ZoneHandle()),
-        table_(8),
-        unknown_function_(NULL) {
+        unknown_function_(NULL),
+        table_(8) {
     unknown_function_ = Add(ProfileFunction::kUnknownFunction,
                             "<unknown Dart function>");
   }
 
   ProfileFunction* LookupOrAdd(const Function& function) {
     ASSERT(!function.IsNull());
     ProfileFunction* profile_function = Lookup(function);
     if (profile_function != NULL) {
       return profile_function;
     }
     return Add(function);
   }
 
-  intptr_t LookupIndex(const Function& function) {
+  ProfileFunction* Lookup(const Function& function) {
     ASSERT(!function.IsNull());
-    for (intptr_t i = 0; i < table_.length(); i++) {
-      ProfileFunction* profile_function = table_[i];
-      if (profile_function->function() == function.raw()) {
-        return i;
-      }
-    }
-    return -1;
+    return function_hash_.Lookup(&function);
   }
 
   ProfileFunction* GetUnknown() {
     ASSERT(unknown_function_ != NULL);
     return unknown_function_;
   }
 
   // No protection against being called more than once for the same tag_id.
   ProfileFunction* AddTag(uword tag_id, const char* name) {
     // TODO(johnmccutchan): Canonicalize ProfileFunctions for tags.
@@ skipping 36 matching lines @@
   }
 
   ProfileFunction* Add(const Function& function) {
     ASSERT(Lookup(function) == NULL);
     ProfileFunction* profile_function =
         new ProfileFunction(ProfileFunction::kDartFunction,
                             NULL,
                             function,
                             table_.length());
     table_.Add(profile_function);
+    function_hash_.Insert(profile_function);
     return profile_function;
   }
 
-  ProfileFunction* Lookup(const Function& function) {
-    ASSERT(!function.IsNull());
-    intptr_t index = LookupIndex(function);
-    if (index == -1) {
-      return NULL;
+  // Needed for DirectChainedHashMap.
+  struct ProfileFunctionTableTrait {
+    typedef ProfileFunction* Value;
+    typedef const Function* Key;
+    typedef ProfileFunction* Pair;
+
+    static Key KeyOf(Pair kv) {
+      return kv->key();

[Ivan Posva, 2016/03/23 15:14:39]

Personally I find these typedefs confusing, as well as the addition of the key()
accessor to ProfileFunction. Can we rename from key() to function()?

[Cutch, 2016/03/23 19:34:21]

I've renamed key() to function() but the typedefs are required by
DirectChainedHashMap.

     }
-    return table_[index];
-  }
+
+    static Value ValueOf(Pair kv) {
+      return kv;
+    }
+
+    static inline intptr_t Hashcode(Key key) {
+      return key->Hash();
+    }
+
+    static inline bool IsKeyEqual(Pair kv, Key key) {
+      return kv->key()->raw() == key->raw();
+    }
+  };
 
   const Function& null_function_;
+  ProfileFunction* unknown_function_;
   ZoneGrowableArray<ProfileFunction*> table_;
-  ProfileFunction* unknown_function_;
+  DirectChainedHashMap<ProfileFunctionTableTrait> function_hash_;
 };
 
 
 ProfileFunction* ProfileCode::SetFunctionAndName(ProfileFunctionTable* table) {
   ASSERT(function_ == NULL);
 
   ProfileFunction* function = NULL;
   if ((kind() == kReusedCode) || (kind() == kCollectedCode)) {
     if (name() == NULL) {
       // Lazily set generated name.
@@ skipping 868 matching lines @@
                                  &inlined_functions,
                                  &inlined_token_positions);
       token_position = code.GetTokenPositionAt(offset);
       if (inlined_functions.length() > 0) {
         // The inlined token position table does not include the token position
         // of the final call. Insert it at the beginning because the table.
         // is reversed.
         inlined_token_positions.InsertAt(0, token_position);
       }
       ASSERT(inlined_functions.length() <= inlined_token_positions.length());
-      if (FLAG_trace_profiler) {
+      if (FLAG_trace_profiler_verbose) {
         for (intptr_t i = 0; i < inlined_functions.length(); i++) {
           const String& name =
               String::Handle(inlined_functions[i]->QualifiedScrubbedName());
           THR_Print("InlinedFunction[%" Pd "] = {%s, %s}\n",
                     i,
                     name.ToCString(),
                     inlined_token_positions[i].ToCString());
         }
       }
     }
@@ skipping 97 matching lines @@
   }
 
   ProfileFunctionTrieNode* ProcessFunction(ProfileFunctionTrieNode* current,
                                            intptr_t sample_index,
                                            ProcessedSample* sample,
                                            intptr_t frame_index,
                                            ProfileFunction* function,
                                            TokenPosition token_position,
                                            intptr_t code_index) {
     if (tick_functions_) {
-      if (FLAG_trace_profiler) {
+      if (FLAG_trace_profiler_verbose) {
         THR_Print("S[%" Pd "]F[%" Pd "] %s %s 0x%" Px "\n",
                   sample_index,
                   frame_index,
                   function->Name(),
                   token_position.ToCString(),
                   sample->At(frame_index));
       }
       function->Tick(IsExecutingFrame(sample, frame_index),
                      sample_index,
                      token_position);
@@ skipping 622 matching lines @@
       ProfileTrieNode* trie = sample->timeline_trie();
       ASSERT(trie->frame_id() != -1);
       event.AddPropertyF("sf", "%" Pd "-%" Pd,
                          isolate_id, trie->frame_id());
     }
   }
 }
 
 
 ProfileFunction* Profile::FindFunction(const Function& function) {
-  const intptr_t index = functions_->LookupIndex(function);
-  if (index < 0) {
-    return NULL;
-  }
-  return functions_->At(index);
+  return functions_->Lookup(function);
 }
 
 
 void Profile::PrintProfileJSON(JSONStream* stream) {
   ScopeTimer sw("Profile::PrintProfileJSON", FLAG_trace_profiler);
   JSONObject obj(stream);
   obj.AddProperty("type", "_CpuProfile");
   PrintHeaderJSON(&obj);
   {
     JSONArray codes(&obj, "codes");
@@ skipping 324 matching lines @@
   // Disable thread interrupts while processing the buffer.
   DisableThreadInterruptsScope dtis(thread);
 
   ClearProfileVisitor clear_profile(isolate);
   sample_buffer->VisitSamples(&clear_profile);
 }
 
 #endif  // !PRODUCT
 
 }  // namespace dart