Home » Community » Forums » » Improving Performance in C++ with Compile Time Polymorphism
  Intel sponsors gamedev.net search:   
[Control Panel] [Register] [Bookmarks] [Who's Online] [Active Topics] [Stats] [FAQ] [Search]

Add Forum to Favorites |  Send Topic To a Friend | View Forum FAQ | Track this topic

Page:   1 2 »»

 Last Thread Next Thread 
 Improving Performance in C++ with Compile Time Polymorphism
Post Reply 
Good Idea... I don't use polymorphism very often so I never really thought about this kind of overhead... now I know how to look out for it...

I'm still having trouble understanding the "Curiously Recurring Template Pattern"

So I can do something like this?:
template<typename GenType>
class Character
{
/* class stuff... no reference to GenType... or did I miss that?*/
};

class NPC: public Character<NPC>
{
};


I'm having trouble getting my head around this... It looks to me like NPC is inheriting from itself in a way... because NPC makes up the type of Character which makes up the type of NPC with makes up the type of Character which....
Obviously I'm missing something fundamental

[edited by - tempuself on November 7, 2003 1:11:04 PM]

 User Rating: 1057   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Templating isn't inheriting.

Think of it this way..

#define GenType NPC

class Character
{
 GenType *SomeVar;
 void DoSomething(GenType param);
};

class NPC : public Character
{
};


That's the same as doing this:

template <class GenType>
class Character
{
public:
 GenType *SomeVar;
 void DoSomething(GenType param);
};

class NPC : public Character<NPC>
{
};


It's simply telling it what to fill in for the type, so in essence, all it's doing is this:
class NPC
{
 NPC *SomeVar;
 void DoSomething(GenType param);
};


Now, this is legal as long as you don't declare a normal variable, only a pointer and/or parameters. If you try declaring it as a normal variable (GenType SomeVar, it should fail.

 User Rating: 1053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Cool... I think I get it now

 User Rating: 1057   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Hehe, sometimes those smileys don't help you a bit.

Like in when where you wrote:

" (GenType SomeVar "

 User Rating: 1015   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Yeah... I hate accidentally referring to std:air or boost:ython.


"Sneftel is correct, if rather vulgar." --Flarelocke

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

The author is mis-using reinterpret_cast in this article. The correct method is to use static_cast for all the examples he gave. Other than that it is a good article on template programming but the specific examples are a bit contrived, but I suppose they have to be in order to get the point across without putting up an entire program.

 User Rating: 968   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

What about the case where you wanted say a vector of Shape objects, that could be any class derived from shape, and wanted to store them as a queue for later processing in a function? Is this a limitation of this system?



 User Rating: 1263   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Original post by duke
The author is mis-using reinterpret_cast in this article. The correct method is to use static_cast for all the examples he gave. Other than that it is a good article on template programming but the specific examples are a bit contrived, but I suppose they have to be in order to get the point across without putting up an entire program.



dynamic_cast would be more suitable for casting down inheritence heirarchies.

Few comments about the article, its quite well written, dont see the need for all the implementation details in it though, somewhat takes away from the point of the article IMHO.

The main problem i have with this article is that there is nothing original in it, static polymorphism is discussed in many text books, using the exact same shape examples. Would be nice to see some original thinking and ideas in a gamedev article for once.

I also note that there is no list of sources at the bottom of the article, and im in no doubt that he used sources for this article, is there a reason for this?

 User Rating: 1015   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Original post by duke
The author is mis-using reinterpret_cast in this article. The correct method is to use static_cast for all the examples he gave.

True. Mea culpa. I'd point out, however, that the only time where it would make a substantive difference is when a class uses multiple inheritance.
quote:
Other than that it is a good article on template programming but the specific examples are a bit contrived, but I suppose they have to be in order to get the point across without putting up an entire program.

When I originally conceived the article, it was a case study of how I'd used methods such as these to improve my content loading code. But since that goes into a lot of disparate topics, I figured I'd focus it down. Perhaps sometime I'll write another article covering it more fully.


"Sneftel is correct, if rather vulgar." --Flarelocke

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Nice article Sneftel, I'm anxious to go evaluate my engine code to see where this might come handy. I'm using a good deal of virtual functions :/

James Simmons
MindEngine Development
http://medev.sourceforge.net

 User Rating: 957   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Original text from l'Artical
...most compilers require templates to be declared inline. This means that all your templated functions will have to go in the header, which can make your code less tidy.

You can always write the definition in an INL (or an excluded-from-build CPP) file, and include that in the header. Makes things just about as tidy.

 User Rating: 1076   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Hmm... I wonder if this could speed up the Enginuity memory manager.

One limitation that you hinted at, Sneftel, but didn't outright name, was that it becomes impossible to aggregate Shapes like you might want to. For example, I'm writing some physics code at the moment which deals with a number of varying collision volumes (spheres, boxes, cylinders, and so on) which all inherit from CPhysicsPrimitive. I can then store a list of CPhysicsPrimitives, and iterate through it to update all my objects.

If CPhysicsPrimitive became parametrized by my shape classes - CPhysicsPrimitive<CSphere> and so on - then I lose my ability to do that.

One solution would be to derive the templated base class itself from *another* base class which is non-parametrised - CPhysicsEntity. I could then store a list of CPhysicsEntity* with no problem. However, to get at the actual object I then need some virtual functions... which defeats the point of the system in the first place

I guess for a fully flexible system it's impossible to avoid virtual functions completely. But curiously recurring templates could still be useful - if I were to perform a series of operations on a single shape, I could use a virtual function to get an ID number for the underlying type, and cast it to BaseClass<thatType> (essentially my own RTTI), and then operate on it that way, avoiding the virtual functions... but then I guess if you're going to do that, you might just as well cast to 'thatType' itself and skip the base class.

Without the templated operational functions (your DrawAShapeOverAndOver) I can't see it fixing very much... though it could be useful for the Enginuity size() function. I'd be able to remove that function from the vtbl and just do 'long size(){return sizeof(T)}' where T is the parameter.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
"Don't document your code; code your documentation." -me


 User Rating: 2118   |  Rate This User  Send Private MessageView ProfileView JournalView GD Showcase Entries Report this Post to a Moderator | Link

quote:
Original post by superpig
One solution would be to derive the templated base class itself from *another* base class which is non-parametrised - CPhysicsEntity. I could then store a list of CPhysicsEntity* with no problem. However , to get at the actual object I then need some virtual functions... which defeats the point of the system in the first place

Yeah, I've explored that system somewhat. It looks something like this:
class A {
    virtual void Foo_Aux();
    void Foo() { Foo_Aux(); }
};

template<typename AType>
class A_Aux : public A
{
    void Foo() { 
        static_cast<AType &>(*this).Bar(); 
        static_cast<AType &>(*this).Baz(); 
    }

    virtual void Foo_Aux() { Foo(); }
};

class B : public A_Aux<B>
{
    void Bar() { ... }
    void Baz() { ... }
};


That way, you can have an A* and call Foo on it, or you can have an AType as a template argument. But no matter how I've tried to format it, it's been unwieldy, ugly, and hackish.
quote:
I guess for a fully flexible system it's impossible to avoid virtual functions completely. But curiously recurring templates could still be useful - if I were to perform a series of operations on a single shape, I could use a virtual function to get an ID number for the underlying type, and cast it to BaseClass<thatType> (essentially my own RTTI), and then operate on it that way, avoiding the virtual functions... but then I guess if you're going to do that, you might just as well cast to 'thatType' itself and skip the base class.

What would be really nice would be a way to force a particular virtual function binding (a 'final' keyword would be ideal), instead of allowing the compiler to do a lookup. But AFAIK such a thing is not to be found in C++. Perhaps Stupid Macro Tricks, but I hate that.

"Sneftel is correct, if rather vulgar." --Flarelocke

[edited by - sneftel on November 7, 2003 10:31:09 PM]

[edited by - sneftel on November 7, 2003 10:31:47 PM]

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Original post by Lepton
and im in no doubt that he used sources for this article


You never know with sneftel. It's very probable that he came up with this stuff all on his own, being the C++ Hotty that hs is

Very informative article sneftel. easy to read and understand.

[edit] quote tag and smiley[/edit]


:::: [ Triple Buffer ] ::::


[edited by - ifoobar on November 7, 2003 10:52:58 PM]

 User Rating: 1531   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Kool article, was waiting a while for this one
Just trying to think of a way to overcome the problems, can someone tell me why this doesnt work:
class VirtualShape {
public:
	virtual void VirtualDraw() = 0;
};

template <typename ShapeType>
class Shape : public VirtualShape {
public:
	void Draw() const {
		static_cast<const ShapeType *>(this)->Draw();
	};
};

class Rectangle : public Shape<Rectangle> {
public:
	void Draw() {
		printf("drawarect\n");
	}
	virtual void VirtualDraw() {Rectangle::Draw();};
};

class Circle : public Shape<Circle> {
public:
	void Draw() {
		printf("drawacircle\n");
	}
	virtual void VirtualDraw() {Circle::Draw();};
};


template<typename ShapeType>
void DrawAShapeOverAndOver(ShapeType* myShape)
{
  for(int i=0; i<5; i++)
  {
    myShape->Draw();
  }
}

void DrawAChangingShapeOverAndOver(VirtualShape **myShape) {
 for(int i=0; i<5; i++)
  {
    myShape[i]->VirtualDraw();
  }
}


It always calls circles draw method,...
(ie: rectangle->VirtualDraw(); calls circles draw..)

Thanks!

 User Rating: 1053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

This idea somehow perverts the initial idea of polymorphism and object structure.

First we may ask these questions:
Does a picture draw itself?
picture.draw();
No.

Does artist draw the picture?
artist.draw(picture);
Yes.

In this case we can still use the same method, however if you are going to be strict about polymorphism, this is the "more" right way.


Of course we are all humans and in the end it comes down to matter of preferance.

Also, putting your drawing headers into one file improves the compile time performace on some compilers.

[edited by - Captian Goatse on November 8, 2003 3:25:52 AM]

 User Rating: 1015   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

Nice article!

I just got hoocked up on one thing... What's the point?

SpecificType *mySpecificObjectPtr = new SpecificType();
mySpecificObjectPtr->CallAnyFunctionThatSpecificTypeHas();

that's basicly what I saw... You don't need virtual functions. You can inherit or not, either way, all functions that SpecificType has will be called without vtbl overhead.

Because, as it said in the article, you can't have a base class pointer so you just lost the whole run-time dynamic binding part.

Dunno, seems like an awful long way to go to achieve what seems to be my example above?

Either way, it's always nice to see new ideas

}-- Programmer/Gamer/Dreamer --{

 User Rating: 1352   |  Rate This User  Send Private MessageView ProfileView Journal Report this Post to a Moderator | Link

quote:
Original post by Seriema
SpecificType *mySpecificObjectPtr = new SpecificType();
mySpecificObjectPtr->CallAnyFunctionThatSpecificTypeHas();

that's basicly what I saw... You don't need virtual functions. You can inherit or not, either way, all functions that SpecificType has will be called without vtbl overhead.

That's true. But this only allows you to refer to the particular hard-coded type in that block. Where this technique really starts becoming useful is when an object is being used in an external polymorphic situation, such as DrawAShapeOverAndOver() did.


"Sneftel is correct, if rather vulgar." --Flarelocke

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

In specific reference to the article's technical thrust, isn't it a bad idea for an object to draw itself anyway? Shouldn't the engine be responsible for this?

ld

 User Rating: 1139   |  Rate This User  Send Private MessageView ProfileView Journal Report this Post to a Moderator | Link

quote:
Original post by Captian Goatse
This idea somehow perverts the initial idea of polymorphism and object structure.

First we may ask these questions:
Does a picture draw itself?
picture.draw();
No.

Does artist draw the picture?
artist.draw(picture);
Yes.

In this case we can still use the same method, however if you are going to be strict about polymorphism, this is the "more" right way.

I disagree with this. Having each object being responsible for rendering itself is more inline with polymorphism. With the second approach the renderer has to know how to draw each type of object making it more hassle to add new objects to the system as you have to keep updating the rendering routine for each time and that's assuming you even have the privileges to change it.

With the first approach you simply write each new class which implements the base interface and your renderer will automatically be able to handle them without having to know the specific details of what it's drawing, which one of the main ideals of polymorphism. Although with this example I'd also be inclined to pass the renderer in as a parameter for added flexibility.

--
"Never Abandon Imagination" - Tony DiTerlizzi

 User Rating: 1015   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

If you want to get all Object-Oriented about it, a Bridge Pattern is probably the most robust and flexible design. I've done a little thinking about how to do a compile-time Bridge Pattern, but haven't come up with an elegant solution yet.


"Sneftel is correct, if rather vulgar." --Flarelocke

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Article
We will make it specifically for Rectangles, so we can just flat-out tell the dumb compiler what it is and forego the lookup code.
void DrawAShapeWhichIsARectangleOverAndOver(Shape* myShape)
{
  for(int i=0; i<10000; i++)
  {
    reinterpret_cast<Rectangle*>(myShape)->DrawOutline();
  }
}
Unfortunately, this doesn't help one bit. Telling the compiler that the object is a Rectangle isn't enough. For all the compiler knows, the object could be a subclass of Rectangle.
Right. However, you can specifically call Rectangle::DrawOutline like this:
void DrawAShapeWhichIsARectangleOverAndOver(Shape* myShape)
{
  for(int i=0; i<10000; i++)
  {
    reinterpret_cast<Rectangle*>(myShape)->Rectangle::DrawOutline();
  }
}


 User Rating: 1408   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

quote:
Original post by Beer Hunter
Right. However, you can specifically call Rectangle::DrawOutline like this:

Absolutely right. And, of course, what that means is that compile-time polymorphism can be implemented without touching the class at all, if you aren't using things like the Strategy Pattern. I think this approach is a bit messy, because it puts the burden of potentially unsafe downcasting outside the class (IMHO, fugly things like casts should be discreetly hidden in source files). Still, if you don't feel like screwing with the CRTP, this can be a good substitute in places.


"Sneftel is correct, if rather vulgar." --Flarelocke

 User Rating: 2053   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link

I'm new to C++, but I was wondering couldn't you just do this?:

void DrawAShapeOverAndOver(Shape* myShape)
{
  void (*Draw)();

  Draw = myShape->DrawOutline;

  for(int i=0; i<10000; i++)
  {
    Draw();
  }
}
 


Just save the function then then call that pointer??

Denny.

[edited by - brain21 on November 9, 2003 7:56:55 PM]

 User Rating: 1019   |  Rate This User  Send Private MessageView Profile Report this Post to a Moderator | Link
Page:   1 2 »»
All times are ET (US)

Post Reply
 Last Thread Next Thread 
Forum Rules:
You may not post new threads
You may post replies
You may not edit your posts
You may not use HTML in your posts
Jump To:
Administrative Options: