[RNG-87] MultiplyWithCarry256

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.3
• Fix Version/s: 1.3
• Component/s: core
• Labels: performance
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 25/Mar/19 16:13
• Updated: 11/Nov/19 14:25
• Resolved: 02/Apr/19 11:50

Description

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:

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++];
}

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

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;
}

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.

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)

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

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)

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

Issue Links

• relates to: RNG-88 Update the GenerationPerformance benchmark
• links to: GitHub Pull Request #33