crush depth

Vultr

If you're reading this, then the migration to Vultr was successful. Additionally, this site should now be accessible to IPv6 users.

Host          | IPv4         | IPv6
------------------------------------------------------------------------
io7m.com      | 45.77.78.222 | 2001:19f0:0005:061d:f000:0000:0000:0000/64
mail.io7m.com | 45.77.76.92  | 2001:19f0:0005:0752:f000:0000:0000:0000/64
A Change Of Scenery

I'm looking at changing my VPS provider from DigitalOcean to Vultr. These were the top two contenders when I initially chose a provider. I can't fault DigitalOcean's service, but Vultr have better pricing and give more control over DNS details such as PTR records.

I have the configurations ready to go, so I suspect I'll make the move over the next few days. I'll be taking this opportunity to enable IPv6 for the http and smtp services. Expect outages!

New VPS

I've moved over to the new VPS. Enabling LZ4 compression on the ZFS filesystem has immediately halved my disk usage.

Mind Your Constants

A little known feature of javac is that it will inline constant references when compiling code. This can mean that it's possible to accidentally break binary compatibility with existing clients of a piece of code when changing the value of a constant. Worse, tools that analyze bytecode have no way of detecting a binary-incompatible change of this type.

For example, the following class defines a public constant called NAME:

public final class Constants
{
  public static final String NAME = "com.io7m.name";

  private Constants()
  {

  }
}

Another class refers to NAME directly:

public final class Main0
{
  public static void main(
    final String args[])
  {
    System.out.println(Constants.NAME);
  }
}

Now, let's assume that NAME actually becomes part of an API in some form; callers may pass NAME to API methods. Because we've taken the time to declare a global constant, it should be perfectly safe to change the value of NAME at a later date without having to recompile all clients of the API, yes? Well, no, unfortunately not. Take a look at the bytecode of Main0:

public final class Main0
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_FINAL, ACC_SUPER
Constant pool:
   #1 = Methodref          #7.#16         // java/lang/Object."<init>":()V
   #2 = Fieldref           #17.#18        // java/lang/System.out:Ljava/io/PrintStream;
   #3 = Class              #19            // Constants
   #4 = String             #20            // com.io7m.name
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   #5 = Methodref          #21.#22        // java/io/PrintStream.println:(Ljava/lang/String;)V
   #6 = Class              #23            // Main0
   #7 = Class              #24            // java/lang/Object
  ...
  #19 = Utf8               Constants
  #20 = Utf8               com.io7m.name
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  #21 = Class              #28            // java/io/PrintStream
  #22 = NameAndType        #29:#30        // println:(Ljava/lang/String;)V
  ...
{
  public Main0();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 1: 0

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: ldc           #4                  // String com.io7m.name
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         5: invokevirtual #5                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
         8: return
      LineNumberTable:
        line 6: 0
        line 7: 8
}

You can see that the value of the NAME constant has been inlined and inserted into the Main0 class's constant pool directly. This means that if you change the value of NAME in the Constants class at a later date, the Main0 class will need to be recompiled in order to see the change.

What can be done instead? Wrap the constant in a static method:

public final class ConstantsWrapped
{
  private static final String NAME = "com.io7m.name";

  public static final String name()
  {
    return NAME;
  }

  private ConstantsWrapped()
  {

  }
}

Call the method instead of referring to the constant directly:

public final class Main1
{
  public static void main(
    final String args[])
  {
    System.out.println(ConstantsWrapped.name());
  }
}

Now the resulting bytecode is:

