Question about efficiency of virtual functions

It is actually best to ask the compiler himself. Many circumstances have influence on many consequences. It possible that no virtual-call is done at all, in case the compiler can prove that a specfic member function gets called. Then, your CPU has a lot of stuff to accelerate this; e.g. branch target buffer may leverage the potential virtual call overhead to a large degree.

In doubt, test a virtual against a non-virtual version directly in your application, and see if the benefits outweigh the disadvantages.

Unless the compiler can resolve the type at compile time then it has to perform the lookup each time.

As to how much this will cost depends on a number of factors; branch prediction will probably help a bit, as will having the vtable in cache.

However if branch prediction fails and the vtable isn't in cache then you are doing a round trip to ram and probably hitting some pipeline stalls which are going to cost you.

Personally I don't think virtual function is a problem.
DirectX uses only virtual functions (COM interface).

If you want to avoid virtual function, you can either not allow polymorphisim or use templates to get compile time polymorphisim. But I don't think it worth the efforts.

Quote:

Personally I don't think virtual function is a problem. DirectX uses only virtual functions (COM interface).

DirectX calls are slow, with or without the virtual function overhead. Getting decent performance relies on doing a lot of work with each individual API call.

The VTable lookup mightn't cost more than a couple of cycles (if you're lucky and don't cache miss), but you still eat the overhead of making an actual function call. The compiler can't inline a function if it's forced to call it virtually.

You can always rewrite the slow parts of your code to not use virtual calls. You don't need to scrap your inheritance design - just store certain objects with their actual pointers and not a pointer to their base class.

Anyway, was the per-pixel virtual calls just an example or are you actually doing that? You don't need a profiler to infer that trying this on thousands, possibly millions of pixels is a bad idea.

Quote:

For example if you have a per-pixel effect (not graphics card shaders, I mean on images in regular computer RAM) implemented in an object oriented way (with an interface and many implementations of different possible per-pixel effects using virtual inheritance), and you loop through all pixels of an image: is this a good idea or is it going to be slow because it has to resolve the virtual function for every pixel again?

Unfortunately, even without virtual functions, calling a function per pixel is pretty slow.

Edit: Unless the compiler takes care of that by inlining, of course.

Quote:

Original post by joachim_n Quote: For example if you have a per-pixel effect (not graphics card shaders, I mean on images in regular computer RAM) implemented in an object oriented way (with an interface and many implementations of different possible per-pixel effects using virtual inheritance), and you loop through all pixels of an image: is this a good idea or is it going to be slow because it has to resolve the virtual function for every pixel again? Unfortunately, even without virtual functions, calling a function per pixel is pretty slow. Edit: Unless the compiler takes care of that by inlining, of course.

For per-pixel operation, I will use inline or macro

Quote:

Original post by Lode If you call a virtual function ... does a C++ program snip... or will the compiler snip... or something similar?

What does the compiler say? Open the FINAL BUILD in your debugger. Review the generated code. Contemplate it, know it, love it. Now you know what it is actually doing. Sometimes compilers apply surprisingly brilliant optimizations; other times they do astoundingly stupid (but extremely safe) things. You never know what it does until you look.

Next, what does your profiler say? Profile the FINAL BUILD. Review what are measured as the most time-intensive, compute expensive, data intensive, and otherwise hotspot areas of your program. Contemplate it, know it, love it. Now you know what should be reviewed. It generally isn't the tight inner loops, but the obscure function run every frame that happens to loop over a compute-intensive function, which in turn loops over another compute-intensive function, which in turn loops over code which should be removed and contributed nothing to the game.


After you know what it is actually doing and how long it actually takes, you are in a position to improve it. You are not ready to do this until you have actually measured, and you won't know if you've improved anything until you change it, review it, and measure it again. Many "improvements" actually make things worse, so proceed with caution.


