Benchmark of JDK17 RandomGenerator & Commons RNG 1.6 algorithms

README.md

This benchmark evaluates the performance of the new random number generators (RNGs) provided by JDK 17's RandomGenerator interface, comparing them to the RNGs available in Apache Commons RNG 1.6.

A selection of very small to very large arrays and lists are shuffled using the given RNG algorithm.

The shuffle code is from the Apache Commons RNG library (see ListSampler and ArraySampler).

As the JDK has no built in method for shuffling an array without some level of indirection, the shuffle code from Commons RNG is used with minimum modification (the method signature is changed to fit the RandomGenerator interface). Additionally, the JDK interfaces are still in flux for Collections.shuffle, and Random.from is not a suitable fix :) Therefore the shuffle code is once again taken from Commons RNG and only the method signature changed to accommodate. This also ensures fairness, as the shuffle code is the same for each RNG, regardless of origin.

Included below is the JMH test suite used, and the results in csv format.

As usual, the standard JMH disclaimer for data should be applied.

CommonsRngSamplerTest.java

package org.tinnedfruit.microbenchmarks;

import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.sampling.ArraySampler;
import org.apache.commons.rng.sampling.ListSampler;
import org.apache.commons.rng.simple.RandomSource;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.RandomAccess;
import java.util.concurrent.TimeUnit;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
public class CommonsRngSamplerTest {

    @Benchmark
    public void shuffleArray(BenchmarkState state) {
        if (state.commons)
            ArraySampler.shuffle(state.crng, state.array);
        else
            // not great, but there's no JDK-based array shuffle
            RngUtil.shuffle(state.jrng, state.array);
    }

    @Benchmark
    public void shuffleList(BenchmarkState state) {
        if (state.commons)
            ListSampler.shuffle(state.crng, state.list);
        else
            // JDK 17 and 18 didn't solve how to use Collections.shuffle with new RNGs
            RngUtil.shuffle(state.jrng, state.list);
    }

    @State(Scope.Benchmark)
    public static class BenchmarkState {
        int[] array;
        List<Integer> list;
        UniformRandomProvider crng;
        RandomGenerator jrng;
        boolean commons;

        // simulate arrays (i.e. neighbourhoods) of 4 and 8 and grids with edges of length 100, 400, 750, 1000
        @Param({"4", "8", "10000","160000","562500","1000000"})
        private int size;

