C++ class question

big_gie · 2009-06-28 19:04:05

Hi,

I have written a code for simulation of an N-body problem. The code compiles with a C++ compiler, but it is mainly plain C (no classes/objects, for now).

The code uses a structure to encapsulate each particles' information (position, mass, etc.) and memory is allocated at the start for an array of this structure which is then populated. I expect to move the O(N^2) algorithm to an O(N log(N)) soon, but that will require some modification to the structure.

I was looking at classes' inheritance and I think I could take advantage of it. Mainly I would create a mother class which two other classes would inherited. Nothing more. But since the code performance is critical, I need to make sure I don't get any overhead with the path I'll take.

I'm thus asking for advice on the issue. Can I achieve the same performance using classes then using structures? Something I need to be careful with? I know I should keep away from virtual functions, which I will. I think constructors/destructors won't be a problem since I allocate a big array at the initialization of the code and this array does not change through the simulation. The destructor should only be called at the end, when the code finishes.

Is there any overhead I'm missing?

Thanx!

arkham · 2009-06-28 19:23:48

As far as I recall, the only difference between classes and structures is that by default the variables and the methods of a class are private. I don't see why you should keep away from virtual funtctions, since they are one of the reasons why someone would want to use base/derived classes.

big_gie · 2009-06-28 21:45:58

By reading on the web, virtual functions might get "slow" because which function to call is detected at run time using the vtable. It is similar to storing a pointer to a variable in another variable versus storing the actual value in the variable. In the first case, you need to dereference 2 pointers to access the data, while in the last one its only once...

I'm still reading this one: http://bjacob.livejournal.com/6110.html which argues that the overhead is minimal. The thing is my application is performance critical. I absolutely cannot afford a single overhead. This can make a difference between a runtime of a month compare to a runtime of a week...

big_gie · 2009-06-28 22:04:50

And while I'm at it, I'll ask also this.
The aforementioned code uses a library meant for certain physics phenomena. The library is to be used by different code, with different structures for the particles. So will be simple (position and mass), others will be more heavyweight (position, vel, accel, mass, charge, etc.) so there is no unified structure. Because of this, the library does not know the structures and relies on functions defined in the code to access the members.

For example, Get_Position(pointer) will return the pointer to the first location of an array of size 3 of doubles. These functions are defined as taking void pointers and they cast it to the actual code's struct and returns the wanted member:
double* Get_Position(void *b) { return ((Particle *)b)->pos; }
This is the only way I was able to make the library 100% independant of any code. I first tried with templates, but the library became dependant on the code which depended on the library... I'm still open for suggestion on a better way to do that...

So now the code needs to define the accessing functions like Get_Position(). But these functions takes void pointers as arguments so they can't know if the pointer was a pointer to the mother class, or one of the two daughter class. I still don't how the Get_*() functions can choose to which class to cast... Any suggestions?

Thanx a lot

Allan · 2009-06-29 03:29:09

Well, you could use the Curiously Recurring Template Pattern to avoid virtual overhead. Something like....

template <typename derived>
struct base
{
    double* get_position() { static_cast<derived*>(this)->get_position(); }
};

struct derived : base<derived>
{
    double* get_position() { return position; }

    private:
    double* position;
};

What this achieves is that what would be a virtual function call (get_position()), is actually evaluated to is derived class at compile time. Thus "no" overhead for achieving something like a virtual function.

gnud · 2009-07-01 19:13:08

The virtual overhead is tiny - it's the same as following a function pointer.

And if you have many child classes using virtual funcitons, I think Alans function might increase your code size a fair bit. Right?

Last edited by gnud (2009-07-01 19:14:17)

Cerebral · 2009-07-01 19:42:42

Allan wrote:

Well, you could use the Curiously Recurring Template Pattern to avoid virtual overhead. Something like....
template <typename derived>
struct base

struct derived : base<derived>
What this achieves is that what would be a virtual function call (get_position()), is actually evaluated to is derived class at compile time. Thus "no" overhead for achieving something like a virtual function.

Yeah, but you lose the common base-class. Now every 'derived' class inherits from a totally different base-class and you lose polymorphism.

alienman · 2009-07-01 19:54:42

