Quiz yourself: Deserialization of Java enum types and records

Whenever code running in a JVM refers to a particular enum value, execution cannot proceed unless that enum value has been initialized.

Imagine you are given the following enum and record:

enum Gender {

  MALE("M"), FEMALE("F"), OTHER;

  Gender() {

    System.out.print("Gender ");

  }

  Gender(String s) {

    System.out.print("GenderS ");

  }

}

record Person(int age, String name, Gender g) implements Serializable {

  Person() {

    this(0, "", Gender.OTHER);

    System.out.print("Person ");

  }

  Person {

    System.out.print("PersonC ");

  }

}

Previously an instance of Person was constructed like the following and serialized to a file:

var v = new Person(60, "John Doe", Gender.MALE);

What might be printed to the console when a program deserializes the contents of the file mentioned above? Choose two.

A. Gender PersonC Person

B. Gender PersonC

C. PersonC Person

D. PersonC

E. Gender Gender Gender Person PersonC

F. GenderS GenderS Gender Person PersonC

G. GenderS GenderS Gender PersonC

Answer. This question investigates the mechanisms of deserialization for both enum types and records.

When a record is deserialized, each of the attributes—in this case the age, name, and gender attributes—must be deserialized to their respective objects or values first. (Note that the age primitive will not create an object.) These attributes are then passed to the canonical constructor of the record. Note that this behavior with records is quite different from deserializing instances of normal classes. No output is printed in handling the int age and the String name attributes, but it’s possible that output might be printed for Gender. You should look at this first.

Whenever code running in a JVM refers to a particular enum value, execution cannot proceed unless that enum value has been initialized. In most cases, the very first reference to one of these values will require several steps to be performed: class loading, class linking, and class preparation. Those three steps must happen in the order listed.

It’s fairly unusual for developers to notice the fact that these steps are separate, but that really doesn’t matter. Class preparation is the step that performs static initialization, and therefore it’s the step that creates the values of the enum itself. This quiz question is unaffected by the earlier steps, so the following discussion will consider the enum to be fully prepared, ignoring the fact that that’s actually the last of several steps. (If you’re interested in this, you can find more in section 12.2 and section 12.3 of the Java Language Specification, which in turn refer to the Java Virtual Machine Specification.)

For this question, you need to know three things.

◉ An attempt to deserialize an object that contains a field of an enum type will make a reference to an enum value.

◉ Any reference to an enum value requires the enum class to be fully prepared.

◉ Therefore, the enum must have been fully prepared—complete with the initialization of all the enum’s constants—before deserialization can proceed.

In view of the above, there are now two distinct possibilities.

First, suppose that at the moment when an instance of Person is deserialized, the enum has not been fully prepared. In this case, it will be necessary to perform that preparation before Person can proceed with deserialization. That initialization includes instantiating all three of the enum’s values. In this situation, expect the three instances to be initialized using their appropriate constructors. (Remember this is the initialization process, not deserialization itself, that is causing this behavior.) So, in this situation, you will see GenderS GenderS Gender as the output, preceding any output referring to Person.

By contrast, if the Gender type has been fully prepared before the moment when an instance of Person is deserialized, the three instances already exist, and no further constructor behavior will be invoked for the Gender type. In such a situation, no messages related to Gender will be output by the deserialization process.

Once the enum is fully prepared, deserialization of the record type can proceed; note that record types differ from other classes in how this happens. A particular difference is that the canonical constructor for a record type is invoked to perform the initialization of the newly allocated object. By contrast, regular serializable classes do not have any constructor invoked, nor is any of the normal instance initialization of the serializable class itself run. (Note, however, that nonserializable parent types will have their default constructors executed during deserialization.)

Given that the canonical constructor is invoked, you will see the message PersonC printed as output. Note that in this case, the canonical constructor is presented in the compact form whereas the argument list is omitted, as is the code that initializes the fields of the record.

Because you might or might not see GenderS GenderS Gender, and you will see PersonC in the output, the two valid answers are

PersonC

GenderS GenderS Gender PersonC

These match options D and G, which tells you that those are the correct options and, by elimination, the other options are incorrect.

If you want to dive more deeply into the serialization process, it is, of course, in the Java specification. See the section that describes the process as it relates to records. In particular, the documentation notes the following:

During deserialization, if the local class equivalent of the specified stream class descriptor is a record class, then first the stream fields are read and reconstructed to serve as the record’s component values; and second, a record object is created by invoking the record’s canonical constructor with the component values as arguments…

 

The process related to enums is documented in this section of the Java specification, which notes

To deserialize an enum constant, ObjectInputStream reads the constant name from the stream; the deserialized constant is then obtained by calling the java.lang.Enum.valueOf method, passing the constant’s enum type along with the received constant name as arguments.

 

Notice that the enum deserialization process does not instantiate the values of the enum unless, by necessity, the static initialization process must be completed to complete the deserialization.

As a side note, the descriptions above touched on the idea that there are several steps on the way to class preparation. Most JVMs will perform these steps lazily, simply ensuring that a class is prepared before it’s actually needed. The exact details can vary from one JVM to the next even if the behavior of the developer’s code conforms to the expectations listed in the Java specification.

This lazy approach can be quite beneficial. For example, consider a program with a help system that is built with many classes that are unique to it. If the help system is never used during an execution of that program, those classes might not be needed, and they might never be loaded at all. Further, even if a class is loaded, it might not need to be prepared. Either of these situations can save memory.

