Bug 1206596: Change js::SavedStacks to use mozilla::FastBernoulliTrial. r=fitzgen
authorJim Blandy <jimb@mozilla.com>
Thu, 17 Sep 2015 16:29:39 -0700
changeset 288179 df0f9214b22402bd7badcd4d3547da1e3bf7ff5a
parent 288178 2a4b512df31d589ff52000cd172be8eb8cf17851
child 288180 430a7d299e7ee2b2b513753ca971c365eddc4fbe
push id8654
push userraliiev@mozilla.com
push dateThu, 29 Oct 2015 11:48:40 +0000
treeherdermozilla-aurora@bc4551debe17 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfitzgen
bugs1206596
milestone44.0a1
Bug 1206596: Change js::SavedStacks to use mozilla::FastBernoulliTrial. r=fitzgen
js/src/builtin/TestingFunctions.cpp
js/src/jit-test/tests/debug/Memory-allocationSamplingProbability-02.js
js/src/vm/SavedStacks.cpp
js/src/vm/SavedStacks.h
--- a/js/src/builtin/TestingFunctions.cpp
+++ b/js/src/builtin/TestingFunctions.cpp
@@ -863,17 +863,17 @@ SetSavedStacksRNGState(JSContext* cx, un
     CallArgs args = CallArgsFromVp(argc, vp);
     if (!args.requireAtLeast(cx, "setSavedStacksRNGState", 1))
         return false;
 
     int32_t seed;
     if (!ToInt32(cx, args[0], &seed))
         return false;
 
-    cx->compartment()->savedStacks().setRNGState((seed ^ RNG_MULTIPLIER) & RNG_MASK);
+    cx->compartment()->savedStacks().setRNGState(seed, seed * 33);
     return true;
 }
 
 static bool
 GetSavedFrameCount(JSContext* cx, unsigned argc, Value* vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     args.rval().setNumber(cx->compartment()->savedStacks().count());
--- a/js/src/jit-test/tests/debug/Memory-allocationSamplingProbability-02.js
+++ b/js/src/jit-test/tests/debug/Memory-allocationSamplingProbability-02.js
@@ -27,10 +27,10 @@ function measure(P, expected) {
 dbg.memory.trackingAllocationSites = true;
 
 // These are the sample counts that were correct when this test was last
 // updated; changes to SpiderMonkey may occasionally cause changes
 // here. Anything that is within a plausible range for the given sampling
 // probability is fine.
 measure(0.0, 0);
 measure(1.0, 100);
-measure(0.1, 9);
-measure(0.5, 51);
+measure(0.1, 7);
+measure(0.5, 44);
--- a/js/src/vm/SavedStacks.cpp
+++ b/js/src/vm/SavedStacks.cpp
@@ -1,16 +1,17 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "vm/SavedStacks.h"
 
+#include "mozilla/ArrayUtils.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/Move.h"
 
 #include <algorithm>
 #include <math.h>
 
 #include "jsapi.h"
@@ -899,16 +900,20 @@ SavedFrame::toStringMethod(JSContext* cx
         return false;
     args.rval().setString(string);
     return true;
 }
 
 bool
 SavedStacks::init()
 {
+    uint64_t seed[2];
+    random_generateSeed(seed, mozilla::ArrayLength(seed));
+    bernoulli.setRandomState(seed[0], seed[1]);
+
     if (!pcLocationMap.init())
         return false;
 
     return frames.init();
 }
 
 bool
 SavedStacks::saveCurrentStack(JSContext* cx, MutableHandleSavedFrame frame, unsigned maxFrameCount)
@@ -1334,70 +1339,42 @@ SavedStacks::chooseSamplingProbability(J
 
     GlobalObject::DebuggerVector* dbgs = global->getDebuggers();
     if (!dbgs || dbgs->empty())
         return;
 
     mozilla::DebugOnly<Debugger**> begin = dbgs->begin();
     mozilla::DebugOnly<bool> foundAnyDebuggers = false;
 
-    allocationSamplingProbability = 0;
+    double probability = 0;
     for (Debugger** dbgp = dbgs->begin(); dbgp < dbgs->end(); dbgp++) {
         // The set of debuggers had better not change while we're iterating,
         // such that the vector gets reallocated.
         MOZ_ASSERT(dbgs->begin() == begin);
 
         if ((*dbgp)->trackingAllocationSites && (*dbgp)->enabled) {
             foundAnyDebuggers = true;
-            allocationSamplingProbability = std::max((*dbgp)->allocationSamplingProbability,
-                                                     allocationSamplingProbability);
+            probability = std::max((*dbgp)->allocationSamplingProbability,
+                                   probability);
         }
     }
     MOZ_ASSERT(foundAnyDebuggers);
+
+    bernoulli.setProbability(probability);
 }
 
 JSObject*
 SavedStacksMetadataCallback(JSContext* cx, JSObject* target)
 {
     RootedObject obj(cx, target);
 
     SavedStacks& stacks = cx->compartment()->savedStacks();
-    if (stacks.allocationSkipCount > 0) {
-        stacks.allocationSkipCount--;
-        return nullptr;
-    }
-
-    if (stacks.allocationSamplingProbability == 0.0)
+    if (!stacks.bernoulli.trial())
         return nullptr;
 
-    // If the sampling probability is set to 1.0, we are always taking a sample
-    // and can therefore leave allocationSkipCount at 0.
-    if (stacks.allocationSamplingProbability != 1.0) {
-        // Rather than generating a random number on every allocation to decide
-        // if we want to sample that particular allocation (which would be
-        // expensive), we calculate the number of allocations to skip before
-        // taking the next sample.
-        //
-        // P = the probability we sample any given event.
-        //
-        // ~P = 1-P, the probability we don't sample a given event.
-        //
-        // (~P)^n = the probability that we skip at least the next n events.
-        //
-        // let X = random between 0 and 1.
-        //
-        // floor(log base ~P of X) = n, aka the number of events we should skip
-        // until we take the next sample. Any value for X less than (~P)^n
-        // yields a skip count greater than n, so the likelihood of a skip count
-        // greater than n is (~P)^n, as required.
-        double notSamplingProb = 1.0 - stacks.allocationSamplingProbability;
-        stacks.allocationSkipCount = std::floor(std::log(random_nextDouble(&stacks.rngState)) /
-                                                std::log(notSamplingProb));
-    }
-
     AutoEnterOOMUnsafeRegion oomUnsafe;
     RootedSavedFrame frame(cx);
     if (!stacks.saveCurrentStack(cx, &frame))
         oomUnsafe.crash("SavedStacksMetadataCallback");
 
     if (!Debugger::onLogAllocationSite(cx, obj, frame, JS_GetCurrentEmbedderTime()))
         oomUnsafe.crash("SavedStacksMetadataCallback");
 
--- a/js/src/vm/SavedStacks.h
+++ b/js/src/vm/SavedStacks.h
@@ -2,16 +2,18 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef vm_SavedStacks_h
 #define vm_SavedStacks_h
 
+#include "mozilla/FastBernoulliTrial.h"
+
 #include "jscntxt.h"
 #include "jsmath.h"
 #include "jswrapper.h"
 #include "js/HashTable.h"
 #include "vm/SavedFrame.h"
 #include "vm/Stack.h"
 
 namespace js {
@@ -146,42 +148,39 @@ namespace js {
 // principals.
 
 class SavedStacks {
     friend JSObject* SavedStacksMetadataCallback(JSContext* cx, JSObject* target);
     friend bool JS::ubi::ConstructSavedFrameStackSlow(JSContext* cx,
                                                       JS::ubi::StackFrame& ubiFrame,
                                                       MutableHandleObject outSavedFrameStack);
 
+
   public:
     SavedStacks()
       : frames(),
-        allocationSamplingProbability(1.0),
-        allocationSkipCount(0),
-        rngState(0),
+        bernoulli(1.0, 0x59fdad7f6b4cc573, 0x91adf38db96a9354),
         creatingSavedFrame(false)
     { }
 
     bool     init();
     bool     initialized() const { return frames.initialized(); }
     bool     saveCurrentStack(JSContext* cx, MutableHandleSavedFrame frame, unsigned maxFrameCount = 0);
     void     sweep(JSRuntime* rt);
     void     trace(JSTracer* trc);
     uint32_t count();
     void     clear();
-    void     setRNGState(uint64_t state) { rngState = state; }
+    void     setRNGState(uint64_t state0, uint64_t state1) { bernoulli.setRandomState(state0, state1); }
     void     chooseSamplingProbability(JSCompartment*);
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
 
   private:
     SavedFrame::Set frames;
-    double          allocationSamplingProbability;
-    uint32_t        allocationSkipCount;
-    uint64_t        rngState;
+    mozilla::FastBernoulliTrial bernoulli;
     bool            creatingSavedFrame;
 
     // Similar to mozilla::ReentrancyGuard, but instead of asserting against
     // reentrancy, just change the behavior of SavedStacks::saveCurrentStack to
     // return a nullptr SavedFrame.
     struct MOZ_RAII AutoReentrancyGuard {
         MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER;
         SavedStacks& stacks;