Idea of feature/optimization for C++

Idea of feature/optimization for C++

[staube]

Hi gcc gurus, hackers and wizards: 
This is the second mail i write to this list, the first one was wirtten a few
days ago and after finishing it I deleted it by mistake.
This is also the first mail i write that will reach you.

I am writing this mail in order to propose and new optimization/feature in the
C++ front end of GCC.
Before doing it i will warn you a few things:
1) I know nothing about the internal code/design of GCC or any of its frontends
so i cannot code the feature i am proposing, at least in the short-term. If
noone is able to do it, i MIGHT try to start reading and some day do it myself,
but you will have to wait.
2) I know nothing about the C++ standards, so my feature might have non standard
compilance.
3) Who knows?, maybe the feature is already implemented, so, i am not adding
anything :-(

The issue i want to cover is virtual functions and late/early-binding. Its
obvious that virtual functions are a very important part of Object Oriented
Programming with C++ but many developers refrain from using it because they
mean a performance loss when they are not needed, other solutions have been
found to implement some of the features that virtual functions provide, for
example templates.

I will illustrate this in an example.... I will write the same program twice.
One version using virtual functions and another one using templates
Look at the following two versions of main.cpp.

Example 1, Version 1 (using virtual functions)
**************************
#include <iostream>
using namespace std;


class HelloWorld {
    protected:
    HelloWorld() { };
    public:
    virtual void doIt() = 0;
};

class HappyHelloWorld : public HelloWorld{
    public:
    HappyHelloWorld() { };
    public:
    virtual void doIt() { cout << "Hello World :)" << endl; };
};

class SadHelloWorld : public HelloWorld {
    public:
    SadHelloWorld() { };
    public: 
    virtual void doIt() { cout << "Hello World :(" << endl; };
};

void letsSee(HelloWorld &hw)
{
    cout << "Lets see what&#8217;s his mood when he says hello World:" << endl;
    hw.doIt();
}

int main(int argc, char *argv[])
{
  SadHelloWorld shw;
  HappyHelloWorld hhw;
  letsSee(hhw);
  letsSee(shw);

  //doing PAUSE
  char c;
  cin >> c;
  return 0;
}

Example 1, Version 2  (using templates)
********************
#include <iostream>
using namespace std;


class HelloWorld {
    protected:
    HelloWorld() { };
    public:
    // no virtual
    // virtual void doIt() = 0; 
};

class HappyHelloWorld : public HelloWorld{
    public:
    HappyHelloWorld() { };
    public:
    /*virtual*/ void doIt() { cout << "Hello World :)" << endl; };
};

class SadHelloWorld : public HelloWorld {
    public:
    SadHelloWorld() { };
    public: 
    /*virtual*/ void doIt() { cout << "Hello World :(" << endl; };
};

template <class MyHelloWorld>
void letsSee(MyHelloWorld &hw)
{
    cout << "Lets see what&#8217;s his mood when he says hello World:" << endl;
    hw.doIt();
}

int main(int argc, char *argv[])
{
  SadHelloWorld shw;
  HappyHelloWorld hhw;
  letsSee(hhw);
  letsSee(shw);

  //doing PAUSE
  char c;
  cin >> c;
  return 0;
}
*******************************************************************************
Output of the two versions
****************************
Lets see what&#8217;s his mood when he says hello World:
Hello World :(
Lets see what&#8217;s his mood when he says hello World:
Hello World :("

As you see both examples do the same thing, only that the second one uses Early
Binding and then is more efficient.

I know than sometimes, virtual functions cannot be replaced by templates, for
example if there is an array of 100 pointers to HelloWorld Objects, we would
have no idea which function has to be called, then only the virtual function
solution would work. 

As a result of this, using virtual functions is always a better that using
templates, at least when you do not care about efficiency.

If we would like more and more developers to start using Object Oriented
Techniques it would be great that virtual functions perform as good as normal
functions whenever possible  &#205; was thinking that if the compiler would be
inteligent enought it could do early binding in the first example too, because
theres no need to do late-binding. Then programmers that would be worried about
the efficency of their code could still use the clean and good syntax of the
first example. Also it would be nice that programmers which do not know about
this optimization using templates, could get this for free :-)
 
How could all this be done??
When compiling any C++ function  the compiler should behave like this:
1 - compile several versions of the same function (usimg different name
decorations) .... one must do all the function calls using latebinding, just in
case we will need it, and the rest of the versions should be the earlybinding
version for every class that inherts from the parent class.
     In the example it would make three versions... the latebindingone, the
earylbinding for class SadHelloWorld and the earybinding for class
HappyHelloWorld.
2 -  If there are function calls to the function (function letsSee in our
example) it should be done to the early binding version whenever possible. 
3 &#8211; There could be problems sometimes because the compiler can only create
versions of letsSee for classes it knows that exist, then if a class was
declared in another file, no letsSee function would be created for that class
and then the user would get a linker error for not finding the earlybinding
version of the function, which would be the correct error to show to the user.
The programmer then would be forced to add the following code before declaring
the letsSee function:
    //AngryHelloWorld is defined in another file
    class AngryHelloWorld : public class HelloWorld;

4 - there should be an option in g++ to disable this behaviour. 
5-This optimization should also be applied to methods from the class itself. Any
method getting the "this" hidden parameter could also do its internal calls
throw latebinding orearlybinding, of course being earlybinding is the preferred
option.
 
Some other problems:
 For functions who get lots of parameters there would be lots of versions which
will increase a lot the size of the binary code. Maybe generating all the
versions should not be the default action but programmers should choose
whatever they want to make earlybinding versions or not. To do that they might
use the well known reserved word "virtual" and an additional one "final" (Am i
starting to sound like Java??).
Then:
  1)   If they write: void letsSee(virtual HelloWorld &hw), the compiler would
make only the latebinding version.
  2)   If they write: void letsSee(final HelloWorld &hw), the compiler would