To see how this works, try building the following code and observing at what point in the process the MyLazySingleton class is prepared. (Remember that preparation relates to the static initialization.)

class MyLazySingleton {

  static {

    System.out.println("preparing MyLazySingleton");

  }

  private static final MyLazySingleton singleton =

    new MyLazySingleton();

  private MyLazySingleton() {

    System.out.println("instantiating MyLazySingleton");

  }

  public static MyLazySingleton get() {

    return singleton;

  }

}

public class TryStuff {

  public static void main(String[] args) {

    System.out.println("Starting");

    MyLazySingleton mls = null;

    System.out.println("mls variable initialized to null");

    Class<?> cl = MyLazySingleton.class;

    System.out.println("MyLazySingleton.class evaluated.");

    mls = MyLazySingleton.get();

    System.out.println("singleton retrieved");

  }

}

If you run this code under a tracing tool, you’ll probably notice that the file myclasspath/packagename/MyLazySingleton.class is read during the reference to the java.lang.Class object MyLazySingleton.class. However, you’ll also see that the static initialization and, with it, the instantiation of the single instance of MyLazySingleton, does not occur until the code invokes MyLazySingleton.get().

Conclusion. The correct answers are options D and G.

Source: oracle.com

Continue reading

TruffleRuby on OCI Container Instances

Elegance at Speed

Ruby is one of my favourite programming languages. I really appreciate how expressive it is, how productive (and how much fun) it makes development.

Unfortunately Ruby has a reputation for being slow compared to other languages such as JavaScript.

While the performance of the default Ruby interpreter has improved, it still hasn't had the engineering investment that goes into V8.

Continue reading

Quiz yourself: Verifying the operation of stinky Java code

What do you do when the certification test shows you deliberately terrible code?

Your colleague is working on an application that analyzes statistics for vehicles of different makes and models. A business rule requirement is that each car instance in the application must have a unique manufacturing year; creating a second instance of a vehicle with the same year must fail.

The Car class created by the colleague is as follows:

Copy code snippet

Copied to ClipboardError: Could not CopyCopied to ClipboardError: Could not Copy

public class Car {

  Integer year;

  String make;

  String model;

  List<Integer> existingYears = new ArrayList<>();

  public Car(Integer year, String make, String model) {

    this.year = year;

    this.make = make;

    this.model = model;

    existingYears.add(year);

    checkYear(year);

  }

  void checkYear(Integer year) {

    for (int i=0; i < existingYears.size()-1; i++ ) {

      if (existingYears.get(i).equals(year)) {

        throw new IllegalArgumentException("Duplicated year !");

      }

    }

  }

}

public class Car {

  Integer year;

  String make;

  String model;

  List<Integer> existingYears = new ArrayList<>();

  public Car(Integer year, String make, String model) {

    this.year = year;

    this.make = make;

    this.model = model;

    existingYears.add(year);

    checkYear(year);

  }

  void checkYear(Integer year) {

    for (int i=0; i < existingYears.size()-1; i++ ) {

      if (existingYears.get(i).equals(year)) {

        throw new IllegalArgumentException("Duplicated year !");

      }

    }

  }

}

You wonder if the business constraint is properly implemented and decide to test the code using the following code fragment:

new Car(2018, "Honda", "Civic"); // line n1

new Car(2021, "Hyundai", "Accent"); // line n2

new Car(2018, "Ford", "Expedition"); // line n3

Which statement is true? Choose one.

A. The test code runs without throwing an exception.

B. Line n1 will cause IllegalArgumentException.

C. Line n1 will cause IndexOutOfBoundsException.

D. Line n3 will cause IllegalArgumentException.

E. Line n2 will cause IndexOutOfBoundsException.

Answer. This example is perhaps not code you’d be proud of, but you didn’t write it, so there’s no need for embarrassment here.

Look at the code presented and notice that it seems the intention is roughly as follows:

◉ For each call to the constructor, add the proposed list to a list called existingYears.

◉ Call the method checkYear, which performs two things. First it determines if that year has been used before and, if it has, it throws an IllegalArgumentException.

The root problem here is that the existingYears list is created as an instance member of a Car object, and therefore every Car object has a List of its own. Consequently, the years in which other Car objects were created will not be found in each List. The code does not work as intended and will not prevent two separate instances of Car from having the same year value.

If instead the existingYears field carried the static modifier, only one instance List would exist in the program. In that case, the comparison would check the current car’s year with those seen before and line n3 would throw an IllegalArgumentException. That change would make option D correct. But since that wasn’t done, option D is incorrect.

You might notice that the current car’s year is added to the list before the check is run. If you fail to pay close attention to the control of the loop that searches through the list, you might expect that an exception would be thrown for every new car, based on an expected collision with its own year. That would lead you to believe that the code would throw an IllegalArgumentException for any and all attempts to instantiate a Car. In that situation, the first exception would presumably prevent further execution, and you would expect an exception at line n1. However, a more thorough investigation shows that the loop stops before the last item is checked, which is why option B is incorrect.

Notice the following test in the loop:

i < existingYears.size()-1

Because the size value is reduced by one, the code would ignore the last item in the list. That item will be the current car’s year, so the feared collision would not occur. Further, because existingYears is an instance field, the list’s size in the checkYear method is always 1, and the body of the loop never executes at all.

