You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2021/08/12 16:33:13 UTC
[commons-rng] 03/03: RNG-160: Extract ziggurat edge sampling to a
separate method
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit b4929c899ea1f60d6bc7d61cfeeb7f589174e31a
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 12 17:33:07 2021 +0100
RNG-160: Extract ziggurat edge sampling to a separate method
This improves performance.
Use nested branches to match implementation in the JMH module where the
performance was verified.
---
.../rng/sampling/distribution/ZigguratSampler.java | 74 ++++++++++++++--------
src/changes/changes.xml | 4 ++
2 files changed, 50 insertions(+), 28 deletions(-)
diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
index 81818aa..641ab79 100644
--- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
+++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
@@ -758,6 +758,9 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
/** {@inheritDoc} */
@Override
public double sample() {
+ // Ideally this method byte code size should be below -XX:MaxInlineSize
+ // (which defaults to 35 bytes). This compiles to 33 bytes.
+
final long xx = nextLong();
// Float multiplication squashes these last 8 bits, so they can be used to sample i
final int i = ((int) xx) & MASK_INT8;
@@ -768,6 +771,19 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
return X[i] * xx;
}
+ return edgeSample(xx);
+ }
+
+ /**
+ * Create the sample from the edge of the ziggurat.
+ *
+ * <p>This method has been extracted to fit the main sample method within 35 bytes (the
+ * default size for a JVM to inline a method).
+ *
+ * @param xx Initial random deviate
+ * @return a sample
+ */
+ private double edgeSample(long xx) {
// Recycle bits then advance RNG:
// u1 = RANDOM_INT63()
long u1 = xx & MAX_INT64;
@@ -807,36 +823,38 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
// uDiff < MAX_IE (upper-right triangle) or rejected as above the curve
u1 = randomInt63();
}
- } else if (j == 0) {
- // Tail
- // Branch frequency: 0.000277067
- // Note: Although less frequent than the next branch, j == 0 is a subset of
- // j < J_INFLECTION and must be first.
- // Loop repeat frequency: 0.0634786
- do {
- x = ONE_OVER_X_0 * exponential.sample();
- } while (exponential.sample() < 0.5 * x * x);
- x += X_0;
} else if (j < J_INFLECTION) {
- // Concave overhang
- // Branch frequency: 0.00251223
- // Loop repeat frequency: 0.0123784
- for (;;) {
- // U_x <- min(U_1, U_2)
- // distance <- | U_1 - U_2 |
- // U_y <- 1 - (U_x + distance)
- long uDiff = randomInt63() - u1;
- if (uDiff < 0) {
- // Upper-right triangle. Reflect in hypotenuse.
- uDiff = -uDiff;
- u1 -= uDiff;
- }
- x = fastPrngSampleX(X, j, u1);
- if (uDiff > MIN_IE ||
- fastPrngSampleY(Y, j, Long.MIN_VALUE - (u1 + uDiff)) < Math.exp(-0.5 * x * x)) {
- break;
+ if (j == 0) {
+ // Tail
+ // Branch frequency: 0.000277067
+ // Note: Although less frequent than the next branch, j == 0 is a subset of
+ // j < J_INFLECTION and must be first.
+ // Loop repeat frequency: 0.0634786
+ do {
+ x = ONE_OVER_X_0 * exponential.sample();
+ } while (exponential.sample() < 0.5 * x * x);
+ x += X_0;
+ } else {
+ // Concave overhang
+ // Branch frequency: 0.00251223
+ // Loop repeat frequency: 0.0123784
+ for (;;) {
+ // U_x <- min(U_1, U_2)
+ // distance <- | U_1 - U_2 |
+ // U_y <- 1 - (U_x + distance)
+ long uDiff = randomInt63() - u1;
+ if (uDiff < 0) {
+ // Upper-right triangle. Reflect in hypotenuse.
+ uDiff = -uDiff;
+ u1 -= uDiff;
+ }
+ x = fastPrngSampleX(X, j, u1);
+ if (uDiff > MIN_IE ||
+ fastPrngSampleY(Y, j, Long.MIN_VALUE - (u1 + uDiff)) < Math.exp(-0.5 * x * x)) {
+ break;
+ }
+ u1 = randomInt63();
}
- u1 = randomInt63();
}
} else {
// Inflection point
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 01e6787..8f17412 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -81,6 +81,10 @@ re-run tests that fail, and pass the build if they succeed
within the allotted number of reruns (the test will be marked
as 'flaky' in the report).
">
+ <action dev="aherbert" type="update" issue="160">
+ "ZigguratSampler.NormalizedGaussian": Performance improvement by extracting ziggurat
+ edge sampling to a separate method.
+ </action>
<action dev="aherbert" type="fix" issue="159">
"ZigguratSampler.NormalizedGaussian": Corrected biased sampling within convex regions
at the edge of the ziggurat.