STL slower than C
tohava
> The STL is a compromise between ease of use, safety and
> functionality.
> It is well known that the run-time performance of the STL can be
> beaten by traditional C-style constructs. It is up to the coder to
> balance the conveniences offered by the STL against the raw
> performance of more 'primitive' coding styles.
I was wondering, can anyone give examples of specific cases which
demonstrate STL slowness in comparison to C. I'm also curious as to
which programming idioms can improve STL efficiency. Note that I feel
that we should separate between cases where the compiler supports
Rvalue-references and cases where it doesn't, since these probably
also have a major effect on container efficiency.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Nick Hounsome
> On the thread regarding C and C# performance, Rune Allnor said:
>
> > The STL is a compromise between ease of use, safety and
> > functionality.
> > It is well known that the run-time performance of the STL can be
> > beaten by traditional C-style constructs. It is up to the coder to
> > balance the conveniences offered by the STL against the raw
> > performance of more 'primitive' coding styles.
>
> I was wondering, can anyone give examples of specific cases which
> demonstrate STL slowness in comparison to C. I'm also curious as to
> which programming idioms can improve STL efficiency. Note that I feel
> that we should separate between cases where the compiler supports
> Rvalue-references and cases where it doesn't, since these probably
> also have a major effect on container efficiency.
There can be no specific examples because
a) The STL performance is STL implementation dependent.
b) The STL performance is compiler implementation dependent.
b) The C performance is developer dependent.
IMHO anyone who has to ask such question should always use the STL and
anyone who really needs to know the answer is in big trouble
since the difference is unlikely to make a significant difference to
application performance except in contrived examples.
Daniel T.
> On the thread regarding C and C# performance, Rune Allnor said:
>
> > The STL is a compromise between ease of use, safety and
> > functionality.
> > It is well known that the run-time performance of the STL can be
> > beaten by traditional C-style constructs. It is up to the coder to
> > balance the conveniences offered by the STL against the raw
> > performance of more 'primitive' coding styles.
>
> I was wondering, can anyone give examples of specific cases which
> demonstrate STL slowness in comparison to C. I'm also curious as to
> which programming idioms can improve STL efficiency. Note that I feel
> that we should separate between cases where the compiler supports
> Rvalue-references and cases where it doesn't, since these probably
> also have a major effect on container efficiency.
I got into an argument about this with a work mate of mine. He insisted
that he could write a custom linked list in C for our application that
was faster than the STL list class. I asked him what evidence he had for
this assertion and all he could come up with was that of course his code
would be faster, because of the reasons you cite above while his code
would be highly optimized for our particular situation.
A challenge ensued and the winner was the STL list class. It was a full
5% faster than anything he could come up with, even when he tried asm
optimizations.
Antonio Pérez Barrero
Best reference on the matter: Scott Meyyer's "Effective STL" (http://
www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629)
[PDF can be found in http://www.uml.org.cn/c++/pdf/EffectiveSTL.pdf]
Joe Smith
"Antonio P�rez Barrero" <apba...@gmail.com> wrote in message
news:6aee09c8-2a27-45db...@j4g2000yqe.googlegroups.com...
>> ... I'm also curious as to which programming idioms can improve STL
>> efficiency.
>
> Best reference on the matter: Scott Meyyer's "Effective STL" (http://
> www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629)
Since Scott Meyers does not provide PDF's of his books on his own site for
free, I'm reasonably confident that he does not want the content of his
books to be posted online. The PDF he offers are sold not free. Thus posting
links like the above are poor form.
Perhaps I am wrong, in which case I fully expect Scott Meyers to let me kow,
since he does read this group (or at least he posts here).
Martin B.
> On 3 Nov, 06:57, tohava <toh...@gmail.com> wrote:
>> On the thread regarding C and C# performance, Rune Allnor said:
>>
>>> The STL is a compromise between ease of use, safety and
>>> functionality.
>>> It is well known that the run-time performance of the STL can be
>>> beaten by traditional C-style constructs. It is up to the coder to
>>> balance the conveniences offered by the STL against the raw
>>> performance of more 'primitive' coding styles.
>> I was wondering, can anyone give examples of specific cases which
>
> There can be no specific examples because
> a) The STL performance is STL implementation dependent.
> b) The STL performance is compiler implementation dependent.
> b) The C performance is developer dependent.
>
I agree with all your points. However, we should add the following
points (both implementation and compiler dependent):
* If compiler optimizations (inlining) are switched off, STL performance
_may_ suffer greatly.
* If the STL implementation provides additional checks for the STL
containers and algorithms (_SECURE_SCL, _HAS_ITERATOR_DEBUGGING) and
these are not switched off, STL performance _will_ suffer greatly.
> IMHO anyone who has to ask such question should always use the STL and
> anyone who really needs to know the answer is in big trouble
> since the difference is unlikely to make a significant difference to
> application performance except in contrived examples.
>
You must know your environment. If you cannot change your
compiler+implementation settings for whatever (legacy) reasons, and if
these are preventing STL code from running to it's full potential then
writing "C code" might be the best approach available.
br,
Martin
CornedBee
>
> I got into an argument about this with a work mate of mine. He insisted
> that he could write a custom linked list in C for our application that
> was faster than the STL list class. I asked him what evidence he had for
> this assertion and all he could come up with was that of course his code
> would be faster, because of the reasons you cite above while his code
> would be highly optimized for our particular situation.
>
> A challenge ensued and the winner was the STL list class. It was a full
> 5% faster than anything he could come up with, even when he tried asm
> optimizations.
Muahahaha!
Seriously, though, linked containers are one of the examples where non-
STL code (I'm not saying C code, because you can still benefit from
e.g. classes and templates in C++ without using the STL) can, in
theory, beat STL code, because the custom-written code can be
intrusive. This is not always an advantage, but when it is, it can be
significant.
Of course, for that we have Boost.Intrusive to give us the interface
of STL containers combined with the efficiency of intrusive
containers. And then you can use STL algorithms on the result. The STL
is, after all, designed to be extensible.
Sebastian
shahav
> tohava <toh...@gmail.com> wrote:
> > I was wondering, can anyone give examples of specific cases which
> > demonstrate STL slowness in comparison to C. I'm also curious as to
> > which programming idioms can improve STL efficiency. Note that I feel
> > that we should separate between cases where the compiler supports
> > Rvalue-references and cases where it doesn't, since these probably
> > also have a major effect on container efficiency.
>
> I got into an argument about this with a work mate of mine. He insisted
> that he could write a custom linked list in C for our application that
> was faster than the STL list class. I asked him what evidence he had for
> this assertion and all he could come up with was that of course his code
> would be faster, because of the reasons you cite above while his code
> would be highly optimized for our particular situation.
>
> A challenge ensued and the winner was the STL list class. It was a full
> 5% faster than anything he could come up with, even when he tried asm
> optimizations.
>
>
optimization space. to compete with this, the c implementation should
be almost completely inlined as well.
Also remember that, unlike the past, most new impl of stl use fairly
good allocators, which gain will be hard to compete with.
Rabin
Rune Allnor
> On the thread regarding C and C# performance, Rune Allnor said:
>
> > The STL is a compromise between ease of use, safety and
> > functionality.
> > It is well known that the run-time performance of the STL can be
> > beaten by traditional C-style constructs. It is up to the coder to
> > balance the conveniences offered by the STL against the raw
> > performance of more 'primitive' coding styles.
>
> I was wondering, can anyone give examples of specific cases which
> demonstrate STL slowness in comparison to C.
My comment was based on a chapter in Bulka & Mayhew's "Efficient C++"
issued in 2000. Maybe compilers have improved improved in the mean
time to the point that their findings are no longer valid, I don't
know.
Rune
Andrei Alexandrescu
>> ... I'm also curious as to which programming idioms can improve STL efficiency.
>
> Best reference on the matter: Scott Meyyer's "Effective STL" (http://
> www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629)
> [PDF can be found in http://www.uml.org.cn/c++/pdf/EffectiveSTL.pdf]
This is the second time a link to an illegally copied book makes it
through moderation.
Andrei
{ Assuming the above is correct: I'm sorry, I let it slip through. It looked
legitimate to me, since I knew that Scott has at least one free e-book. We can
only do so much checking of links, but still I apologize. -mod/alf }
Jeff Schwab
> linked containers are one of the examples where non-
> STL code (I'm not saying C code, because you can still benefit from
> e.g. classes and templates in C++ without using the STL) can, in
> theory, beat STL code, because the custom-written code can be
> intrusive.
Intrusive to what? The value_type? How would that help? STL linked
lists don't allocate separate nodes and values; the values are members
of the nodes.
simont
> CornedBee wrote:
> > linked containers are one of the examples where non-
> > STL code (I'm not saying C code, because you can still benefit from
> > e.g. classes and templates in C++ without using the STL) can, in
> > theory, beat STL code, because the custom-written code can be
> > intrusive.
>
> Intrusive to what? The value_type? How would that help? STL linked
> lists don't allocate separate nodes and values; the values are members
> of the nodes.
Which means, if you have objects already allocated and managed
elsewhere, you either end up storing duplicates, or storing pointers
to them.
You can avoid both copy-construction and the extra indirection with
intrusive containers (such as Boost.Intrusive).
SG
> CornedBee wrote:
> > linked containers are one of the examples where non-
> > STL code (I'm not saying C code, because you can still benefit from
> > e.g. classes and templates in C++ without using the STL) can, in
> > theory, beat STL code, because the custom-written code can be
> > intrusive.
>
> Intrusive to what? The value_type? How would that help? STL linked
> lists don't allocate separate nodes and values; the values are members
> of the nodes.
Yeah, but it creates a copy of it whereas Boost.Intrusive just alters
some pointers and leaves object life-time management to you. I
personally never felt the need to do that, though. Also, my guess is
that Boost.Intrusive will become less attractive in the light of C++0x
and "forwarded/delayed construction" (emplace_back, make_shared, etc)
Cheers,
SG
Antonio Pérez Barrero
> "Antonio P�rez Barrero" <apbarr...@gmail.com> wrote in messagenews:6aee09c8-2a27-45db...@j4g2000yqe.googlegroups.com...
>
> >> ... I'm also curious as to which programming idioms can improve STL
> >> efficiency.
>
> > Best reference on the matter: Scott Meyyer's "Effective STL" (http://
> >www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629)
> > [PDF can be found in [LINK REMOVED FOR REPLY]]
>
> Since Scott Meyers does not provide PDF's of his books on his own site for
> free, I'm reasonably confident that he does not want the content of his
> books to be posted online. The PDF he offers are sold not free. Thus posting
> links like the above are poor form.
>
> Perhaps I am wrong, in which case I fully expect Scott Meyers to let me kow,
> since he does read this group (or at least he posts here).
>
> --
> [ comp.lang.c++.moderated. First time posters: Do this! ]
My apologies for posting the PDF link. I own a paper copy of the book.
Maxim Yegorushkin
> tohava<toh...@gmail.com> wrote:
>
>> On the thread regarding C and C# performance, Rune Allnor said:
>>
>>> The STL is a compromise between ease of use, safety and
>>> functionality.
>>> It is well known that the run-time performance of the STL can be
>>> beaten by traditional C-style constructs. It is up to the coder to
>>> balance the conveniences offered by the STL against the raw
>>> performance of more 'primitive' coding styles.
>>
>> I was wondering, can anyone give examples of specific cases which
>> demonstrate STL slowness in comparison to C. I'm also curious as to
>> which programming idioms can improve STL efficiency. Note that I feel
>> that we should separate between cases where the compiler supports
>> Rvalue-references and cases where it doesn't, since these probably
>> also have a major effect on container efficiency.
I don't quite understand people who claim that C is faster. C++ is
pretty much C on steroids. The rule of thumb is simple: profile and then
use STL where its performance is adequate, use custom
containers/algorithms when STL performance is not enough.
> I got into an argument about this with a work mate of mine. He insisted
> that he could write a custom linked list in C for our application that
> was faster than the STL list class. I asked him what evidence he had for
> this assertion and all he could come up with was that of course his code
> would be faster, because of the reasons you cite above while his code
> would be highly optimized for our particular situation.
std::list<> insertion times are pretty easy to beat with an intrusive
list (no memory allocation on insert). This, however, does not mean that
a C intrusive list beats a C++ intrusive list ;)
--
Max
Branimir Maksimovic
Speed of linked list depends if nodes are sorted by address or not.
For example if nodes are sorted by address pass through linked
list can be double the speed of nodes that are not sorted
in same list:
example:
randomize means randomize elements after particular sort.
This is cumulative result of sorting differently sized list from
1000 elements to 5 million elements.
Sorts that change order of pointers makes pass through list much slower.
In this case it is not that visible because I use strcpy
to randomize nodes.
For example my quick sort does not use random access iterator
rather bidirectional iterator and therefore I get double
the speed of gcc's sort because of cache read ahead.
In this case nodes are allocated with default allocator (new).
initial randomize: 3.813657
merge: 29.382570 randomize: 5.637630
radix: 9.356660 randomize: 6.227840
quick sort nodes by address: 4.449886
quick no address sort after radix: 18.054184
quick: 4.197227 randomize: 4.314877
In this case nodes are allocated in one vector.
initial randomize: 3.345104
merge: 19.606263 randomize: 5.460195
radix: 8.035850 randomize: 6.355689
quick sort nodes by address: 3.723686
quick no address sort after radix: 15.126693
quick: 1.860516 randomize: 3.765984
You see you get double speed of linked list
by just sorting nodes by address and using
custom allocator and avoiding random access iterator.
512kb of cache would be enough to notice
significant difference no matter the size of list.
Greets