5 ms·

AFAIK not nearly enough stuff gets caught by escape analysis - and thus stack allocated - to make a difference.

kibwen 2y ago
I'm open to believing that this is true, but some real numbers would be nice. Surely it wouldn't be a hugely invasive change to fork the Go compiler, change the stack allocation check to `return false`, and then measure the overhead of the garbage collector on real Go programs with stack allocation both enabled and disabled.
- DamonHD 2y ago
  I may have been answering past you - I am thinking of Java running on the JDK here. And indeed I may be out of date also.
  - cempaka 2y ago
    Yeah in Java land specifically I think the question would become, "does the generational hypothesis still hold up once we have Valhalla and a much larger share of short-lived objects are stack allocated as value types?" but of course it may be years until the ecosystem reaches that point, if ever.
    - neonsunset 2y ago
      As shown by C#, it will generally continue to be relevant since both primarily use JIT compilation with ability to modify code at runtime which can violate inter-procedural escape analysis assumptions leading to heap allocations of the objects that are passed down to the callees (there is work scheduled for .NET 10 to address this, at least for AOT compilation where interproc analysis conclusions will be impossible to violate). You can craft a workload which violates the hypothesis by only allocating objects that live for a long time but both JVM and .NET GC implementations are still much faster designs than Go's GC which prioritizes small memory footprint and consistent latency on low allocation traffic (though as of .NET 9, SRV GC puts much more priority on this, making similar tradeoffs).
      - cempaka 2y ago
        > ability to modify code at runtime Would Java's moves towards "integrity by default" mean that this could be ruled out in more cases?
        neonsunset 2y ago
        Reading through the JEP again it does not seem to be related - it is about deprecating unsafe APIs that the executed code itself uses. OpenJDK also has "partial escape analysis" where the object that only conditionally escapes can still be placed on the stack/scalar replaced. I'm not privy to the exact APIs that OpenJDK exposes but in .NET the main limitation around escape analysis that spans multiple methods is the fact that CoreCLR has re-JIT API which allows to perform a multitude of actions like attaching a profiler or a debugger to a live application and forcing the runtime to deoptimize a particular method for debugging, or modifying the implementation and re-JITting the result. Debug codegen is very different especially around GC liveness tracking and escape analysis that builds on top of it - it means that even debug code would have to uphold stack-allocated nature of such object in some way, complicating the design significantly. In addition to that, debuggers and other instrumentation may observe object references that would have otherwise not escaped local scope. This creates an unfortunate situation where the above almost never happens in production, but ignoring it and "just stack-allocating anyway" would lead to disastrous breakage for all sorts of existing instrumentation. Because Go does not have to deal with this constraint, it can perform interproc escape analysis without risk - whether a pointer escapes or not can be statically proven. For NativeAOT, .NET could approach this problem in the same way, but paraphrasing compiler team: "We would like to avoid optimizations only available for one of the target types be it JIT or AOT, and only supporting AOT would not benefit the majority of the .NET users". There is, however, recognition that more comprehensive interproc analysis could be very beneficial, including the EA which is why it is planned to work on it in .NET 10: - https://github.com/dotnet/runtime/issues/108931 https://github.com/dotnet/runtime/issues/108931 IPA framework - https://github.com/dotnet/runtime/issues/104936 https://github.com/dotnet/runtime/issues/104936 Stack allocation enhancements
        cempaka 2y ago
  - DamonHD 2y ago
    Ahem --- JDK => JVM!
- DarkNova6 2y ago
  The reason escape analysis is not "good enough" is why we have project Valhalla trying to bring Value Types into the JVM. I don't have numbers at hand, but I remember the JDK Expert Group talking about this extensively in the past and why they deferred bringing Value Types for such a long time. They hoped complex enough EA can get rid of indirections and heap allocations but it just wasn't powerful enough, even with all advances throughout the years.
