What is the difference between compile time polymorphism and static binding?


Answers

Polymorphism refers to the ability of an object to behave differently to the same message.

Polymorphism is of two types. static or dynamic. In dynamic polymorphism the response to message is decided on run-time while in static polymorphism it is decided on compile-time.

The assignment of data types in dynamic polymorphism is known as late or dynamic binding. In dynamic binding method call occur based on the object (instance) type at Run time. Eg: method overriding

If the assignment of data types is in compile time it is known as early or static binding. In static binding method call occur based on the reference type at compile time. Eg: method overloading

Method Overloading - This means creating a new method with the same name and different signature. It uses early binding.

Method Overriding - This is the process of giving a new definition for an existing method in its child class. All object created at run time on the heap therefore actual binding is done at the runtime only.

Question

This link helped me understand the difference between static binding and dynamic binding? but I am in a confusion that

what is the difference between static binding and compile time polymorphism or no difference is there.

This also creates a doubt about dynamic binding and runtime polymorphism?




In compiled languages, the difference is stark.

Java:

//early binding:
public create_a_foo(*args) {
 return new Foo(args)
}
my_foo = create_a_foo();

//late binding:
public create_something(Class klass, *args) {
  klass.new_instance(args)
}
my_foo = create_something(Foo);

In the first example, the compiler can do all sorts of neat stuff at compile time. In the second, you just have to hope that whoever uses the method does so responsibly. (Of course, newer JVMs support the Class<? extends Foo> klass structure, which can greatly reduce this risk.)

Another benefit is that IDEs can hotlink to the class definition, since it's declared right there in the method. The call to create_something(Foo) might be very far from the method definition, and if you're looking at the method definition, it might be nice to see the implementation.

The major advantage of late binding is that it makes things like inversion-of-control easier, as well as certain other uses of polymorphism and duck-typing (if your language supports such things).







Polymorphism in c++

Understanding of / requirements for polymorphism

To understand polymorphism - as the term is used in Computing Science - it helps to start from a simple test for and definition of it. Consider:

    Type1 x;
    Type2 y;

    f(x);
    f(y);

Here, f() is to perform some operation and is being given values x and y as inputs.

To exhibit polymorphism, f() must be able to operate with values of at least two distinct types (e.g. int and double), finding and executing distinct type-appropriate code.


C++ mechanisms for polymorphism

Explicit programmer-specified polymorphism

You can write f() such that it can operate on multiple types in any of the following ways:

  • Preprocessing:

    #define f(X) ((X) += 2)
    // (note: in real code, use a longer uppercase name for a macro!)
  • Overloading:

    void f(int& x)    { x += 2; }
    
    void f(double& x) { x += 2; }
  • Templates:

    template <typename T>
    void f(T& x) { x += 2; }
  • Virtual dispatch:

    struct Base { virtual Base& operator+=(int) = 0; };
    
    struct X : Base
    {
        X(int n) : n_(n) { }
        X& operator+=(int n) { n_ += n; return *this; }
        int n_;
    };
    
    struct Y : Base
    {
        Y(double n) : n_(n) { }
        Y& operator+=(int n) { n_ += n; return *this; }
        double n_;
    };
    
    void f(Base& x) { x += 2; } // run-time polymorphic dispatch

Other related mechanisms

Compiler-provided polymorphism for builtin types, Standard conversions, and casting/coercion are discussed later for completeness as:

  • they're commonly intuitively understood anyway (warranting a "oh, that" reaction),
  • they impact the threshold in requiring, and seamlessness in using, the above mechanisms, and
  • explanation is a fiddly distraction from more important concepts.

Terminology

Further categorisation

