Monday, December 5, 2022

Java 20: A Sneak Peek on the Panama FFM API (Second Preview)

The new JEP 434 has just seen daylight and describes the second preview of the ”Foreign Function & Memory API” (or FFM for short) which is going to be incorporated in the upcoming Java 20 release! In this article, we will take a closer look at some of the improvements made from the first preview that debuted in Java 19 via the older JEP 424.


Getting familiar with the FFM

This article assumes you are familiar with the FFM API. If not, you can get a good overview via the  new JEP


Short Summary

Here is a short summary of the FFM changes made in Java 20 compared to Java 19:


  • The MemorySegment and MemoryAddress abstractions are unified (memory addresses are now modeled by zero-length memory segments);

  • MemorySession has been split into Arena and SegmentScope to facilitate sharing segments across maintenance boundaries.

  • The sealed MemoryLayout hierarchy is enhanced to facilitate usage with pattern matching in switch expressions and statements (JEP 433)



MemorySegment

A MemorySegment models a contiguous region of memory, residing either inside or outside the Java heap. A MemorySegment can also be used in conjunction with memory mapping whereby file contents can be directly accessed via a MemorySegment


Some changes were done between Java 19 and Java 20 with respect to the MemorySegment concept. In Java 19, there was a notion named MemoryAddress used for “pointers to memory” and function addresses. In Java 20,  MemorySegment::address returns a raw memory address in the form of a long rather than a MemoryAddress object. Additionally, function addresses are now modeled as a MemorySegment of length zero. This means the MemoryAddress class was dropped entirely.


SegmentScope

All MemorySegment instances need a SegmentScope which models the lifecycle of MemorySegment instances. A scope can be associated with several segments, meaning these segments share the same lifecycle and consequently, their backing resources will be released materially at the same time.


In Java 19, the term MemorySession was used for lifecycles but was also a closeable segment allocator. In Java 20, a SegmentScope is a much more concise, lifecycle-only concept.


Perpetual Global Scope Allocation

Native MemorySegment instances that should live during the entire JVM lifetime can be allocated through the SegmentScope.global() scope (i.e. segment memory associated with this scope will never be released unless the JVM exits). The SegmentScope.global() scope is guaranteed to be a singleton.


Automatic JVM-Managed Deallocation

Native MemorySegment instances  that are managed by the JVM can now be allocated through the SegmentScope.auto() factory:


MemorySegment instances associated with new scopes created via the auto() method are also available to all threads but will be automatically managed by the Java garbage collector. This means segments will be released some unspecified time after the segment becomes unreachable. Thus, segments will be released when they are no longer referenced, just like ByteBuffer objects allocated via the ByteBuffer.allocateDirect() method. 


This allows a convenient create-and-forget scheme but also implies giving up exact control of when potentially large segments of off-heap memory are actually released.


Deterministic User-Managed Deallocation via Arena

Native MemorySegment instances can also be managed directly and deterministically via the Arena factory methods:


  • Arena.openConfined()


  • Arena.openShared()


MemorySegment instances associated with an openConfined() Arena will only be available to the thread that first invokes the factory method and the backing memory will exist merely until the Arena::close method is invoked (either explicitly or by participating in a try-with-resources clause) whereafter accessing any segments associated with the closed Arena will throw an exception. 


MemorySegment instances associated with an openShared() Arena behave in a similar way except they are available to any thread. Another difference is when arenas of this type are closed, the JVM has to make sure no other threads are in a critical section (to ensure memory addressing integrity while maintaining performance) and so, closing a shared Arena is slower than closing a confined Arena.


It should be mentioned that forgetting to invoke the Arena::close method means; any and all memory associated with the Arena will remain allocated until the JVM exits. There are no safety nets here and so, a try-with-resource fits nicely for short-lived arenas as it guarantees all the resources of an  Arena are released, no matter what.


An Arena can also be used to co-allocate segments in the same scope. This is convenient when using certain data structures with pointers. For example, a linked list that can be dynamically grown by creating new segments when the old ones become full. The referencing pointers are guaranteed to remain valid as all the participating segments are associated with the same scope. Only when the common scope is closed, all the underlying segment resources can be released.


In Java 19, the MemorySession was similar to the Java 20 Arena but crucially, an Arena is not a lifecycle but is now instead associated with a lifecycle (accessible via the Arena::scope method). 



MemoryLayout and Pattern Matching

In FFM, a MemoryLayout can be used to describe the contents of a MemorySegment. If we, for example, have the following C struct declaration:


typedef struct Point {

    int x,

    int y

} Points[5];


Then, we can model it in FFM like this:


