7

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?

jasonline
  • 8,646
  • 19
  • 59
  • 80
  • 9
    "The way it's commonly implemented" is a very vague thing. Everyone implements it in his/her own way. Technically, it's commonly *not implemented* but reused. – Mehrdad Afshari Feb 12 '10 at 17:21
  • 1
    Please specify which operations you refer to, and how you determined that the standard library is faster. – Malte Clasen Feb 12 '10 at 17:24
  • @Mehrdad, Malte: Yes, I agree. But let's say for an array class, inserting an element in the middle by shifting the elements once place back to create an empty space for the new element. This implementation is much slower than a vector's push_back(). I determine it by getting the time or clock cycles. – jasonline Feb 12 '10 at 17:30
  • 2
    You are comparing inserting to an array with `vector.push_back()`? That doesn't insert, it appends. – UncleBens Feb 12 '10 at 18:52
  • @Malte-Clasen: @UncleBens: Exactly. It appears he's comparing apples and oranges. – Mike Dunlavey Feb 12 '10 at 19:52
  • @UncleBens, Malte: Oops, sorry my mistake. I mean insert() instead of push_back(). Yes, I agree push_back() is for appending. – jasonline Feb 13 '10 at 01:16

6 Answers6

10

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
  • 12,749
  • 1
  • 27
  • 35
5

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
  • 476,176
  • 80
  • 629
  • 1,111
1

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
  • 10,250
  • 2
  • 41
  • 53
  • Double the storage can actually be quite bad after you reach a megabyte or so.... – Hassan Syed Feb 12 '10 at 17:28
  • Hassan Syed: You never waste more than 50% of the allocated memory. I wouldn't call that "quite bad". – Tamas Czinege Feb 12 '10 at 17:35
  • 1
    Apparently std::vector grows by a factor of 1.5: http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865 – Manuel Feb 12 '10 at 17:35
  • 1
    @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 Feb 12 '10 at 17:55
  • @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 Feb 12 '10 at 20:04
  • @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 Feb 12 '10 at 20:20
  • @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. Feb 13 '10 at 14:19
  • @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 Feb 13 '10 at 14:29
1

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
  • 33,368
  • 30
  • 112
  • 143
  • 1
    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 Feb 12 '10 at 19:59
  • -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... –  Feb 12 '10 at 20:12
1

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
  • 24,948
  • 7
  • 64
  • 80
0

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
  • 16,980
  • 13
  • 75
  • 117