static vs. runtime polymorphism

[bitrex]

So there's static polymorphism using e.g the CRTP that allows
logic customization of derived types of an interface at compile time,
but does not allow for dynamic dispatch. This has low (in theory zero)
overhead as compared to runtime polymorphism.

And there's virtual methods which allow for dynamic dispatch of
overloaded derived class methods through a base class pointer, in theory
to an "infinite" number of overloads in various derived classes. And has
the usual vtable + dynamic dispatch overhead.

What I'm wondering is if there's some known hybrid approach that allows
dynamic dispatch-type behavior from a base type pointer, with the lower
overhead of static polymorphism, given the constraint (has to be a
constraint somewhere I guess or you're just talking about regular
virtual based runtime polymorphism, again) that it works only with a
limited subset of potential subclasses designed expressly for that purpose.

Or some other fashion of constraint.

Or would any solution of that type simply also be user-implemented
virtualization "in disguise." I have read a bit about the "Visitor"
pattern which seems relevant to my question but don't know enough to
know for sure. Thanks

[Alf P. Steinbach]

On 13.04.2019 18:42, bitrex wrote:
> So there's static polymorphism using e.g the CRTP that allows
> logic customization of derived types of an interface at compile time,
> but does not allow for dynamic dispatch. This has low (in theory zero)
> overhead as compared to runtime polymorphism.

CRTP can give code duplication overhead.

In the early days that was a real issue, and one wrote template classes
with strict client side type checking as wrappers around a single
`void*` state based implementation. Whose code was not duplicated.

As I recall it was Andrei Alexandrescu who first noted, somewhere in the
late 200x?, that compilers had progressed to a point where code
duplication, template code bloat, was no longer a serious issue.

> And there's virtual methods which allow for dynamic dispatch of
> overloaded derived class methods through a base class pointer, in theory
> to an "infinite" number of overloads in various derived classes. And has
> the usual vtable + dynamic dispatch overhead.
>
> What I'm wondering is if there's some known hybrid approach that allows
> dynamic dispatch-type behavior from a base type pointer, with the lower
> overhead of static polymorphism, given the constraint (has to be a
> constraint somewhere I guess or you're just talking about regular
> virtual based runtime polymorphism, again) that it works only with a
> limited subset of potential subclasses designed expressly for that purpose.
>
> Or some other fashion of constraint.

One can always dispatch on a class id.

But that's an application level indirection, to avoid a core language
level indirection, so not likely to be faster.

> Or would any solution of that type simply also be user-implemented
> virtualization "in disguise." I have read a bit about the "Visitor"
> pattern which seems relevant to my question but don't know enough to
> know for sure. Thanks

The visitor pattern just avoids or (depending on the case) centralizes
downcasting.

Again there's Andrei: he wrote at length about visitor pattern variants
in his now classic Modern C++ Design book.



Cheers!,

- Alf

[Marcel Mueller]

Am 13.04.19 um 20:34 schrieb Alf P. Steinbach:

> On 13.04.2019 18:42, bitrex wrote:
>> So there's static polymorphism using e.g the CRTP that allows
>> logic customization of derived types of an interface at compile time,
>> but does not allow for dynamic dispatch. This has low (in theory zero)
>> overhead as compared to runtime polymorphism.
>
> CRTP can give code duplication overhead.
>
> In the early days that was a real issue, and one wrote template classes
> with strict client side type checking as wrappers around a single
> `void*` state based implementation. Whose code was not duplicated.
>
> As I recall it was Andrei Alexandrescu who first noted, somewhere in the
> late 200x?, that compilers had progressed to a point where code
> duplication, template code bloat, was no longer a serious issue.

I think it is still an issue for C++, it is just no longer that
important. You can still improve cache hit rate by explicit type
erasure. This could be important under some circumstances. The compiler
can only deduplicate identical code. But sometimes it is more efficient
to deduplicate only partial code, e.g. do pointer adjustment in case of
multiple inheritance inline at the caller to keep the core function
identical. I have not seen this as compiler optimization so far.


Marcel

[bitrex]

On 4/13/19 2:34 PM, Alf P. Steinbach wrote:
> On 13.04.2019 18:42, bitrex wrote:
>> So there's static polymorphism using e.g the CRTP that allows
>> logic customization of derived types of an interface at compile time,
>> but does not allow for dynamic dispatch. This has low (in theory zero)
>> overhead as compared to runtime polymorphism.
>
> CRTP can give code duplication overhead.
>
> In the early days that was a real issue, and one wrote template classes
> with strict client side type checking as wrappers around a single
> `void*` state based implementation. Whose code was not duplicated.
>
> As I recall it was Andrei Alexandrescu who first noted, somewhere in the
> late 200x?, that compilers had progressed to a point where code
> duplication, template code bloat, was no longer a serious issue.

The CRTP I like a lot for resource-constrained embedded processors. On
modern compilers it really does seem to allow compile-time interface ->
implementation specialization with no overhead. Tools like Compiler
Explorer show me what code actually generates some asm and what doesn't.
what generally happens in most of my use cases is the appropriate calls
are all figured out and inlined where they need to go, none of the
template-tized interface "stuff" generates anything.

