Faster Vector list... how?

On 19/04/2015 at 12:13, xxxxxxxx wrote:

User Information:
Cinema 4D Version:   15 
Platform:      Mac OSX  ; 
Language(s) :     C++  ;

---------
I'm writing a plugin that uses arrays of Vector like this:

  
Vector* point_list=NULL;   
...   
point_list=new Vector[n_elements];   
...   
delete [] point_list;   

I access these arrays of Vector elements in the usual way:

  
value=point_list[i];   

and

  
point_list[i]=value;   

Is this the fastest method to deal with a list of Vector values?
Is there a more efficient way?

Because I have to deal with, sometimes, HUGE amounts of vectors.
And to create a spline I use this:

  
SplineObject* my_spline = SplineObject::Alloc(n_points, spline_type);   
Vector*      padr = my_spline->GetPointW();   
for (LONG i=0; i<n_points; i++) padr[i]=point_list[i];   

Is there any faster way?

On 19/04/2015 at 13:54, xxxxxxxx wrote:

This is C++ dependent, but using pointer math instead of array indices is faster:

Vector* padr = my_spline->GetPointW();
Vector* lpadr = padr + n_points;
Vector* pl = point_list;
  
for (; padr != lpadr; ++padr, ++pl) *padr = *pl;

The reason for this is that array indices need to be resolved to pointer math in the array and then the memory address retrieved.  With pointers, the memory address is calculated directly.

On 19/04/2015 at 13:58, xxxxxxxx wrote:

Note that adding an integer to a pointer automatically jumps the array index (element size is taken into consideration - even for classes).  In essence, adding the number of array elements to the first element pointer, points it one past the last element.  As soon as the first pointer equals the last pointer, the loop exits.

On 19/04/2015 at 14:56, xxxxxxxx wrote:

Thank you. I will see if I can change all my Vector array stuff to pointer math.
And maybe see if I can do more optimizations on the way. I have too many calculations going on in nested loops :-(

On 20/04/2015 at 00:18, xxxxxxxx wrote:

Originally posted by xxxxxxxx

Thank you. I will see if I can change all my Vector array stuff to pointer math.
And maybe see if I can do more optimizations on the way. I have too many calculations going on in nested loops :-(

You shouldn't do that. kuroyume0161's advice might have been true 5-10 years ago but these days you can rely on compilers producing optimized code instead of fiddling with pointer arithmetics.

Most likely the compiler will create very similar code no matter if you use pointer arithmetics or the [] operator (there is even a chance that an optimizing compiler translates the later into SSE or AVX instructions while he wouldn't for the pointer aritmetics).

Furthermore for your first example (of using new and delete for allocating/manually freeing an array) I'd encourage you to use Cinema's BaseArrays.

They not only take care of releasing the memory when the scope is left - avoiding memory leaks, but also contain bounds checks in debug; making sure you notice when exceeding the array bounds (your manual allocated array can exceed the bounds - in case of a programming error - without letting you know, resulting in a crash or memory trasher).

Best regards,

Wilfried

On 20/04/2015 at 00:58, xxxxxxxx wrote:

There is no risk in exceeding the bounds. Everything is very well calculated (if I may say so myself :-) )
I will look into BaseArrays, then. They are faster than plain Vector arrays?

On 20/04/2015 at 01:15, xxxxxxxx wrote:

Originally posted by xxxxxxxx

There is no risk in exceeding the bounds. Everything is very well calculated (if I may say so myself :-) )
I will look into BaseArrays, then. They are faster than plain Vector arrays?

They are as fast as your manual arrays, but can grow/shrink in size, allow insertions/deletions (that change the array size), have bounds checks, support move operations, support iterators, ...

Unless you have a very unusual programming problem I'll doubt that your real performance problem will be loading or storing data into an array. It's more likely that the bottleneck will be calculations with that data or avoiding unnecessary calculation of that data.

Apple's Instruments (time) profiler is your friend in tracking down these issues!

Best regards,

Wilfried

On 20/04/2015 at 05:39, xxxxxxxx wrote:

  
Vector* point_list=NULL;  
point_list=new Vector[n_elements];  
delete [] point_list;  

Oh please do NOT do this !
Do NOT use code like this !

Prefer to use maxon::BaseArray<Vector> instate.
Or at lest some other kind of C++ arrays.

I would say never use new[] and delete[].

Bet if you want more performance then you will need to start using SIMD (SSE,AVX).
Modern compiler will try to generate SIMD code for you but of course this do not work in all cases.
Also you memory need to be properly aligned.

Second step would be multi-threading...
 
Remo

On 20/04/2015 at 06:07, xxxxxxxx wrote:

I will try to change all my Vector arrays to BaseArrays.
Just out of curiosity, why should I never use new[] and delete[]?

Yes, I definitely need to check out the calculation part of my code to see where I can optimize it.

I'm using XCode. How can I make it generate SIMD code? (I don't even know what that is ;-) )

