If you don’t mind changing one line of code, you might be able to get even more speed by using V.push_back(std::move(x)).
This speedup would be in addition to the gains that you’d expect to get just by using a move-enabled std::vector, which allows the vector to avoid internal copies as it grows.
Willsays:
Thank you for your clear write-up of the benefits of C++11. I haven’t used C++ for a few years, but I remember spending tons of time typing in boilerplate container initialization code. The new syntax looks much clearer.
I’m wondering if you ran into any pitfalls when using the new standard? Or did everything work about as you expected?
An obvious (!!!) drawback of C++11 is that support is still incomplete in most compilers. This makes portability a major concern for the time being. However, I am confident that important compilers will catch with most of C++11. Developers will expect it.
One problem that I have touched upon is the initialization of data structures within the class declaration. I am not sure whether it is supposed to work within C++11, or not… but it did not work for me with GCC 4.7.
Also, the constexpr requirements are very strict. In theory, you’d want all math. functions to be constexpr but in practice, I don’t think it will get as much use as it should. It is a shame since it ought to help compilers with optimization…
There are more nice things that I have left out too…
grepsays:
isn’t constexpr just equivalent of a macro definition then ? I do appreciate the typesafety provided by the compiler in the constexpr case but it doesn’t seem to be all that revolutionary a change.
I’d love to start using C++11, but compatibility with legacy compilers is rather important to the projects I’m working on. One thing is to upgrade the compiler yourself which is simple and another is to make all the users to upgrade. Don’t you have the same problem?
That’s a general remark that is true for all new programming language versions. Sometimes it pays to switch to the latest version early, sometimes it is best to best as late as possible. My own opinion is that C++11 is something you want to adopt earlier rather than later.
Vivek is at Google, this gives you are clue that Google is likely adopting C++11. Moreover, we have clues that Facebook is adopting C++11 as well.
There’s always the question of C vs C++. I like C++, and love C++11, but when it comes to efficiency, nothing beats good ol’ C. By this, I don’t mean that C++ must be thrown away, but that efficient data structures can be written only in a C-like fashion. The STL just doesn’t come close.
As an example, check out the test code I wrote here. The results are surprising, to say the least. The C implementation takes around 0.0025 (wall clock time) seconds on average, while the C++ implementation takes 0.019 seconds (wall clock) on an average (default optimisations).
So, while C++11 has a good STL support, it does not even come close to what custom data structures can do. Further, custom data structures can be adapted to the problem at hand, and optimised even further.
However, my test example is relatively simple, and hardly relies on any optimisations at C level. Yet, the STL version is almost 8x slower.
As Daniel correctly pointed out, your comparison is not fair. Even Daniel’s version does unnecessary initialization of the vector which can be easily avoided, e.g. using boost::counting_iterator . See https://github.com/vitaut/CXX11-STL-Tests/blob/master/vector-vs-array.cpp for example. In this case C++ version is marginally faster.
So STL is not slower, you just need to learn how to use it efficiently, but this is true for any library.
@Daniel:
Your version gives the following output:
The C like implementation took 0.000224585 seconds
The C++ implementation took 0.00241526 seconds
The fair C++ implementation took 0.00284987 seconds
So, resize is actually slower than reserve (at least on my computer). This I’d attribute to the fact that resize calls the constructor for the underlying element type, whereas reserve does not do so.
I’m curious to your opinion on why vector::reserve may not be a fair comparison.
@Victor:
I’m not sure what you mean by “unnecessary initialisation”. If you refer to the fact that a new vector is initialised in every iteration of the outer loop, it’s because I wish to measure time taken to initialise a vector, and insert a bunch of elements in it.
Your code seems to rely on the fact that vector[i] = i. I just used this assignment for lack of a better option; using the counting_iterator approach will not work for vectors that store some useful data.
Or maybe I’ve completely missed your point.
By unnecessary initialization I meant that v.resize(1000000) in Daniel’s version did extra zero initialization. I just demonstrated that it is possible to achieve the same performance as your “C” version by initializing the vector in place and it is not limited to the case vector[i] = i, you can write arbitrarily complex initializers in a similar fashion.
However, if you have more complex initialization, bypassing zero initialization will likely to become unnecessary because it will only amount to a small fraction of the total computation time.
@Daniel, I won’t say that I’m comparing a static array with a dynamic one. The reserve command essentially reserves the size of the container to contain as many elements, so I don’t think that memory copies happen at any time. And I said “C like data structures” not C [:)]. I don’t like C. I’m a C++ guy.
My comparison was directed mainly towards a code that I’m writing ATM. I wrote the code very quickly in C++11 using STL. The comparison of C like data structures (which, for me include raw pointers, memory management, etc.) with the STL was mainly to convince myself that a performance improvement could be obtained by using C like data structures. Initially, I was sceptical; now I think that C like data management may be a faster (performance wise) way to go.
According to Linus Torvalds in his Aalto talk; he likes C because he can figure out exactly what the assembly will look like, something that’s not possible with C++. He also mentioned optimising path name lookups to work in parallel, with no contention, and optimised down to where he would worry about single cache misses.
I’d safely bet that STL (or any library for that matter) cannot give as much control. 🙂
The only reason to use push_back is when you have a dynamic array.
In your case, there is no good reason to use a dynamic array approach, so you should not use push_back.
Now, if you implement it with brackets, you will see that the STL version is just 2x slower. This seems like a lot, but it can be entirely explained by the extra initialization that STL does.
This is somewhat unfortunate, but if you care about performance, you should probably avoid allocating and unallocated memory anyhow, right?
This is quite straightforward. Any C++ user can see the benefits immediately. Thanks for sharing.
Thanks for the information. How can I determine whether my compiler supports C++11?
@Viru
Right now GCC 4.7 and better as well as LLVM (clang) 3.2 have good support for C++11.
Check the documentation of whatever compiler you are using but, obviously, you cannot expect good support for compilers released before 2012.
If you don’t mind changing one line of code, you might be able to get even more speed by using V.push_back(std::move(x)).
This speedup would be in addition to the gains that you’d expect to get just by using a move-enabled std::vector, which allows the vector to avoid internal copies as it grows.
Thank you for your clear write-up of the benefits of C++11. I haven’t used C++ for a few years, but I remember spending tons of time typing in boilerplate container initialization code. The new syntax looks much clearer.
I’m wondering if you ran into any pitfalls when using the new standard? Or did everything work about as you expected?
@Will
An obvious (!!!) drawback of C++11 is that support is still incomplete in most compilers. This makes portability a major concern for the time being. However, I am confident that important compilers will catch with most of C++11. Developers will expect it.
One problem that I have touched upon is the initialization of data structures within the class declaration. I am not sure whether it is supposed to work within C++11, or not… but it did not work for me with GCC 4.7.
Also, the constexpr requirements are very strict. In theory, you’d want all math. functions to be constexpr but in practice, I don’t think it will get as much use as it should. It is a shame since it ought to help compilers with optimization…
There are more nice things that I have left out too…
isn’t constexpr just equivalent of a macro definition then ? I do appreciate the typesafety provided by the compiler in the constexpr case but it doesn’t seem to be all that revolutionary a change.
@grep
isn’t constexpr just equivalent of a macro definition then ?
No, it is not.
Functions from cmath such as acosh are constexpr so that acosh(2) is a compiler-time constant.
I guess you could find a way to write acosh using a macro, but are you going to rewrite all the math. functions as macros? Seems crazy.
I’d love to start using C++11, but compatibility with legacy compilers is rather important to the projects I’m working on. One thing is to upgrade the compiler yourself which is simple and another is to make all the users to upgrade. Don’t you have the same problem?
@Victor
That’s a general remark that is true for all new programming language versions. Sometimes it pays to switch to the latest version early, sometimes it is best to best as late as possible. My own opinion is that C++11 is something you want to adopt earlier rather than later.
Vivek is at Google, this gives you are clue that Google is likely adopting C++11. Moreover, we have clues that Facebook is adopting C++11 as well.
Thanks Daniel. Gives me a reason to go back to c++.
Marcel
There’s always the question of C vs C++. I like C++, and love C++11, but when it comes to efficiency, nothing beats good ol’ C. By this, I don’t mean that C++ must be thrown away, but that efficient data structures can be written only in a C-like fashion. The STL just doesn’t come close.
As an example, check out the test code I wrote here. The results are surprising, to say the least. The C implementation takes around 0.0025 (wall clock time) seconds on average, while the C++ implementation takes 0.019 seconds (wall clock) on an average (default optimisations).
So, while C++11 has a good STL support, it does not even come close to what custom data structures can do. Further, custom data structures can be adapted to the problem at hand, and optimised even further.
However, my test example is relatively simple, and hardly relies on any optimisations at C level. Yet, the STL version is almost 8x slower.
@Skand
Is your comparison fair?
@Skand
As Daniel correctly pointed out, your comparison is not fair. Even Daniel’s version does unnecessary initialization of the vector which can be easily avoided, e.g. using boost::counting_iterator . See https://github.com/vitaut/CXX11-STL-Tests/blob/master/vector-vs-array.cpp for example. In this case C++ version is marginally faster.
So STL is not slower, you just need to learn how to use it efficiently, but this is true for any library.
@Daniel:
Your version gives the following output:
The C like implementation took 0.000224585 seconds
The C++ implementation took 0.00241526 seconds
The fair C++ implementation took 0.00284987 seconds
So, resize is actually slower than reserve (at least on my computer). This I’d attribute to the fact that resize calls the constructor for the underlying element type, whereas reserve does not do so.
I’m curious to your opinion on why vector::reserve may not be a fair comparison.
@Victor:
I’m not sure what you mean by “unnecessary initialisation”. If you refer to the fact that a new vector is initialised in every iteration of the outer loop, it’s because I wish to measure time taken to initialise a vector, and insert a bunch of elements in it.
Your code seems to rely on the fact that vector[i] = i. I just used this assignment for lack of a better option; using the counting_iterator approach will not work for vectors that store some useful data.
Or maybe I’ve completely missed your point.
@Skand
But my concern is that you are comparing a static array with a dynamic one. Is that fair?
I also object that you don’t really compare C with C++. Both solutions are C++. No?
@Skand:
By unnecessary initialization I meant that v.resize(1000000) in Daniel’s version did extra zero initialization. I just demonstrated that it is possible to achieve the same performance as your “C” version by initializing the vector in place and it is not limited to the case vector[i] = i, you can write arbitrarily complex initializers in a similar fashion.
However, if you have more complex initialization, bypassing zero initialization will likely to become unnecessary because it will only amount to a small fraction of the total computation time.
@Daniel, I won’t say that I’m comparing a static array with a dynamic one. The reserve command essentially reserves the size of the container to contain as many elements, so I don’t think that memory copies happen at any time. And I said “C like data structures” not C [:)]. I don’t like C. I’m a C++ guy.
My comparison was directed mainly towards a code that I’m writing ATM. I wrote the code very quickly in C++11 using STL. The comparison of C like data structures (which, for me include raw pointers, memory management, etc.) with the STL was mainly to convince myself that a performance improvement could be obtained by using C like data structures. Initially, I was sceptical; now I think that C like data management may be a faster (performance wise) way to go.
According to Linus Torvalds in his Aalto talk; he likes C because he can figure out exactly what the assembly will look like, something that’s not possible with C++. He also mentioned optimising path name lookups to work in parallel, with no contention, and optimised down to where he would worry about single cache misses.
I’d safely bet that STL (or any library for that matter) cannot give as much control. 🙂
@Skand
Your example is unfair because you are using push_back.
Please see my post Do not waste time with STL vectors where I explain that push_back can be expensive.
The only reason to use push_back is when you have a dynamic array.
In your case, there is no good reason to use a dynamic array approach, so you should not use push_back.
Now, if you implement it with brackets, you will see that the STL version is just 2x slower. This seems like a lot, but it can be entirely explained by the extra initialization that STL does.
This is somewhat unfortunate, but if you care about performance, you should probably avoid allocating and unallocated memory anyhow, right?
See my test here:
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2012/11/26/vector-vs-array.cpp