SequenceLayout pints = MemoryLayout.sequenceLayout(5,

    MemoryLayout.structLayout(

        ValueLayout.JAVA_INT.withName("x"),

        ValueLayout.JAVA_INT.withName("y")

    )

).withName("Points");



Pattern matching (as recently described in JEP 427) will arguably be one of the largest improvements to the Java language ever made and of a similar dignity as generics (appearing in Java 5) and lambdas/functions (appearing in Java 8). In Java 20, the sealed hierarchy of the MemorySegment was overhauled to provide a pattern-matching-friendly definition. This allows, for example,  uncomplicated and concise rendering of memory segments as shown hereunder:


default String render(MemorySegment segment,

                      long offset,

                      ValueLayout layout) {


    return layout.name().orElse(layout.toString())+ " = " +
    switch (layout) {

        case OfBoolean b -> Boolean.toString(segment.get(b, offset));

        case OfByte b -> Byte.toString(segment.get(b, offset));

        case OfChar c -> Character.toString(segment.get(c, offset));

        case OfShort s -> Short.toString(segment.get(s, offset));

        case OfInt i -> Integer.toString(segment.get(i, offset));

        case OfLong l -> Long.toString(segment.get(l , offset));

        case OfFloat f -> Float.toString(segment.get(f, offset));

        case OfDouble d -> Double.toString(segment.get(d, offset));

        case OfAddress a -> 

            "0x"+Long.toHexString(segment.get(a, offset).address());

    };

}



The code above can relatively easily be expanded with cases for the complete MemoryLayout sealed hierarchy including recursive calls for the types SequenceLayout, GroupLayout and for the more simple PaddingLayout.


As a side note, the javadocs in Java 20 will likely come with a pattern-matching nudger in the form of a graphic rendering of the sealed hierarchy for selected classes (i.e. those tagged with “@sealedGraph”). Here is how the graph for  MemoryLayout might look like once Java 20 hits GA:



As can be seen, the graph and the pattern-matching switch example above correspond and the cases are exhaustive with respect to the ValueLayout type.


Other Improvements

Java 20 will also see many other improvements in the FFM API, some of which are summarized hereunder:


  • Reduced API surface, making it easier to learn and understand the new API

  • Improved documentation

  • Ability to access thread local variables in native calls, including errorno


Show Me the Code!

Here are some examples of creating MemorySegment instances for various purposes:


Allocate a 1K MemorySegment for the Entire Duration of an Application’s Lifetime


public static final MemorySegment SHARED_DATA = 

        MemorySegment.allocateNative(1024, MemoryScope.global());



Allocate a Small, 32-byte Temporary  MemorySegment not Bothering When the Underlying Native Memory is Released


var seg = MemorySegment.allocateNative(32, MemoryScope.auto());



Co-allocate a New MemorySegment with an Existing Segment


var coSegment = MemorySegment.allocateNative(32, seg.scope());

// Store a pointer to the original segment

coSegment.set(ValueLayout.ADDRESS, 0, seg);



Allocate a Large, 4 GiB Temporary  MemorySegment Used by the Current Thread Only


try (var arena = Arena.openConfined()) {

    var confined = arena.allocate(1L << 32);

    use(confined);

} // Memory in "confined" is released here via TwR



Allocate a large, 4 GiB temporary  MemorySegment to be Used by Several Threads


try (var arena = Arena.openShared()) {

    var shared = arena.allocate(1L << 32);

    useInParallel(shared);

} // Memory in "shared" is released here via TwR



Access an Array via a MemorySegment


int[] intArray = new int[10];

var intSeg = MemorySegment.ofArray(intArray);



Access a Buffer (of long in This Example) via a MemorySegment



LongBuffer longBuffer = LongBuffer.allocate(20);

var longSeg = MemorySegment.ofBuffer(longBuffer);



What’s Next?

Take FFM for a spin today by downloading a Java 20 Early-Access build. Do not forget to pass the --enable-preview JVM flag or the code will not run. 


Test how you can benefit from FFM already now and engage with the open-source community via the panama mailing list.

Tuesday, June 7, 2022

Exhaustive JUnit5 Testing with Combinations, Permutations and Products

 

Exhaustive JUnit5 Testing with Combinations, Permutations, and Products

Unit testing constitutes an integral part of the process of providing high-quality software. But, how can one write tests covering all variants of several operations? Read this article and learn how to use JUnit5 in conjunction with combinations, permutations, and products.

Test Support Libraries

There are many libraries that make testing better in different aspects. Here are some of them:

Agitar One

Agitator automatically creates dynamic test cases, synthesizes sets of input data, and analyzes the results.


http://www.agitar.com/solutions/products/software_agitation.html


Chaos Monkey

Chaos Monkey is responsible for randomly terminating instances in production to ensure that engineers implement their services to be resilient to instance failures.


