A Value Types Proposal

340 views
Skip to first unread message

Richard Warburton

unread,
May 2, 2014, 4:37:00 AM5/2/14
to mechanica...@googlegroups.com
Hi,

I suspect some people have seen it already, but there's a value types proposal up at:

http://cr.openjdk.java.net/~jrose/values/values-0.html

Seems to have more detail than previous posts on the topic. The emphasis is still on immutability though, so it doesn't seem as useful for solving locality of reference problems as it might be.

regards,

  Richard Warburton

Jimmy Jia

unread,
May 2, 2014, 8:12:39 AM5/2/14
to mechanica...@googlegroups.com
Eh? Isn't

If another class declared a field of type Point, the VM would allocate storage for the x and y components in the hosting class, rather than a reference to a Point box. (This can be viewed as object inlining or flattening.) Similarly, an array of Points would be laid out as a packed array of alternating x and y values, rather than a series of references.

All you need in terms of locality of reference?


--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Rüdiger Möller

unread,
May 2, 2014, 8:50:39 AM5/2/14
to mechanica...@googlegroups.com
This raises the question regarding array size. The Array needs to be of fixed size then .. this reminds me on Gil Tene proposing to require variable object size to enable value types/structs in a useful way. Kind of a mix of Arrays/Objects (or unification of those concepts). Probably its easier to have a pointer to the Value-type array. 
Why do not make Value Types mutable but do a Copy-On-Assignment (pass by value) ? 
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

Martin Thompson

unread,
May 2, 2014, 8:54:43 AM5/2/14
to mechanica...@googlegroups.com
This work is useful but does not address locality of reference in all the important dimensions. For example, the value types cannot contain references and thus restricts their use from building efficient B+ and B* trees.

While the immutable support is great for some classes of usage it severely restricts others in data structure design. 
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

Tomasz Kowalczewski

unread,
May 2, 2014, 8:56:20 AM5/2/14
to mechanica...@googlegroups.com
It looks as they can:

Containment

  • Can a value class contain a field of reference type? Yes. (Because a value codes like a class.)



To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.



--
Tomasz Kowalczewski

Vitaly Davidovich

unread,
May 2, 2014, 8:57:27 AM5/2/14
to mechanica...@googlegroups.com

I haven't finished reading the entire writeup (reached the byte code description section) but this very much sounds like value types in .net, which have been around for 10+ years now.  That's fine - it's a good model for java.

Structs are mutable in .net, but this is a highly discouraged practice since it leads to lots of subtle bugs, precisely due to loss of identity and copy by value semantics.  So even though mutability is allowed there, it's not that common in usage.  If the JIT is good enough at scalarizing them, then this may not be a problem (e.g. an accumulator struct used on stack, think a convenience around building hashcodes or something).

Sent from my phone

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Vitaly Davidovich

unread,
May 2, 2014, 8:58:51 AM5/2/14
to mechanica...@googlegroups.com

They can have references; what they can't have is fields of their own type.  Can you elaborate on locality issue? From what I read this far they will definitely provide locality and that's one of the goals of the whole thing.

Sent from my phone

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Martin Thompson

unread,
May 2, 2014, 9:01:20 AM5/2/14
to mechanica...@googlegroups.com
Missed that. However the values don't have a pointer therefore you cannot chain them or organise them into a tree so my point about data structures still stands.

"Life without pointers

Also a value does not have its own pointer, or a least such a pointer is a secret inside the VM’s implementation. Therefore there are certain additional operations that also either need to be disallowed or assigned a new meaning."


On Friday, 2 May 2014 13:56:20 UTC+1, Tomasz Kowalczewski wrote:
It looks as they can:

Containment

  • Can a value class contain a field of reference type? Yes. (Because a value codes like a class.)

On Fri, May 2, 2014 at 2:54 PM, Martin Thompson <mjp...@gmail.com> wrote:
This work is useful but does not address locality of reference in all the important dimensions. For example, the value types cannot contain references and thus restricts their use from building efficient B+ and B* trees.

While the immutable support is great for some classes of usage it severely restricts others in data structure design. 



On Friday, 2 May 2014 13:12:39 UTC+1, Jimmy Jia wrote:
Eh? Isn't

If another class declared a field of type Point, the VM would allocate storage for the x and y components in the hosting class, rather than a reference to a Point box. (This can be viewed as object inlining or flattening.) Similarly, an array of Points would be laid out as a packed array of alternating x and y values, rather than a series of references.

All you need in terms of locality of reference?
On Fri, May 2, 2014 at 4:37 AM, Richard Warburton <richard....@gmail.com> wrote:
Hi,

I suspect some people have seen it already, but there's a value types proposal up at:

http://cr.openjdk.java.net/~jrose/values/values-0.html

Seems to have more detail than previous posts on the topic. The emphasis is still on immutability though, so it doesn't seem as useful for solving locality of reference problems as it might be.

regards,

  Richard Warburton

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsubscribe...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.



--
Tomasz Kowalczewski

Vitaly Davidovich

unread,
May 2, 2014, 9:01:49 AM5/2/14
to mechanica...@googlegroups.com

