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

runtime/vm/profiler_service.cc

Index: runtime/vm/profiler_service.cc
diff --git a/runtime/vm/profiler_service.cc b/runtime/vm/profiler_service.cc
index 2ef7b813fe871925300718154c6c26cadfa533de..5504831bbfe5908e0ea7d9f2b06c0d82c6741b77 100644
--- a/runtime/vm/profiler_service.cc
+++ b/runtime/vm/profiler_service.cc
@@ -1055,6 +1055,156 @@ class ProfileFunctionTrieNode : public ProfileTrieNode {
 };
 
 
+class ProfileCodeInlinedFunctionsCache : public ValueObject {
+ public:
+  ProfileCodeInlinedFunctionsCache()
+      : cache_cursor_(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++) {
+      if ((cache_[i].pc == pc) && (cache_[i].offset == offset)) {
+        // Hit.
+        if (cache_[i].inlined_functions.length() == 0) {
+          *inlined_functions = NULL;
+          *inlined_token_positions = NULL;
+        } else {
+          *inlined_functions = &cache_[i].inlined_functions;
+          *inlined_token_positions = &cache_[i].inlined_token_positions;
+        }
+        *token_position = cache_[i].token_position;
+        cache_hit_++;
+        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);
+    *inlined_functions = NULL;
+    *inlined_token_positions = NULL;

[srdjan, 2016/03/23 21:55:41]

Move this two lines inside the if below, or move them to the top of the
function.

[Cutch, 2016/03/23 22:31:17]

Done.

+    if (cache_entry->inlined_functions.length() == 0) {
+      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;

[srdjan, 2016/03/23 21:55:40]

Do you have any performance data for cache size 16 and 64?

[Cutch, 2016/03/23 22:31:17]

I've tried 32 and 64 and settled on 128 because it had slightly better
performance. It's hard to tell the exact performance here because as the sample
buffer's contents changes the amount of work done by the profiler changes.

+  intptr_t cache_cursor_;
+  CacheEntry cache_[kCacheSize];
+  intptr_t cache_miss_;
+  intptr_t cache_hit_;
+};
+
+
 class ProfileBuilder : public ValueObject {
  public:
   enum ProfileInfoKind {
@@ -1456,28 +1606,6 @@ class ProfileBuilder : public ValueObject {
     }
   }
 
-  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,
@@ -1491,34 +1619,28 @@ class ProfileBuilder : public ValueObject {
     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);
@@ -1539,12 +1661,12 @@ class ProfileBuilder : public ValueObject {
     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);
         }
@@ -1563,12 +1685,12 @@ class ProfileBuilder : public ValueObject {
     } 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);
         }
@@ -2113,7 +2235,7 @@ class ProfileBuilder : public ValueObject {
   const Function& null_function_;
   bool tick_functions_;
   bool inclusive_tree_;
-
+  ProfileCodeInlinedFunctionsCache inlined_functions_cache_;
   ProcessedSampleBuffer* samples_;
   ProfileInfoKind info_kind_;
 };  // ProfileBuilder.