Are inlined arrays possible in the JVM?

Compiler
1

Can the compiler create method bytecode accessing arbitrary memory address within the layout of the class defining the method? Or is it limited to explicitly refering to fields by symbols? Like would be sooo much easier if I could create an array-like structure inlined in the memory layout of a class…

2

can you elaborate more on what code you want to write? and what you want to store in the array

3

I’m not sure if this applies to your problem, but if you use Java’s java.util.List.of(..), then the JIT in HotSpot can decide to constant-fold acceses to the internal array. I just learned this from this video from Java One about Stable Values.

1 Like
4

Thats a nice trick to know, they also mentioned that method reference lambdas are implemented with hidden classes (added in JDK 15) which are also trusted for constant folding, sounds like scala should update to use those

2 Likes
5

Equivalent of C++

class Tree {
private:
  Tree children[2];
}

(If I mangled it, please forgive me, but it’s been a very long time since I coded in C++). As you likely know, HashMap and Vector are implemented as trees of high rank which do not use classes at all (other than the collection class wrapping the tree), but every node is an array with arrays as its children/elements. This is fine for Vector, which does not require any additional information, but if you wanted to, for example, keep the size at each node, then you have to either wrap each array in an additional object, doubling memory and time complexity, or store it under a predefined index in the array, together with the data.
In the end, in several collections I used the equivalent of:

type Tree[E]
implicit def TreeExtension[E](tree :Tree[E]) :TreeExtension[E] = 
  new TreeExtension(tree.asInstanceOf[Array[Any]])

object Tree {
  def apply[E](left :Tree[E], elem :E, right :Tree[E]) :Tree[E] = {
     val tree = new Array[Any](4)
     tree(0) = left.size + right.size
     tree(1) = elem
     tree(2) = left
     tree(3) = right
     tree.asInstanceOf[Tree[E]]
  }

  class TreeExtension[E](private val tree :Array[Any]) extends AnyVal {
    def size = if (tree eq null) 0 else tree(0).asInstanceOf[Int]
    def value = tree(1).asInstanceOf[E]
    def left = tree(2).asInstanceOf[Tree[E]]
    def right = tree(3).asInstanceOf[Tree[E]]
  }
}

This is a stupid example, because it can be easily done with a class, but when you allow 16-32 children and values in a node, then this is the only way to do it.
However, when you start adding more and more fields (parent, next in iteration order, an array with sizes of the children, etc.) it quickly gets ugly (although nowhere near as ugly as moving all those casts to the actual algorithm code). In Scala 3 you can use opaque types, but it only gets away with the casts between Tree and Array, and that’s the least of the problems.

6

ok so array being inlined into the class, and the answer is no, and i would say potentially JVM can optimise with the changes in the project Valhalla early access build, but i have no clue how it handles recursive types

1 Like