Jump to content
  • Advertisement
Sign in to follow this  
XenoPhyre

Keeping things fast (Lingering doubts about virtual functions and std::list....)

This topic is 3623 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How significant are any penalties to speed incurred by: 1) Using virtual class member functions. and 2) Iterating through lists (std::list). I'm building a game engine and one of the features I'm trying to implement is a kernel that can execute, stop, suspend, and resume tasks on a list. It has a task loop that goes through the list of tasks every frame and sends the task an Update message, signaling it to execute.

//class definition for a task

class taskbase
{
public:
virtual void Update() = 0;
bool IsPaused;
virtual void OnSuspend(){}; //you can do something before you get suspended
virtual void OnResume(){}; //you can do something before you get resumed
}

//the kernel

class kernelbase
{
public:
std::list<taskbase> kernelbase_tasklist;
std::list<taskbase>::iterator kernelbase_taskiterator;
bool running;
void kernelbase_execute()
{
while(running == TRUE)
{
for(kernelbase_taskiterator = kernelbase_tasklist.begin();
kernelbase_taskiterator != kernelbase_tasklist.end();
kernelbase_taskiterator++)
{
if(*kernelbase_taskiterator.IsPaused == FALSE)
{
kernelbase_taskiterator->Update();
}
}
}
}
};

(Didn't include kernel code for pausing and resuming, didn't think it was relevant here...) How slower, approximately, would this task loop run, compared to just letting the tasks go free without the need for an Update signal from the kernel every single time it gets to it in the task list. I have heard that there's a lot of overhead involved in using virtual functions as well as iterating through std::list. I want to preserve execution speed as much as possible.

Share this post


Link to post
Share on other sites
Advertisement
1) Negligible compared to the cost of invoking the function in the first place which is in turn negligible compared to the cost of the function body itself in nearly every case.

2) A single iteration is tiny. Adding two ints for all purposes. Iterating the entire list is of course proportional to the length of the list. Again, negligible compared to the cost of the actual update method.


But basically, all that is meaningless if it doesn't work. Meaningless if it's not maintainable; Meaningless if it's not flexible. Focus on those first.

Share this post


Link to post
Share on other sites
It's meaningless to ask how fast something is if you don't have an alternative in mind. There's a certain amount of work to be done, and it will take time. There is overhead to pay, for example, to call a virtual member function, yes; but that overhead is there in order to determine what code to run. If you actually do have to make a choice, there is no way to have the happen for free. And the compiler knows a lot about making that process efficient and streamlined.

If you're really worried about it, and technically minded, you might try studying compiler implementation. The best way to do this right now is probably to take a university course (one of the few things I thought were actually done pretty well at university).

Share this post


Link to post
Share on other sites
I'd worry more about lines like
while(running == TRUE)

C++ has a real true keyword since... 18 years? Use it! Or better yet, don't:
while(running)

This line has the exact same semantics and isn't less readable.

Share this post


Link to post
Share on other sites
On today's processors, the virtual function overhead, and any overhead from traversing a list, is negligible for almost all applications. If you're planning to do this more than millions of times a second, maybe it's worth worrying about now.

However, if you're using Visual Studio, be sure you disable the draconian bounds checks on std calls, as they are incredibly expensive.

My strategy would be to code things in the cleanest, most straightforward manner. Then, if performance is acceptable, you're done. If it isn't, profile, and fix what's actually slow. Chance are it won't be virtual function usage or list traversal.

Good luck,
Geoff

Share this post


Link to post
Share on other sites
Virtual calls are OK, as long as you use them only at higher levels. For example, Game::Render, Engine::Render, World::Render and maybe Entity::Render would be acceptable. However, Triangle::Render and Particle::Render would not be - there are too many low-level objects like triangles or particles. Any insignificant performance loss for using virtuals at higher levels will be dwarfed by the convenience, in my opinion.

Furthermore, I doubt a simple list iteration for a list of tasks is going to kill your performance. If you want to do something anyway just to calm yourself down, you can use a single-linked list, with the pointers embedded directly in the objects themselves. That way there is no additional allocation and release of list elements, and no additional indirection. This would work because your objects are tasks, which are unique (I assume) and can only be in one list, and can only occur once in that list.

Well, and the last thing. As I myself learned from countless hours of hard work, the best way to go about optimization is to first implement your feature in the easiest and clearest way possible, doing as less work as possible (i.e. using libraries). Then you run the application and assess performance. If you are unsatisifed, track down the causes to one or more bottlenecks and fix the bottlenecks (you will probably have to do tons of reasearch to find out if you used the wrong data structure, etc). Some amount of pre-planning is of course suitable, but trying to get it right the first time (when you don't have enough experience) will do nothing but waste you time and energy.

Share this post


Link to post
Share on other sites
Quote:
Original post by ValMan
Virtual calls are OK, as long as you use them only at higher levels. [...] Triangle::Render and Particle::Render would not be [OK]

So you say you can't have different kinds of particles and treat them polymorphically? Because if you craft your own if/else, switch or function pointer table solution, it won't be faster than a virtual method call.

If you NEED polymorphic behavior, it doesn't make sense to say virtual is too slow.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by ValMan
Virtual calls are OK, as long as you use them only at higher levels. [...] Triangle::Render and Particle::Render would not be [OK]

So you say you can't have different kinds of particles and treat them polymorphically? Because if you craft your own if/else, switch or function pointer table solution, it won't be faster than a virtual method call.

If you NEED polymorphic behavior, it doesn't make sense to say virtual is too slow.

A virtual function per particle is usually overkill and unnecessary - I've always found it better to move the abstraction to the ParticleSystem instead, eg:


class IParticleSystem
{
virtual IParticleSystem();
virtual void render() = 0; // not a real interface
};

class PointParticleSystem
{
virtual void render();
private:
struct PointParticle
{
float x, y;
};
PointParticle particles[];
};

class LineParticleSystem
{
virtual void render();
private:
struct LineParticle
{
float prevX, prevY;
float currentX, currentY;
};
LineParticle particles[];
};


This provides you with all the flexibility you practically need with much less virtual function call overhead (which is necessary if you want lots of particles).

Share this post


Link to post
Share on other sites
Virtual call is only marginally slower than normal function call, however:

- vcalls are not inlined
- vcalls are prone to cache misses because of additional access to vtable

Recommendation: use vcalls for higher level code or do a reasonable amount of processing in the called function. To some extent you can workaround problem with cache misses with method pointers (last resort - makes code ugly :o)

As for List - iterating itself is basically not a problem. Make sure your list implementation allocates nodes from continuous memory pool or you will again suffer cache misses. You can even try experimenting with vector if you have small number of elements and do the additions/removals rarely.

Final note: yes for a few tasks these optimizations are really waste of time :o) However if you encounter similar design choices with containers/vcalls its handy to know whats going on (better data locality can beat seemingly smarter code in terms of performance!).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!