Quadtree: struct vs. class

Assuming you're talking about C++, structs and classes are nearly identical. It's just that structs default to public for inheritance and member visibility, but classes default to private.

As stated above, structs and classes in C++ are nearly identical. Reading into you question, it could be rephrased to mean something else:

Should I implement quadtree nodes as public structs accessed by external functions, or as strictly object oriented classes with most logic as member functions?

There isn't a good answer to this question (and it might even start a C, C++ flame war ;), but I would recommend against using higher level OO techniques in such a performance critical area unless you are entirely cognizant of how to avoid the possible disadvantages of using classes in this way.

Of course, this might not be what you were asking at all.

Quote:

Assuming you're talking about C++, structs and classes are nearly identical.

Sorry, yes I am talking about c++. All the examples I can find show the older C style typedef struct to build the quadtree. I assume struct is fine too. I did know they are almost identical, but I'm not 100% familiar with all the nuances of c++.

Quote:

There isn't a good answer to this question (and it might even start a C, C++ flame war ;), but I would recommend against using higher level OO techniques in such a performance critical area unless you are entirely cognizant of how to avoid the possible disadvantages of using classes in this way. Of course, this might not be what you were asking at all.

This is exactly what I'm looking for. Can you give me some examples of disadvantages? I guess the problem is that I haven't quite figured out how I'm going to be implementing geomipmapping, just that it seems the best approach for how I have my rendering engine setup now. I know I will need to use a quadtree, but I'm only just now learning about them. Since I'm not sure how big or how much I'll be using my quadtree I'm not really sure how to start implementing it, or why others have chosen structs over classes. I was planning on just defining a struct in my terrain class and putting related functions in the same place. But I'm also thinking that it might be better to write an entirely seperate class for the quadtree, especially if it means that I will need a lot of functions to perform the operations necessary for geomipmapping.

Well...i recommend using classes for effective modularization and implementation....and yes...data members in structure are public by default and private in Classes...and also..using OOP techniques will be really helpfull in performance critical projects....

Quote:

Original post by mike_ix Quote: Assuming you're talking about C++, structs and classes are nearly identical. Sorry, yes I am talking about c++. All the examples I can find show the older C style typedef struct to build the quadtree. I assume struct is fine too. I did know they are almost identical, but I'm not 100% familiar with all the nuances of c++.

You can assume those examples are either in C themselves, or that their poster isn't "100% familiar with all the nuances of C++" either. While the typedef trick was useful in C to avoid having to use the struct keyword with every instantiation, it is redundant in C++. Regardless, I wouldn't base my idea of "proper C++ programming" (to the extent that such a thing exists) off such examples.

For a large project, a solid foundation is important. I certainly wouldn't skimp out on modularity for such a project, which while doable in C, most of C++'s features were geared towards making easier. Access specifiers to help avoid dependancies on implementation details, virtual functions to ease orthogonality, etc.

"OOP", classes, and private data isn't a cure-all, remember that. The modularity is what's important. These other things I'd describe as symptoms rather than the cause of a modular architecture.

Quote:

For a large project, a solid foundation is important. I certainly wouldn't skimp out on modularity for such a project, which while doable in C, most of C++'s features were geared towards making easier.

I definitely agree! I know this project will be getting larger than I can handle by myself and the modularity is definitely a good thing. Thanks for all the advice!

Using class style OOP vs C style structs for a OCTTree

There shouldn't be any dramatic slowdown by using a class over a struct unless you start using virtual's all over the place etc. If you don't use virtual's the OOP and external function methods should be similar in performance, any slowdowns if at all will be negliable.

On a PC application virtual classes don't matter so much, on consoles its a little bit more vital to avoid unneccessary virtual classes.

Quote:

Original post by deepdene There shouldn't be any dramatic slowdown by using a class over a struct unless you start using virtual's all over the place etc.

No, no, no. The correct answer was "There will never be any slowdown at by by using a class over a struct, period."

