4 ms·

The JVM can elide most of the Java bounds checks because it has much more static information from Java class files than is available from C code. Once you're e

by KMag 3y ago

The JVM can elide most of the Java bounds checks because it has much more static information from Java class files than is available from C code. Once you're emulating a memory-unsafe language, you lose most of those static semantic guarantees you get from valid Java code. In the general case, in a memory unsafe language, statically removing bounds checks is equivalent to solving the halting problem. One could definitely add some extra load-time static analysis to the JVM, similar to what the NaCL / PNaCL did at binary load time to greatly increase the opportunities for JVM bounds check removal. However, this would need some extensions to the class file format and/or some new class file annotations to expose some more static information than the JVM has for vanilla Java class files. In addition, there are also plenty of ways one could optimize away some bounds checks based on undefined behavior, which would result in a standards-conforming C implementation, yet break tons of C code in the wild. (There at least used to be a C to Go transpiler that implemented C unions this way.) For instance, it's UB to write to one field of a union and then read another field, so it'd be legal for a compiler to implement a union as a struct. However, there's plenty of code in the wild (such as many nanboxing/nunboxing implementations) that rely on union fields occupying the same physical addresses.

kaba0 3y ago
A JIT compiler doesn’t operate at that compile time, so it simply doesn’t have to solve it statically — it notices that this invocation at this place always uses 46 for n, so it can use it as a constant for its compilation, at which point it is more than possible to elide many checks.
- KMag 3y ago
  Bounds checks are either runtime checks or removed by static analysis. JIT just pushes back the time at which that static analysis is done and increases the amount of context available (largely through inlining). It's still fundamentally static analysis, just run at JIT time, not at class file generation time. My point is that the JIT-time static analysis in the JVM is heavily optimized for memory accesses typical of Java programs. Typical C code is drastically different, especially since pointer arithmetic is common in C code. In order to properly statically check an access via pointer arithmetic from a pointer allocated via malloc(), the JIT would need to be operating over a code fragment that included both the malloc call (to know where the base address is relative to the bound) and the memory access site. Lots of C code has way too much code executing between malloc and your pointer arithmetic to reasonably expect that the JIT is going to have all of that code in the execution trace it's currently optimizing. In the specific case suggested above, just using a giant byte array to represent all of memory, bounds-checking some memory access to an arithmetic-modified pointer gotten from malloc(), the bounds removal would be dependent on the exact address returned by malloc(). In some programs, maybe there's tons of access to a small number of buffers allocated at program start-up time. In that case, current JVMs might do a pretty good job at eliding bounds checks by noticing that the base address is usually one of a small number of values and having a dedicated code path for those common cases. However, if you're doing frequent malloc(), then you're getting tons of different base addresses. In other programs, the malloc() and the access will be close enough together that the JIT'd fragment will include both the malloc and the access, in which case the JVM will have enough context to elide the bounds access. However, it's way too hand-wavy to just say the JVM is good at eliding array bounds checks. The JVM is very good at eliding array bounds checks typical of Java programs. This is very different from eliding array bounds checks typical in memory-unsafe languages.