Two of the options suggest that an IndexOutOfBoundsException might be thrown. However, as just noted, the size of the list is always 1 when the checkYear method executes, and the body of the loop will never execute. No code outside that loop attempts to access data from the list using an index; therefore, no code that could possibly throw an IndexOutOfBoundsException will ever be executed. From this you can conclude that options C and E are incorrect.

From the observations above, you can conclude that no exceptions are thrown, and option A must be correct.

Now that the answer has been determined, here are some of the least pleasant aspects of the code—besides the fact that it doesn’t work.

◉ Even though the code for avoiding a collision with the current car’s year is functionally correct, if an attempt is made to add a car that has a duplicate year, existingYears will contain the same year twice. While this would not cause errors in the code shown so far, unexpected behaviors such as this are confusing to programmers trying to make sense of things later, both when they are reading code and when they are debugging. It’s also common for this sort of situation to lead to bugs later when the peculiarity is not thoroughly understood by all. It would be far better to add the year only after it has been approved.

◉ Creating any object with nonprivate mutable fields is generally unwise. It allows changes to be made by any code in the same package. If such changes are made without understanding the implications and, thereby violating some consistency rule pertaining to the data, it’s easy to cause bugs that are hard to track down, especially because such a large amount of code (the entire package or more) might have been responsible for the change.

◉ Checking to see if a Collection contains a given object should be done using the contains method. It’s immediately and unambiguously clear what this method does. By contrast, writing a loop describing how to perform the action leaves the programmer who is reading the code with the responsibility for working out what the code is intended to achieve. Generally speaking, it’s preferable that code have a more declarative nature and a less imperative one. Of course, to be able to use the contains method, you must first ensure that the current car’s year is not added before validation.

◉ Iterating lists using the traditional C-style for loop to control an index for accessing list elements should be avoided. Some lists in Java’s collections (typically those with array backing) iterate tolerably efficiently this way, but if the implementation changes to use a different structure (such as a LinkedList), the resulting efficiency will be relatively or exceedingly poor. If possible, give any data structure the chance to perform its own iteration, since the programmer who created that structure should know best how to iterate the elements efficiently. Instead of using an index-counting loop such as the C-style loop, use Java’s enhanced for loop or extract an Iterator (or perhaps ListIterator, if the situation calls for it) and use that.

Conclusion. The correct answer is option A.

Source: oracle.com

Continue reading

Pseudorandom numbers in Java, Part 2: Randomness with Java 17

When your applications need random numbers, you have several excellent algorithmic options.

Java 17 introduced significant changes to the platform’s pseudorandom number generation capabilities. The first article in this series, “Pseudorandom numbers in Java, Part 1: The Background,” offers a discussion of pseudorandom number generators (PRNGs) and how they work. This article discusses the changes made to PRNGs in Java 17.

Random number generation was perhaps not given quite enough love in early releases of Java. This inspired a Wikipedia discussion of poor-quality PRNGs that noted

As an illustration, consider the widely used programming language Java. Up until 2020, Java still relied on a linear congruential generator (LCG) for its PRNG, which is of low quality…

Developers have been able to choose between several random generators in Java. The best-known is java.util.Random; another well-known interface, java.lang.Math.random(), simply delegates to java.util.Random.nextDouble().

Java 17 introduced a new interface, java.util.random.RandomGenerator, to consolidate the implementations of existing and new random number generators. The new code is in the java.util.random package, which is also new in Java 17. RandomGenerator has the same methods as java.util.Random, including both the legacy methods and the Java 8 methods that generate Java streams of randoms of various types. For example, for double values, the new interface contains the methods described in Listing 1.

Listing 1. Methods from RandomGenerator with double and DoubleStream values

public default double nextDouble();

    public default double nextDouble(double min);

    public default double nextDouble(double min, double max);

    public default DoubleStream doubles();

    public default DoubleStream doubles(double min, double max);

    public default DoubleStream doubles(long count);

    public default DoubleStream doubles(long count, double min,

        double max);

    public default double nextGaussian();

    public default double nextGaussian(double min, double max);

    public default double nextExponential();

There are similar methods for int and long numeric types. Raw bytes and booleans do not get the same treatment; there is only void nextBytes(byte[]) and boolean nextBoolean().

The legacy classes java.util.Random and java.util.SecureRandom were backfitted to implement this interface, so if you switch the declaration to the new interface, the legacy implementations become interchangeable with the new generators. The legacy classes’ algorithms were not improved, however, to avoid breaking Java’s ever-important backwards compatibility. In fact, given the same seed, the java.util.Random class in both Java 11 and Java 17 will output exactly the same sequence.

In the following example, Random5 is a modified version of the random histogram program shown in Part 1 of this series, which starts with a fixed seed. It should (and does) produce the same stream with both implementations. The withjava command is a script of my own that I use to run Random5 on a particular version of Java.

$ withjava 11 java -Xms4G -Xmx4G Random5.java

Using JAVA_HOME=/usr/local/jdk-11 java -Xms4G -Xmx4G Random5.java in /home/ian/git/Randomness/src/main/java/com/darwinsys/random/15vs17

First 5 random ints are:

1553932502 -2090749135 -287790814 -355989640 -716867186

Generating 100000000 randoms using Random

Generating randoms took 6640 mSec

$ withjava 17 java -Xms4G -Xmx4G Random5.java

Using JAVA_HOME=/usr/local/jdk-17 java -Xms4G -Xmx4G Random5.java in /home/ian/git/Randomness/src/main/java/com/darwinsys/random/15vs17

First 5 random ints are:

1553932502 -2090749135 -287790814 -355989640 -716867186

Generating 100000000 randoms using Random

Generating randoms took 7448 mSec

$

In my tests, over multiple runs, the Java 17 implementation was consistently 10% to 12% slower than the Java 11 version, while generating exactly the same outputs.

SecureRandom has always been about generating better random numbers for use in security-related software. The implementation is intended to meet the requirements specified in section 4.9.1 of the US National Institute of Standards and Technology (NIST) FIPS PUB 140-2, “Security Requirements for Cryptographic Modules,” and the Internet Engineering Task Force (IETF) RFC 4086, “Randomness Requirements for Security.”

Java has two other legacy RandomGenerator implementations: ThreadLocalRandom (from Java 1.7) and SplittableRandom (from Java 1.8). These are listed in the Java 17 RandomGenerator documentation. Of these, ThreadLocalRandom is meant for use in multithreaded designs, and the SplittableRandom class is designed for use in fork/join algorithms where each split should have its own independent PRNG. These two do not meet the security requirements mentioned above; SecureRandom should be used when security is needed.

It turns out that most of the methods of the RandomGenerator interface have default methods coded in terms of nextLong() (the only abstract method in the interface); a complete (but not very usable) implementation of this interface is shown in Listing 2.

Listing 2. A minimal implementation of Java 17’s RandomGenerator

public class CrappyRandom implements RandomGenerator {

    // The attacker has a hard time guessing the

    // exact nanosecond at which this is initialized.

    private long x0 = (21 * System.nanoTime()) & 0xffff;

    private long a = (long) Math.pow(2,7) + 1;

    private long c = 1024;   // The increment

    private long mod = (long) Math.pow(2,32);  // The modulus

    private long lastVal = x0;

    public void setKnuthBadParams() {

        // As per Knuth , to get 7 6 9 0, 7 6 9 0, ...

        mod = 10;

        lastVal = x0 = a = c = 7;

    }

    @Override

    /**

     * This is a crude implementation just to get going.

     * Tests will reveal its quality (or lack thereof).

     */

    public long nextLong() {

        return lastVal = (a * lastVal + c) % mod;

    }

}

Important note: Please do not use this sample code for anything! It produces terribly bad random numbers. It is just here to show that if you can write a decent algorithm, the interface will massage its results to provide all the other types needed to complete the interface.

To avoid the poor behavior of LCG algorithms used on their own, Java 17 introduces a new class of random number algorithms called LXM. The name stands for “LCG + XOR + Mix,” representing the three stages: an LCG, an XOR subgenerator, and a mixer to combine them. The first two stages are based on the best-available LCG values and an exclusive-or (XOR) function; this combination has been shown to provide the best results.

To avoid creating dozens of new public classes for this family of algorithms, Java 17 introduces the new RandomGeneratorFactory class, which allows you to create an implementation of a particular algorithm, as follows:

String algorithm = "L64X1024MixRandom";

RandomGenerator genx = RandomGeneratorFactory.of(algorithm).create();

genx.doubles(1000).doSomethingWithValues();

These algorithms are implemented by nonpublic classes with the same names in the private jdk.random package. For example, the snippet above assigns genx to an instance of jdk.random.L64X1024MixRandom. The list of new algorithms is

• L32X64MixRandom
• L32X64StarStarRandom
• L64X128MixRandom
• L64X128StarStarRandom
• L64X256MixRandom
• L64X1024MixRandom
• L128X128MixRandom
• L128X256MixRandom
• L128X1024MixRandom
• Xoshiro256PlusPlus
• Xoroshiro128PlusPlus

The RandomGenerator interface includes a getDefault() default method, which, as expected, returns a usable implementation of the interface without specifying too much about its behavior. In Java 17 on my system, it returns a jdk.random.L32X64MixRandom, but that is not documented and should not be counted on. However, note that getDefault() will be a decent choice unless you need one of the others.

RandomGeneratorFactory also has an all() method that returns a stream of all the providers. Running my simple ShowAllGenerators program displays the following:

Group Name                          Period

      LXM L128X1024MixRandom          Infinity

      LXM L128X128MixRandom         1.15792e+77

      LXM L128X256MixRandom         3.94020e+115

      LXM L32X64MixRandom           7.92282e+28

      LXM L64X1024MixRandom           Infinity

      LXM L64X128MixRandom          6.27710e+57

      LXM L64X128StarStarRandom     6.27710e+57

      LXM L64X256MixRandom          2.13599e+96

   Legacy Random                    2.81475e+14

   Legacy SecureRandom                 0.00000

   Legacy SplittableRandom          1.84467e+19

  Xoshiro Xoshiro256PlusPlus        1.15792e+77

Xoroshiro Xoroshiro128PlusPlus      3.40282e+38

The few algorithms that show Infinity for their period in the output aren’t truly infinite, of course, but they are too large to display in a double. (The RandomGeneratorFactory.period() method actually returns a BigInteger, but I displayed them as double to show the scale instead of a vast run of digits.)

If you know which algorithm you want, you can use the of method, as in the following:

RandomGenerator random = RandomGenerator.of("L128X128MixRandom");

Choosing the best algorithm

The following is excerpted verbatim from the documentation for the java.util.random package, which explains the trade-offs clearly and concisely. So there’s no reason for me to paraphrase it.

There are three groups of random number generator algorithm [sic] provided in Java: the Legacy group, the LXM group, and the Xoroshiro/Xoshiro group.