In C++, class is just another name for a struct, with two small differences. Classes default to private data and inheritance by default, while structs default to public data and inheritance. That's it. Everything else is exactly the same.

CM

Quote:

Original post by Conner McCloud Quote: Original post by deepdene There shouldn't be any dramatic slowdown by using a class over a struct unless you start using virtual's all over the place etc. No, no, no. The correct answer was "There will never be any slowdown at by by using a class over a struct, period." In C++, class is just another name for a struct, with two small differences. Classes default to private data and inheritance by default, while structs default to public data and inheritance. That's it. Everything else is exactly the same. CM

Sorry but working with PS2 consoles etc you soon learn there is a huge difference working with classes that have a virtual table, and using C style classes (where basically in C you stored POD types, and had no virtual evel functions), basically all your classes that you have virtuals in, it'll put a virtual table at the front of your class, and will pass around a this pointer. This causes havok with cache misses generally, so you tend to want to avoid unneccessary virtuals. So we are more talking about as I said, using struct's in a C context with using POD types only and the lack of virtuals then the actual difference, sure you could use a class and declare no virtuals and achieve the same thing.

Just remember that PS2 etc has very little cache on the main CPU so you tend to want to avoid thrasing the cache and unwanted virtuals is a clear way to do that.

Quote:

Original post by deepdene Quote: Original post by Conner McCloud Quote: Original post by deepdene There shouldn't be any dramatic slowdown by using a class over a struct unless you start using virtual's all over the place etc. No, no, no. The correct answer was "There will never be any slowdown at by by using a class over a struct, period." In C++, class is just another name for a struct, with two small differences. Classes default to private data and inheritance by default, while structs default to public data and inheritance. That's it. Everything else is exactly the same. CM Sorry but working with PS2 consoles etc you soon learn there is a huge difference working with classes that have a virtual table, and using C style classes (where basically in C you stored POD types, and had no virtual evel functions), basically all your classes that you have virtuals in, it'll put a virtual table at the front of your class, and will pass around a this pointer. This causes havok with cache misses generally, so you tend to want to avoid unneccessary virtuals. So we are more talking about as I said, using struct's in a C context with using POD types only and the lack of virtuals then the actual difference, sure you could use a class and declare no virtuals and achieve the same thing. Just remember that PS2 etc has very little cache on the main CPU so you tend to want to avoid thrasing the cache and unwanted virtuals is a clear way to do that.

Are you saying that structs with virtual functions doesn't suffer the same performance penalty as classes with virtual functions? You said there wasn't a difference unless you used virtual functions. Since this thread is about classes vs. structs, that implies you mean classes with virtual functions are more expensive than structs with virtual functions. That is, as Conner McCloud said, not correct. If the compiler you use treats virtual functions in classes and virtual functions in structures differently, then I would be mighty surprised.

No I am debating the fact, that the original intention of the article, is talking about traditional use of struct's in C, using struct with pod types only and external functions, or using c++ OOP with embedded functions.

I am saying that virtual functions are a cavet to avoid in C++ since it can be a slowdown, and one of the advantages of using C style POD struct's is that you avoid the cache overhead that you could potentially create if you don't know how to optimise OOP classes correctly.

Quote:

Original post by Brother Bob Quote: Original post by deepdene Quote: Original post by Conner McCloud Quote: Original post by deepdene There shouldn't be any dramatic slowdown by using a class over a struct unless you start using virtual's all over the place etc. No, no, no. The correct answer was "There will never be any slowdown at by by using a class over a struct, period." In C++, class is just another name for a struct, with two small differences. Classes default to private data and inheritance by default, while structs default to public data and inheritance. That's it. Everything else is exactly the same. CM Sorry but working with PS2 consoles etc you soon learn there is a huge difference working with classes that have a virtual table, and using C style classes (where basically in C you stored POD types, and had no virtual evel functions), basically all your classes that you have virtuals in, it'll put a virtual table at the front of your class, and will pass around a this pointer. This causes havok with cache misses generally, so you tend to want to avoid unneccessary virtuals. So we are more talking about as I said, using struct's in a C context with using POD types only and the lack of virtuals then the actual difference, sure you could use a class and declare no virtuals and achieve the same thing. Just remember that PS2 etc has very little cache on the main CPU so you tend to want to avoid thrasing the cache and unwanted virtuals is a clear way to do that. Are you saying that structs with virtual functions doesn't suffer the same performance penalty as classes with virtual functions? You said there wasn't a difference unless you used virtual functions. Since this thread is about classes vs. structs, that implies you mean classes with virtual functions are more expensive than structs with virtual functions. That is, as Conner McCloud said, not correct. If the compiler you use treats virtual functions in classes and virtual functions in structures differently, then I would be mighty surprised.

