315Random Newsletter

Author: Dr Heinz M. KabutzDate: 2024-02-29Java Version: 21Category: Tips and Tricks

Abstract: Classes java.util.Random and java.util.SplittableRandom didn't used to have a common ancestor, making it difficult to write methods that take either. This was finally fixed in Java 17. Let's have a look at some random Java topics together.

Welcome to the 315th edition of The Java(tm) Specialists' Newsletter. It is the third leap year in a row that we sent our newsletter on the 29th of February. A very happy leap birthday for all those happy folks born on this day.

At the end of 2023, we did a major cleanup of our mailing list. We have subscribers going back 23 years. Some have moved on to other technologies, others have retired. I sent out several reminders to switch to the new list, but in case you didn't receive that, please head over to our website and sign up again. Please let me know if you've changed your email address, so we can merge your accounts. This also means that we now have a leaner, but more potent, email list. I believe The Java(tm) Specialists' Newsletter is the longest continuously active Java newsletter, followed three weeks later by Jack Shirazi's excellent Java Performance Tuning Newsletter.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Random Newsletter

We sent out an email to our refreshed newsletter mailing list, inviting subscribers to add their name to our JCrete Lottery for 2024. We ran the lottery last week, and the code looked like this:

import java.util.*;
import java.util.concurrent.*;

public class JCrete2024Lottery {
    public static void main(String... args) {
        pickRandom(2, "AS", "AVV", "CS", "DP", "FZ", "IK",
                "IV", "J-HS", "JM", "LP", "MB", "MD", "MG",
                "MM", "NB", "SB", "SW");

        pickRandom(10, "AdRe", "AdWo", "AlFe", "AlKe",
                "AlSh", "ÁnÁl", "AnLä", "AnNi", "AnPa",
                "ArGa", "ChPa", "DaDa", "DaSa", "DaSc",
                "DaVl", "DiKa", "EmGk", "EmTz", "EnIb",
                "GeKa", "GüKo", "InBu", "IsJa", "JoVi",
                "MaAl", "MaBü", "MaHa", "MuNu", "NaBa",
                "OlNe", "OtCa", "PaNu", "PaPi", "RaAr",
                "RaSt", "RaTh", "RiDe", "ShMu", "SiBr",
                "TaPa", "TiMi", "VeYa", "ViTa");
    }

    private static void pickRandom(int seats, String... initials) {
        System.out.println(STR."Picking \{seats} attendees:");
        System.out.println(STR."""
            Chance is \{seats} in \{initials.length}, \
         thus \{seats * 100 / initials.length}%\
         """);
        var lottery = new ArrayList<>(List.of(initials));
        Collections.shuffle(lottery, ThreadLocalRandom.current());
        lottery.stream().limit(seats).forEach(System.out::println);
    }
}

One of the hopefuls sent me a question as to why I would use ThreadLocalRandom.current() as the random algorithm in the shuffle() method, which then spawned this newsletter.

Towards the end of 2023, we launched the self-study version of our Mastering Java 17 course. The reason it took so long to produce is that we wanted to first present it as an inhouse course several times in order to fine tune it. Since companies take a while to adopt new Java versions, we only started getting requests for inhouse Java 17 classes in 2023.

One of the new features of Java 17 is the RandomGenerator interface. This interface, or something like this, should have been in Java 1.0. Prior to Java 17, any class for generating random numbers would typically extend the java.util.Random class, for example java.security.SecureRandom and java.util.concurrent.ThreadLocalRandom. However, when we subclass java.util.Random, we carry along all the baggage that comes with it. For example, java.util.Random is threadsafe, using compare-and-set with AtomicLong. Most of the functions produce uniformly distributed numbers, meaning that all values are equally likely. In reality there are some values that we could never see, as described in Pushing the Limits in Java's Random. However, the thread safety is fairly expensive to implement, because of the way the algorithm is written:

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

We see that there is a fairly long code path between reading the current seed and when we call compareAndSet(). The longer the path, the higher the probability that during contention we will lose the race and will have to try again. We might ask: "It is random, why do we care about race conditions?" That is a good question indeed. I guess it is important to know that it is threadsafe, and that this may introduce contention. Consider this class:

import java.util.stream.*;

public class MathRandomComparison {
    private static double randomValue() {
        return Math.random();
    }