Value type interaction with generics will be an interesting bit; definitely don't want boxing in those cases.  In .net (reified generics though, so it's easier to do I guess) generic methods taking a type parameter with a constraint will not cause boxing of a value type invocation (e.g. generic method takes a T that must implement an interface).

Sent from my phone

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Vitaly Davidovich

unread,
May 2, 2014, 9:03:37 AM5/2/14
to mechanica...@googlegroups.com

I guess you'd have to stick them into arrays and model the higher level abstraction around that.

Sent from my phone

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Tobias Lindaaker

unread,
May 2, 2014, 9:09:49 AM5/2/14
to mechanica...@googlegroups.com
Sure, you cannot define a structure like this:

final __ByValue class Tree {
    final Tree left, right;
}

since a value type would not allow recursive composition.

But you could define a structure like this:

final __ByValue class Tree {
    final Tree[] children;
}

which would allow you to do very similar things in practice.

-tobias

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Jimmy Jia

unread,
May 2, 2014, 9:28:18 AM5/2/14
to mechanica...@googlegroups.com
Seems like you'd also get pretty close to what you want if you had a way to explicitly refer to a boxed version of the object, no?

Although in the binary tree case above, isn't the only thing you save the dereference to the root of the tree?

The B-Tree case is almost dual because what you really want are array-like things that are interned into the hosting class itself, rather than a dereference away. Schematically, you'd want something like:

class BTreeNode {
    final BTreeRefs_n refs;
}

__ByValue class BTreeRefs_n {
    final BTreeNode node_0;
    final BTreeNode node_1;
    ...
    final BTreeNode node_{n-1};
}

except with syntactic sugar around retrieving elements by index, bounds checking, guaranteed memory layout, &c. But it's basically just a value type.

Martin Thompson

unread,
May 2, 2014, 9:29:20 AM5/2/14
to mechanica...@googlegroups.com
It is a interesting point but does raise some questions such as does the child array get inline/folded into the parent?

For efficient trees we need to put m -ways into branch node. How would that level of mutation vs full structure (block node) copy work in practice?

Rüdiger Möller

unread,
May 3, 2014, 6:47:41 AM5/3/14
to
I'd speculate arrays can be "lined into" the hosting class only if their length is known at compile compile time and is static per class (to keep object size constant). So most of the time one would have one dereference same as with current primitive arrays.

Imo the immutability constraint is ok'ish for real value type classes, however it reduces the benefits a lot when trying to use this as "struct" replacements with "embedded" value types, e.g. composing a value type from existing value types.

e.g. 

value class FixedString { char [15]; }
value class Person { FixedString name; FixedString firstName; int age; }

just updating the the age would require a complete allocation+rewrite of the complete 'Person' class. In order to avoid this, one would have to fall back to "pointered" Strings, so runs into the usual pointer chasing thingy again.

another bad example would be something like

value class Packet {
    long receiveTimeStamp;
    long processingTimeStamp;
    [inline] byte payload = new byte[8000];
}

in order to set the timestamp, one would have to allocate and copy the whole thingy.
I really think the immutability constraint should be dropped. It reduces the applicability of the new language construct (as far I understood the proposal) for use with small sized value types.

If the only motivation for immutability is preventing programmers from making errors, I'd argue its a bad trade. People aren't that stupid, they probably can handle it as they handle side effects of pure pointer based objects today.

Maybe add the option for 'mutable value class' with a new keyword.

Remi Forax

unread,
May 3, 2014, 9:02:25 AM5/3/14
to mechanica...@googlegroups.com
On 05/03/2014 12:45 PM, Rüdiger Möller wrote:
> If the only motivation for immutability is preventing programmers from
> making errors, I'd argue its a bad trade. People aren't that stupid,
> they probably can handle it as they handle side effects of pure
> pointer based objects today.

Immutability of value type allow to keep the pass by value semantics of
Java,
it avoid the expose the notion of address of a stack value to the JVM world.

This is on of the tricks that makes the introduction of value types
practically possible.

Rémi

Kirk Pepperdine

unread,
May 3, 2014, 10:04:02 AM5/3/14
to mechanica...@googlegroups.com
Not convinced of the value of this or immutability dogmatically applied.

Regards,
Kirk


Martin Thompson

unread,
May 3, 2014, 10:04:59 AM5/3/14
to mechanica...@googlegroups.com
Now having read through the proposal a few times it has really grown on me for real value types. It seems to be very well thought out from that perspective. I can see huge value with stack allocated values, not just for simple types, but also things like iterators were a small amount of state gets passed around on the stack. This will greatly help with the shortcomings of escape analysis. This is also great for the multi-core world by taking a lot of pressure away from GC and It's concurrent implications, while giving stack locality. It is just a shame that things like a stack allocated smallish array cannot be passed by ref into a function rather than having the copy hit. Sure compilers could optimize this but the track record, with the likes of escape analysis, on Hotspot does not suggest it is likely. A big omission for me is to not be able to allocate a small array on the stack as a buffer and then receive data into it. The fact that doing such a simple thing requires allocation and subsequent GC is just wasteful and missing the point of the multi-core world.

