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..bf1ccc32c63ae1e35d6de1ec5355a10742c62f09 100644
--- a/src/profiler/sampling-heap-profiler.cc
+++ b/src/profiler/sampling-heap-profiler.cc
@@ -33,6 +33,19 @@ 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_));
+  return {size, static_cast<unsigned int>(count * scale + 0.5)};

[ofrobots, 2016/02/19 04:29:29]

Where did the 0.5 come from?

[mattloring, 2016/02/19 04:31:07]

Thought it would be more accurate to round than truncate. Happy to go with
truncating if that is the desired behavior.

[ofrobots, 2016/02/19 04:46:43]

Ah. This deserves a comment in the code.

[mattloring, 2016/02/19 04:50:41]

Done.

+}
+
 SamplingHeapProfiler::SamplingHeapProfiler(Heap* heap, StringsStorage* names,
                                            uint64_t rate, int stack_depth)
     : isolate_(heap->isolate()),
@@ -46,7 +59,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 +210,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));
     }
   }