Given the polymorphic mechanisms above, we can categorise them in various ways:

  • When is the polymorphic type-specific code selected?

    • Run time means the compiler must generate code for all the types the program might handle while running, and at run-time the correct code is selected (virtual dispatch)
    • Compile time means the choice of type-specific code is made during compilation. A consequence of this: say a program only called f above with int arguments - depending on the polymorphic mechanism used and inlining choices the compiler might avoid generating any code for f(double), or generated code might be thrown away at some point in compilation or linking. (all mechanisms above except virtual dispatch)

  • Which types are supported?

    • Ad-hoc meaning you provide explicit code to support each type (e.g. overloading, template specialisation); you explicitly add support "for this" (as per ad hoc's meaning) type, some other "this", and maybe "that" too ;-).
    • Parametric meaning you can just try to use the function for various parameter types without specifically doing anything to enable its support for them (e.g. templates, macros). An object with functions/operators that act like the template/macro expects1 is all that template/macro needs to do its job, with the exact type being irrelevant. The "concepts" cut from C++11 help express and enforce such expectations - let's hope they make it into a later Standard.

      • Parametric polymorphism provides duck typing - a concept attributed to James Whitcomb Riley who apparently said "When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.".

        template <typename Duck>
        void do_ducky_stuff(const Duck& x) { x.walk().swim().quack(); }
        
        do_ducky_stuff(Vilified_Cygnet());
    • Subtype (aka inclusion) polymorphism allows you to work on new types without updating the algorithm/function, but they must be derived from the same base class (virtual dispatch)

1 - Templates are extremely flexible. SFINAE (see also std::enable_if) effectively allows several sets of expectations for parametric polymorphism. For example, you might encode that when the type of data you're processing has a .size() member you'll use one function, otherwise another function that doesn't need .size() (but presumably suffers in some way - e.g. using the slower strlen() or not printing as useful a message in the log). You can also specify ad-hoc behaviours when the template is instantiated with specific parameters, either leaving some parameters parametric (partial template specialisation) or not (full specialisation).

"Polymorphic"

Alf Steinbach comments that in the C++ Standard polymorphic only refers to run-time polymorphism using virtual dispatch. General Comp. Sci. meaning is more inclusive, as per C++ creator Bjarne Stroustrup's glossary (http://www.stroustrup.com/glossary.html):

polymorphism - providing a single interface to entities of different types. Virtual functions provide dynamic (run-time) polymorphism through an interface provided by a base class. Overloaded functions and templates provide static (compile-time) polymorphism. TC++PL 12.2.6, 13.6.1, D&E 2.9.

This answer - like the question - relates C++ features to the Comp. Sci. terminology.

Discussion

With the C++ Standard using a narrower definition of "polymorphism" than the Comp. Sci. community, to ensure mutual understanding for your audience consider...

  • using unambiguous terminology ("can we make this code reusable for other types?" or "can we use virtual dispatch?" rather than "can we make this code polymorphic?"), and/or
  • clearly defining your terminology.

Still, what's crucial to being a great C++ programmer is understanding what polymorphism's really doing for you...

    letting you write "algorithmic" code once and then apply it to many types of data

...and then be very aware of how different polymorphic mechanisms match your actual needs.

Run-time polymorphism suits:

  • input processed by factory methods and spat out as an heterogeneous object collection handled via Base*s,
  • implementation chosen at runtime based on config files, command line switches, UI settings etc.,
  • implementation varied at runtime, such as for a state machine pattern.

When there's not a clear driver for run-time polymorphism, compile-time options are often preferable. Consider:

  • the compile-what's-called aspect of templated classes is preferable to fat interfaces failing at runtime
  • SFINAE
  • CRTP
  • optimisations (many including inlining and dead code elimination, loop unrolling, static stack-based arrays vs heap)
  • __FILE__, __LINE__, string literal concatenation and other unique capabilities of macros (which remain evil ;-))
  • templates and macros test semantic usage is supported, but don't artificially restrict how that support is provided (as virtual dispatch tends to by requiring exactly matching member function overrides)

Other mechanisms supporting polymorphism

As promised, for completeness several peripheral topics are covered:

  • compiler-provided overloads
  • conversions
  • casts/coercion

This answer concludes with a discussion of how the above combine to empower and simplify polymorphic code - especially parametric polymorphism (templates and macros).

Mechanisms for mapping to type-specific operations

> Implicit compiler-provided overloads

Conceptually, the compiler overloads many operators for builtin types. It's not conceptually different from user-specified overloading, but is listed as it's easily overlooked. For example, you can add to ints and doubles using the same notation x += 2 and the compiler produces:

  • type-specific CPU instructions
  • a result of the same type.

Overloading then seamlessly extends to user-defined types:

std::string x;
int y = 0;

x += 'c';
y += 'c';

Compiler-provided overloads for basic types is common in high-level (3GL+) computer languages, and explicit discussion of polymorphism generally implies something more. (2GLs - assembly languages - often require the programmer to explicitly use different mnemonics for different types.)

> Standard conversions

The C++ Standard's fourth section describes Standard conversions.

The first point summarises nicely (from an old draft - hopefully still substantially correct):

