Use a cache for inlining information (functions + token positions) to speed up function profile

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"
@@ skipping 1047 matching lines @@
     ProfileFunctionTrieNodeCode code_object(index);
     code_object.Tick();
     code_objects_.Add(code_object);
   }
 
  private:
   ZoneGrowableArray<ProfileFunctionTrieNodeCode> code_objects_;
 };
 
 
+class ProfileCodeInlinedFunctionsCache : public ValueObject {
+ public:
+  ProfileCodeInlinedFunctionsCache()
+      : cache_cursor_(0),
+        last_hit_(0) {
+    for (intptr_t i = 0; i < kCacheSize; i++) {
+      cache_[i].Reset();
+    }
+    cache_hit_ = 0;
+    cache_miss_ = 0;
+  }
+
+  ~ProfileCodeInlinedFunctionsCache() {
+    if (FLAG_trace_profiler) {
+      intptr_t total = cache_hit_ + cache_miss_;
+      OS::Print("LOOKUPS: %" Pd " HITS: %" Pd " MISSES: %" Pd "\n",
+                total,
+                cache_hit_,
+                cache_miss_);
+    }
+  }
+
+  void Get(uword pc,
+           const Code& code,
+           ProcessedSample* sample,
+           intptr_t frame_index,
+           // Outputs:
+           GrowableArray<Function*>** inlined_functions,
+           GrowableArray<TokenPosition>** inlined_token_positions,
+           TokenPosition* token_position) {
+    const intptr_t offset = OffsetForPC(pc, code, sample, frame_index);
+    if (FindInCache(pc,
+                    offset,
+                    inlined_functions,
+                    inlined_token_positions,
+                    token_position)) {
+      // Found in cache.
+      return;
+    }
+    Add(pc, code, sample, frame_index,
+        inlined_functions, inlined_token_positions, token_position);
+  }
+
+ private:
+  bool FindInCache(uword pc,
+                   intptr_t offset,
+                   GrowableArray<Function*>** inlined_functions,
+                   GrowableArray<TokenPosition>** inlined_token_positions,
+                   TokenPosition* token_position) {
+    // Simple linear scan.
+    for (intptr_t i = 0; i < kCacheSize; i++) {
+      intptr_t index = (last_hit_ + i) % kCacheSize;
+      if ((cache_[index].pc == pc) && (cache_[index].offset == offset)) {
+        // Hit.
+        if (cache_[index].inlined_functions.length() == 0) {
+          *inlined_functions = NULL;
+          *inlined_token_positions = NULL;
+        } else {
+          *inlined_functions = &cache_[index].inlined_functions;
+          *inlined_token_positions = &cache_[index].inlined_token_positions;
+        }
+        *token_position = cache_[index].token_position;
+        cache_hit_++;
+        last_hit_ = index;
+        return true;
+      }
+    }
+    cache_miss_++;
+    return false;
+  }
+
+  // Add to cache and fill in outputs.
+  void Add(uword pc,
+           const Code& code,
+           ProcessedSample* sample,
+           intptr_t frame_index,
+           // Outputs:
+           GrowableArray<Function*>** inlined_functions,
+           GrowableArray<TokenPosition>** inlined_token_positions,
+           TokenPosition* token_position) {
+    const intptr_t offset = OffsetForPC(pc, code, sample, frame_index);
+    CacheEntry* cache_entry = &cache_[NextFreeIndex()];
+    cache_entry->pc = pc;
+    cache_entry->offset = offset;
+    code.GetInlinedFunctionsAt(offset,
+                               &(cache_entry->inlined_functions),
+                               &(cache_entry->inlined_token_positions));
+    cache_entry->token_position = code.GetTokenPositionAt(offset);
+    *token_position = (cache_entry->token_position);
+    if (cache_entry->inlined_functions.length() == 0) {
+      *inlined_functions = NULL;
+      *inlined_token_positions = NULL;
+      return;
+    }
+    // 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.
+    cache_entry->inlined_token_positions.InsertAt(
+        0,
+        cache_entry->token_position);
+
+    // Write outputs.
+    *inlined_functions = &(cache_entry->inlined_functions);
+    *inlined_token_positions = &(cache_entry->inlined_token_positions);
+  }
+
+  intptr_t NextFreeIndex() {
+    cache_cursor_ = (cache_cursor_ + 1) % kCacheSize;
+    return cache_cursor_;
+  }
+
+  intptr_t OffsetForPC(uword pc,
+                       const Code& code,
+                       ProcessedSample* sample,
+                       intptr_t frame_index) {
+    intptr_t offset = pc - code.EntryPoint();
+    if (frame_index != 0) {
+      // The PC of frames below the top frame is a call's return address,
+      // which can belong to a different inlining interval than the call.
+      offset--;
+    } else if (sample->IsAllocationSample()) {
+      // Allocation samples skip the top frame, so the top frame's pc is
+      // also a call's return address.
+      offset--;
+    } else if (!sample->first_frame_executing()) {
+      // If the first frame wasn't executing code (i.e. we started to collect
+      // the stack trace at an exit frame), the top frame's pc is also a
+      // call's return address.
+      offset--;
+    }
+    return offset;
+  }
+
+  struct CacheEntry {
+    void Reset() {
+      pc = 0;
+      offset = 0;
+    }
+    uword pc;
+    intptr_t offset;
+    GrowableArray<Function*> inlined_functions;
+    GrowableArray<TokenPosition> inlined_token_positions;
+    TokenPosition token_position;
+  };
+
+  static const intptr_t kCacheSize = 128;
+  intptr_t cache_cursor_;
+  intptr_t last_hit_;
+  CacheEntry cache_[kCacheSize];
+  intptr_t cache_miss_;
+  intptr_t cache_hit_;
+};
+
+
 class ProfileBuilder : public ValueObject {
  public:
   enum ProfileInfoKind {
     kNone,
     kOptimized,
     kUnoptimized,
     kNative,
     kInlineStart,
     kInlineFinish,
     kNumProfileInfoKind,
@@ skipping 381 matching lines @@
       }
 
       // Truncated tag.
       if (sample->truncated()) {
         current = AppendTruncatedTag(current);
         InclusiveTickTruncatedTag();
       }
     }
   }
 
