[jira] [Created] (RNG-87) MultiplyWithCarry256

["Alex D Herbert (JIRA)" <ji...@apache.org>]

Alex D Herbert created RNG-87:
---------------------------------

             Summary: MultiplyWithCarry256
                 Key: RNG-87
                 URL: https://issues.apache.org/jira/browse/RNG-87
             Project: Commons RNG
          Issue Type: Improvement
          Components: core
    Affects Versions: 1.3
            Reporter: Alex D Herbert
            Assignee: Alex D Herbert


The {{MultiplyWithCarry256}} currently uses a length 256 array for internal state. This is cycled through continuously. The current implementation refills the state every 256 calls to next:

{code:java}
public int next() {
    if (index == Q_SIZE) { // Whole state used up.
        // Refill.
        for (int i = 0; i < Q_SIZE; i++) {
            final long t = A * (state[i] & 0xffffffffL) + carry;
            carry = (int) (t >> 32);
            state[i] = (int) t;
        }

        // Reset current index.
        index = 0;
    }

    return state[index++];
}
{code}

This can be changed to continuously update the state for only a single index on each call to next:

{code:java}
public int next() {
    // Produce an index in the range 0-255
    final int i = index++ & 0xFF;
    final long t = A * (state[i] & 0xffffffffL) + carry;
    carry = (int) (t >> 32);
    return state[i] = (int) t;
}
{code}

This avoids an {{if}} statement check and *marginally* improves performance. It has the advantage of not advancing the state further ahead than necessary.

MWC_256B is the new version. JMH results from the GenerationPerformance benchmark.

{noformat}
openjdk version "1.8.0_191"
OpenJDK Runtime Environment (build 1.8.0_191-8u191-b12-2ubuntu0.16.04.1-b12)
OpenJDK 64-Bit Server VM (build 25.191-b12, mixed mode)
{noformat}

||numValues||randomSourceName||Method||Score||Error||Median||
|1|SPLIT_MIX_64|nextInt|0.00478|4.45e-05|0.00477|
|1|MWC_256|nextInt|0.00521|1.69e-05|0.00521|
|1|MWC_256B|nextInt|0.00519|0.000321|0.00512|
|100|SPLIT_MIX_64|nextInt|0.421|0.0131|0.418|
|100|MWC_256|nextInt|0.452|0.000968|0.452|
|100|MWC_256B|nextInt|0.443|0.00183|0.442|
|10000|SPLIT_MIX_64|nextInt|41.7|0.0725|41.7|
|10000|MWC_256|nextInt|44.5|2.25|43.9|
|10000|MWC_256B|nextInt|42.6|0.037|42.6|
|1000000|SPLIT_MIX_64|nextInt|3.77e+03|21.2|3.77e+03|
|1000000|MWC_256|nextInt|4.16e+03|12.8|4.16e+03|
|1000000|MWC_256B|nextInt|3.98e+03|120|3.96e+03|

{noformat}
java version "11.0.2" 2019-01-15 LTS
Java(TM) SE Runtime Environment 18.9 (build 11.0.2+9-LTS)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11.0.2+9-LTS, mixed mode)
{noformat}

||numValues||randomSourceName||Method||Score||Error||Median||
|1|SPLIT_MIX_64|nextInt|0.00469|4.98e-06|0.00469|
|1|MWC_256|nextInt|0.00553|2.09e-05|0.00553|
|1|MWC_256B|nextInt|0.00493|4.32e-05|0.00492|
|100|SPLIT_MIX_64|nextInt|0.435|0.000624|0.435|
|100|MWC_256|nextInt|0.467|0.00284|0.466|
|100|MWC_256B|nextInt|0.455|0.00105|0.455|
|10000|SPLIT_MIX_64|nextInt|43|4.94|41.9|
|10000|MWC_256|nextInt|45.8|0.132|45.8|
|10000|MWC_256B|nextInt|43|0.033|43|
|1000000|SPLIT_MIX_64|nextInt|3.7e+03|7.88|3.7e+03|
|1000000|MWC_256|nextInt|4.17e+03|45.3|4.15e+03|
|1000000|MWC_256B|nextInt|4.12e+03|4.76|4.12e+03|





--
This message was sent by Atlassian JIRA
(v7.6.3#76005)