4 ms·

In JVM languages maybe, in C++ with the CRTP there's zero overhead for sure

frankzinger 8y ago
Why the CRTP? Plenty of zero-overhead Visitors have been implemented with regular templates. I don't see the connection.
- humanrebar 8y ago
  It's moot either way. There is dynamic dispatch based on use provided inputs. There will always be lookups, jumps, and cache misses regardless of the syntax or semantics.
  - frankzinger 8y ago
    Is it moot? With templates, the Visitor type is selected at compile time and needn't even be polymorphic. The member function call(s) can often be inlined. Pretty sure there is no dynamic dispatch or jumps in such a scenario. Cache misses, sure, but I don't think that's important in this case.
    - humanrebar 8y ago
      Almost always these systems operate on external inputs like source files or JSON blobs. You cannot compile time collapse the branching needed to parse that sort of thing.
xxs 8y ago
Polymorhic call sites can hardly be called 'zero overhead' - they remove any chance for inlining to begin with. So no, JVM is not amongst them
- KirinDave 8y ago
  Since you're on the hook for a polymorphic call anyways in a rewrite of a runtime runtime structure, I think this is not the "overhead" that anyone was talking about.
  - xxs 8y ago
    Overhead would "loosely" relate to better performance, and v-table dispatch type that visitor pattern is built upon, cannot be considered 'zero overhead'. It's a trade off and the article shows no proof the of an improved performance by reducing the 'overhead'. For example object allocation in JVM is really cheap (pointer bump in the TLAB + check&perfectly predicted jump), reusing objects in a cycling list/buffer is similar, etc. In the end the post is about performance and I pointed that the multiple mentions of 'zero overhead' are incorrect.
    - KirinDave 8y ago
      Ah yes. So triggering a GC in the middle of your duplicated tree-on-heap traversal will totally not risk any pipeline stalls. I'm sure that N vtable calls per node is totally worse than re-enumerating the objects on the heap N times. When I talk about how the OO community has anti-intellectual toxicity can try to buzzword bingo architecture away, Visitor is my go to example. Because that's sure what it seems like to me. You will 100% end up with pipeline stalls with a sufficiently large, random input anyways. This complaint about vtables is not substantial in this case, and I welcome you to prove they do.
- weberc2 8y ago
  I don’t think this is true. If you know the set of functions that can be dispatched to, you could inline them in a jump table / switch statement. JVM could definitely do this since it doesn’t even need to know the full set; it could inline new functions as it encounters them. This is all theoretical, of course.
  - xxs 8y ago
    There are inline caches (IC) and JVM uses that to a point. The inline caching for hotspot is 2 targets with guard checks[0] and then a polymorphic call. However if there are no dominating/common calls the IC is useless. On top of that JVM has an inline budget and just stops at a point. So the switch stuff ain't happening for megamorph. [0]:https://blog.h2o.ai/2010/04/inline-caches-and-call-site-optimization/ https://blog.h2o.ai/2010/04/inline-caches-and-call-site-opti...
  - dnomad 8y ago
    This is exactly what the JVM does. See [0]. [0] https://mechanical-sympathy.blogspot.com/2012/04/invoke-interface-optimisations.html https://mechanical-sympathy.blogspot.com/2012/04/invoke-inte...
    - xxs 8y ago
      >>jump table / switch statement. >This is exactly what the JVM does. See [0]. The jump table from Martin's blog is the virtual call one.
  - MrBuddyCasino 8y ago
    Monomophisation is a common optimization on the JVM, combined with a guard condition that de-optimizes should the type assertion fail. Not sure if that only affects the hot path.

Why the CRTP? Plenty of zero-overhead Visitors have been implemented with regular templates. I don't see the connection.

humanrebar 8y ago
It's moot either way. There is dynamic dispatch based on use provided inputs. There will always be lookups, jumps, and cache misses regardless of the syntax or semantics.
- frankzinger 8y ago
  Is it moot? With templates, the Visitor type is selected at compile time and needn't even be polymorphic. The member function call(s) can often be inlined. Pretty sure there is no dynamic dispatch or jumps in such a scenario. Cache misses, sure, but I don't think that's important in this case.
  - humanrebar 8y ago
    Almost always these systems operate on external inputs like source files or JSON blobs. You cannot compile time collapse the branching needed to parse that sort of thing.

xxs 8y ago

Polymorhic call sites can hardly be called 'zero overhead' - they remove any chance for inlining to begin with. So no, JVM is not amongst them

KirinDave 8y ago
Since you're on the hook for a polymorphic call anyways in a rewrite of a runtime runtime structure, I think this is not the "overhead" that anyone was talking about.
- xxs 8y ago
  Overhead would "loosely" relate to better performance, and v-table dispatch type that visitor pattern is built upon, cannot be considered 'zero overhead'. It's a trade off and the article shows no proof the of an improved performance by reducing the 'overhead'. For example object allocation in JVM is really cheap (pointer bump in the TLAB + check&perfectly predicted jump), reusing objects in a cycling list/buffer is similar, etc. In the end the post is about performance and I pointed that the multiple mentions of 'zero overhead' are incorrect.
  - KirinDave 8y ago
    Ah yes. So triggering a GC in the middle of your duplicated tree-on-heap traversal will totally not risk any pipeline stalls. I'm sure that N vtable calls per node is totally worse than re-enumerating the objects on the heap N times. When I talk about how the OO community has anti-intellectual toxicity can try to buzzword bingo architecture away, Visitor is my go to example. Because that's sure what it seems like to me. You will 100% end up with pipeline stalls with a sufficiently large, random input anyways. This complaint about vtables is not substantial in this case, and I welcome you to prove they do.
weberc2 8y ago
I don’t think this is true. If you know the set of functions that can be dispatched to, you could inline them in a jump table / switch statement. JVM could definitely do this since it doesn’t even need to know the full set; it could inline new functions as it encounters them. This is all theoretical, of course.
- xxs 8y ago
  There are inline caches (IC) and JVM uses that to a point. The inline caching for hotspot is 2 targets with guard checks[0] and then a polymorphic call. However if there are no dominating/common calls the IC is useless. On top of that JVM has an inline budget and just stops at a point. So the switch stuff ain't happening for megamorph. [0]:https://blog.h2o.ai/2010/04/inline-caches-and-call-site-optimization/ https://blog.h2o.ai/2010/04/inline-caches-and-call-site-opti...
- dnomad 8y ago
  This is exactly what the JVM does. See [0]. [0] https://mechanical-sympathy.blogspot.com/2012/04/invoke-interface-optimisations.html https://mechanical-sympathy.blogspot.com/2012/04/invoke-inte...
  - xxs 8y ago
    >>jump table / switch statement. >This is exactly what the JVM does. See [0]. The jump table from Martin's blog is the virtual call one.
- MrBuddyCasino 8y ago
  Monomophisation is a common optimization on the JVM, combined with a guard condition that de-optimizes should the type assertion fail. Not sure if that only affects the hot path.