As for multithreading, I definitely DON'T KNOW how to implement that.
Is it even possible for a spline generation plugin?

On 20/04/2015 at 06:35, xxxxxxxx wrote:

Just out of curiosity, why should I never use new[] and delete[]?
Because it is all too easy to make a mistake and produce memory-leak.

  
Vector* point_list = new Vector[n_elements];  
//do some work here  
delete point_list; // this is wrong  

  
Vector* point_list = new Vector[n_elements];  
//do some work here  
if(well_done) return true;  
//do more work here  
delete[] point_list; // this will be not called  

I would also avoid naked/manual delete in almost all cases.

Xcode 6 will try to use SSE3 per default, how well this really work is of course other question.
Handmade SIMD code can be faster but also much more complicated and error-prone.
So it makes sense to some library optimized for this.

If you want to do it multithreading in hard and not comfortable way then try to use C4DThread form C4D API :)

Remo

On 20/04/2015 at 06:39, xxxxxxxx wrote:

Well, my code is well behaved (I don't leave inbetween the new[] and delete[]) but I see your point. I will change to BaseArrays :-)
I'm still using XCode 5.0.3
Will XCode 6.x create more optimized code?

I have to see how that C4DThread stuff is. I'm not a professional programmer so, it may be too much for me ;-)

On 20/04/2015 at 07:08, xxxxxxxx wrote:

Originally posted by xxxxxxxx

Well, my code is well behaved (I don't leave inbetween the new[] and delete[]) but I see your point. I will change to BaseArrays :-)
I'm still using XCode 5.0.3
Will XCode 6.x create more optimized code?

I have to see how that C4DThread stuff is. I'm not a professional programmer so, it may be too much for me ;-)

Xcode 6 (6.2/6.3) has a variety of options going from no optimizations up to aggressive optimizations (which can include link time optimizations). There are similar options for Xcode 5 (but not the aggressive optimizations option).

The used vector ops are determined by the code generation settings in Xcode and are by default SSE 3 in the current SDK (as any supported machine has it included). If you enable new vector ops (e.g. AVX) you might gain speed (depending on your problem), but reduce the amount of machines that can run your plugin.

Regarding multithreading: Understand your single-threaded performance bottlenecks and optimize them before start digging into multithreading. It's a different playground - a lot to learn and lot of things that can go wrong :-)

Best regards,

Wilfried

On 20/04/2015 at 07:14, xxxxxxxx wrote:

Thank you for all the answers.
I will check out the optimization of the code.
And I prefer to have my code running in more types of machines :-)

On 20/04/2015 at 15:54, xxxxxxxx wrote:

How does one use, say, BaseArray with my_spline->GetPoints()?  Do you simply cast or does one need to copy the Vector* array into the BaseArray?  What exactly?  You guys continue to tout this stuff but where are the extensive usage examples?  Even these types are well hidden in the API docs.  And they are not used in the cinema4dsdk examples.  One reason that I don't use them is there is no exemplification of their usage.

On 20/04/2015 at 16:10, xxxxxxxx wrote:

Well, that is an excellent question, Robert.
I would also like to know that.

On 20/04/2015 at 17:02, xxxxxxxx wrote:

I'd use STL, std::vector can handle all of this, fast, cache friendly, I think I use it 99% of the time.

On 20/04/2015 at 17:16, xxxxxxxx wrote:

The problem with the STL is that is utilizes Exceptions and the C4D SDK does not.  If an exception is thrown you must be assured to capture and handle all of them or the code will unwind back to C4DMain (and crash).  As the docs say:

"Do not use external libraries (e.g STL or BOOST) unless absolutely necessary."

and

"C++ exceptions and RTTI will not be used in any of our projects unless external libraries require it (also RTTI operators typeid and dynamic_cast cannot be used)."

You can use them but be aware of the caveats.

ETA: I see that the "Plugin Code Style Guide" does mention the use of BaseArray et al in a basic sense.  It would be nice to know more about using these classes with the built-in pointer arrays (such as Vector and CPolygon arrays).

On 20/04/2015 at 18:26, xxxxxxxx wrote:

I think you can compile with exceptions turned off? at least this is doable in visual studio, not sure about xcode.

On 20/04/2015 at 18:38, xxxxxxxx wrote:

I am pretty certain that doing so causes the compiler to complain since they are needed.  Been there, tried that.  Maybe there are ways to circumvent it, but if you disable "Handle Exceptions" in a project, it typically errors on the build if there are exceptions in the code.

On 20/04/2015 at 19:46, xxxxxxxx wrote:

oh, I wasn't aware of this "I guess I'm learning more about exceptions everyday "

I don't want to jump over the thread with my questions now, but I'm curious about 2 things:
1- I'm using a dll which uses STL very heavily , is this safe?
2- any suggestion of STL like containers library that doesn't use exceptions? "I didn't try Boost yet but I don't know if it uses exceptions or not".