Quote:

Original post by deepdene No I am debating the fact, that the original intention of the article, is talking about traditional use of struct's in C, using struct with pod types only and external functions, or using c++ OOP with embedded functions. I am saying that virtual functions are a cavet to avoid in C++ since it can be a slowdown, and one of the advantages of using C style POD struct's is that you avoid the cache overhead that you could potentially create if you don't know how to optimise OOP classes correctly.

Of course dynamic function calls are poteitially slower than static function calls. But how would you implement a dynamic function call comparable to C++'s virtual functions using C style structs and external functions without some extra cost? If you don't use dynamic funcion calls in C++ then you don't pay for them. If you use them, you have to use corresponding functionality in C style aswell.

Quote:

Original post by Brother Bob Of course dynamic function calls are poteitially slower than static function calls. But how would you implement a dynamic function call comparable to C++'s virtual functions using C style structs and external functions without some extra cost? If you don't use dynamic funcion calls in C++ then you don't pay for them. If you use them, you have to use corresponding functionality in C style aswell.

Instead of having a heterogeneous list of objects and choosing the function via lookup for each element, you have several homogeneous lists of objects and process each list with a single function (or you could have a single list and sort by object type). Of course, this is not a general solution, but it is the solution for the particular problem at hand -- cache thrashing due to repeated vtable lookup.

I would be rather suprised if the OP is programming for the PS2...

I would suggest to just get it running (using classes or structs,
whatever you like - my personal opinion would be to try using
classes first) - and if it runs, download a copy of vtune or
amd-codeanalist, profile, and see if there are any bottlenecks
and then optimize.

Just use classes. You shouldn't need virtuals in a quadtree implimentation anyway, so it's kinda pointless discussing it. Virtuals aren't in themselves slow, nor do they bloat your code that much (vs. implimemting your own ad-hok C solution to solve the problem of runtime polymorphism). They only become slow when you use them for the wrong purpose, and using them for a hierarchical quadtree node (where all nodes are the same and do not need polymorphism at runtime), would be the wrong purpose....

I would say you could either:
use a struct (due to data members being public).
or
use a class with data members public(to avoid a function call)
or
use a class with data members private and the functions inlined.

Quote:

There isn't a good answer to this question (and it might even start a C, C++ flame war

I see what you mean.

Quote:

Original post by MidoriKid There isn't a good answer to this question (and it might even start a C, C++ flame war ;), but I would recommend against using higher level OO techniques in such a performance critical area unless you are entirely cognizant of how to avoid the possible disadvantages of using classes in this way.

Neverminding linguistic preferences, this is a fairly pointless suggestion. Here's why: If someone is ignorant of the performance characteristics of different approaches, they should either learn them or not be writing performance critical code.

That said, it is possible to write a high performance engine in fully object oriented C++ for the PS2 (I'm certain of this, as I've done it), so long as you pay attention to what parts of the language have an impact on performance. And none of this hooey about how the core of the renderer needs to be straight old-school C for performance, but the game code can be OO - that's dinosaur thinking.

As to the original post, choosing an appropriate algorithm like geomipmapping is going to have a much larger performance impact than a few d-cache misses for vtable lookup would. So, I would highly recommend using a clean object oriented approach.