Arrays in Java and Scala

Despite the fact they both run on the JVM, Java and Scala have very different type systems. Say you want to create an array of type T[] in Java where T is any type. It is possible but messy. You might call Array.newInstance but it's signature is:

    public static Object newInstance(Class componentType, int length)

that is, it returns an Object so you'd have to cast it.

If you want to get the component type of a particular array, you'd call Class.getComponentType() but that can be called an any class, not necessarily an array. If it's not called on a type that's an array, it returns null. What's more, it returns Class not Class<T>.

Finally, Java's arrays are covariant (unlike its generics) so you run the danger of getting an ArrayStoreException at runtime if you're not careful. Put another way, Java's arrays don't adhere to the Get and Put Principle that its collections do ("The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when both get and put." [1])

Yuck. Scala cleans this up using an invariant Array[T] class constructor. If you JAD the code, you can see how Scala does it. Say we want a multi-dimensional array of Ints, we might call:

    val matrix            = Array.ofDim[Int](7,9)

if we then decompiled the .class file of scala.Array into Java, we can see what Scala is doing. It looks like this:

    public Object[] ofDim(int n1, int n2, ClassTag evidence$4) { ...

where our type (Int) has cheekily been added as an extra parameter. Note, the method returns an array of Object.  As it happens, each of these Objects are arrays of the type we want, in this case Int ultimately using the same Java API method, newInstance, we saw above.

This is another nice feature of Scala in that we can dynamically create arrays of a given type. The ofDim method looks like:

  def ofDim[T: ClassTag](n1: Int): Array[T] = ...

or, equivallently:

  def ofDim(n1: Int)(implicit T: ClassTag[T]): Array[T] = ...

allowing us to do something like:

      val anArray = new Array[T](length) 

without this ClassTag, you'll get "cannot find class tag for element type T".

[1] Java Generics and Collections - Naftalin and Wadler

Atomics and Speeds

Just to compare strategies for writing to arrays, I put together some code where one thread writes a non-zero value to an array while another reads through the array, spinning on any elements that are still zero. There is no locking, so this should be fast.

The four different approaches are:

1. Writing to a simple int[] array.
2. Writing to a simple int[] array but occasionally reading/writing a volatile field
3. Writing to a simple int[] array but always reading/writing a volatile field
4. Using AtomicIntegerArray.set(...)
5. Using AtomicIntegerArray.lazySet(...)

The test:

1. Starts the producer thread
2. Starts the consumer thread
3. Joins on the producer thread
4. Joins on the consumer thread but times out after 10 seconds. If the reader thread has not finished after this time, we regard the test in error.

The same framework code is used for all approaches. After a few runs, the results look like:

Approach	Mean (seconds)	Standard Deviation (seconds)
AtomicIntegerArray.set(...)	131.2	3.6
Normal Array Access With Constant Volatile Read/Write	96.6	5.1
AtomicIntegerArray.lazySet(...)	42.3	6.0
Normal Array Access	37.4	4.7
Normal Array Access With Occasional Volatile Read/Write	6.3	3.8

So, we can quickly see that the set(...) method is the slowest way of writing to an array on my machine.

Normal array access looks reasonably fast but it is wrong! Occasionally, you will see the timeout in test step #4 being triggered as there is no guarantee that (in the absence of memory semantics) that the reader thread will see what the writer thread puts in the array.

The winner by far is the strategy to read/write to the array as normal but occasionally have the array writer thread write to some volatile field and the reader thread sometimes read from it. How often is a matter of tuning and what your needs are.

So, in summary:

1. Avoid reading/writing from arrays with multiple threads with no further memory semantics (and making the reference to the array volatile is not sufficient). You might find one thread never sees the data another thread has put into the array.
2. If you want the fastest exchange of data and can tolerate it being somewhat stale, occasionally use memory semantics.