fweimer 2y ago
Historically, Hotspot's escape analysis only resulted in avoided heap allocations (via scalar replacement) if all uses were inlined. I don't think this has changed.
eikenberry 2y ago
Is there a language that makes this explicit, allocates the variables on the stack via compiler enforced notation?
- fanf2 2y ago
  C, C++, Rust, Zig, …
  - im3w1l 2y ago
    I'm not sure about Zig, but what strikes me about the others are that they change the type of the object. T vs T*. It would be kind of neat if you could have an annotation on the variable instead that didn't change the type. You could in C++ make a reference T& which is almost that - references behave identically to the real thing. But I think freeing the memory backing a reference is probably quite questionable?
  - eikenberry 2y ago
    What's Zig's notation for it?
    - masklinn 2y ago
      Not doing anything, same as the other 3. Heap allocation is what requires requesting memory from an allocator.
      - eikenberry 2y ago
        Right.. been using GC languages to long. Everything allocated to the stack unless it is specifically allocated to the heap. I was stuck thinking about what the keywords were. But I'm still curious.. are there any GC languages that have a way to specify if something should go on the stack or the heap?
        masklinn 2y ago
        > are there any GC languages that have a way to specify if something should go on the stack or the heap? I think only in the sense that some GCd language have value (stack) types as a separate hierarchy from heap types? E.g. structs in C# or Swift are stack-allocated (and value-identity, and copied) whereas classes are heap-allocated. Adding that for java is one of the goals of Project Valhalla I believe.
masklinn 2y ago
Go has much more significant stack allocation capabilities, most notably it has no problem allocating entire structs on the stack so doesn't need scalar replacement, which falls over if you breathe on it (https://pkolaczk.github.io/overhead-of-optional/ https://pkolaczk.github.io/overhead-of-optional/). According to https://github.com/golang/go/discussions/70257#discussioncomment-11201305 https://github.com/golang/go/discussions/70257#discussioncom... > the weak generational hypothesis does not hold up well with respect to heap-allocated memory in many real-world Go programs (think 60-70% young object mortality vs. the 95% typically expected)

I'm open to believing that this is true, but some real numbers would be nice. Surely it wouldn't be a hugely invasive change to fork the Go compiler, change the stack allocation check to `return false`, and then measure the overhead of the garbage collector on real Go programs with stack allocation both enabled and disabled.

DamonHD 2y ago
I may have been answering past you - I am thinking of Java running on the JDK here. And indeed I may be out of date also.
- cempaka 2y ago
  Yeah in Java land specifically I think the question would become, "does the generational hypothesis still hold up once we have Valhalla and a much larger share of short-lived objects are stack allocated as value types?" but of course it may be years until the ecosystem reaches that point, if ever.
  - neonsunset 2y ago
    As shown by C#, it will generally continue to be relevant since both primarily use JIT compilation with ability to modify code at runtime which can violate inter-procedural escape analysis assumptions leading to heap allocations of the objects that are passed down to the callees (there is work scheduled for .NET 10 to address this, at least for AOT compilation where interproc analysis conclusions will be impossible to violate). You can craft a workload which violates the hypothesis by only allocating objects that live for a long time but both JVM and .NET GC implementations are still much faster designs than Go's GC which prioritizes small memory footprint and consistent latency on low allocation traffic (though as of .NET 9, SRV GC puts much more priority on this, making similar tradeoffs).
    - cempaka 2y ago
      > ability to modify code at runtime Would Java's moves towards "integrity by default" mean that this could be ruled out in more cases?
      - neonsunset 2y ago
        Reading through the JEP again it does not seem to be related - it is about deprecating unsafe APIs that the executed code itself uses. OpenJDK also has "partial escape analysis" where the object that only conditionally escapes can still be placed on the stack/scalar replaced. I'm not privy to the exact APIs that OpenJDK exposes but in .NET the main limitation around escape analysis that spans multiple methods is the fact that CoreCLR has re-JIT API which allows to perform a multitude of actions like attaching a profiler or a debugger to a live application and forcing the runtime to deoptimize a particular method for debugging, or modifying the implementation and re-JITting the result. Debug codegen is very different especially around GC liveness tracking and escape analysis that builds on top of it - it means that even debug code would have to uphold stack-allocated nature of such object in some way, complicating the design significantly. In addition to that, debuggers and other instrumentation may observe object references that would have otherwise not escaped local scope. This creates an unfortunate situation where the above almost never happens in production, but ignoring it and "just stack-allocating anyway" would lead to disastrous breakage for all sorts of existing instrumentation. Because Go does not have to deal with this constraint, it can perform interproc escape analysis without risk - whether a pointer escapes or not can be statically proven. For NativeAOT, .NET could approach this problem in the same way, but paraphrasing compiler team: "We would like to avoid optimizations only available for one of the target types be it JIT or AOT, and only supporting AOT would not benefit the majority of the .NET users". There is, however, recognition that more comprehensive interproc analysis could be very beneficial, including the EA which is why it is planned to work on it in .NET 10: - https://github.com/dotnet/runtime/issues/108931 https://github.com/dotnet/runtime/issues/108931 IPA framework - https://github.com/dotnet/runtime/issues/104936 https://github.com/dotnet/runtime/issues/104936 Stack allocation enhancements
        cempaka 2y ago