https://netflix.github.io/chaosmonkey/


Chronicle Test Framework

This library provides support classes for writing JUnit tests. It supports both JUnit4 and JUnit5. Tools like permutations, combinations, and products can be leveraged to create exhaustive tests. Agitar One can automatically identify and generate tests whereas Chronicle Test Framework provides programmatic support for writing your own tests.

 

https://github.com/OpenHFT/Chronicle-Test-Framework


In this article we will be talking about Chronicle Test Framework.

Objective

Suppose we have written a custom implementation of java.util.List called MyList and that we want to test the implementation against a reference implementation such as ArrayList. Further, assume that we have a number of operations  O1, O2, …, On. that we can apply to these objects. The question now is: how can we write tests assuring that the two objects provide the same result regardless of how the operations are applied?

Combinations, Permutations, and Products

Before we continue, we remind ourselves of what combinations, permutations, and products are from a mathematical perspective. Assume we have a set X = {A, B, C} then;


The combinations of X are:

[]

[A]

[B]

[C]

[A, B]

[A, C]

[B, C]

[A, B, C]


The permutations of X are:

[A, B, C]

[A, C, B]

[B, A, C]

[B, C, A]

[C, A, B]

[C, B, A]


The permutations of all combinations of X are:

[]

[A]

[B]

[C]

[A, B]

[B, A]

[A, C]

[C, A]

[B, C]

[C, B]

[A, B, C]

[A, C, B]

[B, A, C]

[B, C, A]

[C, A, B]

[C, B, A]


Where [] denotes a sequence of no elements. As can be seen from the sequences above, the number of variants will increase very rapidly as the number of set members increases. This puts a practical limit on the exhaustiveness of the test one can write.


Another concept (not exemplified in this article) is “Products” (aka Cartesian Products). Suppose we have a sequence s1 = [A, B] of one type and another sequence s2 = [1, 2] of another type then;


The product of s1 and s2 is:

[A, 1]

[A, 2]

[B, 1]

[B, 2]


Products have many similarities with database “join” operations and relate to nested loops.

The Test Framework

In this test, we will be using open-source Chronicle-Test-Framework that supports the aforementioned combination, permutation, and product features. Here is an example:


// Prints: [], [A], [B], [C], [A, B], [B, C], … (8 sequences)

Combination.of("A", "B", "C")

    .forEach(System.out::println)


This prints all the combinations of {A, B, C} the result being the same as in the previous chapter. In the same way, the following example will print out all the permutations of {A, B, C}:


// Prints: [A, B, C], [A, C, B], [B, A, C], … (6 sequences)

Permutation.of("A", "B", "C")

    .forEach(System.out::println)


In this following example, we combine the capabilities of combinations and permutations:


// Prints: [], [A], [B], [C], [A, B], [B, A], …(16 sequences)

Combination.of("A", "B", "C")

    .flatMap(Permutation::of)

    .forEach(System.out::println)


The methods above produce a Stream of Collection elements allowing easy adaptations to other frameworks such as JUnit5.


When it comes to products, things work slightly differently. Here is an example:


final List<String> strings = Arrays.asList("A", "B");

final List<Integer> integers = Arrays.asList(1, 2);


Product.of(strings, integers)

        .forEach(System.out::println);


This will print:


Product2Impl{first=A, second=1}

Product2Impl{first=A, second=2}

Product2Impl{first=B, second=1}

Product2Impl{first=B, second=2}


If a more recent Java version is used, the following scheme would typically be used instead:


record StringInteger(String string, Integer integer){}


Product.of(strings, integers, StringInteger::new)

        .forEach(System.out::println);


This will produce:


StringInteger[string=A, integer=1]

StringInteger[string=A, integer=2]

StringInteger[string=B, integer=1]

StringInteger[string=B, integer=2]


In my opinion, the above is better than the default Product2Impl tuple because the record is a “nominal tuple” where the names and types of the state elements are declared in the record header compared to the Product2Impl which relies on generic types and “first” and “second” as names.

The Objective

Suppose that we want to make sure two java.lang.List implementations behave the same way for a number of mutating operations.  Here, lists contain Integer values (ie implements List<Integer>).


We start by identifying the mutating operations to use. One (arbitrary) suggestion is to use the following operations:


list.clear()

list.add(1)
list.remove((Integer) 1) // Will remove the object 1 and not @index 1

list.addAll(Arrays.asList(2, 3, 4, 5))

list.removeIf(ODD)


Where Predicate<Integer> ODD = v -> v % 2 == 1.


In this article, we will initially use ArrayList and LinkedList for comparison.


As the reader might suspect, the List types are going to be tested against each other with all the possible sequences of operations. But, how can this be achieved?