-1- Standard conversions are implicit conversions defined for built-in types. Clause conv enumerates the full set of such conversions. A standard conversion sequence is a sequence of standard conversions in the following order:

  • Zero or one conversion from the following set: lvalue-to-rvalue conversion, array-to-pointer conversion, and function-to-pointer conversion.

  • Zero or one conversion from the following set: integral promotions, floating point promotion, integral conversions, floating point conversions, floating-integral conversions, pointer conversions, pointer to member conversions, and boolean conversions.

  • Zero or one qualification conversion.

[Note: a standard conversion sequence can be empty, i.e., it can consist of no conversions. ] A standard conversion sequence will be applied to an expression if necessary to convert it to a required destination type.

These conversions allow code such as:

double a(double x) { return x + 2; }

a(3.14);
a(42);

Applying the earlier test:

To be polymorphic, [a()] must be able to operate with values of at least two distinct types (e.g. int and double), finding and executing type-appropriate code.

a() itself runs code specifically for double and is therefore not polymorphic.

But, in the second call to a() the compiler knows to generate type-appropriate code for a "floating point promotion" (Standard §4) to convert 42 to 42.0. That extra code is in the calling function. We'll discuss the significance of this in the conclusion.

> Coercion, casts, implicit constructors

These mechanisms allow user-defined classes to specify behaviours akin to builtin types' Standard conversions. Let's have a look:

int a, b;

if (std::cin >> a >> b)
    f(a, b);

Here, the object std::cin is evaluated in a boolean context, with the help of a conversion operator. This can be conceptually grouped with "integral promotions" et al from the Standard conversions in the topic above.

Implicit constructors effectively do the same thing, but are controlled by the cast-to type:

f(const std::string& x);
f("hello");  // invokes `std::string::string(const char*)`

Implications of compiler-provided overloads, conversions and coercion

Consider:

void f()
{
    typedef int Amount;
    Amount x = 13;
    x /= 2;
    std::cout << x * 1.1;
}

If we want the amount x to be treated as a real number during the division (i.e. be 6.5 rather than rounded down to 6), we only need change to typedef double Amount.

That's nice, but it wouldn't have been too much work to make the code explicitly "type correct":

void f()                               void f()
{                                      {
    typedef int Amount;                    typedef double Amount;
    Amount x = 13;                         Amount x = 13.0;
    x /= 2;                                x /= 2.0;
    std::cout << double(x) * 1.1;          std::cout << x * 1.1;
}                                      }

But, consider that we can transform the first version into a template:

template <typename Amount>
void f()
{
    Amount x = 13;
    x /= 2;
    std::cout << x * 1.1;
}

It's due to those little "convenience features" that it can be so easily instantiated for either int or double and work as intended. Without these features, we'd need explicit casts, type traits and/or policy classes, some verbose, error-prone mess like:

template <typename Amount, typename Policy>
void f()
{
    Amount x = Policy::thirteen;
    x /= static_cast<Amount>(2);
    std::cout << traits<Amount>::to_double(x) * 1.1;
}

So, compiler-provided operator overloading for builtin types, Standard conversions, casting / coercion / implicit constructors - they all contribute subtle support for polymorphism. From the definition at the top of this answer, they address "finding and executing type-appropriate code" by mapping:

  • "away" from parameter types

    • from the many data types polymorphic algorithmic code handles

    • to code written for a (potentially lesser) number of (the same or other) types.

  • "to" parametric types from values of constant type

They do not establish polymorphic contexts by themselves, but do help empower/simplify code inside such contexts.

You may feel cheated... it doesn't seem like much. The significance is that in parametric polymorphic contexts (i.e. inside templates or macros), we're trying to support an arbitrarily large range of types but often want to express operations on them in terms of other functions, literals and operations that were designed for a small set of types. It reduces the need to create near-identical functions or data on a per-type basis when the operation/value is logically the same. These features cooperate to add an attitude of "best effort", doing what's intuitively expected by using the limited available functions and data and only stopping with an error when there's real ambiguity.

This helps limit the need for polymorphic code supporting polymorphic code, drawing a tighter net around the use of polymorphism so localised use doesn't force widespread use, and making the benefits of polymorphism available as needed without imposing the costs of having to expose implementation at compile time, have multiple copies of the same logical function in the object code to support the used types, and in doing virtual dispatch as opposed to inlining or at least compile-time resolved calls. As is typical in C++, the programmer is given a lot of freedom to control the boundaries within which polymorphism is used.




