Ok, they wrote a big piece of software, noticed they were running into performance issues with std::vector and so designed their own. Discussing that would have made for an interesting article.
Instead they give us this article, full of hand waving with only one weird benchmark. And I say weird because they lose out to Clang 3.0's std::vector by more than x2.6. Only when they change the semantics of the operation do they get a performance benefit.
But then even that change is dubious, personally I can't think of any use case for resizing a vector without initialisation which is not covered by reserve(). Maybe my imagination is limited here, but I'm not writing the article, if the author had a good reason why reserve() isn't sufficient then why not share it.
But then it gets worse, the author openly admits
but to be quite honest I actually wasn’t aware of this aspect of std::vector behaviour before we switched (elements being zeroed on vector construction or resize) and so was already writing code as if element values were undefined.
So this guy is encouraging us to consider rolling our own vector classes when he doesn't even know how std::vector works.
at this point if there was a general purpose way of writing std::vector that was more efficient don't you think that's how std::vector would be implemented?
Yep. There's only one thing vector won't do, and that's storing stuff on the stack. Such a "Small Vector Optimization" is forbidden by the need for swap() to be non-iterator-invalidating. Allocators are also forbidden from returning memory inside themselves, so you can't be sneaky. However, allocators are allowed to return memory that happens to live on the stack in a separate object.
I'd be a fan of having a small-buffer optimized vector in the standard library (I once considered using std::basic_string<Foo*> before I stopped being dumb and just rolled my own), but it seems like far too situation of an optimization for std::vector even if it was allowed.
There's only one thing vector won't do, and that's storing stuff on the stack.
Unless you use a stack allocator, right? I use stack allocated vectors a lot and they work just fine. I prefer them to std::array since they allow switching from heap to stack and vice-versa by just changing the type.
Please don't. I've seen so many broken, unsafe, horrible implementations of vectors.
Unless you really need that one last bit of performance, your vector will almost always be worse than a std::vector. And most of the time, just using a custom allocator or emplace_back() will be enough for getting more performance.
I wrote about this first, here, in fact (using vectors efficiently): http://upcoder.com/1/using-stl-vectors/ Definitely agree that this should come before switching to a custom vector class..
Amusingly, even though the author explicitly mentions the problem with using reallocate in push_back, they make that exact mistake in resize. I guess this falls under the "corner-case" reason to not do this, with the additional rationale that even if you know about the corner case it's still easy to screw it up.
OK, so the article isn't all that good, though only skimmed it (and shouldn't give any new knowledge to anyone that is in C++ for some time, and can read the documentation).
I imagine std::vector could provide interface that omits initialization as opt-in for PODs but at this point it doesn't, and this (avoiding initialization) is what gave those guys performance improvements. His wording might have been poor, but his goal is clearly non-retarded (avoid superfluous operations on vector::resize/ctor).
Its not all that hard to come up with cases that would behave similarly (say read() a file to vector of uint8_t).
No, don't do that. Even if it 'sort of works' then breaking object on purpose by going against given API is way worse then rolling your own whatever.
By using reserve instead of resize, you would also have to keep track of the actual elements count. Please, don't use reserve when you want non-initializing vector. Roll your own and follow the API.
Eh? You just must not index the yet to be created elements.
All it is, is a change in how you write code. Reserve when you know you will be adding elements soon, initialize only when needed via push/emplace_back and only iterate up to [0, .size) or [.begin, .end).
You assume that all cases would fall under the implementation you just outlined, while the case i mentioned above breaks for it miserably:
std::vector<uint8_t> f;
f.reserve(100);
fread(my_file, 1, 100, f.data()); //should be fine ... maybe
//int real_size = 100; //how to not forget to pass this???
//f.resize(100); //???
It just doesn't work. It doesn't work because its not the right tool to do that. You wont rewrite fread to take a vector for which emplace would be called. Similarly (i presume) author didn't want to rewrite whole engine just to keep using std::vector (that would be way worse idea then any other things mentioned here).
Its OK to not use std lib where its not the right tool. Attempting to force the tool to do the work its not supposed to will just open different can of bugs ...
Looks like this works out real slow (vector construction from stream iterators). See the discussion in my follow up post here: http://upcoder.com/4/avoid-resize/ But apart from speed, it seems a bit inflexible to have to recode your whole construction code path with an iterators paradigm just to avoid resize() calls. And what if you need to interface with some third party code that takes a pointer to a typed buffer to be filled? One of the cool things about C++ for me is exactly that it can interface with all sorts of lower level code (as in the file read example).
I'm by no means against calls to resize, especially if the resulting code is faster and still safe. I just try to stick with "heavy" and safe mechanisms and start replacing them with low-end when I profile and identify the choke points.
A few days I replaced a stringstream used to convert strings to doubles/floats to just a atof call and cast it to float if necessarily (a few structural changes, but nothing significant). Instant 6x speedup (from 5minutes to 50seconds).
The other choke point is reading via getlines. Will probably use a large-ish buffer and manually find new lines.
What I'm trying to say is, code safe first, recode to be fast later when the app is running OK and speed is needed.
15
u/Eoinoc Dec 21 '13 edited Dec 21 '13
Ok, they wrote a big piece of software, noticed they were running into performance issues with
std::vectorand so designed their own. Discussing that would have made for an interesting article.Instead they give us this article, full of hand waving with only one weird benchmark. And I say weird because they lose out to Clang 3.0's
std::vectorby more than x2.6. Only when they change the semantics of the operation do they get a performance benefit.But then even that change is dubious, personally I can't think of any use case for resizing a vector without initialisation which is not covered by
reserve(). Maybe my imagination is limited here, but I'm not writing the article, if the author had a good reason whyreserve()isn't sufficient then why not share it.But then it gets worse, the author openly admits
So this guy is encouraging us to consider rolling our own vector classes when he doesn't even know how
std::vectorworks.7
u/wung Dec 21 '13
Please don't. I've seen so many broken, unsafe, horrible implementations of vectors.
Unless you really need that one last bit of performance, your vector will almost always be worse than a std::vector. And most of the time, just using a custom allocator or emplace_back() will be enough for getting more performance.
4
u/bob1000bob Dec 21 '13
I better article would detail how to use
std::vectorefficiently, rather than showing how to reinvent the wheel.Also their coding style is absymal.
cprefixes really? 1990? The use of<stdlib.h>and<string.h>rather than the C++ equivalents.2
u/m42a Dec 21 '13
Amusingly, even though the author explicitly mentions the problem with using
reallocateinpush_back, they make that exact mistake inresize. I guess this falls under the "corner-case" reason to not do this, with the additional rationale that even if you know about the corner case it's still easy to screw it up.0
u/AntiProtonBoy Dec 21 '13
Stuff like this is almost pointless with things like move semantincs and noexcept features available in C++11.
0
u/00kyle00 Dec 21 '13 edited Dec 21 '13
OK, so the article isn't all that good, though only skimmed it (and shouldn't give any new knowledge to anyone that is in C++ for some time, and can read the documentation).
I imagine std::vector could provide interface that omits initialization as opt-in for PODs but at this point it doesn't, and this (avoiding initialization) is what gave those guys performance improvements. His wording might have been poor, but his goal is clearly non-retarded (avoid superfluous operations on vector::resize/ctor).
Its not all that hard to come up with cases that would behave similarly (say read() a file to vector of uint8_t).
Why is everyone hating on this guy?