Is there any way a Java-like language could implement immutable primitive arrays without incurring performance penalties?

Question

I asked: What prevents Java from having immutable primitive arrays? a while back and got an answer: Because immutable primitive arrays would typically require checking some immutable flag every time a write attempt is made, slowing down performance.

But I just thought, variables and references themselves can be made read-only (final). Yet they do not have a immutable flag associated with them (as far as I know), rather, they are checked at compile time. Would having a similar mechanism for immutable arrays be possible?

For example, a mutable array reference could be converted to an immutable one but not vice versa, and thus any attempt made to write to an immutable array could be rejected at compile time, similar to other final items? Or are there edge cases that would make that not work out somehow?

While this is technically having immutable views to arrays rather than actual immutable arrays themselves, is there any difference in practice between a 'true' immutable array and an array created as an immutable view, so no non-immutable view exists? Either way, the array cannot and will not be modified.

Answer 1

The answers you got about "but then the JVM would have to check some status bit to gate writes" is true but misleading; such a check is easily hoisted out of loops, propagated through inlined code, etc. So in reality, the performance penalty (outside of the interpreter) is entirely manageable.

The point that people didn't mention is that the array has to get its initial contents somehow. Java has final fields, but final fields are mutable during construction; it is only after the constructor finishes that these values are frozen and nevermore mutable. Construction exists in the language to manage the larval state of objects, which is special (final fields aren't, and the object may not be seen to respect its representational invariants.) To have immutable arrays, arrays would need a phase analogous to construction, where the array could be mutated.

The most likely scenario is some sort of "freezing", where an array goes through a mutable-to-immutable transition. In the common case where the array is not aliased with other code (which can frequently be deduced by the JIT), the array can be frozen "in place" rather than copying; if we cannot prove linearity, freezing would fall back to copying.

The reason this model is more likely is that array immutability would be cumbersome as a static property; it would be much easier if existing code that accepted arrays could accept mutable or immutable arrays, rather than having to create new versions of each API point that accepts arrays. Treating it as a dynamic property makes array types in the JVM more like interfaces with multiple concrete implementations.

Answer 2

There is nothing stopping a Java-like language from having statically-enforced immutable arrays. These would be of a different type to the existing mutable arrays. Freshly-constructed array literals can trivially be treated as immutable array constructors of this type, and the compiler will know which references have that type so that no mutation operations will be permitted, and no casts to anything but another immutable array type can be performed.

On this level, there’s no issue with using the existing static type system to back that. Java specifically does make its primitive arrays visibly special via their interactions with overloading, variadic methods, and erasure, and a new array type would be incompatible with those, but this isn’t a broader issue.

The more you’re happy to prohibit statically, the easier this is, and the more you can reuse the baseline primitive mutable arrays and implement the semantics purely in the compiler. Prohibiting all cast and assignment operations, and making the immutable type unassignable to mutable array types, is sufficient. If you want to hold them in erased generic storage locations, for example, you need to implement a distinct runtime type as well, but if you disallow that you can probably get away without it.

---

Your proposal that

a mutable array reference could be converted to an immutable one but not vice versa

works only for unique linear or affine array references; otherwise, it would still be possible to mutate the array via a pre-existing reference, just not through the new one. Unique references would be an additional new concept for Java, though a number of research languages that are broadly Java-like have general linear, affine, immutable, or read-only references already, and would get all this for free.

If only source-level literal immutable arrays are required, you don’t need this conversion at all. A method on the mutable array type that produces a new immutable array with the same contents covers many uses for it also.

A read-only array type, which could contain either a mutable or immutable array, would likely be useful. This would be a purely static construct, with no difference in the storage type, and it’s possible that this is more what you’re thinking of given the example. You couldn’t mutate an array through one of these references, but you could observe changes made through aliases.

---

It’s also worth noting that C#, perhaps the most Java-like language, has immutable “arrays” in the System.Collections.Immutable.ImmutableArray<T> struct. These have some runtime support and are accessed identically once created, but are not quite as primitive as base arrays and don’t have their compiler support.

Answer 3

To have immutable arrays that are statically checked for immutability in a statically typed language, the immutability needs to be part of the array's type. That requires syntax at least; not insurmountable - we can take inspiration from C++, and imagine e.g. final int[] foo vs. int final[] foo (the latter meaning that the array itself is immutable, and that it can be replaced, but only by another immutable array).

But do keep in mind that this fundamentally makes the immutability a property of the variable, not the object it holds. The point of static typing, and thus static checking, is to examine the statically available information; and the objects don't exist until runtime.

Converting references would probably not be desirable. Of course it would defeat the purpose to be able to treat an immutable array as if it were mutable. But binding a mutable array to an "immutable array" type variable is also not that useful; while that could help the programmer avoid certain kinds of unintended mutations, it would not allow for any additional reasoning about the code (i.e. "the array's elements will not change within this scope") as long as anyone else could have a reference to the same array object.

Answer 4

Nothing about the overall design of Java would preclude support for an immutable array type. Having the underlying virtual machine "understand" a type that includes support for "real" immutability, however, could make things more efficient than would be possible under the JVM.

A good starting basis would be a type of reference that could identify any of four kinds of arrays:

1. Arrays which may be read or written, but may only be accessed on the thread where they are created.

2. Arrays which may only be read, but may be accessed on any thread.

3. Arrays which may be read or written, but only on the thread where it is created.

4. Arrays which may be read or written on any thread.

An array instance of the first type could be safely converted to any of the others (but only on the thread which created it), but any conversion would be "permanent". Because only one thread would be able to do anything with an array instance prior to its conversion to some other type, there would be no way conversion could create any kind of race condition.

From this, one could add a family of reference-to-array types which could identify various subsets of the above.

• Reference to any array
• Reference to any array that's readable on the current thread
• Reference to any array that's readable and writable by the current thread
• Reference to any array that was created by the current thread
• Reference to an array of type #1 that was created by the current thread
• Reference to any array that's readable on any thread
• Reference to any array that's readable and writable on any thread
• Reference to any array that's immutable (and thus readable by any thread)

Conversions to more general reference types could be performed without need for run-time checks, while conversions to more specific types would require runtime checks. Additionally, operations that load a reference of a type that's limited to working with the current thread would need to validate that the object in question is associated from the correct thread unless the container from being which it is loaded is already bound to the current thread. I'm not sure how best to syntactically distinguish among the different array types, or between references that encapsulate array contents versus those that identify arrays "owned" by other objects, but semantics are more important than syntax.

A common weakness in many "Popsicle immutability" designs is that race conditions may arise if a thread tries to write an object as it is being frozen. Requiring that the thread that created an object must either freeze it or permanently prevent it from being frozen before any other thread can do anything with it would eliminate that race condition.

Additionally, it may be useful for each array to hold a "reference to array known to be equal" field which is initially empty, and would only be relevant on arrays that end up being "frozen". If two immutable arrays are compared and found to be equal, and the VM defined a "seniority" characteristic for references, the junior array could have a reference to the senior array stored here and then, at the next GC cycle, any existing references to the junior array could be replaced with references to the senior one (allowing the junior array to be collected).

Answer 5

Yes, it's possible and exists as a library for Kotlin running on the JVM:

https://github.com/daniel-rusu/pods4k/tree/main/immutable-arrays

It uses primitives and doesn't incur any extra performance overhead as that's enforced at the type level by the Kotlin compiler. In fact, immutability enables many optimizations that makes them even faster than regular primitive arrays for many common operations.