array vs vector

Quote:

---

Originally Posted by Paul McKenzie

The question hasn't been asked yet.

Did you time a release (optimized) build, or a debug build? If you timed a debug build, then this whole discussion is pointless.

Regards,

Paul McKenzie

---

I did the test on a release build. My main objective is to have an array with a member _size. It is easy to implement but if std::vector is as fast as a simple array class, I'll use it.

I've also compared how fast it was to assign values to an array and to copy it to another array:

Code:

---

int* a=new int[size];
int* b=new int[size];

for(int i=0; i<size;i++) a[i]=i;

memcpy(b,a,size*sizeof(a));

---

is still more than 20% faster than

Code:

---

std::vector<int> x;

std::vector<int> y;

x.reserve(size);
y.reserve(size);

for(int i=0; i<size;i++) x.push_back(i);

y.assign(x.begin(), x.end());

---

push_back is quite slow, but I can't do:

Code:

---

for(int i=0; i<size;i++) x.[i]=i;

---

because the iterators returned by x.begin() and x.end() are not incremented, and I can't use assign or copy....

Do you see any way to make that faster using vector?

Thanks again to everybody for your help

Ujl

Code:

---

memcpy(b,a,size*sizeof(a));

---

this is very very very wrong first of al sizeof(a) must be sizeof(int) second you do not use memcpy with new

Quote:

---

Originally Posted by dcjr84

Vectors, and especially arrays, should always be
initialized. period. Doesn't matter if its by the user or done
automatically by it's implementation. The performance impact is
negligible.

And even if it did reduce performance; I would rather
have a program that runs at 50% speed but is guaranteed to
an extremely high percentage to never make a mistake
in calculation because it might at some point use an unintialized
garbage value from an array or vector, than have one that runs
at 100% speed but the results might be incorrect at some point
because there is the possibility it might use an uninitialized element
from an array or vector.

---

Then, you should not program in C++.
There are lots of much safer languages (at the cost of a small performance overhead).

Try Ada... Or Common LISP if you need a high level of expressivity.

It is true that having determistic behaviour can be good... But there must be a way to escape that! There should be a way to create an uninitialized vector (if the type in the vector is POD)... Probably with a special constructor (thus, the default choice would be reproductibility rather than performance).

On some OS, it may seriously reduce speed, because of cache reasons, and need for physical allocation.
If a big bunch of memory is allocated and not accessed, the OS may be able to avoid the physical allocation of the memory...
Of course, it is very unlikely to affect by a great factor the overall performance of the program.
But, on the other side, during a long time, C++ had the principle of zero-overhead : Even a 3% performance penalty (compared to plain C) was inacceptable.

There is a correct solution:
Instead of writing manually, a buggy array class, simply download STLPort, and add, manually, a constructor to std::vector...
Thus, you'll benefit from the implementation quality of STLPort, with the additional feature you want.

But you can't use memcpy with non-POD data, so you immediately lose out by taking that route.

Remember Herb Sutter's wise advice: correct is better than fast.

Do not concern yourself at the design/initial coding stage with these sort of matters. In the vast majority of cases, the "inefficiency" that you're worrying about will not manifest itself, because the program will actually slow down somewhere completely unexpected.

Get the program correct first, then use a profiler to tell you where the time is going and attack those areas. Really, honestly, truly: premature optimisation is the root of many, many problems.

Quote:

---

Originally Posted by Ujl

I did the test on a release build. My main objective is to have an array with a member _size. It is easy to implement but if std::vector is as fast as a simple array class, I'll use it.

---

Boost has a fixed array class. Maybe you should check it out.

Quote:

---

I've also compared how fast it was to assign values to an array and to copy it to another array:

Code:

---

int* a=new int[size];
int* b=new int[size];

for(int i=0; i<size;i++) a[i]=i;

memcpy(b,a,size*sizeof(a));

---

---

This test assumes you are using POD types. The equivalent test in vector is this:

Code:

---

std::vector<int> x;
std::vector<int> y;

x.reserve(size);
y.reserve(size);

for(int i=0; i<size;i++)
    x.push_back(i);
y = x;
// or if you want to use memcpy
// y.resize(size);
// memcpy(&y[0], &x[0], sizeof(int) * size);

---

Except for initialization, a vector can really be treated as an array of T, just as my code above demonstrates.

Quote:

---

Do you see any way to make that faster using vector?

---

In general, the address of the first element of a vector is your array. Then you do with it what you want, just like arrays.

Also, the loop to initialize the vector can be replaced by the std::generate_n() algorithm, but I don't know if this will make the code faster or not.

Regards,

Paul McKenzie