The legacy group includes random number generators that existed before JDK 17: Random, ThreadLocalRandom, SplittableRandom, and SecureRandom. Random (LCG) is the weakest of the available algorithms, and it is recommended that users migrate to newer algorithms. If an application requires a random number generator algorithm that is cryptographically secure, then it should continue to use an instance of the class SecureRandom.

The algorithms in the LXM group are similar to each other. The parameters of each algorithm can be found in the algorithm name. The number after “L” indicates the number of state bits for the LCG subgenerator, and the number after “X” indicates the number of state bits for the XBG subgenerator. “Mix” indicates that the algorithm uses an 8-operation bit-mixing function; “StarStar” indicates use of a 3-operation bit-scrambler.

The algorithms in the Xoroshiro/Xoshiro group are more traditional algorithms (see David Blackman and Sebastiano Vigna, “Scrambled Linear Pseudorandom Number Generators,” ACM Transactions on Mathematical Software, 2021); the number in the name indicates the number of state bits.

For applications (such as physical simulation, machine learning, and games) that do not require a cryptographically secure algorithm, this package provides multiple implementations of interface RandomGenerator that provide trade-offs among speed, space, period, accidental correlation, and equidistribution properties.

For applications with no special requirements, L64X128MixRandom has a good balance among speed, space, and period, and is suitable for both single-threaded and multi-threaded applications when used properly (a separate instance for each thread).

If the application uses only a single thread, then Xoroshiro128PlusPlus is even smaller and faster, and certainly has a sufficiently long period.

For an application running in a 32-bit hardware environment and using only one thread or a small number of threads, L32X64MixRandom may be a good choice.

For an application that uses many threads that are allocated in one batch at the start of the computation, either a “jumpable” generator such as Xoroshiro128PlusPlus or Xoshiro256PlusPlus may be used, or a “splittable” generator such as L64X128MixRandom or L64X256MixRandom may be used.

For an application that creates many threads dynamically, perhaps through the use of spliterators, a “splittable” generator such as L64X128MixRandom or L64X256MixRandom is recommended. If the number of generators created dynamically may be very large (millions or more), then using generators such as L128X128MixRandom or L128X256MixRandom, which use a 128-bit parameter rather than a 64-bit parameter for their LCG subgenerator, will make it much less likely that two instances use the same state cycle.

For an application that uses tuples of consecutively generated values, it may be desirable to use a generator that is k-equidistributed such that k is at least as large as the length of the tuples being generated. The generator L64X256MixRandom is provably 4-equidistributed, and L64X1024MixRandom is provably 16-equidistributed.

For applications that generate large permutations, it may be best to use a generator whose period is much larger than the total number of possible permutations; otherwise it will be impossible to generate some of the intended permutations. For example, if the goal is to shuffle a deck of 52 cards, the number of possible permutations is 52! (52 factorial), which is larger than 2225 (but smaller than 2226), so it may be best to use a generator whose period is at least 2256, such as L64X256MixRandom or L64X1024MixRandom or L128X256MixRandom or L128X1024MixRandom. (It is of course also necessary to provide sufficiently many seed bits when the generator is initialized, or else it will still be impossible to generate some of the intended permutations.)

There are other interesting methods in the factory class; running javap (or looking at the documentation) reveals them all.

$ javap java.util.random.RandomGeneratorFactory

Compiled from "RandomGeneratorFactory.java"

public final class RandomGeneratorFactory<T extends RandomGenerator> {

  static <T extends RandomGenerator> T of(String, Class<T>) throws IllegalArgumentException;

  static <T extends RandomGenerator> RandomGeneratorFactory<T> factoryOf(String, Class<T>) throws IllegalArgumentException;

  public static <T extends RandomGenerator> RandomGeneratorFactory<T> of(String);

  public static RandomGeneratorFactory<RandomGenerator> getDefault();

  public static java.util.stream.Stream<RandomGeneratorFactory<RandomGenerator>> all();

  public String name();

  public String group();

  public int stateBits();

  public int equidistribution();

  public java.math.BigInteger period();

  public boolean isStatistical();

  public boolean isStochastic();

  public boolean isHardware();

  public boolean isArbitrarilyJumpable();

  public boolean isJumpable();

  public boolean isLeapable();

  public boolean isSplittable();

  public boolean isStreamable();

  public boolean isDeprecated();

  public T create();

  public T create(long);

  public T create(byte[]);

}

$

The informational methods (such as isHardware() and isJumpable()) are in the RandomGeneratorFactory but not in the RandomGenerator instances themselves. The full list of informational methods is shown in Table 1.

Table 1. Informational methods in RandomGeneratorFactory

Name	Meaning
isStatistical()	Returns true if the generated values are computed using an algorithm that is statistically deterministic.
isStochastic()	Returns true if the generated values are computed using some external or entropic input(s).
isHardware()	Returns true if the random number generator (RNG) is implemented as a hardware random number generator (HRNG).
isJumpable()	Returns true if the RNG can jump ahead in the cycle of random data.
isArbitrarilyJumpable()	Returns true if the RNG can jump arbitrarily far into the cycle of data.
isLeapable()	Returns true if the RNG can jump to a very distant point in the cycle.
isSplittable()	Returns true if the RNG can be cloned to make a second generator with the same properties but positioned further in the cycle.
isStreamable();	Returns true if the RNG can output into a Java stream.
isDeprecated()	Returns true if the implementation of RandomGenerator has been marked for deprecation.