-  intptr_t OffsetForPC(uword pc,
-                       const Code& code,
-                       ProcessedSample* sample,
-                       intptr_t frame_index) {
-    intptr_t offset = pc - code.EntryPoint();
-    if (frame_index != 0) {
-      // The PC of frames below the top frame is a call's return address,
-      // which can belong to a different inlining interval than the call.
-      offset--;
-    } else if (sample->IsAllocationSample()) {
-      // Allocation samples skip the top frame, so the top frame's pc is
-      // also a call's return address.
-      offset--;
-    } else if (!sample->first_frame_executing()) {
-      // If the first frame wasn't executing code (i.e. we started to collect
-      // the stack trace at an exit frame), the top frame's pc is also a
-      // call's return address.
-      offset--;
-    }
-    return offset;
-  }
-
   ProfileFunctionTrieNode* ProcessFrame(
       ProfileFunctionTrieNode* current,
       intptr_t sample_index,
       ProcessedSample* sample,
       intptr_t frame_index) {
     const uword pc = sample->At(frame_index);
     ProfileCode* profile_code = GetProfileCode(pc,
                                                sample->timestamp());
     ProfileFunction* function = profile_code->function();
     ASSERT(function != NULL);
     const intptr_t code_index = profile_code->code_table_index();
     ASSERT(profile_code != NULL);
     const Code& code = Code::ZoneHandle(profile_code->code());
-    GrowableArray<Function*> inlined_functions;
-    GrowableArray<TokenPosition> inlined_token_positions;
+    GrowableArray<Function*>* inlined_functions = NULL;
+    GrowableArray<TokenPosition>* inlined_token_positions = NULL;
     TokenPosition token_position = TokenPosition::kNoSource;
     if (!code.IsNull()) {
-      const intptr_t offset = OffsetForPC(pc, code, sample, frame_index);
-      code.GetInlinedFunctionsAt(offset,
-                                 &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());
+      inlined_functions_cache_.Get(pc, code, sample, frame_index,
+                                   &inlined_functions,
+                                   &inlined_token_positions,
+                                   &token_position);
       if (FLAG_trace_profiler_verbose) {
-        for (intptr_t i = 0; i < inlined_functions.length(); i++) {
+        for (intptr_t i = 0; i < inlined_functions->length(); i++) {
           const String& name =
-              String::Handle(inlined_functions[i]->QualifiedScrubbedName());
+              String::Handle((*inlined_functions)[i]->QualifiedScrubbedName());
           THR_Print("InlinedFunction[%" Pd "] = {%s, %s}\n",
                     i,
                     name.ToCString(),
-                    inlined_token_positions[i].ToCString());
+                    (*inlined_token_positions)[i].ToCString());
         }
       }
     }
-    if (code.IsNull() || (inlined_functions.length() == 0)) {
+    if (code.IsNull() ||
+        (inlined_functions == NULL) ||
+        (inlined_functions->length() == 0)) {
       // No inlined functions.
       if (inclusive_tree_) {
         current = AppendKind(code, current);
       }
       current = ProcessFunction(current,
                                 sample_index,
                                 sample,
                                 frame_index,
                                 function,
                                 token_position,
                                 code_index);
       if (!inclusive_tree_) {
         current = AppendKind(code, current);
       }
       return current;
     }
 
     ASSERT(code.is_optimized());
 
     if (inclusive_tree_) {
-      for (intptr_t i = inlined_functions.length() - 1; i >= 0; i--) {
-        Function* inlined_function = inlined_functions[i];
+      for (intptr_t i = inlined_functions->length() - 1; i >= 0; i--) {
+        Function* inlined_function = (*inlined_functions)[i];
         ASSERT(inlined_function != NULL);
         ASSERT(!inlined_function->IsNull());
-        TokenPosition inlined_token_position = inlined_token_positions[i];
-        const bool inliner = i == (inlined_functions.length() - 1);
+        TokenPosition inlined_token_position = (*inlined_token_positions)[i];
+        const bool inliner = i == (inlined_functions->length() - 1);
         if (inliner) {
           current = AppendKind(code, current);
         }
         current = ProcessInlinedFunction(current,
                                          sample_index,
                                          sample,
                                          frame_index,
                                          inlined_function,
                                          inlined_token_position,
                                          code_index);
         if (inliner) {
           current = AppendKind(kInlineStart, current);
         }
       }
       current = AppendKind(kInlineFinish, current);
     } else {
       // Append the inlined children.
       current = AppendKind(kInlineFinish, current);
-      for (intptr_t i = 0; i < inlined_functions.length(); i++) {
-        Function* inlined_function = inlined_functions[i];
+      for (intptr_t i = 0; i < inlined_functions->length(); i++) {
+        Function* inlined_function = (*inlined_functions)[i];
         ASSERT(inlined_function != NULL);
         ASSERT(!inlined_function->IsNull());
-        TokenPosition inlined_token_position = inlined_token_positions[i];
-        const bool inliner = i == (inlined_functions.length() - 1);
+        TokenPosition inlined_token_position = (*inlined_token_positions)[i];
+        const bool inliner = i == (inlined_functions->length() - 1);
         if (inliner) {
           current = AppendKind(kInlineStart, current);
         }
         current = ProcessInlinedFunction(current,
                                          sample_index,
                                          sample,
                                          frame_index + i,
                                          inlined_function,
                                          inlined_token_position,
                                          code_index);
@@ skipping 527 matching lines @@
   Isolate* vm_isolate_;
   SampleFilter* filter_;
   Profile::TagOrder tag_order_;
   intptr_t extra_tags_;
   Profile* profile_;
   DeoptimizedCodeSet* deoptimized_code_;
   const Code& null_code_;
   const Function& null_function_;
   bool tick_functions_;
   bool inclusive_tree_;
-
+  ProfileCodeInlinedFunctionsCache inlined_functions_cache_;
   ProcessedSampleBuffer* samples_;
   ProfileInfoKind info_kind_;
 };  // ProfileBuilder.
 
 
 Profile::Profile(Isolate* isolate)
     : isolate_(isolate),
       zone_(Thread::Current()->zone()),
       samples_(NULL),
       live_code_(NULL),
@@ skipping 479 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