3 ms·

Yeah, it strikes me as an odd choice that V8 doesn't just use C code for something as central and important as sorting, but maybe there's some technical reason.

inbx0 5y ago
There's probably some overhead for switching between a C++ implementation and user-defined JS, and the sorter would need to do that a lot since most sort calls come with the compare-callback.
- derefr 5y ago
  My understanding comes from Erlang’s HiPE optimizer (which was AoT rather than a JIT), but I think you’ve nailed it. Most JITs can’t optimize across a native↔interpreted boundary, any more than compilers can optimize across a dynamic-linkage (dlopen(2)) boundary. When all the code is interpreted, you get something that’s a lot more WPO-like. IIRC, some very clever JITs do a waltz here: 1. replace the user’s “syscall” into the runtime, with emitted bytecode; 2. WPO the user’s bytecode together with the generated bytecode; 3. Find any pattern that still resembles the post-optimization form of part of the bytecode equivalent of the call into the runtime, and replace it back with a “syscall” to the runtime, for doing that partial step. Maybe clearer with an example. Imagine there’s a platform-native function sha256(byte[]). The JIT would: 1. Replace the call to sha256(byte[]) with a bytecode loop over the buffer, plus a bunch of logic to actually do a sha256 to a fixed-size register; 2. WPO the code with that bytecode loop embedded; 3. Replace the core of the remnants of the sha256-to-a-fixed-size-register code, with a call to a platform-native sha256(register) function.
pornel 5y ago
For some functions speed-up from inlining and run-time specialization via JIT outweigh the benefit of native code speed. There's similarly a cost in crossing JS<>WASM boundary, so WASM doesn't help for speeding up small functions and can't make DOM-heavy code faster.
masklinn 5y ago
> maybe there's some technical reason Native code is opaque to the JIT, which means no inlining through native code (inlining being the driver for lots of optimisations) and no specialisation. This means if you have a JIT native code is fine for "leaf" functions but not great for intermediate ones, as it hampers everything. When ES6 compatibility was first released, the built-in array methods were orders of magnitude slower than hand-rolling pure JS versions. This issue is one of the things Graal/Truffle attempts to fix, by moving the native code inside the JIT.

inbx0 5y ago

There's probably some overhead for switching between a C++ implementation and user-defined JS, and the sorter would need to do that a lot since most sort calls come with the compare-callback.

derefr 5y ago
My understanding comes from Erlang’s HiPE optimizer (which was AoT rather than a JIT), but I think you’ve nailed it. Most JITs can’t optimize across a native↔interpreted boundary, any more than compilers can optimize across a dynamic-linkage (dlopen(2)) boundary. When all the code is interpreted, you get something that’s a lot more WPO-like. IIRC, some very clever JITs do a waltz here: 1. replace the user’s “syscall” into the runtime, with emitted bytecode; 2. WPO the user’s bytecode together with the generated bytecode; 3. Find any pattern that still resembles the post-optimization form of part of the bytecode equivalent of the call into the runtime, and replace it back with a “syscall” to the runtime, for doing that partial step. Maybe clearer with an example. Imagine there’s a platform-native function sha256(byte[]). The JIT would: 1. Replace the call to sha256(byte[]) with a bytecode loop over the buffer, plus a bunch of logic to actually do a sha256 to a fixed-size register; 2. WPO the code with that bytecode loop embedded; 3. Replace the core of the remnants of the sha256-to-a-fixed-size-register code, with a call to a platform-native sha256(register) function.

pornel 5y ago

For some functions speed-up from inlining and run-time specialization via JIT outweigh the benefit of native code speed. There's similarly a cost in crossing JS<>WASM boundary, so WASM doesn't help for speeding up small functions and can't make DOM-heavy code faster.

masklinn 5y ago

> maybe there's some technical reason Native code is opaque to the JIT, which means no inlining through native code (inlining being the driver for lots of optimisations) and no specialisation. This means if you have a JIT native code is fine for "leaf" functions but not great for intermediate ones, as it hampers everything. When ES6 compatibility was first released, the built-in array methods were orders of magnitude slower than hand-rolling pure JS versions. This issue is one of the things Graal/Truffle attempts to fix, by moving the native code inside the JIT.