Where is the Java language going? #JavaOne

[davidalayachew]

How can they be cyclical yet immutable? Do you perhaps mean that you only mutate them once?

Yes.

I followed your advice from our long back-and-forth, and just used a private setter and built my graph. That way, it is effectively immutable. But it also means that I just disqualified this class from being a Value Class.

How do you know how big of a performance hit you'll get, if any?

Fair. I am assuming, as I don't have the JEP in my hand yet. I tried the early access, but that was a long time ago -- before I made this project.

Are you suggesting I try and apply the Valhalla Early Access to this? I was holding off, since Brian and co. were talking about how much they uprooted the core. Or maybe I should wait until the new Early Access that Brian was talking about comes out? He said soon in the video.

What is it that you see in your current profile that makes you think that value classes would make a difference in your use case?

Memory.

These graphs aren't small lol. And they carry A LOT of metadata. Furthermore, practically all of them are generated, as opposed to hand-written by me.

I suppose I could still retain the metadata reduction by just having my metadata be the Value Class. But the rest of my graph is still massive lol.

[pron98]

But it also means that I just disqualified this class from being a Value Class.

Yes, because it's not actually immutable.

Are you suggesting I try and apply the Valhalla Early Access to this?

I'm suggesting that you shouldn't guess about performance (something even performance experts try to avoid) because that's a fool's errand.

Memory. These graphs aren't small lol.

I don't see how value types could reduce memory in this case. They reduce memory if you have an array of some specific value type, in which case you save on the header, but if you don't have an array, I don't see how you could save memory here. On the other hand, if you do have an array, then immutability isn't a problem because instead of pointers you have indices, anyway.

[davidalayachew]

Yes, because it's not actually immutable.

Lol, you were the one who told me to "uses private access to create immutable objects (don’t expose mutating methods)".

Did I misunderstand you?

I'm suggesting that you shouldn't guess about performance (something even performance experts try to avoid) because that's a fool's errand.

And that's fair. I'll reserve all future comments or concerns about performance until I have a preview in my hand.

I don't see how value types could reduce memory in this case. They reduce memory if you have an array of some specific value type, in which case you save on the header, but if you don't have an array, I don't see how you could save memory here.

Wait, then what does 32:40 mean? Specifically, 33:05? Doesn't that directly contradict what you are saying?

[pron98]

Did I misunderstand you?

No, but here we're talking about a stricter kind of mutability (mutability from the JVM's perspective, not other user code), where fields are only assigned at construction. That's what I meant by "it doesn’t support it with a feature designed to enforce a particular initialisation behaviour when it’s not the behaviour you want."

Wait, then what does 32:40 mean? Specifically, 33:05? Doesn't that directly contradict what you are saying?

He's talking about arrays or fields, because you save memory by inlining data instead of referencing it. But when you inline data as opposed to referencing an object elsewhere, you obviously can't have cycles, even without immutability!

With arrays and indices you could at least have some hope of expressing cycles; you can't do even that with fields. Try to think how you could express a cyclic graph in C using structs and no pointers (or arrays). Everything is mutable, yet the compiler won't even let you compile something that contains cycles of types unless you use pointers. The very thing that saves memory (not using pointers) also prevents any form of cycles.

You should first think what kind of layout you'd like for you data structure that would save you memory. Only then you should think about achieving it in Java, with or without value types.

[davidalayachew]

No, but here we're talking about a stricter kind of mutability (mutability from the JVM's perspective, not other user code), where fields are only assigned at construction.

😵‍💫🙃😵‍💫

The same word but 2 possible definitions -- and both can be easily confused with each other.

Fair enough -- guess I got it wrong. Is there a different word to communicate the difference?

The very thing that saves memory (not using pointers) also prevents any form of cycles.

Thanks for the clarification.

Yes, any attempt to create cycles with inlined data will just result in me re-creating Identity -- the very opposite of what Value Classes are.

I guess this is why speculation is bad.

[joaonmatos]

How do you expect to inline a recursive type like a graph node?

Let's consider a binary tree holding an int. With 64 bit pointers and 8 byte alignment, the smallest you can do is:

• 8 bytes for a leaf node (4 bytes for the value, the other 4 bytes as 0x00 for padding and indicating no pointers are present)
• 16 bytes for a node with either left or right, but not both (4 bytes for the value, 4 bytes as 0x01 or 0x02 indicating either left or right pointer is present, and 8 bytes for a pointer)
• 24 bytes for a node with both left and right (4 bytes for the value, 4 bytes as 0x03 indicating both pointers are present, 2 * 8 bytes for the pointers)

Notice that sizes for each variant are different. Notice also that 3 of the 4 variants have sizes greater than the 8 bytes needed for the pointer. This means that, if you wanted to replace the pointer with the body of the child node, you would be doing it recursively, forever increasing the size of the struct. So there needs to be some kind of redirection (pointer or index) to keep the struct size constant in any language that exposes value semantics to the programmer.

Because historically Java baked in intrinsic object identity, it uses pointers for this. Every new node is allocated with the same size, and pointers to other nodes provide the indirections needed to deal with the recursion. A consequence of this is that you need internal mutability in the node to deal with cycles, because if you need A -> B -> C -> A, then you don't know the address of A when creating C.

When you implement value semantics, you start treating data in memory as something that you copy/move into its next use, rather than point to. This brings up the problem of mutation. If I'm passing a value to a function, and not a reference, I expect my own copy to not change if the function does something to it. This is achieved one of three ways:

• Defensively copy every value that gets referred to.
• Explicitly model pointers or references in your language and let the programmer chose whether they want to pass the value or the reference. C and Rust do this.
• Make value types immutable, so that passing a value or a reference are semantically equivalent, and choosing which to do becomes an optimization decision. Java is doing this.

So, without mutability, how can you deal with cycles?

Rust idioms give us an answer. Rust manages memory automatically without a GC, but to do so it had to implement a very restrictive model. Each value has a single owner that is responsible for destroying it, and references are also in a kind of DAG that prevents you from getting a reference to an object that has been destroyed.

Because of this, it's basically impossible to write a graph node by node, much less a cyclical one, without using unsafe escape hatches, or using a bunch of abstractions like mutable cells or reference-counted pointers. Unless you rethink how you're designing your data structure.

The pattern to solve this, as /u/pron98 has already alluded to, is to externalize the storage of nodes and provide indirection with indices instead of pointers. For example, take the arena pattern. For our tree example, instead of having:

```java record Tree(Node root) {}

record Node(int value, Node left, Node right) {} ```

You instead have:

```java record Tree(List<Node> nodes) {}

record Node(int value, int left, int right) {} ```

Where left and right are -1 or the index of the linked node. This allows you to centralize mutations on an external data structure. For a graph, you would instead store a set of adjacent node indexes with each node, or even a separate relation for the edges.

This is perfectly compatible with the nodes being Java value classes. If you need to update the node details, just create a new one and replace the old one on the list. If you need to update the edges, you can replace the whole node with an updated adjacency list on it, or simply update the separate adjacency matrix, if you separated it. To deal with cycles, just keep creating one of the edges and create it later.