4 ms·
The heap is an implementation detail. With escape analysis, the compiler can allocate the data on the heap, stack, or even stick it in registers. https://www.
by shagie 6y ago
The heap is an implementation detail.
With escape analysis, the compiler can allocate the data on the heap, stack, or even stick it in registers.
https://www.beyondjava.net/escape-analysis-java https://www.beyondjava.net/escape-analysis-java
https://shipilev.net/jvm/anatomy-quarks/18-scalar-replacement/ https://shipilev.net/jvm/anatomy-quarks/18-scalar-replacemen...
https://www.javaadvent.com/2020/12/seeing-escape-analysis-working.html https://www.javaadvent.com/2020/12/seeing-escape-analysis-wo...
- anonymoushn 6y agoCan you have an array of 1 million structs, not pointers to structs?
- shagie 6y agoThe first question is "through static analysis, can you guarantee that the structs do not leave the scope?" The second question to look at is "which JVM are you using?" Different JVMs may implement this differently. This isn't something that one can say about Java. It is something that one might be able to say about HotSpot, Zulu, or GraalVM.
- iainmerrick 6y agoYou’re technically correct that this stuff is all possible in principle, but the answer in practice right now is “no”.
- shagie 6y agoFrom the link about GraalVM: > Something that Graal can do that C2 cannot, and a key advantage of GraalVM, is partial escape analysis. Instead of determining a binary value of whether an object escapes the compilation unit or not, this can determine on which branches an object escapes it, and move allocation of the object to only those branches where it escapes. And from https://docs.oracle.com/en/java/javase/11/vm/java-hotspot-virtual-machine-performance-enhancements.html#GUID-6BD8FCB5-995B-4AE9-BFAA-B2C7DE2BA5CD https://docs.oracle.com/en/java/javase/11/vm/java-hotspot-vi... > The Java HotSpot Server Compiler implements the flow-insensitive escape analysis algorithm described in: > ... > After escape analysis, the server compiler eliminates the scalar replaceable object allocations and the associated locks from generated code. The server compiler also eliminates locks for objects that do not globally escape. It does not replace a heap allocation with a stack allocation for objects that do not globally escape. ---- So, some JVMs implement, others only do a limited subset of the optimizations available with escape analysis. I would not say that the answer of "is it used in practice" is "no."
- dtech 6y agoGraalVM is excellent in performing escape analysis on objects on the call stack, but it does not prevent the pointer overhead that a JVM array-of-heap-object-references has vs an array-of-structs that e.g. .NET supports [2]. Theoretically it could do hat, but that's just the classic "sufficient smart compiler" strawman [1] [1] https://wiki.c2.com/?SufficientlySmartCompiler https://wiki.c2.com/?SufficientlySmartCompiler [2] https://stackoverflow.com/questions/29665748/memory-allocation-for-an-array-of-struct-and-class-object https://stackoverflow.com/questions/29665748/memory-allocati...
- shagie 6y agoMy point wasn't so much "can GraalVM do {some optimization}" but rather that the Java Language Specification doesn't say anything about it and that different JVMs have a different set of optimizations. So "does Java allocate a record in an array directly as some structure of values in the array or as a pointer to a record object?" isn't one that can be answered by looking at Java. It is an interesting question, and I'd be curious to see someone do a deep dive into the internals of GraalVM to show what can be done. The other part that trickled out in other comments from the person posing the question about the array of records: > It's a global array of structs, let's say. and > No, because my competitors who are attempting to fill the same orders I am attempting to fill are not chasing pointers. ... which, I'd be curious to see how .NET supports an array of struts (that are presumably changing over the lifetime of the array) that is allocated as a global. That sort of use case and the specifics of how it is implemented could make escape analysis give up and you'll see an array on the heap with pointers to records on the heap as they're passed off to different threads (which each have their own stack).
- dtech 6y agoThe point is those optimizations are not here now, and haven't been there for the last 25 years. Hand-waving them away as theoretically possible is dishonest. We're 25 years into the most popular programming language's lifetime and the most advanced VM available only recently learned good escape analysis. It isn't easy. > which, I'd be curious to see how .NET supports an array of struts (that are presumably changing over the lifetime of the array) that is allocated as a global. Very easy. An array-of-structs (which can still be on the heap mind you) will just be a continuous block of memory. This is totally independent of any locking and synchronization. For example in a class with 2 32-bit fields, and an array of objects a b object-ref array will look like: [p_ap_b], p being a pointer to [a_0a_1] or [b_0b_1]. A struct-array will look like [a_0a_1b_0b_1].
- kelnos 6y agoSure, but I think that's still important that it's possible. And if it doesn't get implemented, the reason may be because JVM developers have done the work to figure out that in the real world the optimization doesn't buy all that much. Regardless, if you care about performance enough (via actual benchmarks) that you know that you really need some data to be guaranteed to be stack-allocated structs, then you probably shouldn't be using Java (or any GC'd language?) in the first place. Records don't change that calculus.
- anonymoushn 6y agoIt's a global array of structs, let's say.
- shagie 6y agoIf it's a global, it's very likely allocated on the heap. The question of "what is the representation of the object on the heap?" then open. However, the "this is global" complicates it. This isn't a question for Java to answer. You would need to dig into the specifics of the particular VM that you are using and how it allocates such a structure along with what optimizations it has available.
- im3w1l 6y ago1 million is not a lot. I'd begin by asking myselves "can I afford to chase those pointers?", because maybe you can.
- anonymoushn 6y agoNo, because my competitors who are attempting to fill the same orders I am attempting to fill are not chasing pointers.
- secondcoming 6y agoare your competitors using java?
- anonymoushn 6y agoJava is relatively common in HFT yes.
- jandrese 6y agoYou are chasing nanoseconds with a garbage collected language?
- jhgb 6y agoThose nanoseconds tend to add up.
- Bjartr 6y agoThat's a good question to ask when faced with a problem that could be solved that way, but a real answer to the question would be useful too.
- deleted 6y ago[deleted]
- Someone 6y agoJava compilers are getting more and more advanced, but I don’t think they will ever become the magical “sufficiently advanced compiler” that produces code that’s as good as humans _could_ (but often won’t, because of time constraints) write. I don’t think anybody fully disagrees with that. At least, I haven’t heard people claim int can be removed from the language because a good compiler can produce identical code for Integers. And yes, that can also apply to instances that do escape. A sufficiently advanced compiler could in some/many cases figure out that an array of Integer can be compiled down to an array of int. However, it’s way easier for a compiler to check a programmer’s claim “we won’t use features of Integer on these ints” than to deduce that code won’t, so a little bit of programmer effort allows for a simpler compiler that can produce faster code. For me, records and (future) value types are examples of such “little bits of programmer effort”
- eklavya 6y agoI could be wrong but I don’t think dart has ints, I think it only has objects.
- Someone 6y agohttps://api.dart.dev/stable/2.6.0/dart-core/int-class.html https://api.dart.dev/stable/2.6.0/dart-core/int-class.html: “Classes cannot extend, implement, or mix in int.” https://api.dart.dev/stable/2.6.0/dart-core/num-class.html https://api.dart.dev/stable/2.6.0/dart-core/num-class.html: “It is a compile-time error for any type other than int or double to attempt to extend or implement num.” ⇒ it seems that, technically, you’re right. int is an object in Dart. At the same time, it’s a restricted type of object. So restricted that I think it is aan object only in name/at compile time.