- DamonHD 2y ago
  Ahem --- JDK => JVM!
DarkNova6 2y ago
The reason escape analysis is not "good enough" is why we have project Valhalla trying to bring Value Types into the JVM. I don't have numbers at hand, but I remember the JDK Expert Group talking about this extensively in the past and why they deferred bringing Value Types for such a long time. They hoped complex enough EA can get rid of indirections and heap allocations but it just wasn't powerful enough, even with all advances throughout the years.

fweimer 2y ago

Historically, Hotspot's escape analysis only resulted in avoided heap allocations (via scalar replacement) if all uses were inlined. I don't think this has changed.

eikenberry 2y ago

Is there a language that makes this explicit, allocates the variables on the stack via compiler enforced notation?

fanf2 2y ago
C, C++, Rust, Zig, …
- im3w1l 2y ago
  I'm not sure about Zig, but what strikes me about the others are that they change the type of the object. T vs T*. It would be kind of neat if you could have an annotation on the variable instead that didn't change the type. You could in C++ make a reference T& which is almost that - references behave identically to the real thing. But I think freeing the memory backing a reference is probably quite questionable?
- eikenberry 2y ago
  What's Zig's notation for it?
  - masklinn 2y ago
    Not doing anything, same as the other 3. Heap allocation is what requires requesting memory from an allocator.
    - eikenberry 2y ago
      Right.. been using GC languages to long. Everything allocated to the stack unless it is specifically allocated to the heap. I was stuck thinking about what the keywords were. But I'm still curious.. are there any GC languages that have a way to specify if something should go on the stack or the heap?
      - masklinn 2y ago
        > are there any GC languages that have a way to specify if something should go on the stack or the heap? I think only in the sense that some GCd language have value (stack) types as a separate hierarchy from heap types? E.g. structs in C# or Swift are stack-allocated (and value-identity, and copied) whereas classes are heap-allocated. Adding that for java is one of the goals of Project Valhalla I believe.

masklinn 2y ago

Go has much more significant stack allocation capabilities, most notably it has no problem allocating entire structs on the stack so doesn't need scalar replacement, which falls over if you breathe on it (https://pkolaczk.github.io/overhead-of-optional/ https://pkolaczk.github.io/overhead-of-optional/). According to https://github.com/golang/go/discussions/70257#discussioncomment-11201305 https://github.com/golang/go/discussions/70257#discussioncom... > the weak generational hypothesis does not hold up well with respect to heap-allocated memory in many real-world Go programs (think 60-70% young object mortality vs. the 95% typically expected)