This feels like a nice step forward for true value types however we still need something else to better support the implementation of advanced data structures for moderate heap sized applications (even a few GB upwards).

Martin...

Jimmy Jia

unread,
May 3, 2014, 11:05:02 AM5/3/14
to mechanica...@googlegroups.com
I think the problem with having mutable stack-allocated value types that can be explicitly passed by reference is that you need to prevent them from being returned or otherwise accessed in a dangling-pointer way, which means you end up needing something like the Rust borrow checker as a feature of the language.

Personally that also feels a little "un-Javonic" to me. Maybe I haven't been working in Java for long enough, but it seems like the whole point of Java is to write your code in a "dumb" way, then let the compiler optimize it for you into something reasonable. I think what feels more natural would be boxing up the value type and letting escape analysis figure out whether that should be treated as a reference to the stack-allocated value v. copied into something heap allocated - though of course there are issues there.

Mutability is a bit of a weird thing in this context anyway. In some sense "value types" are necessarily immutable since, well, that's just what they are. I think what we're really talking about is the ability to update some container of a value type without unnecessary memory copying, and maybe having some syntactic sugar around updating only one field of such a struct. Like you want to do something along the lines of

box.point = new Point(box.point.x, box.point.y + 5); (1)

and have it only update the one double for Point.y, or maybe even write it as

box.point.y += 5; (2)

Of course the motivating examples in practice are going to be more complicated, but that's the idea, no? Certainly for sufficiently deeply nested value types, (1) would be a pain and (2) would be much easier to use, but it wouldn't be ridiculous to be in a state of the world where at a language level, (2) is syntactic sugar for (1), but the compiler turns (1) back into something more like (2).

Dan Eloff

unread,
May 4, 2014, 10:00:18 PM5/4/14
to mechanica...@googlegroups.com
> Like you want to do something along the lines of
> box.point = new Point(box.point.x, box.point.y + 5); (1)
> and have it only update the one double for Point.y, or maybe even write it as
> box.point.y += 5; (2)

There is a bit of weirdness with mutable value types that s well known in C#. When you return a value type, it must be by copy (and that's hard to get around, since you can't return a pointer to something on the stack.) So you end up with code like this:

obj.getPoint().y += 5;

Which one would think updates the Point value type in obj. What it really does is modify a temporary. Granted a compiler can catch some of those cases and mark them as errors, but it can't be perfect. In C#, as a result of this I've seen a lot of articles that recommend only using immutable value types.

A sufficiently smart compiler could convert box.point = new Point(box.point.x, box.point.y + 5) into just y += 5 anyway, but using the shorter syntax is problematic. Of course no compiler is sufficiently smart, so more complex examples would probably elude that kind of optimization.

However, where immutable value types really seem to suck (to me, and maybe I'm just missing something) is with iterators. How would you use a value type as an iterator in Java with this proposal?




--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Jimmy Jia

unread,
May 5, 2014, 8:27:15 AM5/5/14
to mechanica...@googlegroups.com
IMO the problem with the iterator case is something like

Let's say you want to pass around a stack-allocated iterator by reference.

How do you prevent someone from doing something that will cause the reference to escape? That's basically escape analysis, right? Maybe you can make this a special kind of reference that allows static escape analysis, but (1) eww, a new kind of reference (??!), and (2) it's still not an easy problem to solve.

And the flip side of it is that if you have good enough escape analysis to do this safely, you don't need value types to do this at all!

Whereas e.g. for the issue of memory layout, building efficient hash maps, &c., this kind of thing matters quite a lot, and there's no other way around it.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

Georges Gomes

unread,
May 7, 2014, 6:26:35 AM5/7/14
to mechanical-sympathy

I tend to agree with this.

Escape analysis should work fantastically to reduce GC and Gil/Martin object layout would deal with the performance aspect.

Language would be unchanged - kept simple.
I would love to see this happening.

Is escape analysis impossible to implement with great benefits or just poorly implemented right now?

Cheers
Georges

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.

Alexandru Nedelcu

unread,
May 7, 2014, 7:56:47 AM5/7/14
to mechanica...@googlegroups.com

Hi,

On Wed, May 7, 2014 at 1:26 PM, Georges Gomes <george...@gmail.com> wrote:

Escape analysis should work fantastically to reduce GC and Gil/Martin object layout would deal with the performance aspect.

Language would be unchanged - kept simple.
I would love to see this happening.

Escape Analysis as currently implemented is apparently based on the flow-insensitive escape analysis algorithm, which means that it misses a lot of opportunities for optimization. Oracle published a paper for partial escape analysis that could be better and may be implemented in future versions. However, escape analysis will never be as good or as predictable or the same as using value types. This is because it requires runtime profiling and optimizing and the opportunity for that is not without bounds - the resources used by the runtime to optimize something means that those resources aren’t used for optimizing something else or for the application to make progress.

--
Alexandru Nedelcu
www.bionicspirit.com

PGP Public Key:
https://bionicspirit.com/key.aexpk
Reply all
Reply to author
Forward
0 new messages