Unsampling for the sampling heap profiler

src/profiler/sampling-heap-profiler.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/profiler/sampling-heap-profiler.h"
 
 #include <stdint.h>
 #include <memory>
 #include "src/api.h"
 #include "src/base/utils/random-number-generator.h"
@@ skipping 15 matching lines @@
   if (FLAG_sampling_heap_profiler_suppress_randomness) {
     return static_cast<intptr_t>(rate);
   }
   double u = random_->NextDouble();
   double next = (-std::log(u)) * rate;
   return next < kPointerSize
              ? kPointerSize
              : (next > INT_MAX ? INT_MAX : static_cast<intptr_t>(next));
 }
 
+// Samples were collected according to a poisson process. Since we have not
+// recorded all allocations, we must approximate the shape of the underlying
+// space of allocations based on the samples we have collected. Given that
+// we sample at rate R, the probability that an allocation of size S will be
+// sampled is 1-exp(-S/R). This function uses the above probability to
+// approximate the true number of allocations with size *size* given that
+// *count* samples were observed.
+v8::AllocationProfile::Allocation SamplingHeapProfiler::ScaleSample(
+    size_t size, unsigned int count) {
+  double scale = 1.0 / (1.0 - std::exp(-static_cast<double>(size) / rate_));
+  // Round count instead of truncating.
+  return {size, static_cast<unsigned int>(count * scale + 0.5)};
+}
+
 SamplingHeapProfiler::SamplingHeapProfiler(Heap* heap, StringsStorage* names,
                                            uint64_t rate, int stack_depth)
     : isolate_(heap->isolate()),
       heap_(heap),
       new_space_observer_(new SamplingAllocationObserver(
           heap_, static_cast<intptr_t>(rate), rate, this,
           heap->isolate()->random_number_generator())),
       other_spaces_observer_(new SamplingAllocationObserver(
           heap_, static_cast<intptr_t>(rate), rate, this,
           heap->isolate()->random_number_generator())),
       names_(names),
       profile_root_("(root)", v8::UnboundScript::kNoScriptId, 0),
       samples_(),
-      stack_depth_(stack_depth) {
+      stack_depth_(stack_depth),
+      rate_(rate) {
+  CHECK_GT(rate_, 0);
   heap->new_space()->AddAllocationObserver(new_space_observer_.get());
   AllSpaces spaces(heap);
   for (Space* space = spaces.next(); space != NULL; space = spaces.next()) {
     if (space != heap->new_space()) {
       space->AddAllocationObserver(other_spaces_observer_.get());
     }
   }
 }
 
 
@@ skipping 129 matching lines @@
     if (script->name()->IsName()) {
       Name* name = Name::cast(script->name());
       script_name = ToApiHandle<v8::String>(
           isolate_->factory()->InternalizeUtf8String(names_->GetName(name)));
     }
     Handle<Script> script_handle(script);
 
     line = 1 + Script::GetLineNumber(script_handle, node->script_position_);
     column = 1 + Script::GetColumnNumber(script_handle, node->script_position_);
     for (auto alloc : node->allocations_) {
-      allocations.push_back({alloc.first, alloc.second});
+      allocations.push_back(ScaleSample(alloc.first, alloc.second));
     }
   }
 
   profile->nodes().push_back(v8::AllocationProfile::Node(
       {ToApiHandle<v8::String>(
            isolate_->factory()->InternalizeUtf8String(node->name_)),
        script_name, node->script_id_, node->script_position_, line, column,
        std::vector<v8::AllocationProfile::Node*>(), allocations}));
   v8::AllocationProfile::Node* current = &profile->nodes().back();
   for (auto child : node->children_) {
@@ skipping 18 matching lines @@
   auto profile = new v8::internal::AllocationProfile();
 
   TranslateAllocationNode(profile, &profile_root_, scripts);
 
   return profile;
 }
 
 
 }  // namespace internal
 }  // namespace v8