Unsampling for the sampling heap profiler

src/profiler/sampling-heap-profiler.cc

Index: src/profiler/sampling-heap-profiler.cc
diff --git a/src/profiler/sampling-heap-profiler.cc b/src/profiler/sampling-heap-profiler.cc
index 4127858123af5400b0c5415214d1c62c88291898..1b12913863a709a49a2e9a27baa4112392ca90eb 100644
--- a/src/profiler/sampling-heap-profiler.cc
+++ b/src/profiler/sampling-heap-profiler.cc
@@ -33,6 +33,20 @@ intptr_t SamplingAllocationObserver::GetNextSampleInterval(uint64_t rate) {
              : (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::Unsample(
+    size_t size, unsigned int count) {
+  double scale = 1.0 / (1.0 - std::exp(-size / rate_));

[ofrobots, 2016/02/19 05:01:27]

Need an assertion (probably in the constructor, perhaps earlier in the
v8-profiler API) that rate is non-zero to avoid a division by zero here.

[mattloring, 2016/02/19 05:16:10]

What form do assertions take here? Is that the same as DCHECK?

+  // 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()),
@@ -46,7 +60,8 @@ SamplingHeapProfiler::SamplingHeapProfiler(Heap* heap, StringsStorage* names,
       names_(names),
       profile_root_("(root)", v8::UnboundScript::kNoScriptId, 0),
       samples_(),
-      stack_depth_(stack_depth) {
+      stack_depth_(stack_depth),
+      rate_(rate) {
   heap->new_space()->AddAllocationObserver(new_space_observer_.get());
   AllSpaces spaces(heap);
   for (Space* space = spaces.next(); space != NULL; space = spaces.next()) {
@@ -196,7 +211,7 @@ v8::AllocationProfile::Node* SamplingHeapProfiler::TranslateAllocationNode(
     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(Unsample(alloc.first, alloc.second));
     }
   }