public final class Main1
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_FINAL, ACC_SUPER
Constant pool:
   #1 = Methodref          #6.#15         // java/lang/Object."<init>":()V
   #2 = Fieldref           #16.#17        // java/lang/System.out:Ljava/io/PrintStream;
   #3 = Methodref          #18.#19        // ConstantsWrapped.name:()Ljava/lang/String;
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   #4 = Methodref          #20.#21        // java/io/PrintStream.println:(Ljava/lang/String;)V
   #5 = Class              #22            // Main1
   #6 = Class              #23            // java/lang/Object
   #7 = Utf8               <init>
   #8 = Utf8               ()V
   #9 = Utf8               Code
  #10 = Utf8               LineNumberTable
  #11 = Utf8               main
  #12 = Utf8               ([Ljava/lang/String;)V
  #13 = Utf8               SourceFile
  #14 = Utf8               Main1.java
  #15 = NameAndType        #7:#8          // "<init>":()V
  #16 = Class              #24            // java/lang/System
  #17 = NameAndType        #25:#26        // out:Ljava/io/PrintStream;
  #18 = Class              #27            // ConstantsWrapped
  #19 = NameAndType        #28:#29        // name:()Ljava/lang/String;
  #20 = Class              #30            // java/io/PrintStream
  #21 = NameAndType        #31:#32        // println:(Ljava/lang/String;)V
  #22 = Utf8               Main1
  #23 = Utf8               java/lang/Object
  #24 = Utf8               java/lang/System
  #25 = Utf8               out
  #26 = Utf8               Ljava/io/PrintStream;
  #27 = Utf8               ConstantsWrapped
  #28 = Utf8               name
  #29 = Utf8               ()Ljava/lang/String;
  #30 = Utf8               java/io/PrintStream
  #31 = Utf8               println
  #32 = Utf8               (Ljava/lang/String;)V
{
  public Main1();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 1: 0

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: invokestatic  #3                  // Method ConstantsWrapped.name:()Ljava/lang/String;
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         6: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
         9: return
      LineNumberTable:
        line 6: 0
        line 7: 9
}

This effectively solves the issue. The ldc opcode is changed to an invokestatic opcode, at no point does the string com.io7m.name appear directly in the Main1 class, and the value of the constant can be changed at a later date without breaking binary compatibility. Additionally, the JIT compiler will inline the invokestatic call at run-time, meaning that there's no performance degradation over using the constant directly.

FreeBSD ZFS Root

When I set up the initial FreeBSD install to host io7m.com, I didn't realize how trivial it was to use ZFS as the root partition. Having used this option several times since, I now wish I had done this for the io7m VPS. I might spin up a new VPS over the next few days with a ZFS root partition, copy the configuration data over to the new VPS, and then reconfigure DNS to point to the new system. If there's a mysterious outage, this will be the reason why.

Half Float Pain

