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 1037 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) {
+    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 {
     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 524 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