🔒 Locked

Inline, optimizing etc.

Unity

Started by Opwiz Jul 2, 2004 at 5:52 PM 6 replies 550+ views

Original Post

Opwiz

Jul 2, 2004 at 5:52 PM

I've designed my own interfaces for containers and iterators. I wanted to support polymorphic iterators because I think they are neat and I've created a rather basic interface for a container that enables generic iterations through the container, i.e. any container can be iterated through without knowing its exact type. This in turn enables the ability to create tree structures etc. that can use any container for its children and data without the necessity to have multiple implementations of the tree iterators, which is also neat.. Anyway, I also created a basic static array container to test the performance of my code. I was rather suprised to find out that iteration through the elements of the container is almost ten times as slow as with the vector class in the standard library. I thought it had to do with the overhead of using a polymorphic iterator, it means one extra level of indirection as I had to use a smart-pointer to take care of the deletion of the iterator pointer. Then I thought that inlining some functions would help but that resulted in same or even slower execution (!). Now it really bothers me so I tried removing one level of indirection by using the iterator pointer directly.. and the performance gets even worse. Now I'm really confused, does it have to do with the compilers ability to optimize the code? Maybe it optimizes the code better under certain cicumstances that are not obvious to the programmer? My second guess is that it has to do with the profiler. I'm using DevPartner community edition, anyone know how reliable it is? Just wanted to share my experiences and hear if anyone might have any comments.

DigitalDelusion

Jul 2, 2004 at 5:58 PM

Basicly what you did was this, you took an interface designed specificly to be non intrusive lightweigh and fast and replaced it with virtual functions and some extra abstraction layers and then you wonder why the speed fell so drasticly?

std::vector can be viewed (after technical corrigendum) as a linear chunk of memory, and its iterators are often (but not always and you shouldn't depend on this) just plain pointers.

That means that moving the pointer is a single op for the CPU in most cases.

Now have a look at your virtual iterator design when you tell it to advance one position the least thing it must do is to make a roundtrip to the vtable fetch a function pointer and call it and hopefully eventually get back to doing usefull stuff, the roundtrip alone is more work than increasing the std::vector iterator.

So even if you consider your design neat, most C++ programers would shrug it of as a Java solution it's just not the way to write highly effective C++ programs for those you use generic programing concepts to get rid of inheritance and let the compiler do its work.

ApochPiQ

1,378

ApochPiQ

Jul 2, 2004 at 7:05 PM

First rule of optimization: optimize your algorithm first, before you worry about optimizing individual pieces of code. Your algorithm sounds very powerful but it is not practical for performance-critical scenarios. I highly doubt you will get a generic system like this working anywhere near as fast as std::vector - generic functionality virtually always comes at the expense of performance.

The question to ask at this point is, would you rather save yourself a tiny bit of programming effort at the expense of speed, or maintain speed at the cost of a little more work for yourself? There really isn't a "right answer" for all cases - it depends entirely on what your needs are. Save whichever form of time you need the most - programming time, or execution time.

Opwiz

Author

Opwiz

Jul 3, 2004 at 5:12 AM

I was hoping that the powerful design would outweigh the loss of performance. I am working on a 3d engine and one example where it would be useful is when designing a generic container for spatial objects. This container could be an octree, kd-tree, quadtree, etc. The renderer or physics engine could easily iterate through the objects this container without knowing its exact type. This makes the engine very flexible and makes it easier for the client programmer to use and expand the engine. But it won't be any good I guess if the performance of the rendering loop is poor.

DigitalDelusion

Jul 3, 2004 at 5:19 AM

The real question is whatever iteration will really in any way affect performance in that case, really you're comparing applpes and oragnges. When using a vector the prime thing is often iteration and access it has to be fast otherwise it's pretty much useless. When moving to more complex containers and doing other significant work the iteration time probably becomes neglible in comparasion to transformation and rendering.

You'll just have to evalutate your system, but really in that usage scenario I don't think your solution should pose a performance problem but for straight iteration it's obviously not a good candidate ;)

__fold

Jul 3, 2004 at 6:20 AM

It sounds to me that all you want to do can be done with the standard STL classes along with templates... but I might be wrong.

DigitalDelusion

Jul 3, 2004 at 6:23 AM

Quote:
Original post by __fold
It sounds to me that all you want to do can be done with the standard STL classes along with templates... but I might be wrong.

sans changing the underlying structure runtime...

Opwiz

Author

Opwiz

Jul 3, 2004 at 7:58 AM

Hmm.. yes it could work if you don't need to change the underlying structure during run-time as DigitalDelusion pointed out. A possible scenario is that the renderer needs to be able to render the objects in a bsptree at one point and the objects in a quadtree at another point. It could work if the renderer method that draws the objects in the spatial container is templated. However, the renderer interface needs to be abstract so that different renderer implementations can be used.. and templated methods can't be virtual.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.