I have been using vector in c++ lately, but I needed to speed up my code a bit so someone recommended I use regular arrays. My question is 2 part -
1) I thought you couldn't do this!!?? For some reason it is working with no problem?

2) I used a timer (from the VUL library of VXL) to time the following two functions. The only difference is one of the arrays is allocated using a global int, and the other is allocated using a #define. It actually turns out the the global int is twice as fast!!?? I thought they should be about the same (if the int even worked at all! (see question 1))


Any thoughts on either of these?

Thanks,

Dave

> 1) I thought you couldn't do this!!?? For some reason it is working with no problem?
Depends on your compiler.
Some compiler extensions permit this, so you just get lucky.
Enable whatever "strict ANSI" flags for a better idea of what is allowed and what isn't

2 million int's = 8MB of stack space.
Since stack space is allocated on demand, the first one to be called has all the overheads of allocating yet another page of stack every 4K.

But the second one - now that's already got the stack allocated from the first one, so it just blitzes through.

Swap the calls over, you'll see the reverse.

Or they could have been the same for a completely difference reason. Namely that the array is not used, and the compiler could have optimised the code out.

you're right, I switched the order and in both cases the first one took longer!!

How would you make an array of size determined at run time if you're compiler doesn't allow this?

Thanks,

Dave

int *myArray = new int [ somesize ];

Using arrays instead of vectors only saves you the overhead of C++'s object model, especially if you need a dynamically sized array. Instead of playing memory games, try using something other than a linear storage structure for your data. Your code might be too slow because you should be using a set instead of a vector, for example.

Never use std::vector for numbers crunching (in scientific or engineering calculations). This STL container never intended for fast calculations. If you don't want to take much trouble over new/delete, use std::valarray class.

For example, times to calculate sum of 10000000 double type elements:
AMD 5000+,VC++ 9 (Plauger's STL implementation), release mode, optimization for speed.
The vector was previously resized and initialized - no "overhead of C++'s object model" in the test loop. Timing precision was equal to ~1 microsecond.

I agree with Radical Edward - you may save some time switching from vectors to arrays (maybe half the time), but you may be able to structure your data so that you can perform your most often called operations in log(n) time instead of linear time. In this case a linear solution that took 1 second might take 10ms - a much larger improvement. What exactly are you storing and what kind of operations are you doing that is taking your program too long?

Alas, there are lots of problems (in computational physics, for exampe) where you never achieve O(log n) or more realistic O(n*log n) computational complexity. For example, you never multiply two matrices with better than O(n**2) operations (all existing algorithms have slightly better than O(n**3) ). There are lots of gas and fluids mechanics problems where computational complexity O(n**4) or even more...

I am not really doing operations on the vector, I am just storing values and retrieving them later. The problem is there are just lots and lots of them. I'll look into valarray's, but for now, if I use a standard array
don't I have to then manually delete the variable when I'm done with it?

Also, how can you get the length of the array after the fact (ie. the equivalent of MyVector.size() )?

Thanks,
Dave

How are you retrieving them? Is it in linear order or some kind of search? A straight traversal from beginning to end or end to beginning is well suited for an array, but you probably won't see a big difference between an array and a vector in that case. The storage overhead for a vector will be overwhelmed right away by the values, and the runtime cache difference between an array and a vector will be nonexistent.

If you're searching for values, the time you spend paging cache lines in and out is probably going to be significant with lots and lots of values, so a structure designed for searching like a set or hash_set should be your first step in optimizing the performance.

Yes, if you manually allocate memory, you have to manually delete it.

If it's an actual array you can divide the size of the array as a whole by the size of a single element to get the number of elements:
If all you have is a pointer, you have to rely on passing around the size as a separate entity. Or you can wrap the whole thing in an object so that it has a size() method, just like the vector class.