If one implements an array class the way it is commonly implemented, its performance is slower compared to its STL equivalent like a vector. So what makes STL containers/algorithms fast?
+1
A:
The standard library uses good algorithms, like in the case of an array (std::vector) it usually doubles the storage every time you run out of space, while a naïve implementation might increment storage by one element every time. Because increasing the amount of storage is very slow (all existing data needs to be copied from the old allocation to the new allocation), this can make a huge difference.
Similarly, all the other algorithms are implemented in rather optimal ways. The standard library usually doesn't use any kind of loop unrolling or other such optimizations on source code level. It is just regular good and simple code (with horrible variable names and a lot of templates) that the compiler then optimizes.
What I said is not specified by the C++ standard, but is what the common practice in existing implementations seems to be.
Tronic
2010-02-12 17:24:33
Double the storage can actually be quite bad after you reach a megabyte or so....
Hassan Syed
2010-02-12 17:28:16
Hassan Syed: You never waste more than 50% of the allocated memory. I wouldn't call that "quite bad".
DrJokepu
2010-02-12 17:35:12
Apparently std::vector grows by a factor of 1.5:http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865
Manuel
2010-02-12 17:35:41
@Manuel:It's required to be a constant factor. While 2 was used in most early implementations, 1.5 (or so) is now much more common. As far as I know, Andrew Koenig was the first to point out why this should be done: http://groups.google.com/group/comp.lang.c++.moderated/msg/ba558b4924758e2e
Jerry Coffin
2010-02-12 17:55:46
@Jerry - Thanks for the link, it's good to know the reason why 1.5 is widely used (I think Python lists grow the same way). But you seem to imply that I said it wasn't a constant factor, what made you think so?
Manuel
2010-02-12 20:04:41
@Manuel:I didn't mean to say that what you wrote wasn't a constant factor. All I meant was that *any* constant factor will satisfy the requirements of the standard. You're completely right, of course, that 1.5 is a constant factor, and a widely used one at that.
Jerry Coffin
2010-02-12 20:20:10
@Jerry Coffin: always amusing to see the golden section emerge in a discussion... I wonder if the Greeks ever knew it would be used in a field invented 2 thousands of years afterwards!
Matthieu M.
2010-02-13 14:19:22
@Matthieu:It is. Some of those Greeks were arrogant enough that it wouldn't surprise me if they believed it would be used in *all* fields two thousand years later!
Jerry Coffin
2010-02-13 14:29:01
+2
A:
The algorithms in the STL have been studied for years by all levels of mathematicians and computer scientists, and they typically use the absolute most efficient algorithms, which your implementation may not be using. The common implementation is one which is probably not fastest, but is easiest to understand; the STL is probably using a more optimized implementation.
Ricket
2010-02-12 17:24:34
When all kinds of highly educated people have blessed something (IF they have) don't assume you don't need to think about it. They are quite able and qualified to be wrong.
Mike Dunlavey
2010-02-12 19:59:22
-1: I would say that's just not a true statement at all. The "algorithms" are implementation specific. Only the exposed behavior of STL algorithms/containers, etc., is specified. There are many many many implementations of the STL and they have not all been scrutinized (in fact, I'd say most haven't) to anywhere near a level you claim. Many implementations are better than the average coder can write, but a good coder can easily compete with them...
2010-02-12 20:12:12
+5
A:
Most people's array classes increase the size by a constant increment rather than a constant factor (as the standard library requires). This means inserting an element takes roughly linear time rather than the amortized constant time for the standard library.
Jerry Coffin
2010-02-12 17:27:10
@DrJokepu: You are assuming the developer HAS a computer science degree :) +1
Billy ONeal
2010-02-12 17:34:56
+9
A:
STL algorithms like for_each take function objects that can be easily inlined. C, on the other hand, uses function pointers which are much more difficult for the compiler to optimize.
This makes a big difference in some algorithms like sorting in which the comparer function must be called many times.
Wikipedia has some more information in case you are interested.
EDIT:
As for the STL's vector class, I don't think it's necessarily faster that what you could find in, say, glibc.
Manuel
2010-02-12 17:27:35
A:
the code is written in a compiler-friendly way, e.g. inlining, etc.
of course, the algorithms they use are state-of-the-art.
Yin Zhu
2010-02-12 17:30:17
A:
In addition to good, general algorithms (as others have noted), the STL is also quite efficient because of the heavy use of templates.
Template metaprograms have the nice feature that the compiler aggressively optimizes them. Some compilers are very good about this and reduce templates to the smallest, most efficient, required code for a given task. And in general, that means that functions are inlined whenever possible, and code to interact with a particular type is reduced to its simplest form. Most implementations of the STL (and most of Boost), of course, takes advantage of this to the fullest.
greyfade
2010-02-12 18:50:35