also make the earlybinding version
  3)   If they write: void letsSee(HelloWorld &hw), the compiler would
show&#209;

                Warning: main.cpp:XX : HelloWorld has virtual functions but    
                "virtual" nor "final" were specified when getting 
                the params of letsSeefunction, to disable this warning use 
                the -Wnobind flag.

The last problem i have thinked of, is the binary distribution of libs. In those
cases functions cannot be instantiated (the same problem that the template
solution would have!!!). In that cases it would be impossible to call letsSee
using earlybinding on new classes declared by the user which inhert from
HelloWorld, of course, unless there could be a very advanced feature would be
implemented in the linker which would instantiate the latebinding binary code
to the needed earlybinding version (i don´t think it is going to happen anytime
soon). In those cases when optimizing would be impossible, the old fashion
latebinding should be used.

Another optimization: inline and virtual!!!
A method could be declared at the same time inline and virtual. then when a
function call that method using earlybinding it will inline the function, but
in the latebinding version it would call the method in the standard way.

Hey, i hope you liked this optimization, please tell me whatever you think about
it.
If it would be impossible to implement, tell me.
If it would be possible but noone has the time or will to do it, tell me too. I
will be happy to know that at least it was a good idea and i wil try to help
implement it in the future.

Thank you very much for your time,
Sincerilly,
Marcelo Taube

RE: Idea of feature/optimization for C++

[Dave Korn]

> -----Original Message-----
> From: gcc-owner  On Behalf Of staube
> Sent: 01 September 2004 10:30

> I am writing this mail in order to propose and new 
> optimization/feature in the
> C++ front end of GCC.