Consider that programs use virtual functions all over the place. Consider that most programmers either think nothing about it, or think of it as a barely-measurable performance cost in exchange for incredible flexibility and abstraction. That should give you some additional insights.

Quote:

Original post by Lode For example if you have a per-pixel effect (not graphics card shaders, I mean on images in regular computer RAM) implemented in an object oriented way (with an interface and many implementations of different possible per-pixel effects using virtual inheritance), and you loop through all pixels of an image:

If speed is all that matters, then implement it and run a profiler.

Otherwise, such design is simply wrong. Per-pixel processing is a very well understood problem, and it's solved using streaming algorithms.

Quote:

is this a good idea or is it going to be slow because it has to resolve the virtual function for every pixel again?

Unless using compile-time polymorphism via templates, compiler needs to determine which function to call for each pixel.

Java standard library used this approach in some of first versions and it was a disaster. It's imply unwieldy and cumbersome.


What kind of processing are you really trying to do?

Quote:

Consider that most programmers either think nothing about it, or think of it as a barely-measurable performance cost in exchange for incredible flexibility and abstraction.

It depends whom such implementation targets. Anyone with basic background in graphics will scream in agony over object-per-pixel design. It's not flexible or convenient, merely clumsy. It's really not rocket science to use streaming design, even convolution filters are easy to grasp. Having virtual functions and encapsulated objects does not add or contribute to flexibility. Good design suitable to problem at hand does.

Quote:

Original post by frob Consider that programs use virtual functions all over the place. Consider that most programmers either think nothing about it, or think of it as a barely-measurable performance cost in exchange for incredible flexibility and abstraction. That should give you some additional insights.

It depends WHERE they are being used.

In your game object or GUI hierarchy, sure the cost is going to outweigh the benifit but once you start talking about taking a few virtual call hits per pixel in an object alarm bells should start ringing if you want any sort of performance.

Virtuals aren't bad in the general case, I don't think anyone is going to argue about that, but applying the general case to everything isn't going to end well. Virtuals serve you best when you can't predict or ensure certain types are going to be worked on; but as soon as you get into any sort of situation where the types can be predicted ahead of time or are setup once and never change (or change very infrequently) then a better design might well be called for.

Quote:

Original post by Antheus Otherwise, such design is simply wrong. Per-pixel processing is a very well understood problem, and it's solved using streaming algorithms.

Do you mean this: http://en.wikipedia.org/wiki/Streaming_algorithm ?

Quote:

Original post by Lode Quote: Original post by Antheus Otherwise, such design is simply wrong. Per-pixel processing is a very well understood problem, and it's solved using streaming algorithms. Do you mean this: http://en.wikipedia.org/wiki/Streaming_algorithm ?

No, SIMD. Choose one single operation upfront. Apply it to all pixels. Whether SSE is used or not is irrelevant, but since compiler optimizations were mentioned, C++ compilers are capable of some basic optimizations of such algorithms.

What you end up is dozens or hundreds of different functions (maybe generated through templates) that each handles one particular case.

In C++, something like this works:

template < class Pixel > struct MinMaxFilter {}template <> struct MinMaxFilter<RGB> {  size_t stride() const { return 3;}  void apply(char * ptr) {    ptr[0] = (ptr[0] > max) ? max : ptr[0];    ptr[1] = (ptr[1] > max) ? max : ptr[1];    ptr[2] = (ptr[2] > max) ? max : ptr[2];  }}template <class Filter>void apply(Filter & f, char * pixels, size_t count) {  char * end = pixels+count;  for ( ; p < end; p += f.stride()) f.apply(p);}

Note that despite apparent function calls, no decisions are made on per-pixel basis (besides actual pixel processing logic). Any algorithm designed in such a way is conceptually compatible with everything from SIMD to CUDA.

That retains the flexibility of polymorphism with no algorithmic overhead, even if it's not hardware-optimal (alignment, full saturation for SIMD and similar), but those aren't necessarily relevant.