    public static void main(String... args) {
        System.out.println(IntStream.range(0, 100_000_000)
                .mapToDouble(i -> randomValue())
                .sum());
    }
}

If we run it as-is on my MacBook Pro M2 Max, it takes about 1.7 seconds of real time, with an equivalent of 1.7 seconds of CPU time. If we use a parallel stream, it instead takes 80 seconds of real time, with a whopping 800 seconds of CPU time. Yikes! If we also make randomValue() synchronized with the paralle stream, the time drops to 10 seconds of real time, with 12 seconds of CPU time. Of course, none of these are good solutions. Much better is to use ThreadLocalRandom.current().nextDouble() instead of Math.random(), in which case with a parallel stream we drop to 74 ms of real time, with 600 ms of CPU time.

You might wonder how we measured the real and CPU time. Real is easy - just use System.nanoTime(). But for CPU time, we want to use the ThreadMXBean, find all the CPU time of the parallel stream threads before and after and add them up. This would not work in a production system, because other threads might also run parallel streams at the same time. But for us it is "good enough". Another approach would be to set the java.util.concurrent.ForkJoinPool.common.threadFactory system property and to then capture all the threads that are working in the parallel streams.

import java.lang.management.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.stream.*;

public class TimeMeasurer {
    public static void main(String... args) {
        for (int i = 0; i < 10; i++) {
            test(MathRandomComparison::main);
        }
    }

    private static void test(Runnable task) {
        // find all the thread ids of the parallel stream threads
        var parallelism = ForkJoinPool.getCommonPoolParallelism();
        var phaser = new Phaser(parallelism);
        var threads = IntStream.range(0, parallelism)
                .parallel()
                .mapToObj(i -> {
                    phaser.arriveAndAwaitAdvance();
                    return Thread.currentThread();
                })
                .collect(Collectors.toUnmodifiableSet());

        var startCpuTimes = threads.stream()
                .collect(Collectors.toMap(Function.identity(),
                        TimeMeasurer::getThreadCpuTime));
        var realTime = System.nanoTime();

        task.run();

        realTime = System.nanoTime() - realTime;
        var cpuTimes = startCpuTimes.entrySet().stream()
                .mapToLong(entry -> {
                    long start = entry.getValue();
                    long end = getThreadCpuTime(entry.getKey());
                    return end - start;
                })
                .sum();
        System.out.printf("realTime = %dms, cpuTimes = %dms%n",
                realTime / 1_000_000,
                cpuTimes / 1_000_000);
    }

    private static final ThreadMXBean tmb =
            ManagementFactory.getThreadMXBean();

    private static long getThreadCpuTime(Thread thread) {
        return tmb.getThreadCpuTime(thread.threadId());
    }
}

We see that using ThreadLocalRandom.current().nextDouble() is a lot faster than Math.random(). However, ThreadLocalRandom is still subclassed from java.util.Random. In Java 17, they introduced a new interface RandomGenerator, which would allow us to plug in different random number generators. It all starts with the RandomGeneratorFactory, which also displays what attributes the algorithm will have (splittable, stochastic, jumpable, etc.) There are quite a few shipped as part of standard Java:

import java.lang.reflect.*;
import java.util.*;
import java.util.random.*;
import java.util.stream.*;

public class ShowGenerators {
    public static void main(String... args) {
        Stream.of(RandomGeneratorFactory.class.getMethods())
                .filter(method -> method.getName().startsWith("is"))
                .sorted(Comparator.comparing(Method::getName))
                .forEach(ShowGenerators::printAttributeDetails);
    }

    private static void printAttributeDetails(Method method) {
        System.out.println(method.getName() + ":");
        RandomGeneratorFactory.all()
                .filter(factory -> {
                    try {
                        return (boolean) method.invoke(factory);
                    } catch (ReflectiveOperationException e) {
                        throw new IllegalStateException(e);
                    }
                })
                .map(RandomGeneratorFactory::create)
                .map(Object::getClass)
                .map(Class::getSimpleName)
                .sorted()
                .map("\t%s"::formatted)
                .forEach(System.out::println);
    }
}

When we run this code, we see:

isArbitrarilyJumpable:
isDeprecated:
isHardware:
isJumpable:
	Xoroshiro128PlusPlus
	Xoshiro256PlusPlus