My suggestion is that if the performance is that critical, you should stay with C and instead learn how to simulate object inheritance. An example could be gtk libraries.

I don't know if that could help you, since I don't have many experience in C development.

krolden · 2009-07-01 20:08:20

alienman wrote:

My suggestion is that if the performance is that critical, you should stay with C and instead learn how to simulate object inheritance. An example could be gtk libraries.
I don't know if that could help you, since I don't have many experience in C development.

In the end it all depends on how the thing is compiled. I can imagine that C++ doesn't have to be less performant than C.

A lot depends on how smart you program it.

ngoonee · 2009-07-01 20:25:02

AFAIK, if you're ALREADY compiling with a C++ compiler anyway, there is NO difference between struct and class, especially in terms of performance.

Concerning performance, as a rule of thumb this is only a concern when/if you've profiled your code to see what takes up the most time. Unless you have literally millions of calls to a function (I don't know how involved your simulation is, of course) the cost of an additional indirection *MAY* be negligible compared to the actual meat of your processing algorithm.

Allan · 2009-07-02 02:10:05

Cerebral wrote:

Allan wrote:
Well, you could use the Curiously Recurring Template Pattern to avoid virtual overhead. Something like....
template <typename derived>
struct base

struct derived : base<derived>
What this achieves is that what would be a virtual function call (get_position()), is actually evaluated to is derived class at compile time. Thus "no" overhead for achieving something like a virtual function.
Yeah, but you lose the common base-class. Now every 'derived' class inherits from a totally different base-class and you lose polymorphism.

You do, so you can not really use this if you want to create an array of base<T> store everything... but it works well for some things (e.g. I believe the stl valarray class in gcc uses a combination this and expression templates).

big_gie · 2009-07-05 17:36:07

alienman wrote:

My suggestion is that if the performance is that critical, you should stay with C and instead learn how to simulate object inheritance. An example could be gtk libraries.

Performance _is_ critical. This code will run on supercomputers
A previous code was using a hack to mimic inheritance:

struct base_struct
{
    double position[3];
};
struct child_struct
{
    base_struct base;
    double charge;
}
double * Get_Position(void *p) { return ((base_struct *) p)->position; }

This works because casting to "base_struct *" and accessing the "position" element will tell the compiler "take the pointer to the start of the structure, and go a certain offset to access position". Because the child_struct contains a base_struct element, an offset from the start of the base_struct will give the same value as the same offset but from the start of the child_struct.
This works (if you don't insert values _before_ "base_struct base" in the structure). The cast is evil though. I'd like to get rid of it.

But then, this is a library which does not know the structure: its using void pointers. So it will need to cast anyway. So maybe inheritance wont help me here. I think I might just put the "position" array directly inside the "child_struct"...

"ngoonee wrote:

Unless you have literally millions of calls to a function (I don't know how involved your simulation is, of course) the cost of an additional indirection *MAY* be negligible compared to the actual meat of your processing algorithm.

These functions will be used millions and probably billions of times (30 000 particles, hundreds of thousands of time steps, etc.). Before profiling it, I need an implementation, which I don't have. So before getting one, I prefer thinking of the best way to do it.

I think putting the needed elements directly in the "child" struct/class will be the simplest resolution...

Thanx all for your input

By the way, anyone have experience with Z-ordering (Morton order, N-order)? I'm trying it with double precisions values but I can't make it work. It only works if I scale the positions and cast to integer...

Arch Linux

#1 2009-06-28 19:04:05

C++ class question

#2 2009-06-28 19:23:48

Re: C++ class question

#3 2009-06-28 21:45:58

Re: C++ class question

#4 2009-06-28 22:04:50

Re: C++ class question

#5 2009-06-29 03:29:09

Re: C++ class question

#6 2009-07-01 19:13:08

Re: C++ class question

#7 2009-07-01 19:42:42

Re: C++ class question

#8 2009-07-01 19:54:42

Re: C++ class question

#9 2009-07-01 20:08:20

Re: C++ class question

#10 2009-07-01 20:25:02

Re: C++ class question

#11 2009-07-02 02:10:05

Re: C++ class question

#12 2009-07-05 17:36:07

Re: C++ class question

Board footer