(Sorry, reply above was to Ujl, post #47)

Quote:

---

Originally Posted by Mitsukai

[code]second you do not use memcpy with new

---

Only if the objects allocated with new are non-POD types should you not use memcpy().

With POD types, memcpy() is safe.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

Only if the objects allocated with new are non-POD types should you not use memcpy().

With POD types, memcpy() is safe.

Regards,

Paul McKenzie

---

i know but with an array object you do not know if it is a POD or not.

Quote:

---

Originally Posted by Graham

But, if you use vector::reserve, then it does create an uninitialised array. It's just that you can't randomly access the values until you put something in it, and then only the values that you've added.

---

That's the problem.
Assume you have to connect your program with an old unsafe C library and you have to call a function which "return" a string, in that way:

Code:

---

void OldUglyCFunction(char* UserAllocatedBuffer); /* the buffer must be LARGE enough... and there is no way to know how many bytes must be allocated */

---

The C++ programmer passes a big amount of memory (16KB for example), because he wants to avoid buffer overflows.

Here, using an initialized std::vector<char>(16384) may reduce performances by a HUGE factor!
Using a static buffer for the first copy, is not an option in multithreaded environments... And, using TLS would consume much memory if there are a lot of threads, and be overcomplicated...

Quote:

---

Originally Posted by dcjr84

Again, this is negligible. Hundreds if not thousands of cpu cycles are
probably wasted every minute of every day by your computer for a
multitude of reasons: bad CPU scheduler decisions, etc, etc. I highly
doubt that using a vector is going to decrease your computers lifetime
by so much that it would even be noticeable.

---

It may be negligible... But when it is not, there should be a not-too-ugly mean to avoid this overhead...

Quote:

---

And even if it did reduce performance; I would rather
have a program that runs at 50% speed but is guaranteed to
an extremely high percentage to never make a mistake
in calculation because it might at some point use an unintialized
garbage value from an array or vector, than have one that runs
at 100% speed but the results might be incorrect at some point
because there is the possibility it might use an uninitialized element
from an array or vector.

---

I think Mitsukai's point here is that zero or default initialised elements may not necessarily be any better than garbage values from uninitialised elements when one does such calculations. For the calculations to be correct, the input values have to correct, and so one must either initialise or assign (directly or indirectly) the correct values to the elements used in calculation.

However, I think that std::vector is flexible enough such that Mitsukai's worries are unfounded.

Quote:

---

Do you see any way to make that faster using vector?

---

Does the performance bottleneck in your code lie in this part of the code?

Quote:

---

Then, you should not program in C++.
There are lots of much safer languages (at the cost of a small performance overhead).

---

In the end, you guys are going to do whatever you feel is right and so
will I. For me, that means always initializing an array to some known
value to promote determinism. Unless, for some extreme reason which I
highly doubt would arise, I had to write a program which absolutely
could not spare the extra CPU cycles to initialize what I needed.

Cheers :)
By the way, no bad blood here. I always enjoy a good
constructive criticism conversation :)

Too much, too fast!

I guess I should have made this more clear in my code:
//use pointers instead of classes when using malloc.
I put that there because I knew that my class could not handle aArr<class1> arr;
but can handle aArr<class1*> arr;
That's just something you have to remember when using it.

Keep in mind that the code is not finished yet and I should have mentioned that when I posted it.

Quote:

---

Originally Posted by Paul McKenzie

Only if the objects allocated with new are non-POD types should you not use memcpy().

With POD types, memcpy() is safe.

---

But it costs later when POD gets substituted with non-POD. IMHO it's simplier to write code which handles both cases.

Quote:

---

Originally Posted by RoboTact

But it costs later when POD gets substituted with non-POD. IMHO it's simplier to write code which handles both cases.

---

Right, you should always assume that when you code these things to assume that you are working with both non-POD and POD types.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by dcjr84

In the end, you guys are going to do whatever you feel is right and so
will I. For me, that means always initializing an array to some known
value to promote determinism. Unless, for some extreme reason which I
highly doubt would arise, I had to write a program which absolutely
could not spare the extra CPU cycles to initialize what I needed.

Cheers :)
By the way, no bad blood here. I always enjoy a good
constructive criticism conversation :)

---

The sentence "Then, you should not program in C++." was not to be taken too litterally...
You know, nowadays determinism can really be a Good Thing(TM).
I meant that there are really very good determinist languages, having performances very close to C++ (unlike in 1985).
OCaml is probably the language having the best performances after C and C++.

So, OCaml is better than C++ except for:

• A few percents of performances...
• The (perhaps) unreachable level of expressivity and power of C++...
• A few other Good Things of C++ which makes it suitable for system programmation (such as an efficient and natural to use RAII).
• Really usable for embedded systems

But, if the point is stability and determinism... C++ is not the ideal tool.
C, C++ and Fortran are not good for that.

IMHO, it is a Good Idea to improve C++ determinism... But, if there is any performance tradeoff, there must be an explicit way to avoid the penalty, at the cost of safety.
For instance, it could be a good idea to default-initialize *all* variables, provided that there is a mean to create uninitialized data:

For instance:

Code:

---

class C {
public:
int a; /* a would be initialized to zero, even if constructors doesn't initialize it explicitly */

C():a(?) /* except when a special "constructor" would be invoked */
{
}

};

---

C++ must be able to replace C in any and each way... Otherwise, we would see programs containing C modules (for critical code) and C++ modules (for higher level code).

Until now, I think that C++ can fully replace old C.