        @Param({"COMMONS_JDK",
                "COMMONS_WELL_512_A",
                "COMMONS_WELL_1024_A",
                "COMMONS_WELL_19937_A",
                "COMMONS_WELL_19937_C",
                "COMMONS_WELL_44497_A",
                "COMMONS_WELL_44497_B",
                "COMMONS_MT",
                "COMMONS_ISAAC",
                "COMMONS_SPLIT_MIX_64",
                "COMMONS_XOR_SHIFT_1024_S",
                "COMMONS_TWO_CMRES",
                "COMMONS_MT_64",
                "COMMONS_MWC_256",
                "COMMONS_KISS",
                "COMMONS_XOR_SHIFT_1024_S_PHI",
                "COMMONS_XO_RO_SHI_RO_64_S",
                "COMMONS_XO_RO_SHI_RO_64_SS",
                "COMMONS_XO_SHI_RO_128_PLUS",
                "COMMONS_XO_SHI_RO_128_SS",
                "COMMONS_XO_RO_SHI_RO_128_PLUS",
                "COMMONS_XO_RO_SHI_RO_128_SS",
                "COMMONS_XO_SHI_RO_256_PLUS",
                "COMMONS_XO_SHI_RO_256_SS",
                "COMMONS_XO_SHI_RO_512_PLUS",
                "COMMONS_XO_SHI_RO_512_SS",
                "COMMONS_PCG_XSH_RR_32",
                "COMMONS_PCG_XSH_RS_32",
                "COMMONS_PCG_RXS_M_XS_64",
                "COMMONS_PCG_MCG_XSH_RR_32",
                "COMMONS_PCG_MCG_XSH_RS_32",
                "COMMONS_MSWS",
                "COMMONS_SFC_32",
                "COMMONS_SFC_64",
                "COMMONS_JSF_32",
                "COMMONS_JSF_64",
                "COMMONS_XO_SHI_RO_128_PP",
                "COMMONS_XO_RO_SHI_RO_128_PP",
                "COMMONS_XO_SHI_RO_256_PP",
                "COMMONS_XO_SHI_RO_512_PP",
                "COMMONS_XO_RO_SHI_RO_1024_PP",
                "COMMONS_XO_RO_SHI_RO_1024_S",
                "COMMONS_XO_RO_SHI_RO_1024_SS",
                "COMMONS_PCG_XSH_RR_32_OS",
                "COMMONS_PCG_XSH_RS_32_OS",
                "COMMONS_PCG_RXS_M_XS_64_OS",
                "COMMONS_L64_X128_SS",
                "COMMONS_L64_X128_MIX",
                "COMMONS_L64_X256_MIX",
                "COMMONS_L64_X1024_MIX",
                "COMMONS_L128_X128_MIX",
                "COMMONS_L128_X256_MIX",
                "COMMONS_L128_X1024_MIX",
                "COMMONS_L32_X64_MIX",
                "JDK17_L32X64MixRandom",
                "JDK17_L128X128MixRandom",
                "JDK17_L64X128MixRandom",
                "JDK17_SecureRandom",
                "JDK17_L128X1024MixRandom",
                "JDK17_L64X128StarStarRandom",
                "JDK17_Xoshiro256PlusPlus",
                "JDK17_L64X256MixRandom",
                "JDK17_Random",
                "JDK17_Xoroshiro128PlusPlus",
                "JDK17_L128X256MixRandom",
                "JDK17_SplittableRandom",
                "JDK17_L64X1024MixRandom"
        })
        private String randomSource;

        @Setup
        public void prepare() {
            array = IntStream.range(0, size).toArray();
            list = new ArrayList<>(IntStream.range(0, size).boxed().toList());

            if (randomSource.startsWith("JDK17_")) {
                randomSource = randomSource.substring(6);
                jrng = RandomGenerator.of(randomSource);
                commons = false;
            }
            else if (randomSource.startsWith("COMMONS_")) {
                randomSource = randomSource.substring(8);
                crng = RandomSource.valueOf(randomSource).create();
                commons = true;
            }
            else {
                throw new IllegalStateException("Rogue RNG name");
            }

        }
    }

    static class RngUtil {
        public static int[] shuffle(RandomGenerator rng, int[] array) {
            for (int i = array.length; i > 1; i--) {
                swap(array, i - 1, rng.nextInt(i));
            }
            return array;
        }

        /**
         * Swaps the two specified elements in the array.
         *
         * @param array Array.
         * @param i First index.
         * @param j Second index.
         */
        private static void swap(int[] array, int i, int j) {
            final int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }


        private static final int RANDOM_ACCESS_SIZE_THRESHOLD = 4;

        public static <T> void shuffle(RandomGenerator rng,
                                       List<T> list) {
            if (list instanceof RandomAccess || list.size() < RANDOM_ACCESS_SIZE_THRESHOLD) {
                // Shuffle list in-place
                for (int i = list.size(); i > 1; i--) {
                    swap(list, i - 1, rng.nextInt(i));
                }
            } else {
                // Shuffle as an array
                final Object[] array = list.toArray();
                for (int i = array.length; i > 1; i--) {
                    swap(array, i - 1, rng.nextInt(i));
                }

                // Copy back. Use raw types.
                final ListIterator it = list.listIterator();
                for (final Object item : array) {
                    it.next();
                    it.set(item);
                }
            }
        }

        private static <T> void swap(List<T> list, int i, int j) {
            final T tmp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, tmp);
        }

        private static void swap(Object[] array, int i, int j) {
            final Object tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
}

results-jdk17-commons-all.csv