4 ms·

Yes. If you can generate code on the fly [1], you can handle a subset of cases very efficiently. [1]: JIT. Just in case some people confuse concepts, I'm not t

by vardump 12y ago

Yes. If you can generate code on the fly [1], you can handle a subset of cases very efficiently. [1]: JIT. Just in case some people confuse concepts, I'm not talking about JVM, virtual machines and such. Just plain runtime machine language generation.

tomp 12y ago
The problem with JIT is that it's not very simple. Sure, you can write your own single-purpose runtime-code-generating routine. But the beauty of OO is that it's widely applicable. If you want to achieve comparable speeds with JIT, you pretty much need some sort of a virtual machine; in particular, simple method-at-a-time JITs are not very efficient; you need some sort of measuring or tracing, so that you know what code to compile and how to optimize it.
- vardump 12y ago
  Sure high performance generic JITs are not simple. NOTE: Following is meant for dynamically dispatched lightweight methods, like those that just read (or compare) or store (or modify) some simple field value or do other simple operations where dispatch and call frame setup costs dominate. In inner loops which are executed enough many times that the codegen overhead is less. The rationale is that branches are very expensive on modern CPUs, especially indirect subroutine (= method or function) calls. Consistently 14-20 clock cycles lost in addition to whatever time call frame setup takes, pushing and popping registers from stack. If inner loop cost is otherwise just a cycle or two and the dispatched method is trivial, it's easy to see how branch mispredict and call setup costs can dominate. In some cases some unrolling and prefetching could be done in addition. In this case I envision routines that fuse (inline) dynamically dispatched (function pointer, message passing, pattern recognition) method inside a loop. A compiler could generate the rules and runtime system can do the actual composition. The method would then be dynamically inlined within the loop. No call, no function pointer call (=vtable), no full pattern recognition, no message dispatch, etc. Just fused, inlined code. Pattern match can't be completely resolved early? Just generate code inside the loop that does the rest of the work with tests and branches. Try the most likely case always first (may require some profiling). Same with other dynamic dispatch. Many cases, but known exponential distribution of probabilities? Inline some most likely cases, dynamically dispatch the rest. Like before, most likely first and some profiling may be required. This way very expensive (data dependent) indirect function call is avoided. Call frame setup and teardown is avoided. The savings can be an order of magnitude for short dispatched methods. Definitely no complete virtual machine needed. Note: Edited multiple times.
  - tomp 12y ago
    Hm... not sure if I agree (if I understand this correctly). If in the inner loop, the same method is called (of the same class), this means that the target of the indirect function call is always the same, and I assume that the CPU can predict that. If not, the compiler can hoist the lookup out of the loop. In certain languages, e.g. in Objective C (where lookups are dynamic, and much more expensive than vtable approach), it's a common programming pattern to manually hoist the lookup out of the loop, get the method descriptor (i.e. the jump target) and call the descriptor in the loop, without going through the lookup again. If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach.
    - vardump 12y ago
      Well, last I checked, the cost for an indirect function call for simple operations was about 5-10x compared to inlining. Each function call constitutes of at least two branches - the call and return. Caller needs to preserve any registers that may be altered by the callee according to ABI conventions. Same for callee. That is for correctly branch predicted calls. Far worse for mispredicted calls. > If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach. Say 90% of the objects are of certain same type and the code generator knows that. Codegen puts the test for this case as first one and inlines the code directly in the loop body. Then you can at least have those 5-10x savings in 90% of cases and have branch mispredicts for the rest of the time. That can still be a significant saving.

by vardump 12y ago

tomp 12y ago

The problem with JIT is that it's not very simple. Sure, you can write your own single-purpose runtime-code-generating routine. But the beauty of OO is that it's widely applicable. If you want to achieve comparable speeds with JIT, you pretty much need some sort of a virtual machine; in particular, simple method-at-a-time JITs are not very efficient; you need some sort of measuring or tracing, so that you know what code to compile and how to optimize it.

vardump 12y ago
Sure high performance generic JITs are not simple. NOTE: Following is meant for dynamically dispatched lightweight methods, like those that just read (or compare) or store (or modify) some simple field value or do other simple operations where dispatch and call frame setup costs dominate. In inner loops which are executed enough many times that the codegen overhead is less. The rationale is that branches are very expensive on modern CPUs, especially indirect subroutine (= method or function) calls. Consistently 14-20 clock cycles lost in addition to whatever time call frame setup takes, pushing and popping registers from stack. If inner loop cost is otherwise just a cycle or two and the dispatched method is trivial, it's easy to see how branch mispredict and call setup costs can dominate. In some cases some unrolling and prefetching could be done in addition. In this case I envision routines that fuse (inline) dynamically dispatched (function pointer, message passing, pattern recognition) method inside a loop. A compiler could generate the rules and runtime system can do the actual composition. The method would then be dynamically inlined within the loop. No call, no function pointer call (=vtable), no full pattern recognition, no message dispatch, etc. Just fused, inlined code. Pattern match can't be completely resolved early? Just generate code inside the loop that does the rest of the work with tests and branches. Try the most likely case always first (may require some profiling). Same with other dynamic dispatch. Many cases, but known exponential distribution of probabilities? Inline some most likely cases, dynamically dispatch the rest. Like before, most likely first and some profiling may be required. This way very expensive (data dependent) indirect function call is avoided. Call frame setup and teardown is avoided. The savings can be an order of magnitude for short dispatched methods. Definitely no complete virtual machine needed. Note: Edited multiple times.
- tomp 12y ago
  Hm... not sure if I agree (if I understand this correctly). If in the inner loop, the same method is called (of the same class), this means that the target of the indirect function call is always the same, and I assume that the CPU can predict that. If not, the compiler can hoist the lookup out of the loop. In certain languages, e.g. in Objective C (where lookups are dynamic, and much more expensive than vtable approach), it's a common programming pattern to manually hoist the lookup out of the loop, get the method descriptor (i.e. the jump target) and call the descriptor in the loop, without going through the lookup again. If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach.
  - vardump 12y ago
    Well, last I checked, the cost for an indirect function call for simple operations was about 5-10x compared to inlining. Each function call constitutes of at least two branches - the call and return. Caller needs to preserve any registers that may be altered by the callee according to ABI conventions. Same for callee. That is for correctly branch predicted calls. Far worse for mispredicted calls. > If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach. Say 90% of the objects are of certain same type and the code generator knows that. Codegen puts the test for this case as first one and inlines the code directly in the loop body. Then you can at least have those 5-10x savings in 90% of cases and have branch mispredicts for the rest of the time. That can still be a significant saving.