major bottleneck on VS was related to the usage of STL and push_backs, yada yada yada. So, I tried to improve it as much as I could (or I know).
Yes, that's a common experience. STL is not free
It is quite possible, as mentioned before, that a slightly different STL implementation is significantly faster in extreme cases. In fact, if compiler and STL were really the only parameters that changed, then what else could it be
How can such gross differences between different STLs occur if they do the same thing?
For example, suppose both implementations start with a
vector size of
5. One implementation reallocates in steps of
n*1.5 elements, and the other in steps of
n*2 elements. The implementation is not required to use a specific number, so the assumption that different implementations use different numbers is not unrealistic. Insignificant, one might say at first. Really?
What happens if you
push_back 10000 elements? The first implementation would run this sequence:
5;8;11;17;25;38;57;85;128;192;288;432;649;973;1460;3284;4926;7389;11084.
while the other would run that one:
5;10;20;40;80;160;320;640;1280;2560;5120;10240
Remember that a new memory block is allocated and the whole dataset has to be copied every time. Allocations are slow, and worse, copying takes linear time.
Clearly, the second implementation will be a lot faster (even though it is still very, very inefficient).
Many people make claims like "the STL is evil" for reasons like the above. However, when people say that the STL is the problem, they are wrong almost every time. Rather, they are no using it correctly. For example,
push_back is mostly harmless if you
reserve appropriately. Actually, in that case, using
vector is not any worse than using an array, only more comfortable and safer. Since you normally know the number of elements that you'll need (if not exactly, then at least approximately), that is usually not a problem.
Personally, I use STL a lot, and I bow to the people who wrote it. In almost every case, the STL is very close to or beats hand-written, optimised code, and you don't have to worry about the "hard stuff".
But one has to be aware that the functionality behind STL is no arcane magic, nor is it generally free. Especially when using containers in an inappropriate manner (or with inappropriate objects), the cost can be quite high. That's not a bug, though. That's due to design.