At which point starting with GIL makes more sense anyway.

Another option might be to move the tight loop inside the virtual function call (so pass the buffer of pixels/data to the virtual function, rather than one pixel at a time).

Not sure if that's possible with the algorithm you're trying to implement or not.

Quote:

Original post by Milkshake Not sure if that's possible with the algorithm you're trying to implement or not.

Yes, it's certainly possible, and I was planning to in case not doing it that way is too slow, it just means a little bit more code duplication (retyping the for loop everywhere).

The template solution would be possible as well, but a bit more work to implement in my situation.

Quote:

Original post by phantom Unless the compiler can resolve the type at compile time then it has to perform the lookup each time.

That doesn't seem right to me. As long as there aren't aliasing problems, it should be able to hoist the "dereference the vtable pointer" etc. instructions out of the loop, since the addresses are constant.

Unless some of my knowledge is very suspect at the point of 'lookup here' the runtime has to fetch the vtable for the correct type, lookup the function required and then jump to that location.

As I understand it each sub-type has its own vtable, so until the runtime hits the point where it is doing the lookup it has no idea of the type, so has to resolve it each time. Not a huge problem if the vtable is still in cache somewhere but an issue as soon as it falls out of cache and we stall on the lookup.

Now, it might be clever and try to cache details locally so it can avoid a lookup for the same types happening twice and avoid the cache miss but this is only going to help if we are ordered by type.

For example;
D1,D1,D1,D2,D3

Would work nicely with cache or another caching system as well as branch prediction.

However;
D1, D3, D1, D1, D2, D1, D1, D3, D3, D2

If likely to cause both cache misses (if foo is non-trival work wise) AND branch misprediction as its not a pattern it can predict well. (At a guess that would cause maybe 6 mispredictions).

Of course I could be totally wrong on all the above points so if someone knows for certain please correct me, but that is my understanding of the problem and why its an issue (more so on a console than an x86/x64 cpu, but still a problem all the same).

That is an issue. Even when the vtables are in cache, branch misprediction can still slow things down. Not much, but it can add up if the things in questions are, say, particles in a particle system, in, say, a particular game engine that was, say, coded several years prior without much regard for performance. (GodDAMN that was some slow code.)

At about the time when vtable lookups become a performance issue, arrays of pointers-to-structs also become a performance issue. So you'll generally end up segregating objects by their dynamic type and either shoving them into a series of per-type arrays, or even going further with an SOA representation, which makes things even weirder. What you want, basically, is for your inner loop to not have to worry about the type of the object, both for pipeline reasons and for vectorization reasons.

Quote:

Original post by phantom Unless some of my knowledge is very suspect at the point of 'lookup here' the runtime has to fetch the vtable for the correct type, lookup the function required and then jump to that location.

I was thinking of the case where 'ptr' is constant throughout the loop, since that seemed to be what the OP was thinking of. Even then it might not be a straightforward optimization, though.

Quote:

Original post by Sneftel That is an issue. Even when the vtables are in cache, branch misprediction can still slow things down. Not much, but it can add up if the things in questions are, say, particles in a particle system, in, say, a particular game engine that was, say, coded several years prior without much regard for performance. (GodDAMN that was some slow code.)

That is true enough, but it the exception and not the rule.

Virtual functions themselves should be used wherever they are needed. In the general term, even for many fairly tight loops, they are just fine. The very few exceptions to the rule can be picked up by profiler.

And as you pointed out with your example, the slower version can be in place for years without much need for change. Better to have something slow that ships than to spend a theoretically optimal game that is never complete.

Quote:

Original post by frob The very few exceptions to the rule can be picked up by profiler.

Designing image processing object with per-pixel polymorphism is one of those cases where profiling isn't even needed. It's just the wrong choice.

Quote:

Better to have something slow that ships than to spend a theoretically optimal game that is never complete.

SoA vs. AoS design decision is very far from theoretical optimality.