Suppose you wanted to determine which RandomGenerator instances are streamable, that is, which can emit random values as a stream.

// From ShowStreamableGenerators

RandomGeneratorFactory.all()

    .filter(rgFactory -> rgFactory.isStreamable())

    .map(rgFactory-> rgFactory.name())

    .sorted()

    .forEach(System.out::println);

As you might expect, all the new PRNGs are streamable, and all the legacy ones are not.

Testing randomness

Two of the main test suites for RNGs are TestU01 and PractRand.

TestU01, by Pierre L’Ecuyer and Richard Simard at the University of Montreal, includes a 200-page user manual that is highly recommended for those who are mathematically oriented; it’s useful even if you don’t plan to use the test suite. The authors note the following, in passing:

There is no universal test or battery of tests that can guarantee, when passed, that a given generator is fully reliable for all kinds of simulations. Passing many tests improves one’s confidence in the RNG, although it never proves that the RNG is foolproof. In fact, no RNG can pass every conceivable statistical test. One could say that a bad RNG is one that fails simple tests, and a good RNG is one that fails only very complicated tests that are extremely hard to find or impractical to run.

The LXM algorithms have been tested against both TestU01 and PractRand, and they passed. The work for Java 17 was done under JEP 356, Enhanced pseudo-random number generators, which contains more information on the choices made, the tests performed and passed, and so on.

Performance

If you need only a few random numbers, performance isn’t a big deal. But if you need millions or billions, speed matters. To measure the relative performance of each generator, I wrote a simple timing loop called TimeAllGenerators. I generated 10 million randoms with each generator to get measurable values.

dalai-LAPTOP-random $ java TimeAllGenerators.java | sort -k5n

Generating 10000000 randoms took 55 mSec using SplittableRandom

Generating 10000000 randoms took 56 mSec using Xoroshiro128PlusPlus

Generating 10000000 randoms took 57 mSec using L64X128MixRandom

Generating 10000000 randoms took 57 mSec using L64X128StarStarRandom

Generating 10000000 randoms took 58 mSec using L32X64MixRandom

Generating 10000000 randoms took 59 mSec using Xoshiro256PlusPlus

Generating 10000000 randoms took 63 mSec using L64X1024MixRandom

Generating 10000000 randoms took 65 mSec using L64X256MixRandom

Generating 10000000 randoms took 76 mSec using L128X128MixRandom

Generating 10000000 randoms took 77 mSec using L128X256MixRandom

Generating 10000000 randoms took 89 mSec using L128X1024MixRandom

Generating 10000000 randoms took 207 mSec using Random

Generating 10000000 randoms took 2571 mSec using SecureRandom

As you can see, the legacy implementation java.util.Random takes around four times as long as the more modern algorithms and gives less-reliable randomness. SecureRandom is 10 times slower but gives good randomness for security-based applications. If you need to generate a lot of random numbers, take this into account. If you need only a small number of randoms, any of the generators will do.

Migrating to the new APIs

Should you change to a newer API? Migrate if good random performance and reliability is important. If you are just using one or two random values, it may not be worthwhile. Otherwise, yes; you should migrate.

The first step in migrating would be to change

Random random = new Random();

to

RandomGenerator random = new Random();

Then, at least you are depending on the interface. A better option would be to change to the following:

RandomGenerator random = RandomGenerator.default();

Then, you would be using one of the newer implementations, which is chosen for you.

If you want to ask for a particular implementation, based on the performance figures I generated and on the notes on choosing a generator given previously, use the following:

RandomGenerator random = RandomGenerator.of("L64X1024MixRandom");

Finally, consider moving the code to a streams approach, since you now have a stream-capable random generator. Note that migrating iterative code to streams is a topic for another article. For that, I’ll refer you to Raoul-Gabriel Urma’s article, “Processing data with Java SE 8 streams, Part 1.”

In summary, Java 17 provides a new framework for building multiple implementations of PRNGs that provide a standard interface and whose implementations may more readily be exchanged. While the legacy implementations are not changed and still use LCGs, the new ones use the best-known LCG parameters and combine these with an XOR operation to be more random.

My final advice: For general use, if you want good randomness, use RandomGenerator.default() in new code, and consider migrating to that while maintaining legacy code. For security work, continue to use SecureRandom.

Source: oracle.com

Continue reading

Pseudorandom numbers in Java, Part 1: The Background

Random and pseudorandom numbers are needed for everything from simulations to cryptography. Here’s how they work.

Computing pioneer John von Neumann, who invented one of the first “arithmetical” computer algorithms for pseudorandom numbers, said “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

What is randomness? And how does it relate to Java’s random number generators? Let’s ask the question in context. What is the probability of your winning the top prize in the next national lottery? Lottery ticket buyers must believe that the game is fair, that the winning numbers are in fact chosen randomly, and that each ticket has the same probability of winning. They wouldn’t risk their money if they thought the contest was rigged.

But what exactly is randomness? This article is for software developers who may or may not be mathematics whizzes. To those who are, my apologies for what will, with high probability, be perceived as a lack of precision.

Just for fun, I asked ChatGPT for a definition, and it replied as follows:

Randomness is the quality or state of being unpredictable or lacking a definite pattern or order. In other words, randomness is the absence of predictability or regularity in events or processes. For example, the toss of a coin is a random event because it is impossible to know with certainty whether it will land on heads or tails. Randomness is a fundamental concept in many areas of science and mathematics, and it is often used to model complex systems and to generate random numbers for various purposes.