- KMag 3y ago
  I'm really interested in this space. I'm the original author of the Wikipedia page on SafeTSA. I really want compiling to native code to be as common as writing inline assembly currently is (and I see no fundamental reason why it won't eventually be). I used to be one of 5 developers for the most popular Java desktop program in the early 2000s. I have some ideas for hardware features to reduce the overhead of run-time code re-optimization based on real-time profiles. I guess when I eventually retire, I'll play around with an FPGA CPU implementation of my ideas. I really believe JITs can do what you're describing, but I think it's important not to over-sell current JIT implementations. Over-selling the technology results in skepticism. In my ideal world, we compile to either a high-level control-flow-graph/static-single-assignment representation (maybe similar to SafeTSA) as a distribution format. At installation time, we AoT-compile to native code (similar to the current Android runtime). At run-time, we take advantage of extremely low overhead hardware profiling/tracing features to re-optimize hot spots. Optimal ordering/inclusion of various optimizations is a bit of a black art, so I expect some degree of randomization here. In cases where profiling shows the re-optimized code out-performs the AoT version, we'd then cache the re-optimizations to disk. Optionally, a periodic process would periodically perform more expensive offline static-re-optimization of the AoT'd binary, similar to the current Android runtime. Crucially, the garbage collector should be decoupled from the binary generation/re-optimization system. The CPU overhead of garbage collection can be brought pretty low, but there's a size/space trade off. Last I checked, the rule of thumb is that unless you're manually pooling objects, you can expect a GC'd program to use roughly twice as much memory as an equivalent C++ program. Now, the cognitive/development overhead of manual memory management usually isn't worth the memory savings. However, I've worked in several domains where the memory savings are worth the slower development time.

by KMag 3y ago

kaba0 3y ago

A JIT compiler doesn’t operate at that compile time, so it simply doesn’t have to solve it statically — it notices that this invocation at this place always uses 46 for n, so it can use it as a constant for its compilation, at which point it is more than possible to elide many checks.

KMag 3y ago
Bounds checks are either runtime checks or removed by static analysis. JIT just pushes back the time at which that static analysis is done and increases the amount of context available (largely through inlining). It's still fundamentally static analysis, just run at JIT time, not at class file generation time. My point is that the JIT-time static analysis in the JVM is heavily optimized for memory accesses typical of Java programs. Typical C code is drastically different, especially since pointer arithmetic is common in C code. In order to properly statically check an access via pointer arithmetic from a pointer allocated via malloc(), the JIT would need to be operating over a code fragment that included both the malloc call (to know where the base address is relative to the bound) and the memory access site. Lots of C code has way too much code executing between malloc and your pointer arithmetic to reasonably expect that the JIT is going to have all of that code in the execution trace it's currently optimizing. In the specific case suggested above, just using a giant byte array to represent all of memory, bounds-checking some memory access to an arithmetic-modified pointer gotten from malloc(), the bounds removal would be dependent on the exact address returned by malloc(). In some programs, maybe there's tons of access to a small number of buffers allocated at program start-up time. In that case, current JVMs might do a pretty good job at eliding bounds checks by noticing that the base address is usually one of a small number of values and having a dedicated code path for those common cases. However, if you're doing frequent malloc(), then you're getting tons of different base addresses. In other programs, the malloc() and the access will be close enough together that the JIT'd fragment will include both the malloc and the access, in which case the JVM will have enough context to elide the bounds access. However, it's way too hand-wavy to just say the JVM is good at eliding array bounds checks. The JVM is very good at eliding array bounds checks typical of Java programs. This is very different from eliding array bounds checks typical in memory-unsafe languages.
KMag 3y ago
I'm really interested in this space. I'm the original author of the Wikipedia page on SafeTSA. I really want compiling to native code to be as common as writing inline assembly currently is (and I see no fundamental reason why it won't eventually be). I used to be one of 5 developers for the most popular Java desktop program in the early 2000s. I have some ideas for hardware features to reduce the overhead of run-time code re-optimization based on real-time profiles. I guess when I eventually retire, I'll play around with an FPGA CPU implementation of my ideas. I really believe JITs can do what you're describing, but I think it's important not to over-sell current JIT implementations. Over-selling the technology results in skepticism. In my ideal world, we compile to either a high-level control-flow-graph/static-single-assignment representation (maybe similar to SafeTSA) as a distribution format. At installation time, we AoT-compile to native code (similar to the current Android runtime). At run-time, we take advantage of extremely low overhead hardware profiling/tracing features to re-optimize hot spots. Optimal ordering/inclusion of various optimizations is a bit of a black art, so I expect some degree of randomization here. In cases where profiling shows the re-optimized code out-performs the AoT version, we'd then cache the re-optimizations to disk. Optionally, a periodic process would periodically perform more expensive offline static-re-optimization of the AoT'd binary, similar to the current Android runtime. Crucially, the garbage collector should be decoupled from the binary generation/re-optimization system. The CPU overhead of garbage collection can be brought pretty low, but there's a size/space trade off. Last I checked, the rule of thumb is that unless you're manually pooling objects, you can expect a GC'd program to use roughly twice as much memory as an equivalent C++ program. Now, the cognitive/development overhead of manual memory management usually isn't worth the memory savings. However, I've worked in several domains where the memory savings are worth the slower development time.