Re: Initializing an array data member?
Quote:
Originally Posted by muse1987
As long as I can think of, using C-style arrays is cheaper than using std::vector or std::string.
Not to any significant degree, if you use them properly. I mean, sure, if you're passing a std::vector by value all over the place and duplicating it on a whim, or resizing it a lot, it can get expensive. But if you treat it just like a C-array----pass by reference or const reference, initialize a size on construction and leave it that size, etc----the extra cost is completely negligible, and your code becomes far cleaner. Similar logic applies to std::string.
Re: Initializing an array data member?
Quote:
Originally Posted by muse1987
As long as I can think of, using C-style arrays is cheaper than using std::vector or std::string.
Try to resize a C-style array.
Quote:
I've made a template class for static arrays
So you're just referring to static arrays? Then a std::vector has negligible difference between itself and an array if the vector isn't resized.
Code:
for( size_t i = 0; i < Length; i ++ )
Data[i] = pData[i]; // <-- introduces inefficiency
Probably faster:
Code:
std::copy(pData, pData + Length, Data);
Also your assignment operator doesn't check for self-assignment.
Regards,
Paul McKenzie
Re: Initializing an array data member?
Quote:
Originally Posted by Paul McKenzie
Try to resize a C-style array.
When I say C-style array is cheaper than std::vector, it implies the case where we can choose either one. How can we compare their costs otherwise?
Quote:
Originally Posted by Paul McKenzie
So you're just referring to static arrays? Then a std::vector has negligible difference between itself and an array if the vector isn't resized.
Are you sure? In my understanding, std::vector allocates its buffer on the heap. And heap is far expensive than stack. The following code takes 225 nanoseconds on my machine (mine is not too old, with 2GHz core frequency)
Code:
std::vector<int> V(10);
But obviously C-style array like "int V[10];" have almost no overhead, as all it needs is just modifying the stack pointer.
Quote:
Originally Posted by Paul McKenzie
Probably faster:
Code:
std::copy(pData, pData + Length, Data);
Isn't it essentially the same? I used to write my own code for trivial cases because overwhelmingly complicated STL code often fools my compiler optimization. In the case static_array<int,10>, the implementation that uses std::copy() takes 32.8 nanoseconds while the one with for( ;; ) takes 16 nanoseconds on my machine.
And furthermore, what I meant by 'inefficiency' was not that (I wrote this in the previous post but writing again). Suppose elements of the array are heavy objects, e.g. they acquire some system resources when they're constructed. In that case my first version constructs all elements, which involves resource acquisition, and then copy the objects. The second version I've posted fixed that issue by copy-constructing elements directly. (well, this idea was borrowed from STL implementation)
Quote:
Originally Posted by Paul McKenzie
Also your assignment operator doesn't check for self-assignment.
You specified the right point. Thanks. Maybe it has worked fine until now because each elements' assignment operator checks self-assignment. But I do appreciate your advice as it makes it faster in the self-assignment case.
Re: Initializing an array data member?
Quote:
Originally Posted by Lindley
Not to any significant degree, if you use them properly. I mean, sure, if you're passing a std::vector by value all over the place and duplicating it on a whim, or resizing it a lot, it can get expensive. But if you treat it just like a C-array----pass by reference or const reference, initialize a size on construction and leave it that size, etc----the extra cost is completely negligible, and your code becomes far cleaner. Similar logic applies to std::string.
Please look at my post above. It would tell you why we should use C-style arrays in trivial cases.
Re: Initializing an array data member?
You're correct that stack allocations are faster than heap allocations. But std::vector is certainly no worse than using new[]. So if you know the size at compile time, go nuts with the stack; if not, use a std::vector.
I recently encountered a class called UnicodeString, part of the ICU project. Not only does it have copy-on-write semantics, but it *also* contains a small internal buffer, which is used until the string it contains grows too large, at which point it moves the data to the heap. It would be nice if the STL had containers with such mechanisms.
Re: Initializing an array data member?
Quote:
Originally Posted by muse1987
When I say C-style array is cheaper than std::vector, it implies the case where we can choose either one. How can we compare their costs otherwise?
Invariably, whenever the discussion of which is faster, it always comes down to the resizing that eventually invalidates arrays being faster than vector.
Of course using arrays in a trivial way are faster. Arrays are basic 'C' types. But how many times do you see people trying to beat vectors using pointers and new[]/delete[], believing what they're doing is faster than a vector?
Quote:
Are you sure? In my understanding, std::vector allocates its buffer on the heap. And heap is far expensive than stack. The following code takes 225 nanoseconds on my machine (mine is not too old, with 2GHz core frequency)
Real code is more than just initialization.
Quote:
Isn't it essentially the same?
The same thing in terms of final results -- it isn't necessarily the same thing in terms of how those results are achieved. For example, you post-increment the loop counter -- I'm sure that a good implementation would pre-increment the loop counter. Also, a good implementation would specialize std::copy to do a memcpy() if POD types are used.
Quote:
I used to write my own code for trivial cases because overwhelmingly complicated STL code often fools my compiler optimization.
Get another compiler. I've not tested std::copy, but I know STL algorithms such as std::transform(), std::for_each(), etc. are invariably faster than hand-written loops.
Also, what is "overwhelmingly complicated" to you may be trivial to someone else. So "overlywhelmingly complicated" is highly subjective.
Quote:
Suppose elements of the array are heavy objects,
Then a C++ programmer would know to use a vector of some pointer or smart pointer type, not a vector of objects. Maybe they would use the vector of objects to get something working, but then switch to the (smart) pointer vector when finally optimizing the code.
In other words, there is no sense in timing things that no smart programmer would really ever do. If you were to time, say an array of smart pointers against a vector of smart pointers, then that is different.
Regards,
Paul McKenzie
Re: Initializing an array data member?
Quote:
Originally Posted by Lindley
It would be nice if the STL had containers with such mechanisms.
The Visual C++ implementation of std::string uses "short-string" optimizations as you described.
However, I believe that copy-on-write is going to be outlawed for std::string implementations, since std::string must be implemented internally as an array of char type (an upcoming addition to the ANSI standard).
Regards,
Paul McKenzie
Re: Initializing an array data member?
Quote:
Originally Posted by Paul McKenzie
The Visual C++ implementation of std::string uses "short-string" optimizations as you described.
However, I believe that copy-on-write is going to be outlawed for std::string implementations, since std::string must be implemented internally as an array of char type (an upcoming addition to the ANSI standard).
Regards,
Paul McKenzie
Well, copy-on-write could still be used; they'd just have to make sure that the non-const version of .c_str() and the non-const version of operator[] triggered the copy, and any other non-const means of accessing the underlying array. You'd still get major savings that way for const strings.
Of course, it may not be worth it; const strings could be passed by reference as easily as by value, and the C++0x concept of an R-value reference handles most of the other potential savings areas.
Re: Initializing an array data member?
Here we go again and again and again. Some people just can't get enough of bashing std::vector and trying to rewrite the C++ std template library in their spare time. I guess some people have a lot of time on their hands. While it's true that vector default initializes the members most people would manually initialize a c style array anyhow. So unless you are dealing with an enormous buffer that doesn't need to be default initialized I can't see the advantage of rejecting the std::vector. It'd be nice if in a future release of the C++ std the vector constructor is redesigned to not initialize the memory unless the user specifies a value in the constructor.
Re: Initializing an array data member?
Quote:
Originally Posted by muse1987
Please look at my post above. It would tell you why we should use C-style arrays in trivial cases.
Sorry, I do not see any post that tells me this. I don't really care if heap memory is slower than stack memory and I am not sure that I buy your statement that there is a significant difference. You didn't provide any numbers for the use of stack memory. You said that it takes 225 ns for your heap example. How much faster is stack? Even if it is slightly faster why does that mean I have to use a c array instead of a vector? There are cases where a vector might be slower but is still a better design choice in the long run (code readability and maintainability, better OO design for instance). Not all programs are perfectly optimized for speed nor do they need to be.
Re: Initializing an array data member?
Quote:
Originally Posted by kempofighter
I don't really care if heap memory is slower than stack memory and I am not sure that I buy your statement that there is a significant difference.
Well now, let's not go dismissing the benefits of avoiding heap allocations altogether. That way lies terrible code.
Getting memory from the heap involves some fairly complex algorithms to choose the right bit to give you. Getting memory on the stack requires one addition instruction. *If* you're absolutely certain that you only need 10 elements in an array, and out-of-bounds accesses aren't even a remote possibility, go ahead and stack-construct it by all means.
std::vector is great. I use it all the time. But there is no one correct solution to every situation.
Re: Initializing an array data member?
From a newbie's point of view,
I prefer vector over array because;
1. My first book devoted far more pages on vectors than it did on arrays, so I'm used to vector
2. I fear that I might have shortcomings, but realized that vector does pretty much anything array does
3. Vector offers simplicities enticing beginners and allowing us to have good time programming.
Re: Initializing an array data member?
Quote:
Originally Posted by Paul McKenzie
Invariably, whenever the discussion of which is faster, it always comes down to the resizing that eventually invalidates arrays being faster than vector.
Of course using arrays in a trivial way are faster. Arrays are basic 'C' types. But how many times do you see people trying to beat vectors using pointers and new[]/delete[], believing what they're doing is faster than a vector?
As I said before, I'm referring the case where we don't need to resize the array. From the first I never told new[]/delete[] is better than std::vector.
And you should have realized what I'm telling when you saw my class : it isn't designed for dynamic arrays. It just encapsulates static C-style array to help array-copy. There's absolutely no point to mention new[]/delete[] since I didn't talk about it.
Quote:
Real code is more than just initialization.
And much more initializations.
Quote:
The same thing in terms of final results -- it isn't necessarily the same thing in terms of how those results are achieved. For example, you post-increment the loop counter -- I'm sure that a good implementation would pre-increment the loop counter. Also, a good implementation would specialize std::copy to do a memcpy() if POD types are used.Get another compiler.
std::copy is already implemented through memcpy(). And MSVC2005 doesn't actually generate function call but inlines it. So, what's happening in the for( ;; ) loop? The compiler unrolls the loop since it knows how much time it executes in the compile time. An ideal C++ compiler would even unroll memcpy() if size is known in compile time. C++ compilers aren't as perfect as one might expect.
Pre-increment isn't better than post-increment for POD types. And I would mention that the code I posted is more than 6 years old.
Quote:
I've not tested std::copy, but I know STL algorithms such as std::transform(), std::for_each(), etc. are invariably faster than hand-written loops.
Depending on the programmer's skills. Nothing can be always good. If hand-written code is slower, that means the programmer isn't very skilled. I'm sure almost every algorithm can be optimized for special cases. When a skilled programmer implements it, it will be significantly faster than STL's general algorithms.
However most of time we don't have to worry about optimization. Most performance improvement can be achieved by optimizing only 10% or even less amount of whole code. So they would save a lot of time by using STL.
Quote:
Also, what is "overwhelmingly complicated" to you may be trivial to someone else. So "overlywhelmingly complicated" is highly subjective.
"overwhelmingly complicated" means it's complicated for compiler, not for me.
Quote:
Then a C++ programmer would know to use a vector of some pointer or smart pointer type, not a vector of objects. Maybe they would use the vector of objects to get something working, but then switch to the (smart) pointer vector when finally optimizing the code.
In other words, there is no sense in timing things that no smart programmer would really ever do. If you were to time, say an array of smart pointers against a vector of smart pointers, then that is different.
Are you talking that the second implementation is worse than the first one? No.
At least the second implementation saves the programmer from having to use smart pointers. You don't have to waste space&time just to say "this isn't much useful", if you don't find anything bad.
And I forgot to mention one thing, the storage overhead. Suppose we need to int array of size 4, which is 16bytes. What will happen if we make it std::vector? Let's look at just Windows. The vector itself consumes at least 8 bytes (in MSVC2005, it's even 16 bytes but let's just forget about it), and since the buffer is allocated on the heap memory, another 16 bytes is consumed for block header. So it uses 40 bytes in total. It's absolutely abuse. So I'd recommend using built-in arrays if they can do the job.
Re: Initializing an array data member?
Quote:
I've made a template class for static arrays which is essentially the same with C-style arrays except they are more convenient.
Incidentally, from the Boost libraries work there is now std::tr1::array.
Re: Initializing an array data member?
Quote:
Originally Posted by laserlight
Incidentally, from the Boost libraries work there is now std::tr1::array.
Yes, and I agree that it's a nice one. Just it would be a little better if it can copy-construct the elements directly, as std::vector does.