Compile time vs run time polymorphism in C++ advantages/disadvantages

Static polymorphism produces faster code, mostly because of the possibility of aggressive inlining. Virtual functions can rarely be inlined, and mostly in a "non-polymorphic" scenarios. See this item in C++ FAQ. If speed is your goal, you basically have no choice.

On the other hand, not only compile times, but also the readability and debuggability of the code is much worse when using static polymorphism. For instance: abstract methods are a clean way of enforcing implementation of certain interface methods. To achieve the same goal using static polymorphism, you need to restore to concept checking or the curiously recurring template pattern.

The only situation when you really have to use dynamic polymorphism is when the implementation is not available at compile time; for instance, when it's loaded from a dynamic library. In practice though, you may want to exchange performance for cleaner code and faster compilation.




In C++ when it is possible to implement the same functionality using either run time (sub classes, virtual functions) or compile time (templates, function overloading) polymorphism, why would you choose one over the other?

I would think that the compiled code would be larger for compile time polymorphism (more method/class definitions created for template types)...

Often yes - due to multiple instantiations for different combinations of template parameters, but consider:

  • with templates, only the functions actually called are instantiated
  • dead code elimination
  • constant array dimensions allowing member variables such as T mydata[12]; to be allocated with the object, automatic storage for local variables etc., whereas a runtime polymorphic implementation might need to use dynamic allocation (i.e. new[]) - this can dramatically impact cache efficiency in some cases
  • inlining of function calls, which makes trivial things like small-object get/set operations about an order of magnitude faster on the implementations I've benchmarked
  • avoiding virtual dispatch, which amounts to following a pointer to a table of function pointers, then making an out-of-line call to one of them (it's normally the out-of-line aspect that hurts performance most)

...and that compile time would give you more flexibility...

Templates certainly do:

  • given the same template instantiated for different types, the same code can mean different things: for example, T::f(1) might call a void f(int) noexcept function in one instantiation, a virtual void f(double) in another, a T::f functor object's operator()(float) in yet another; looking at it from another perspective, different parameter types can provide what the templated code needs in whatever way suits them best

  • SFINAE lets your code adjust at compile time to use the most efficient interfaces objects supports, without the objects actively having to make a recommendation

  • due to the instantiate-only-functions-called aspect mentioned above, you can "get away" with instantiating a class template with a type for which only some of the class template's functions would compile: in some ways that's bad because programmers may expect that their seemingly working Template<MyType> will support all the operations that the Template<> supports for other types, only to have it fail when they try a specific operation; in other ways it's good because you can still use Template<> if you're not interested in all the operations

    • if Concepts [Lite] make it into a future C++ Standard, programmers will have the option of putting stronger up-front contraints on the semantic operations that types used as template paramters must support, which will avoid nasty surprises as a user finds their Template<MyType>::operationX broken, and generally give simpler error messages earlier in the compile

...while run time would give you "safer" polymorphism (i.e. harder to be used incorrectly by accident).

Arguably, as they're more rigid given the template flexibility above. The main "safety" problems with runtime polymorphism are:

  • some problems end up encouraging "fat" interfaces (in the sense Stroustrup mentions in The C++ Programming Language): APIs with functions that only work for some of the derived types, and algorithmic code needs to keep "asking" the derived types "should I do this for you", "can you do this", "did that work" etc..

  • you need virtual destructors: some classes don't have them (e.g. std::vector) - making it harder to derive from them safely, and the in-object pointers to virtual dispatch tables aren't valid across processes, making it hard to put runtime polymorphic objects in shared memory for access by multiple processes

Can anyone give a specific example where both would be viable options but one or the other would be a clearly better choice?

Sure. Say you're writing a quick-sort function: you could only support data types that derive from some Sortable base class with a virtual comparison function and a virtual swap function, or you could write a sort template that uses a Less policy parameter defaulting to std::less<T>, and std::swap<>. Given the performance of a sort is overwhelmingly dominated by the performance of these comparison and swap operations, a template is massively better suited to this. That's why C++ std::sort clearly outperforms the C library's generic qsort function, which uses function pointers for what's effectively a C implementation of virtual dispatch. See here for more about that.

Also, does compile time polymorphism produce faster code, since it is not necessary to call functions through vtable, or does this get optimized away by the compiler anyway?

It's very often faster, but very occasionally the sum impact of template code bloat may overwhelm the myriad ways compile time polymorphism is normally faster, such that on balance it's worse.




Links



Tags