[prev in list] [next in list] [prev in thread] [next in thread] 

List:       jakarta-commons-dev
Subject:    [commons-rng] branch master updated: RNG-160: Use ternary operator to sort two long values
From:       aherbert () apache ! org
Date:       2021-09-29 16:07:45
Message-ID: 163293166576.17104.16185818748206409511 () gitbox ! apache ! org
[Download RAW message or body]

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


The following commit(s) were added to refs/heads/master by this push:
     new b1ae71b  RNG-160: Use ternary operator to sort two long values
b1ae71b is described below

commit b1ae71bae7070d73d631350d42dded4ca26468a0
Author: aherbert <aherbert@apache.org>
AuthorDate: Wed Sep 29 16:52:06 2021 +0100

    RNG-160: Use ternary operator to sort two long values
    
    This removes a 50:50 branch statement from concave overhang sampling.
---
 .../rng/sampling/distribution/ZigguratSampler.java | 35 ++++++++++------------
 src/changes/changes.xml                            |  3 ++
 2 files changed, 18 insertions(+), 20 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 fc03145..e2e27b6 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
 @@ -676,17 +676,14 @@ public abstract class ZigguratSampler implements \
SharedStateContinuousSampler {  //        |    | \
                 //        |    u2 \
                 //        +-------- X[j-1],Y[j-1]
-                // u2 = u1 + (u2 - u1) = u1 + uDistance
+                // Create a second uniform deviate (as u1 is recycled).
+                final long u = randomInt63();
                 // If u2 < u1 then reflect in the hypotenuse by swapping u1 and u2.
-                long uDistance = randomInt63() - u1;
-                if (uDistance < 0) {
-                    // Upper-right triangle. Reflect in hypotenuse.
-                    uDistance = -uDistance;
-                    // Update u1 to be min(u1, u2) by subtracting the distance \
                between them
-                    u1 -= uDistance;
-                }
+                // Use conditional ternary to avoid a 50/50 branch statement to swap \
the pair. +                final long u2 = u1 < u ? u : u1;
+                u1 = u1 < u ? u1 : u;
                 final double x = interpolate(X, j, u1);
-                if (uDistance >= E_MAX) {
+                if (u2 - u1 >= E_MAX) {
                     // Early Exit: x < y - epsilon
                     return x;
                 }
@@ -696,7 +693,7 @@ public abstract class ZigguratSampler implements \
SharedStateContinuousSampler {  // Accept Y   = 0.161930
                 // Reject Y   = 0.0147417 (recursion)
 
-                if (interpolate(Y, j, u1 + uDistance) <= Math.exp(-x)) {
+                if (interpolate(Y, j, u2) <= Math.exp(-x)) {
                     return x;
                 }
 
@@ -1136,17 +1133,15 @@ public abstract class ZigguratSampler implements \
SharedStateContinuousSampler {  // Expected frequency: 0.00249694
                     // Observed loop repeat frequency: 0.0123784
                     for (;;) {
-                        // u2 = u1 + (u2 - u1) = u1 + uDistance
-                        long uDistance = randomInt63() - u1;
-                        if (uDistance < 0) {
-                            // Upper-right triangle. Reflect in hypotenuse.
-                            uDistance = -uDistance;
-                            // Update u1 to be min(u1, u2) by subtracting the \
                distance between them
-                            u1 -= uDistance;
-                        }
+                        // Create a second uniform deviate (as u1 is recycled).
+                        final long u = randomInt63();
+                        // If u2 < u1 then reflect in the hypotenuse by swapping u1 \
and u2. +                        // Use conditional ternary to avoid a 50/50 branch \
statement to swap the pair. +                        final long u2 = u1 < u ? u : u1;
+                        u1 = u1 < u ? u1 : u;
                         x = interpolate(X, j, u1);
-                        if (uDistance > CONCAVE_E_MAX ||
-                            interpolate(Y, j, u1 + uDistance) < Math.exp(-0.5 * x * \
x)) { +                        if (u2 - u1 > CONCAVE_E_MAX ||
+                            interpolate(Y, j, u2) < Math.exp(-0.5 * x * x)) {
                             break;
                         }
                         u1 = randomInt63();
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 0becee6..d17b1d3 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -81,6 +81,9 @@ 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": Performance improvement using ternary operator to sort \
values. +      </action>
 </release>
 
     <release version="1.4" date="2021-09-13" description="


[prev in list] [next in list] [prev in thread] [next in thread]