The Solution

JUnit5 provides a @TestFactory annotation and DynamicTest objects, allowing a test factory to return a Stream of DynamicTest instances. This is something that we can leverage, as shown below:


 private static final Collection<NamedConsumer<List<Integer>>> OPERATIONS =
    Arrays.asList(

        NamedConsumer.of(List::clear, "clear()"),

        NamedConsumer.of(list -> list.add(1), "add(1)"),

        NamedConsumer.of(list -> list.remove((Integer) 1), "remove(1)"),

        NamedConsumer.of(list -> list.addAll(Arrays.asList(2, 3, 4, 5)),
                                "addAll(2,3,4,5)"),

        NamedConsumer.of(list -> list.removeIf(ODD), "removeIf(ODD)")

);



@TestFactory

Stream<DynamicTest> validate() {

    return DynamicTest.stream(Combination.of(OPERATIONS)

                    .flatMap(Permutation::of),

            Object::toString,

            operations -> {

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

                List<Integer> second = new LinkedList<>();

                operations.forEach(op -> {

                    op.accept(first);

                    op.accept(second);

                });

                assertEquals(first, second);

            });

}


This is the entire solution, and when run under IntelliJ (or other similar tools), the following tests will be performed (only the first 16 of the 326 tests are shown for brevity):



Image 1, Shows the first 16 test runs of the 326 tests.


The reason NamedConumer is used over the standard java.util.function.Consumer is that it allows real names to be shown rather than some cryptic lambda reference like ListDemoTest$$Lambda$350/0x0000000800ca9a88@3d8314f0. It certainly looks better in the output and provides much better debug capabilities.

Expanding the Concept

Suppose we have a more significant number of List implementations we’d like to test, such as:


ArrayList

LinkedList

CopyOnWriteArrayList

Stack

Vector


To expand the concept, we begin by creating a collection of List<Integer> constructors:


private static final Collection<Supplier<List<Integer>>> CONSTRUCTORS =
        Arrays.asList(

            ArrayList::new,

            LinkedList::new,

            CopyOnWriteArrayList::new,

            Stack::new,

            Vector::new);


The reason for working with constructors rather than instances is that we need to be able to create new List implementations for each dynamic test.


Now, we only need to do minor modifications to the previous test:


@TestFactory

Stream<DynamicTest> validateMany() {

    return DynamicTest.stream(Combination.of(OPERATIONS)

                    .flatMap(Permutation::of),

            Object::toString,

            operations -> {


                // Create a fresh list of List implementations

                List<List<Integer>> lists = CONSTRUCTORS.stream()

                        .map(Supplier::get)

                        .collect(Collectors.toList());


                // For each operation, apply the operation on each list

                operations.forEach(lists::forEach);


                // Test the lists pairwise

                Combination.of(lists)


                    // Filter out only combinations with two lists

                    .filter(set -> set.size() == 2)


                    // Convert the Set to a List for easy access below

                    .map(ArrayList::new)


                    // Assert the pair equals

                    .forEach(pair -> assertEquals(pair.get(0), pair.get(1)))

            });

}


Strictly, this is a bit of cheating as a single dynamic test contains several subtests for a plurality of List pairs. However, It would be reasonably easy to modify the code above to flatMap() in the various assertions under separate dynamic tests. This is left to the reader as an exercise.

A Final Warning

Combinations, permutations, and products are potent tools that can increase test coverage, but they can also increase the time it takes to run all tests as the number of sequences explodes even with only a moderate increase in the number of input variants. 


For example, here is a list of the number of permutations of all combinations for some given sets S of size s:

 

s = size(S)

poc(s) (permutations of combinations)

0

1

2

2

5

3

16

4

65

5

326

6

1,957

7

13,700

8

109,601

9

986,410

10

986,4101

11

108,505,112


Table 1, shows the number of permutations of combinations for some set sizes.


More generally, it can be shown that: poc(s) = poc(s - 1) * s + 1. 


If in doubt, the number of combinations can be checked using the .count() stream operation which will return the number of sequences returned as shown below:


long poc6 = Combination.of(1, 2, 3, 4, 5, 6)

        .flatMap(Permutation::of)

        .count();


The stream above will, unsurprisingly, return 1,957 as there are six input elements.


Combinatorics can make a huge impact. However, make sure to keep the number of dynamic tests under control, or else test time might increase significantly.


Libraries like Chronicle Queue and Chronicle Map make use of the Chronicle-Test-Framework to improve testing. Here is an example from Chronicle Map where five Map operations are exhaustively tested providing 326 dynamic tests in just a few lines of code.



Resources

Open-Source Chronicle-Test-Framework

The code in this article (Open-Source)