>> And there's virtual methods which allow for dynamic dispatch of
>> overloaded derived class methods through a base class pointer, in
>> theory to an "infinite" number of overloads in various derived
>> classes. And has the usual vtable + dynamic dispatch overhead.
>>
>> What I'm wondering is if there's some known hybrid approach that
>> allows dynamic dispatch-type behavior from a base type pointer, with
>> the lower overhead of static polymorphism, given the constraint (has
>> to be a constraint somewhere I guess or you're just talking about
>> regular virtual based runtime polymorphism, again) that it works only
>> with a limited subset of potential subclasses designed expressly for
>> that purpose.
>>
>> Or some other fashion of constraint.
>
> One can always dispatch on a class id.
>
> But that's an application level indirection, to avoid a core language
> level indirection, so not likely to be faster.

The use case for me is essentially not so much speed (the execution
cycle overhead of a vtable lookup and indirection on a modern RISC
processor is pretty darn low) but, in relatively resource constrained
embedded processors where, because reasons, vtables are copied to SRAM
when they don't strictly need to be. And if I have a lot of small class
instances the extra 4 or 8 bytes for a hidden pointer can become a
significant part of the total object size.

But sometimes I do just need to have base pointers stored in a list
where at runtime I don't know what type of derived class the pointer is
pointing to and being able to do a virtual call just makes life so much
easier.

>> Or would any solution of that type simply also be user-implemented
>> virtualization "in disguise." I have read a bit about the "Visitor"
>> pattern which seems relevant to my question but don't know enough to
>> know for sure. Thanks
>
> The visitor pattern just avoids or (depending on the case) centralizes
> downcasting.
>
> Again there's Andrei: he wrote at length about visitor pattern variants
> in his now classic Modern C++ Design book.
>

I have a copy somewhere around here, it's a pretty dense book so I've
been working my way thru it. Haven't gotten there yet I guess...

>
> Cheers!,
>
> - Alf
>
>

[David Brown]

It is often difficult to construct test examples here, and to know which
optimisations really help - sometimes optimisations that increase code
size can give faster results by fine-tuning the different function
versions, sometimes it can be slower due to cache effects, branch
buffers, etc. So getting the very best results can be a lot of effort
with testing, profiling, playing with compiler options, etc. And often
it will only give the best results on one particular system - a slightly
different cpu in the same family may need different choices.

However, modern compilers can have a lot of techniques that can help
here. For code de-duplication, this can be done by the compiler at the
level of internal code trees (long before generating assembly). It can
also be done at link time when the linker sees the same assembly for
different functions. And compilers /do/ have partial inlining and
cloning. They can clone functions and then make copies which depend on
constant propagation - it is particularly easy to see how this can work
when a function takes a "bool" parameter. Two versions - one for a
"true" parameter, one for a "false" parameter, along with a wrapper
function for an unknown value, might end up smaller and faster than a
single large function.

There are all sorts of fun optimisations to read about for compilers,
such as:

<https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html>

Some optimisations take a great deal of compilation time and memory,
however - there is no way to get everything that you might imagine.

The compiler gets its best chances with link-time optimisation. But
part of the fun of that when testing and investigating this stuff, is
that changes to one part of the code can affect the final code
generation in entirely different parts of the system.

[Öö Tiib]

On Saturday, 13 April 2019 19:42:31 UTC+3, bitrex wrote:
> So there's static polymorphism using e.g the CRTP that allows
> logic customization of derived types of an interface at compile time,
> but does not allow for dynamic dispatch. This has low (in theory zero)
> overhead as compared to runtime polymorphism.
>
> And there's virtual methods which allow for dynamic dispatch of
> overloaded derived class methods through a base class pointer, in theory
> to an "infinite" number of overloads in various derived classes. And has
> the usual vtable + dynamic dispatch overhead.

Note that when compiler can figure most derived type of object out
compile time then it can call virtual methods directly or even
inline those.

> What I'm wondering is if there's some known hybrid approach that allows
> dynamic dispatch-type behavior from a base type pointer, with the lower
> overhead of static polymorphism, given the constraint (has to be a
> constraint somewhere I guess or you're just talking about regular
> virtual based runtime polymorphism, again) that it works only with a
> limited subset of potential subclasses designed expressly for that purpose.

I do not know. The other way of dynamic polymorphism is to use
function pointers.
Bonuses compared with virtual method calls:
* calls are cheaper by one level of indirection.
* bigger flexibility since pointers can be re-directed during object's life-time.
Minuses:
* Object is bigger taking function pointer per "method".
* Object's initialization code is bigger by setting these up.
* Compilers tend to not optimize calls through function pointers.

> Or some other fashion of constraint.
>
> Or would any solution of that type simply also be user-implemented
> virtualization "in disguise." I have read a bit about the "Visitor"
> pattern which seems relevant to my question but don't know enough to
> know for sure. Thanks

Visitor pattern is double-dispatch pattern. Two virtual dispatches
joined together for to find the right spot in visitor/visitable square.
It means that technically we are paying *more* for adding new
operations to visitables without modifying the classes of visitables.
I am unsure if that was what you needed.