That’s pretty good. You should expect that lottery numbers will be random, revealing no pattern of any digits appearing more or less frequently than others over the long haul. Random numbers to be used for security purposes must be extremely hard for an aggressor to guess.

There are several measures for testing random number generators. One obvious measurement is speed, that is, how quickly random numbers can be generated. Sometimes an application needs a lot of random numbers, but for the common case of an application needing only one or a few random numbers, speed is irrelevant and outweighed by the main work of the application.

More important and still easy to measure is the randomness or consistency, that is, how reliably the values that are generated are spread throughout the range of possible values. In other words, the generator should generate with equal probability all the possible outcomes. An easy way to measure this is to run a given generator many times and visually examine the distribution. I did this in Java Cookbook. There, a program (Random5) creates a java.util.Random instance and calls its nextDouble() and nextGaussian() methods 100,000 times each. The program then invokes an R script to plot the values, producing the plots in Figure 1.

Figure 1. The values of nextDouble() and nextGaussian()

You’d probably intuitively expect the nextDouble() histogram to be relatively flat (meaning all values were picked equally) and the nextGaussian() plot to approximate a bell curve. You can see that both predictions were fulfilled. You can download and run the code yourself to replicate this.

Randomness is not the only measure of goodness for random number generators. Another measure is predictability, that is, how hard it is for an outsider to figure out what value a given call will yield. Low predictability is a requirement for use in cryptography, as explained in John Graham-Cumming’s blog post on why cryptography requires the generation of random numbers.

When it comes to predictability, the period is a measure of how many generations can be requested before the values begin to repeat. If a random number generator repeats values too quickly, an attacker might be able to guess with reasonable accuracy the values used in the encryption.

Random number generators can also be jumpable, meaning that you should be able to skip forward without disrupting the sequence to a point in time that is equivalent to invoking and discarding a number of operations. Similarly, a leapable algorithm is one that can take a huge step without disrupting the sequence.

Randomness has many uses in general computing. For example, in UNIX-like systems, you can create reasonably secure temporary files using the following command:

someprogram > $ mktemp /tmp/scriptXXXXXXXXX

The mktemp utility program uses a random character generator (and characters are just numbers within the range of the ASCII or UTF-8 character set). The mktemp invocation above creates a file with a hard-to-guess name such as /tmp/scriptogWqMcWOygi, and the file is readable and writable only by the owner. Such files provide a reasonably secure way of creating files in a public directory. Even-better systems also randomize the process id numbers given to each program that is run. This makes it harder for an attacker to anticipate the process id number of an upcoming command—and that, in turn, makes it harder to attack the system.

True random numbers versus pseudorandom numbers

Most computers do not have truly random random numbers, just as they don’t have real real numbers; truly random numbers are computationally expensive (and thus time consuming), and generally they aren’t needed unless, for example, you are running a lottery.

Instead, many applications leverage faster, more efficient software that can generate pseudorandom numbers using a pseudorandom number generator (PRNG).

PRNGs use an algorithm that has a starting value, or seed, and a permutation. The permutation part of a commonly used linear congruential generator (LCG) algorithm is based on the following formula:

Xn+1 = (a * Xn + c) mod m

In that equation, X0 is the seed, and each value is based on the previous value multiplied by a constant a; that result is added to another constant called c; and the result of that taken modulo a third constant, m. What if Xn gets large or even overflows? No problem. Whatever’s left will still result in a nice pseudorandom value. And, in practice, many implementations using the LCG algorithm also use bit masking on subsequent calls to remove some of the bits that are not changing on subsequent calls.

The LCG algorithm is comparable to hashCode(), which generates a seemingly random number, with the current state of the given object being the seed. You’ve probably seen a typical IDE-generated hashCode method, such as the one shown in Listing 1.

Listing 1. Datum class with IDE-generated hashCode

public class Datum {

    long id;

    String name;

    int yearJoined;

    @Override

    public int hashCode() {

        int result = (int) (id ^ (id >>> 32));

        result = 31 * result + (name != null ? name.hashCode() : 0);

        result = 31 * result + yearJoined;

        return result;

    }

    ...

}

In mutable objects, changing the state changes the hashCode() value, permitting you to take the comparison a bit farther, as shown in Listing 2. If you run this program, you’ll see it generates random-looking numbers, but they are not very good ones.

Listing 2. Running hashCode() as a bad random number generator

import java.util.stream.IntStream;

public class DatumHash {

    public static void main(String[] args) {

        Datum d = new Datum(123, "Ian", 1999);

        // Loop by 175 just to get a good range of values

        for (int i = 1; i <= 2020; i+=175) {

            d.setId(2020 % i); // just generate some value here

            d.setYearJoined(i);

            System.out.println(d +" hashCode: "+d.hashCode());

        });

    }

}

It’s Knuth time

A definitive treatment of PRNGs can be found in Donald Knuth’s The Art of Computer Programming, volume 2, chapter 3—particularly section 3.2.1, which devotes 16 pages of mathematical discussion to LCGs. Meanwhile, section 3.2.2 dedicates 12 more pages to other PRNG algorithms.

This material will interest mathematics and computer science majors but may reach over the head of those who are not mathematically oriented. Even those who don’t care should note the following, however. Knuth points out that if you exercise really bad judgment in selecting the values for X0, a, m, and c in the formula shown previously, for example, by setting X0, a, and c all to 7 and setting m to 10, the formula will generate the following series as output:

7 6 9 0 7 6 9 0 7 6 9 0 ...

That series has a repeating period of 4, which is completely useless for most purposes. Let that be a caution to you: Do not implement your own LCG algorithm unless you really know what you’re doing! Instead, use existing generators provided in the JDK. (Note: Choosing better values for the various values takes up quite a bit of Knuth’s discussion, and it remains a problem for developers building PRNGs for production use.)

Another problem for generating useful random numbers is that the seed must come from somewhere. In the rare case where you are testing the random number function itself, you probably want the seed to be fixed (you can feed the seed into the constructor or use the setSeed() call), so that the algorithm will generate the same set of numbers each time you run your test.

However, in production use of a random number function, you want the seed to be…wait for it…random. And that would require the use of yet another random number function, which in turn would require its own random seed from yet another random number function. You can see where this will (or won’t) end.

What about true randomness? Only a process that doesn’t follow a fixed algorithm can generate truly random numbers.

Lava lamps for randomness?

One of the first computer-based true random number generators used Lavarand, a lava lamp set in front of a web cam. A lava lamp contains two nonmiscible liquids—wax and a clear liquid—in a clear upright container. The heat from an incandescent bulb causes the wax to rise, where it cools and then falls, in an endless cycle that is slightly different every time.

The idea behind this is that the flow of the wax blobs would be reasonably random and couldn’t be guessed by people who didn’t have a camera focused on the lamp—and even then, they’d not know exactly which part of the lamp the camera was focused on. Since the patent on the original Lavarand has expired, the methodology can be used by anyone and, in fact, a whole wall of lamps is used by internet backbone carrier Cloudflare to secure traffic on the current internet—really.

Most developers probably don’t have lava lamps or another true random number generation system, but they need a random seed value to start. PRNGs tend to use a source of semirandomness such as the low-order bits of the high-precision system clock, which changes every microsecond or nanosecond, making the value almost impossible to guess.

Some operating systems, such as OpenBSD, calculate randomness (termed entropy) from the keyboard, the time, the arrangement of things in the environment, and so on. Such operating systems save some of this randomness to disk when the computer is shut down, so that even when the operating system first boots up, it already has a good source of entropy. Few other operating systems go that far, yet.

Source: oracle.com

Continue reading

Quiz yourself: Use an Optional object when you might have zero data items

Given the following method

public void printSomething(Optional<Integer> o) {

  var p = o.filter(v -> v == null);

  p.ifPresent(System.out::println);

}

and the code fragment

printSomething(Optional.ofNullable(0));    // line 1

printSomething(Optional.ofNullable(null)); // line 2

What is the result? Choose one.

A. There is no output.

B. One blank line is printed.

C. Two blank lines are printed.

D. 0 is printed and then nothing else.

E. 0 is printed followed by a blank line.

Answer. Using a null pointer to indicate that a data item does not exist can be error prone. Another—typically more robust—way to address the possibility of a data item not existing is to use something such as an array. In Java, an array can contain any number of items, and the array knows how many items it contains. If you write code to process all the elements in the array but the array is empty, you simply process nothing, and no consequential errors will occur.

This idea is formalized in the Optional class that was added in Java 8. An Optional object is a kind of wrapper that contains either zero or one data items. The Optional also provides methods that can apply processing to all the elements in the Optional in a manner comparable to what was just outlined for an array, providing another safe way to handle a missing element. This question investigates the behavior of two methods in the Optional API and one of the methods that can create an Optional instance.

The method Optional.ofNullable creates a new Optional object that either contains the provided argument or, if that argument value is null, is empty. So, line 1 in the code snippet above creates an Optional that contains an autoboxed Integer that has a value of zero. Line 2 creates an Optional object representing emptiness.

The Optional.filter() method is similar to the intermediate operation of the Stream method with the same name. It takes a Predicate as an argument and tests elements with that Predicate. The filter method then returns an Optional based on that algorithm, as follows:

◉ If the Optional was empty, filter() returns the same Optional (which is still empty, of course).

◉ If the object contained in the Optional returns false from the Predicate test, an empty Optional is returned.

◉ Otherwise, the same Optional is returned, which still contains the original value.

The filtering operation in the example looks like the following:

var p = o.filter(v -> v == null);

The Predicate shown above returns true only if the argument value is null. In other words, anytime this Predicate is used in a filter operation on an Optional, the result must be an empty Optional. If the original Optional was not empty, the test fails, resulting in an empty result. If the original Optional was actually already empty, the test is never applied and the filter simply returns the original, unchanged—and still empty—Optional.

From the discussion above, you can deduce that both line 1 and line 2 must have the same effect. Option B suggests that one blank line is printed, which could only happen if lines 1 and 2 had different effects. Similarly, options D and E both hinge on different effects for the two lines. You can therefore deduce that options B, D, and E must be incorrect.

Next, consider the behavior of the Optional.ifPresent() method. This method takes a Consumer as its argument. If the Optional contains a value, the Consumer is invoked with the value of the Optional being passed as the argument. If the Optional is empty, ifPresent does nothing.

At this point, you’ve already established that when the code reaches the point of invoking ifPresent, the Optional is empty regardless of the situation prior to that. This in turn shows that no printing is ever invoked. From that, you can determine that the code produces no output and option A is correct, while option C (which suggests that println is called but with an empty string as an argument) is incorrect.

Conclusion. The correct answer is option A.

Source: oracle.com

Continue reading