diff options
Diffstat (limited to 'src/runtime/malloc.go')
| -rw-r--r-- | src/runtime/malloc.go | 46 |
1 files changed, 26 insertions, 20 deletions
diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index d68ebcc5d2..9965ea19a2 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -865,11 +865,13 @@ func profilealloc(mp *m, x unsafe.Pointer, size uintptr) { mProf_Malloc(x, size) } -// nextSample returns the next sampling point for heap profiling. -// It produces a random variable with a geometric distribution and -// mean MemProfileRate. This is done by generating a uniformly -// distributed random number and applying the cumulative distribution -// function for an exponential. +// nextSample returns the next sampling point for heap profiling. The goal is +// to sample allocations on average every MemProfileRate bytes, but with a +// completely random distribution over the allocation timeline; this +// corresponds to a Poisson process with parameter MemProfileRate. In Poisson +// processes, the distance between two samples follows the exponential +// distribution (exp(MemProfileRate)), so the best return value is a random +// number taken from an exponential distribution whose mean is MemProfileRate. func nextSample() int32 { if GOOS == "plan9" { // Plan 9 doesn't support floating point in note handler. @@ -878,25 +880,29 @@ func nextSample() int32 { } } - period := MemProfileRate + return fastexprand(MemProfileRate) +} - // make nextSample not overflow. Maximum possible step is - // -ln(1/(1<<kRandomBitCount)) * period, approximately 20 * period. +// fastexprand returns a random number from an exponential distribution with +// the specified mean. +func fastexprand(mean int) int32 { + // Avoid overflow. Maximum possible step is + // -ln(1/(1<<randomBitCount)) * mean, approximately 20 * mean. switch { - case period > 0x7000000: - period = 0x7000000 - case period == 0: + case mean > 0x7000000: + mean = 0x7000000 + case mean == 0: return 0 } - // Let m be the sample rate, - // the probability distribution function is m*exp(-mx), so the CDF is - // p = 1 - exp(-mx), so - // q = 1 - p == exp(-mx) - // log_e(q) = -mx - // -log_e(q)/m = x - // x = -log_e(q) * period - // x = log_2(q) * (-log_e(2)) * period ; Using log_2 for efficiency + // Take a random sample of the exponential distribution exp(-mean*x). + // The probability distribution function is mean*exp(-mean*x), so the CDF is + // p = 1 - exp(-mean*x), so + // q = 1 - p == exp(-mean*x) + // log_e(q) = -mean*x + // -log_e(q)/mean = x + // x = -log_e(q) * mean + // x = log_2(q) * (-log_e(2)) * mean ; Using log_2 for efficiency const randomBitCount = 26 q := fastrand()%(1<<randomBitCount) + 1 qlog := fastlog2(float64(q)) - randomBitCount @@ -904,7 +910,7 @@ func nextSample() int32 { qlog = 0 } const minusLog2 = -0.6931471805599453 // -ln(2) - return int32(qlog*(minusLog2*float64(period))) + 1 + return int32(qlog*(minusLog2*float64(mean))) + 1 } // nextSampleNoFP is similar to nextSample, but uses older, |