Whilst working on smf, I ran into an issue when resampling 32-bit floating point mesh data to 16-bit floating point format. The issue turned out to be poor handling of subnormal values by my ieee754b16 package. I went looking for better implementations to borrow and found a nice paper by Jeroen van der Zijp called Fast Half Float Conversions. It uses precomputed lookup tables to perform conversions and appears to be drastically more accurate than my manual process (the mathematics of which I've almost entirely forgotten).

I decided to put together a simple C99 implementation in order to see how the code worked but am having some strange issues with some very specific values. My test suite basically tries to prove that packing a double value and then unpacking it should be an approximate identity operation. Essentially, ∀x. unpack(pack(x)) ≈ x. Unfortunately, some very specific values are failing. For some reason, my implementation yields these results:

unpack(pack(2048.0)) → 2048.0
unpack(pack(2047.0)) → -0.0
unpack(pack(2046.0)) → 2046.0
unpack(pack(16375.0)) → 16368.0
unpack(pack(16376.0)) → 0.0

All of the other values in the range [-32000, 32000] appear to be correct. The unusual 16375.0 → 16368.0 result is expected; the conversion is necessarily a lossy procedure and 16368.0 is simply the nearest representable value when converting down to 16-bits. However, the 0.0 values are utterly wrong. This suggests that there's an issue in implementation that's almost certainly caused by a mistake generating the conversion tables. It seems that packing is correct, but unpacking isn't. I've gone over the code several times, even going so far as to implement it twice in two different languages and have gotten the same results every time. I've spoken to Jeroen and he showed me some results from his own implementation and test suite that show that the above isn't a problem with the algorithm. So, assuming that I haven't managed to screw up the same implementation after some five clean-room attempts, there may be a transcription mistake in the paper. I'm waiting to hear more from Jeroen.

Maven Assembly Plugin Redux

A few months back, I filed a bug for the Maven Assembly Plugin. Karl Heinz Marbaise finally got back to me and solved the issue right away. Thanks again!

JEP 305 - Pattern Matching

http://openjdk.java.net/jeps/305

This is a good first step towards getting algebraic data types into Java.

Sender Policy Framework

Set up SPF for the io7m.com mail server today. Took about 30 seconds. Hopefully I'll still be able to send and receive mail when the DNS changes propagate.

OSGi Requirements And Capabilities

OSGi is an extremely powerful module system for the Java virtual machine. Code and resources are packaged into bundles that can be installed into a running OSGi container for use.

Using bundles to deliver compiled Java code is essentially a solved problem. Bundles specify what Java packages they export and import. If a package is exported, then that package can be imported by other bundles. The OSGi resolver is responsible for wiring bundles together. For example, if a bundle B0 specifies that it imports a package named P0, and another bundle B1 specifies that it exports a package named P0, then the OSGi runtime will create a wire W0 from B0 to B1. Whenever code in B0 references a class in P0, then that class will be loaded from B1 by traversing W0. This creates a directed acyclic graph where the vertices of the graph are packages and the edges of the graph are wires.

We can look at this in more general terms: We can think of the above in terms of requirements that can be satisfied by capabilities. For example, we can think of a package import as being a specific requirement: A package p attempting to import a particular package q can be thought of as a requirement for q by p. Conversely, a package export can be thought of as a capability: An export of a package p can be thought of as a capability to satisfy a requirement for p.

In these terms, then, the OSGi runtime is essentially a constraint solving system that takes a set of requirements and capabilities as input, and tries to find a solution that satisfies all of the requirements using the provided capabilities.

So what's the point of explaining all of this? Well, beyond importing and exporting Java code, the OSGi system actually allows developers to declare their own types of capabilities and requirements that will be solved by the OSGi runtime when the bundles specifying them are installed. This allows for bundles that contain things other than Java classes to get the same strong versioning and dependency handling that Java code enjoys.

In my case, I'm using this to get versioning and dependency handling for game engine assets. A bundle in the system I've put together can place declarations in the manifest such as:

Provide-Capability: com.io7m.callisto.resources.package; name = a.b.c; version = 1.0

That is, the bundle states that it provides a package called a.b.c, version 1.0, containing resources, in the category of requirements called com.io7m.callisto.resources.package. Another bundle declares:

Require-Capability: com.io7m.callisto.resources.package; filter=(& (name = a.b.c) (version >= 1.0) (version < 2.0))

That is, the bundle states that it requires a package that has the name a.b.c AND has a version greater than or equal to 1.0 AND has a version less than 2.0 (so for example, 1.1 would satisfy the requirement, but 2.1 would not). The requirement is only satisfied when all three constraints are met.

Those bundles will be wired together when they're installed and a bundle can only access the resources of another bundle via the created wire when it explicitly imports that bundle via a Require-Capability declaration. I get all of the benefits of strong versioning, dependency handling, proper cross-bundle resource visibility, good error messages when dependencies aren't met, etc, essentially for free. If a user wants to install a bundle containing resources, the declared capabilities and requirements of the package mean that it's trivial to automatically fetch dependencies of the bundles without the user having to do anything.

I don't know of any modern game engines that use a system like this. Apart from anything, it's phenomenally impractical to build a system like this outside of a virtual machine due to the constraints imposed by working with native code directly. Game developers are religiously opposed to anything that isn't C++ and so refuse to consider the alternatives. Generally, in most games, all of the resources are stuffed into one giant flat namespace without any sort of versioning, privacy control, dependency handling, or anything else. The result is immediate dependency hell as soon as third parties try to produce modifications for the games. Because there's no dependency information, installing modifications for games must be done manually, and there's absolutely no way to ensure that arbitrary modifications are compatible with each other. Worse, when modifications are incompatible, the result will be obscure problems and crashes at runtime instead of actionable "Modification X is incompatible with modification Y" error messages.

In life never do as others do...

Stack Overflow

I actually asked a while back on Stack Overflow if anyone had any idea how to solve the problem I've been attempting to solve with the room model.

Given that I've now actually solved it, I went back to append the answer to my question. I immediately ran into an endless series of idiotically draconian checks that essentially wouldn't let me post the answer to my own question. I eventually gave up trying to get the post to pass the full body cavity search and blood sample analysis, so ended up wrapping the entire thing in preformatted text tags and preceding it with a plea that a passing editor fix it. Consider me discouraged from ever bothering to post on Stack Overflow again.

For future reference, here's the solution I posted:

I came up with a solution to this. In order to solve this efficiently, some sort of spatial data structure is needed in order to query which polygons are overlapped by a given rectangular area. I used a Quadtree. It's also necessary for the polygon data structure being used to be able to distinguish between internal and external edges. An edge is internal if it is common to two polygons.

The steps are as follows (assuming a coordinate system with the origin in the top-left corner):

  1. Insert all polygons into whatever spatial data structure you're using.

  2. Iterate over all polygons and build a list of all of the Y values upon which vertices occur. This has the effect of conceptually dividing up the scene into horizontal strips:

    Strips

  3. Iterate over the pairs of Y values from top to bottom. For each pair (y0, y1) of Y values, declare a rectangular area a with the the top left corner (0, y0) and bottom right corner (width, y1). Determine the set of polygons S that are overlapped by a by querying the spatial data structure. For each polygon p in S, determine the set of edges E of p that are overlapped by a. For best results, ignore any edge in E with a normal that points directly up or down. For each edge e in E, it's then necessary to determine the pair of points at which e intersects the top and bottom edges of a. This is achieved with a simple line intersection test, treating the top and bottom edges of a as simple horizontal line segments. Join the intersection points to create a set of new line segments, shown in red:

    Segments

  4. Create vertical line segments L0 = (0, y0) → (0, y1) and L1 = (width, y0) → (width, y1). Working from left to right, gather any line segments created in the preceding step into pairs, ignoring any line segments that were created from internal edges. If there were no intersecting external edges, then the only two edges will be L0 and L1. In this example strip, only four edges remain:

    Pairs

  5. Join the vertices in the remaining pairs of edges to create polygons:

    Polygons

Repeating the above process for each horizontal strip achieves the desired result. Assuming a set of convex, non-overlapping polygons as input, the created polygons are guaranteed to be either triangles or quadrilaterals. If a horizontal strip contains no edges, the algorithm will create a single rectangle. If no polygons exist in the scene, the algorithm will create a single rectangle covering the whole scene.

Cell Connectivity

Good progress made on the room model.

Cell Connectivity

The algorithm now correctly breaks up the space into horizontal spans, and produces a graph of cells that each have links to the cells above and below. I believe this should be enough information to semi-realistically propagate water through the space simply by walking up and down the graph of nodes.

Cells

Been working intensely on the room model.

Cells

The intention here is to analyze a set of polygons and divide the space outside the polygons into horizontal spans. The horizontal spans represent areas within which water would pool if it was poured into the space. Actually producing these polygons with usable up/down connectivity information has turned out to be a surprisingly fiddly computational geometry problem! I've still not completely solved it.

Polygons

Experimenting with a room model for the engine.

Polygons
Zeptoblog XHTML Strict

Made some corrections to zeptoblog to ensure that the output is valid XHTML 1.0 Strict. I bring this up because it directly affects this blog. I'm now validating the output of this blog against the XHTML 1.0 Strict XSD schema, so any problems of this type should be caught immediately in future.

Validate Now!

Evolving Generated Types

I released version 1.0.0 of jregions a while back and then found that I wanted to make some changes to the API. I didn't want to make a compatibility-breaking change this close to 1.0.0, so I decided to make the changes but keep some deprecated compatibility methods in place.

However, some of the types involved are generated by the immutables package. The way the package works is that you define an abstract interface type and immutables generates an immutable implementation of this interface. One of the parts of the generated implementation is a builder type that allows you to construct instances of the implementation type in multiple steps. For example, a declaration like this:

@Value.Immutable
interface SizeType
{
  int width();

  int height();
}

... would result in the generation of an immutable Size class that contained a mutable Size.Builder type capable of constructing values of Size:

Size s = Size.builder().setWidth(640).setHeight(480).build();

In my case, I wanted to rename the width and height methods to something more generic. Specifically, width should be sizeX and height should be sizeY. Clearly, if I just renamed the methods in the SizeType, then the generated type and the generated builder type would both be source and binary incompatible. I could do this:

@Value.Immutable
interface SizeType
{
  int sizeX();

  int sizeY();

  @Deprecated
  default int width()
  {
    return sizeX();
  }

  @Deprecated
  default int height()
  {
    return sizeY();
  }
}

That would at least preserve source and binary compatibility for the API of the generated type, but the generated builder type would no longer have setWidth or setHeight methods, so source and binary compatibility would be broken there. I asked on the immutables.org issue tracker, and right away Eugene Lukash stepped in with a nice solution. Thanks again Eugene!

How To Fix Intellij IDEA build issues

Switch to the project directory, and:

$ find . -name '*.iml' -exec rm -v {} \;
$ rm -rfv .idea

Reopen the project and hope intensely.

Fix

Pulsing Headache

PulseAudio has some problems.

I have a laptop and various machines for testing software across platforms, and they all send audio over the network to my main development machine. This allows me to use a single pair of headphones and to control audio levels in a single place. I'm using PulseAudio's networking support to achieve this but, unfortunately, it seems rather poor at it.

The first major problem with it is that when the TCP connection between the client and the server is broken for any reason, the only way to get that connection back appears to be to restart the client. This is pretty terrible; network connections are not reliable and any well-written networked software should be designed to be resilient in the case of bad network conditions. Simply retrying the connection with exponential backoff would help, possibly with an explicit means to reconnect via the pactl command line tool. As an aside, the use of TCP is probably not a great choice either. Software that streams audio has soft real-time requirements and TCP is pretty widely acknowledged as being unsuitable for satisfying those requirements. An application such as an audio server is receiving packets of audio data and writing them to the audio hardware as quickly as it can. The audio data is time critical: If a packet of audio is lost or turns up late, then that is going to result in an audible gap or glitch in the produced sound no matter what happens. Therefore, an algorithm like TCP that will automatically buffer data when packets are reordered, and will automatically re-send data when packets are lost, is fundamentally unsuitable for use in this scenario. Best to use an unreliable transport like UDP, consider lost or late packets as lost, and just live with the momentary audio glitch. The next piece of audio will be arriving shortly anyway! Ironically, the use of an unreliable transport would seem to make the software more reliable by eliminating the problem of having to supervise and maintain a connection to the server as sending data over UDP is effectively fire and forget.

The second major problem, and I'm suspicious (without good evidence) that this may be related to the choice of TCP as a protocol, is that the client and server can become somehow desynchronized requiring both the client and server to be restarted. Essentially, what happens is that when either the client or server are placed under heavy load, audio (understandably) begins to glitch. The problem is that even when the load returns to normal, audio remains broken. I've not been able to capture a recording of what happens, but it sounds a little like granular synthesis. As mentioned, the only way to fix this appears to be to restart both the client and server. A broken client can break the server, and a broken server can break the client!

Amber Expert Group

A few weeks back, I was contacted by none other than Brian Goetz inviting me to become part of the Project Amber expert group. I was quite honoured, and I accepted! It'll be my job to get into arguments on the mailing list about algebraic data types. Honestly, right now I'd be perfectly happy with simple Kotlin-style case classes, but I understand that full pattern matching is being considered for implementation. A while back, I wrote:

Given the typical Java conservatism, Java will probably gain closed types and pattern matching abilities some time after 2025.

I never considered that I might be slightly responsible for meeting or beating that estimate!

Three Day Insight

Been working on some difficult software architecture problems lately. I'm a proponent of a method of thinking that, according to my rather faulty memory, was attributed to Einstein, possibly by Robert Anton Wilson. I can't actually find any evidence that Einstein used this method now, but I find it useful nevertheless! Essentially, the theory goes that the subconsious mind is highly effective at problem solving but does not work quickly. Whereas the conscious mind is useful for making snap decisions (on the timescale of seconds or minutes) that can mean the difference between escaping a predator or being eaten, the subconscious mind works on timescales approaching days, weeks, months, and beyond. An effective way to use the subconscious mind is therefore to pose a question or series of questions to it, then banish those questions from the conscious mind (either by occult means or by sheer distraction). Upon returning to the problem in roughly three days time, the subconscious mind will usually have arrived at some sort of solution.

To achieve this, I spent the last few days hammering away at the mindless task of modularizing an existing codebase. In this case, jsycamore. I'm only really this year getting a handle on applying a service-oriented approach to programming and each new project is an opportunity to find new places where the model can be applied. For example, the user interface in the jsycamore package is themable. Previously, the core package provided a set of four default themes, each of which emulated the look and feel of an existing operating system. The modularization of the code moved those themes into their own modules with the themes being published as services. This allows programmers to publish their own themes as services and have them automatically made available to any program using jsycamore without anyone having to write extra code to use them. If nothing else good comes from Jigsaw, I hope at least that it shoves programmers in the direction of publishing services as opposed to relying on ClassLoader and reflection hacks to provide late-binding of functionality in this way. Much of the JDK has been converted to services, apparently, and they're now a core part of the new module system instead of lurking in the background the way they have since Java 6.

Lies!

Just because you can convince 9 out of 10 people that your stupid idea is a good idea doesn't make it a good idea it just makes you a skilled liar.

Morale shall continue until beatings improve.

Etc.

GitHub Contributions

Managed to hit 3000 GitHub contributions today:

GitHub

Renames

Had a change of heart. Doing all of the package renames now rather than waiting for Java 9. I wrote:

There is the possibility that changing the entire name of a project could be considered a non-compatibility-breaking change according to semantic versioning...

I'm choosing to believe this is true and am renaming projects and modules without incrementing the major version number. I'm using japicmp to verify that I'm not introducing binary or source incompatible changes.

Bulldozing

Mutable Numbers

Sometimes, what you really need is a mutable, boxed integer.

While updating jcanephora, I discovered that I needed to update jpra to use the new jtensors types. Whilst doing this, I discovered that the new simplified implementation of the ByteBuffer based storage tensors that I'd implemented were too simple: The jpra package made use of the cursor-like API that the old jtensors-bytebuffered package provided. I'd not provided anything analogous to this in the new API, so I had to do some rewriting. In the process, I discovered that the code that jpra generated was using an AtomicLong value to store the current byte offset value. The reason it used an AtomicLong value was simply because there was no mutable, boxed long value in the Java standard library. To remedy this, I've created a trivial mutable numbers package upon which the com.io7m.jtensors.storage.bytebuffered and com.io7m.jpra.runtime.java modules now depend. I should have done this years ago but didn't, for whatever reason.

https://github.com/io7m/jmutnum

It may be the least interesting software package I've ever written.

jcanephora on jtensors 8

Going to start working on moving jcanephora to jtensors 8.0.0-SNAPSHOT in order to flush out any problems with jtensors before I try to do a stable 8.0.0 release.

jtensors implementation

The jtensors implementation is basically done. I need to release the 1.0.0 version of the primogenitor, though, and I can't do this until the 0.10.0 version of japicmp is released.

I like this sort of pure code because it allows for property-based testing ala QuickCheck. The general idea is to specify mathematical properties of the code abstractly and then check to see if those properties hold concretely for a large set of randomly selected inputs. In the absense of tools to formally prove properties about code, this kind of property-based testing is useful for checking the likelihood that the code is correct. For example, the test suite now has methods such as:

/**
 * ∀ v0 v1. add(v0, v1) == add(v1, v0)
 */

@Test
@PercentagePassing
public void testAddCommutative()
{
  final Generator<Vector4D> gen = createGenerator();

  final Vector4D v0 = gen.next();
  final Vector4D v1 = gen.next();

  final Vector4D vr0 = Vectors4D.add(v0, v1);
  final Vector4D vr1 = Vectors4D.add(v1, v0);

  checkAlmostEquals(vr0.x(), vr1.x());
  checkAlmostEquals(vr0.y(), vr1.y());
  checkAlmostEquals(vr0.z(), vr1.z());
  checkAlmostEquals(vr0.w(), vr1.w());
}

Of course, in Haskell this would be somewhat less verbose:

quickCheck (\(v0, v1) -> almostEquals (add v0 v1) (add v1 v0))

The @PercentagePassing annotation marks the test as being executed 2000 times (by default) with at least 95% (by default) of the executions being required to pass in order for the test to pass as a whole. The reason that the percentage isn't 100% is due to numerical imprecision: The nature of floating point numbers means that it's really only practical to try to determine if two numbers are equal to each other within an acceptable margin of error. Small (acceptable) errors can creep in during intermediate calculations such that if the two results were to be compared for exact equality, the tests would almost always fail. Sometimes, the errors are large enough that although the results are "correct", they fall outside of the acceptable range of error for the almost equals check to succeed.

There's a classic (and pretty mathematically intense) paper on this called "What Every Computer Scientist Should Know About Floating-Point Arithmetic". This was given an extensive treatment by Bruce Dawson and his explanations formed the basis for my jequality package. I actually tried to use junit's built-in floating point comparison assertions for the test suite at first, but they turned out to be way too unreliable.

Update: Without even an hour having passed since this post was published, japicmp 0.10.0 has been released!

Mathematics With An Axe

I've reached peak frustration with jtensors.

The API is riddled with inconsistencies due to mistakes caused by the ridiculous amount of hand-specialization. The design of the API is also suboptimal on modern JVMs due to the use of interface types to abstract over vector implementations: Vector method call sites become megamorphic which prevents inlining and harms the ability of the JIT to produce good code.

The API also distinguishes between immutable and mutable vectors and matrices, the latter of which really only exist to allow for avoiding the allocation of temporary objects when working with vectors (and, via interface types, to mutate vectors held in off-heap memory). However, on modern JVMs that employ escape analysis, short-lived objects don't entail any allocations at all as long as the call sites that refer to them are at most bimorphic. The sheer number of interfaces and implementations prevents this important optimization. Without mutable vectors, these interfaces would most likely be pointless. If the API allowed the JVM's escape analysis to work well, the mutable vectors likely wouldn't be needed at all.

The API provides interfaces that abstract over readable and writable vectors so that APIs that use types from the jtensors package can specify types such as "any readable 4-element vector" and the like, without caring what the specific underyling type of vector is used. The interface types were originally introduced because I wanted to have lots of different vector implementations that had different approaches to storage. For example, some vectors might be backed by a ByteBuffer that contains IEEE754 Binary16-encoded ("half precision") values. Other vectors might be represented by pointers into large off-heap arrays.

So what's actually good about jtensors?

Personally, I find the use of static methods in the API to be more readable than other Java vector algebra libraries. For example, to me, this:

return add(v1, subtract(v2, v3));

... Reads a lot better than this:

return v1.add(v2.subtract(v3));

The API strongly distinguishes between immutable and mutable types to allow programmers to pick which guarantees they want. The API contains hand-specialized variants of vector and matrix types for float, double, long, and int. Finally, the API provides phantom typed variants of all of the types for enforcing the correctness of your mathematics at compile-time. I'm not aware of any other vector algebra package that provides this. This is extremely valuable when working with graphics systems! Matrix multiplication is not commutative and it's very easy to accidentally perform a multiplication in the wrong order. The usual result will be strange visual results or, even worse, a blank screen. Trying to track down bugs like this is mind-bendingly horrible so preventing as many of them as possible at compile-time is a must. The use of phantom types allows for writing code like this:

MatrixM4x4<Object, World> m_model;
MatrixM4x4<World, View> m_view;
MatrixM4x4<Object, View> m_modelview;

MatrixM4x4.multiply(m_view, m_model, m_modelview);

The multiply method takes a matrix of type MatrixM4x4<T, U>, a matrix of type MatrixM4x4<U, V> and writes the resulting multiplication to a matrix of type Matrix<T, V>. Any programmer familiar with something like OpenGL will have experienced the horror of accidentally switching the order of the matrices; the result is silent failure and blank screens. The use of phantom types in the jtensors API makes the above mistake a compile-time error. You are physically prevented from giving the matrices in the wrong order because the types won't line up. Additionally, they act as documentation. It's immediately obvious to anyone looking at the above that m_modelview is a matrix that transforms positions in Object space to their equivalent representation in View space. I've lost track of the number of times that I've been implementing graphics algorithms and have gotten coordinate spaces wrong because the original papers helpfully failed to specify them (and any example code had no way of expressing the coordinate spaces). The classic literature on normal mapping actually contained a serious error of this type as explained on The Tenth Planet blog and evidently nobody noticed it for years. Stronger types would have prevented it!

Finally, the implementation is heavily tested. The test suite may be the largest I've ever written and contains over 8000 test cases with 100% branch coverage. Algorithms have been checked against multiple textbook sources, all assumptions and conventions have been made explicit and documented, and the implementation results have been tested against results produced by multiple third-party implementations.

I have a ton of code that already depends on jtensors but I just can't bear to maintain it in its current form. Other Java vector algebra libraries do not have a feature set comparable to jtensors, so I can't just switch to one of those. In particular, I use the phantom typed API heavily. I'd like to do a clean-room rewrite of jtensors, fixing all of the above issues, generating as much of the code as possible, and drastically simplifying the implementation. I can't wait around for Java 10's value types, but I can at least reorganize things so that a transition to value types will be easier than it would be currently. I also now know much more about the shapes of code that modern JVMs like to consume than I did when I first started writing jtensors back in 2011. Indeed, those code shapes have changed since 2011! Don't forget that, at that time, the most commonly deployed version of Java was still Java 5! Escape analysis was added fairly early in Java 6's lifetime and has been heavily improved ever since.

So, what should a modern jtensors rewrite look like?

  1. Separate the types of tensors used for computation and storage.

    In other words, make any code that computes with tensors work purely with immutable tensors and keep that code strictly monomorphic. The package can still have mutable vectors and matrices for storage and can still abstract over storage tensors with interfaces, but the APIs for computing with tensors and matrices must yield monomorphic call sites to static methods for maximum performance.

    Additionally, because the types of computation and storage tensors are cleanly separated, the range of types of computation tensors can be limited to those directly supported by the JVM. In other words, tensors over int, long, float, and double because those are the four types that have bytecode instructions on the JVM. The API can also require that operations such as the dot product return a value of the highest-precision type variant applicable to the current type. That is, the dot product for int-typed vectors will be returned in a long value. The dot product for float-typed vectors will be returned in a double value, and so on. This will eliminate the annoying API inconsistencies I mentioned earlier.

    External APIs that used the interface types to accept "any readable 4-element vector" or "any writable vector" and the like should just accept immutable vectors of specific types. Tough luck.

  2. Generate as much as possible.

    The tensor types should be generated by Immutables and the computation APIs (including the test suite) should be generated using a template. No hand-specializaton. No hand-written equals, hashCode, toString, etc.

    This is the best that can be done without value types.

  3. Keep the phantom-typed variants.

    I actually use these more than I use the tensors that don't have type parameters.

  4. Provide a range of storage types.

    The computation types can be kept simple, immutable, and in a form that the JVM loves to compile as described above. The storage types, however, can be as JIT-hostile as they like without causing performance problems. IEEE754b16 matrices. Matrices stored in direct ByteBuffers. sun.misc.Unsafe! In addition, this may address performance problems like ticket 7 because intermediate computations won't incur the cost of reading from or writing to tensors with unusual storage characteristics.

  5. Handedness?

    I work in a right-handed coordinate system. jtensors has no support for anything else. Perhaps it'd be a good idea to mark those methods that give explicitly right-handed results as doing so, and then provide left-handed variants too?

    Even if no left-handed variants are provided at first, it'd make sense to do this to make the API clearer and to allow for the addition of left-handed variants at a later date whilst keeping the API consistent.

  6. Get it done in less than a month

    I've rewritten the jtensors codebase at least five times. With the addition of templating, I should be able to get the whole implementation done very quickly as there are essentially no unknowns. The main issue will then be updating all of the other packages that depend on jtensors. It'll be an enormously backwards-incompatible change, so I'll do the naming convention changes at the same time.

jtensors is dead. Long live jtensors.

Plans

Distraction Scenario

I have to admit: Reorganizing a codebase to move to generating code that I've already written (and rewritten several times over the past five years) is on the far side of tedious.

On the plus side, I just heard about Project Amber. This is almost certainly the start of the process to get algebraic data types into Java (and hopefully, the JVM infrastructure to allow for a common representation of those types between JVM languages).

Foolish Inconsistency

Been working on moving the jtensors codebase over to source generation as I mentioned previously. I've discovered some annoying inconsistencies in the API that are making it harder to generate the sources from a single template. For example, the VectorM4I type has a method that takes a double-typed parameter as a scaling value, but has a scaleInPlace method that takes an int-typed parameter as a scaling value.

VectorM4I.scale

VectorM4I.scaleInPlace

The fact that this hasn't been noticed up until now is both evidence to the lack of utility of the latter method, and a testament to the fallibility of humans when it comes to performing repetitive tasks.

In any case, fixing the above would be a backwards-incompatible change and I'm really trying to avoid those until Java 9 appears. Likely going to deprecate the old methods and add new ones with the correct types.

japicmp update

Big thanks to Martin Mois for implementing a recent feature request to relax the rules for semantic versioning enforcement in japicmp when the current project version is less than 1.0.0.

My basic problem was that I wanted to configure the plugin once in the primogenitor POM and then have the semantic versioning check automatically start working when the API is marked as stable (in other words, when it reaches 1.0.0). Without the feature above, I'd have had to redeclare the plugin's configuration in every project, disable it, and then remember to re-enable it every time a project reached 1.0.0.