> 3) Who knows?, maybe the feature is already implemented, so, 
> i am not adding
> anything :-(
> 
> The issue i want to cover is virtual functions and 
> late/early-binding. 

> As you see both examples do the same thing, only that the 
> second one uses Early
> Binding and then is more efficient.

> functions whenever possible  Í was thinking that if the 
> compiler would be
> inteligent enought it could do early binding in the first 
> example too, because
> theres no need to do late-binding. 

http://www.google.com/search?hl=en&lr=&ie=UTF-8&q=binding+compile-time+resol
ution+virtual+function+c%2B%2B

  It is indeed an excellent idea, and your presentation of the idea and
analysis of the benefits of this optimisation were spot on, but it has
already been done; at least to some extent.

> Another optimization: inline and virtual!!!
> A method could be declared at the same time inline and 
> virtual. then when a
> function call that method using earlybinding it will inline 
> the function, but
> in the latebinding version it would call the method in the 
> standard way.

  That too is done, in the cases where the compiler can deduce the binding
at compile time and where the function body has already been seen and was
defined directly in the class declaration or has the inline attribute
applied to it.

    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....

RE: Idea of feature/optimization for C++

[staube]

Dave, thank you very much for all your comments and also for the google link
(however if you have an exact link to a page that talks about this topic i
would appreciate even more because i found it difficult to find it in google).

Anyway, since you said the optimization is already implemented i have been
trying to test its performance in "gcc version 3.3.3 (mingw special)".
Unfortunatelly the results are not good. I have made a very simple and short
programm in only one short .cpp file. I compiled it in two versions, using
templates and using virtual functions, the performance is pretty different.
The classes are the same HappyHelloWorld and SadHelloWorld of my previous post,
only that this time they dont print anything because i want to measure only the
function calls overhead.
And now instead of calling the functions two times it calls them 200000000 (two
hundred billion times????).
This is the code for the two versions.

main.cpp (virtual function version)
********
#include <iostream>
#include<windows.h>
using namespace std;

class HelloWorld {
    protected:
    HelloWorld() { };
    public:
    // no virtual
    virtual void doIt() = 0; 
};

class HappyHelloWorld : public HelloWorld{
    public:
    HappyHelloWorld() { };
    public:
    virtual void doIt() {};
};

class SadHelloWorld : public HelloWorld {
    public:
    SadHelloWorld() { };
    public: 
    virtual void doIt() {};
};


void letsSee(HelloWorld &hw)
{
    hw.doIt();
}

int main(int argc, char *argv[])
{
  SadHelloWorld shw;
  HappyHelloWorld hhw;
  DWORD previous = GetTickCount();
  for(unsigned i=1; i<100000000;i++) {
     letsSee(hhw);
     letsSee(shw);
  }
   DWORD current = GetTickCount();
   cout << (current-previous) << " milliseconds have passed\n";

  return 0;
}

main.cpp (templates version)
********


#include <iostream>
#include<windows.h>
using namespace std;


class HelloWorld {
    protected:
    HelloWorld() { };
    public:
    // no virtual
    // virtual void doIt() = 0; 
};

class HappyHelloWorld : public HelloWorld{
    public:
    HappyHelloWorld() { };
    public:
    /*virtual*/ void doIt() {};
};

class SadHelloWorld : public HelloWorld {
    public:
    SadHelloWorld() { };
    public: 
    /*virtual*/ void doIt() {};
};

template <class MyHelloWorld>
void letsSee(MyHelloWorld &hw)
{
    hw.doIt();
}

int main(int argc, char *argv[])
{
  SadHelloWorld shw;
  HappyHelloWorld hhw;
  DWORD previous = GetTickCount();
  for(unsigned i=1; i<100000000;i++) {
    letsSee(hhw);
    letsSee(shw);
  }
  DWORD current = GetTickCount();
  cout << (current-previous) << " milliseconds have passed\n";
  return 0;
}


NOW THE RESULTS
***************
I have run each version three times compiling normally and other three times
compiling with -O3.

All the results are in milliseconds.

virtual normal - 4586, 4507, 4546
virtual OPTIMIZED - 1432, 1462, 1452

template normal - 1983, 2043, 2043
template OPTIMIZED - 992. 1022, 1002

My conclusion is that the optimization i am proposing is not implemented in "gcc
version 3.3.3 (mingw special)".

Maybe what you said is implemented is something which i saw documented in some
C++ tutorials, and its optimizing to early binding if you call directly the
virtual memeber function which is of course different of calling a function
which calls the virtual member function. 

Am i right?
Again, I wish i could get some more comments about the optimization i am
proposing.

Quoting Dave Korn <dk@artimi.com>:

> > -----Original Message-----
> > From: gcc-owner  On Behalf Of staube
> > Sent: 01 September 2004 10:30
> 
> > I am writing this mail in order to propose and new 
> > optimization/feature in the
> > C++ front end of GCC.
> 
> > 3) Who knows?, maybe the feature is already implemented, so, 
> > i am not adding
> > anything :-(
> > 
> > The issue i want to cover is virtual functions and 
> > late/early-binding. 
> 
> > As you see both examples do the same thing, only that the 
> > second one uses Early
> > Binding and then is more efficient.
> 
> > functions whenever possible  &#205; was thinking that if the 
> > compiler would be
> > inteligent enought it could do early binding in the first 
> > example too, because
> > theres no need to do late-binding. 
> 
> http://www.google.com/search?hl=en&lr=&ie=UTF-8&q=binding+compile-time+resol
> ution+virtual+function+c%2B%2B
> 
>   It is indeed an excellent idea, and your presentation of the idea and
> analysis of the benefits of this optimisation were spot on, but it has
> already been done; at least to some extent.
> 
> > Another optimization: inline and virtual!!!
> > A method could be declared at the same time inline and 
> > virtual. then when a
> > function call that method using earlybinding it will inline 
> > the function, but
> > in the latebinding version it would call the method in the 
> > standard way.
> 
>   That too is done, in the cases where the compiler can deduce the binding
> at compile time and where the function body has already been seen and was
> defined directly in the class declaration or has the inline attribute
> applied to it.
> 
>     cheers, 
>       DaveK
> -- 
> Can't think of a witty .sigline today....
>