isLeapable:
	Xoroshiro128PlusPlus
	Xoshiro256PlusPlus
isSplittable:
	L128X1024MixRandom
	L128X128MixRandom
	L128X256MixRandom
	L32X64MixRandom
	L64X1024MixRandom
	L64X128MixRandom
	L64X128StarStarRandom
	L64X256MixRandom
	SplittableRandom
isStatistical:
	L128X1024MixRandom
	L128X128MixRandom
	L128X256MixRandom
	L32X64MixRandom
	L64X1024MixRandom
	L64X128MixRandom
	L64X128StarStarRandom
	L64X256MixRandom
	Random
	SplittableRandom
	Xoroshiro128PlusPlus
	Xoshiro256PlusPlus
isStochastic:
	SecureRandom
isStreamable:
	L128X1024MixRandom
	L128X128MixRandom
	L128X256MixRandom
	L32X64MixRandom
	L64X1024MixRandom
	L64X128MixRandom
	L64X128StarStarRandom
	L64X256MixRandom
	SplittableRandom
	Xoroshiro128PlusPlus
	Xoshiro256PlusPlus

Since ThreadLocalRandom does not have a RandomGeneratorFactory, it is not listed here, but it is similar to SplittableRandom.

We might also ask ourselves what the difference between streamable, splittable, jumpable, etc.? They have are represented by different inner interfaces. Here is an excerpt from RandomGenerator, to give us some idea of what the jumping and leaping is all about. For more information, please refer to JEP 356 and the Javadoc for java.util.random.RandomGenerator.

public interface RandomGenerator {
    /**
     * The {@link StreamableGenerator} interface augments the
     * {@link RandomGenerator} interface to provide methods that
     * return streams of {@link RandomGenerator} objects.
     * Ideally, such a stream of objects would have the property
     * that the behavior of each object is statistically
     * independent of all the others. In practice, one may have
     * to settle for some approximation to this property.
     */
    interface StreamableGenerator extends RandomGenerator {
        Stream<RandomGenerator> rngs();
    }

    /**
     * This interface is designed to provide a common protocol
     * for objects that generate sequences of pseudorandom values
     * and can be <i>split</i> into two objects (the original one
     * and a new one) each of which obey that same protocol (and
     * therefore can be recursively split indefinitely).
     */
    interface SplittableGenerator extends StreamableGenerator {
        SplittableGenerator split();
    }

    /**
     * This interface is designed to provide a common protocol
     * for objects that generate pseudorandom values and can
     * easily <i>jump</i> forward, by a moderate amount (ex.
     * 2<sup>64</sup>) to a distant point in the state cycle.
     */
    interface JumpableGenerator extends StreamableGenerator {
        void jump();
        double jumpDistance();
        RandomGenerator copyAndJump();
    }

    /**
     * This interface is designed to provide a common protocol
     * for objects that generate sequences of pseudorandom values
     * and can easily not only jump but also <i>leap</i> forward,
     * by a large amount (ex. 2<sup>128</sup>), to a very distant
     * point in the state cycle.
     */
    interface LeapableGenerator extends JumpableGenerator {
        void leap();
        double leapDistance();
        JumpableGenerator copyAndLeap();
    }

    /**
     * This interface is designed to provide a common protocol
     * for objects that generate sequences of pseudorandom values
     * and can easily <i>jump</i> forward, by an arbitrary
     * amount, to a distant point in the state cycle.
     */
    interface ArbitrarilyJumpableGenerator extends LeapableGenerator {
        void jumpPowerOfTwo(int logDistance);
        void jump(double distance);
        ArbitrarilyJumpableGenerator copyAndJump(double distance);
    }
}  

We also see in the list that the only stochastic implementation is SecureRandom. For cryptographic work, this is AFAIK our only option in Java. It can be quite slow, because it would typically source the randomness from an external source such as /dev/random or even from hardware. On my MacBook, it takes 13 seconds for the sequential stream MathRandomComparison, as opposed to 1.7s for Math.random().

Was there any point in using ThreadLocalRandom for my JCrete 2024 lottery, or was I just showing off? Well, it might be microscopically faster, but not enough to use it. I guess it is just a habit. A more random number generator would have been SecureRandom. Either way, we only had 12 extra seats to give away. We are quite crowded this year, because the venue is being renovated and thus we don't have access to as many rooms.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive