How to stl library efficiently?
Peng Yu
I came across some discussion on that improper usage stl library could
make program performance bad. Some tips are trivial, such as using the
appropriate algorithm, choosing the best data structure (say, vector
vs. list).
I'm wondering whether are less obvious tricks to make stl based
program performance as good as the hard coded C program?
Thanks,
Peng
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ulrich Eckhardt
> I came across some discussion on that improper usage stl library could
> make program performance bad. Some tips are trivial, such as using the
> appropriate algorithm, choosing the best data structure (say, vector
> vs. list).
There is also deque as possible unordered container. BTW, can you supply a
URL of mentioned discussion?
> I'm wondering whether are less obvious tricks to make stl based
> program performance as good as the hard coded C program?
It's a very obvious trick but it still applies here: profile first, optimise
later.
Lastly: the STL was in large parts incorporated into the C++ stardardlibrary
but the overlap is not 100%. I'd generally target my code at the C++
standardlibrary, the STL itself is pretty much dead nowadays.
Uli
red floyd
> Hi,
>
> I came across some discussion on that improper usage stl library could
> make program performance bad. Some tips are trivial, such as using the
> appropriate algorithm, choosing the best data structure (say, vector
> vs. list).
>
> I'm wondering whether are less obvious tricks to make stl based
> program performance as good as the hard coded C program?
>
Get Scott Meyer's "Effective STL".
Mathias Gaunard
> I'm wondering whether are less obvious tricks to make stl based
> program performance as good as the hard coded C program?
You need move semantics and in-place construction for comparable
performance.
Which are not in the current implementation.
Lance Diduck
> program performance as good as the hard coded C program?
>
> Thanks,
> Peng
programs. See sites like http://theory.stanford.edu/~amitp/rants/c++-vs-c/
and http://www.tilander.org/aurora/2007/12/comparing-stdsort-and-qsort.html
Outside of the advice to always select the proper container and
algorithms, there are other tricks one can do to improve performance.
Most of these involve using custom allocators in containers. Here are
some papers http://xushiwei.com/allocators-performance-on-stl-collections,
and http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2486.pdf
There are a number of platform specific ways to improve performance.
On MSVC, define _SECURE_SCL=0 to get rid of a lot of overhead for
security checks. On gcc, this is a good read
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html.
If these still arent good enough, the next thing is to define your own
containers and algorithms. The STL defines a number of concepts to use
for this. For example, you may design your own version of of a sorted
container tailored to your needs, and if you follow the guidelines
your container will play nice with all of the other STL components.
See http://www.cs.rpi.edu/~musser/STL_concept_web/ and
http://www.sgi.com/tech/stl/Container.html. boost has a lot of STL
based containers, as well as gcc for example
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html
Lance
Sergey P. Derevyago
> I'm wondering whether are less obvious tricks to make stl based
> program performance as good as the hard coded C program?
>
Please read "C++ multithreading: mem_pool" message:
Message-ID: <4899c3e1$0$90276$1472...@news.sunsite.dk>
http://groups.google.com/group/comp.programming.threads/msg/b52ce202a371778b
-----------------------------------8<-----------------------------------
void start_std(void*)
{
list<int> lst;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) lst.push_back(j);
for (int j=0; j<M; j++) lst.pop_front();
}
}
void start_ders(void*)
{
mem_pool mp;
stl_allocator<int> alloc(mp);
list<int, stl_allocator<int> > lst(alloc);
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) lst.push_back(j);
for (int j=0; j<M; j++) lst.pop_front();
}
}
-----------------------------------8<-----------------------------------
The table at http://ders.stml.net/cpp/mtprog/mtprog.html#3.1.1 shows
that start_ders() function is tens and hundreds (!!!) of times faster:
1 CPU : 38.1
1 CPU,HT : 42.1
2 CPU,SMP: 321.6 (!!!)
2 CPU,HT : 37.0
--
With all respect, Sergey. http://ders.stml.net/
mailto : ders at skeptik.net
Peng Yu
> Peng Yu wrote:
> > I came across some discussion on that improper usage stl library could
> > make program performance bad. Some tips are trivial, such as using the
> > appropriate algorithm, choosing the best data structure (say, vector
> > vs. list).
>
> There is also deque as possible unordered container. BTW, can you supply a
> URL of mentioned discussion?
I came across such webpage long time back. I can recall where it is.
Sorry about that.
> > I'm wondering whether are less obvious tricks to make stl based
> > program performance as good as the hard coded C program?
>
> It's a very obvious trick but it still applies here: profile first, optimise
> later.
>
> Lastly: the STL was in large parts incorporated into the C++ stardardlibrary
> but the overlap is not 100%. I'd generally target my code at the C++
> standardlibrary, the STL itself is pretty much dead nowadays.
I always use the following website for the documentation when I use
STL.
http://www.sgi.com/tech/stl/
Where is the C++ Standard Library manual? I found this one
http://gcc.gnu.org/onlinedocs/libstdc++/. Is it appropriate?
What is the major difference between C++ Standard Library and STL? I
usually use GCC C++ compiler. It has the complete C++ Standard
Library, right?
Peng Yu
> that start_ders() function is tens and hundreds (!!!) of times faster:
The website you mentioned in some language rather than English (maybe
Russian). I don't understand that language. Is there an English
version for it.
Thanks,
Peng
Peng Yu
> Peng Yu wrote:
> > Hi,
>
> > I came across some discussion on that improper usage stl library could
> > make program performance bad. Some tips are trivial, such as using the
> > appropriate algorithm, choosing the best data structure (say, vector
> > vs. list).
>
> > I'm wondering whether are less obvious tricks to make stl based
> > program performance as good as the hard coded C program?
>
> Get Scott Meyer's "Effective STL".
It seems that it is a little bit outdated. For example, it mentioned
auto_ptr, but people usually use boost::shared_ptr. I'm wondering what
are the things that have been changed since the book was written.
Thanks,
Peng
Erik Wikström
STL is the name that was used before it became part of the C++ standard,
the C++ standard library contains the STL and some other stuff (like IO
capabilities etc.), so you can say that the STL is a subset of the
standard library.
The gcc standard library implementation is probably close to complete,
you can probably find detailed information about its conformance at the
gnu site.
--
Erik Wikström
Erik Wikström
>> Peng Yu wrote:
>> > Hi,
>>
>> > I came across some discussion on that improper usage stl library could
>> > make program performance bad. Some tips are trivial, such as using the
>> > appropriate algorithm, choosing the best data structure (say, vector
>> > vs. list).
>>
>> > I'm wondering whether are less obvious tricks to make stl based
>> > program performance as good as the hard coded C program?
>>
>> Get Scott Meyer's "Effective STL".
>
> It seems that it is a little bit outdated. For example, it mentioned
> auto_ptr, but people usually use boost::shared_ptr. I'm wondering what
> are the things that have been changed since the book was written.
Nothing, the C++ standard has not been update since then. On the other
hand a number of new libraries have been developed and evolved since
then (such as boost), but none of them are part of the C++ standard.
Work on the next version of the C++ standard is ongoing the new version
(which contains something like boost::shared_ptr, and much more) will
hopefully be out in 2009, but it will take a while longer until
compilers and libraries support the new stuff.
--
Erik Wikström
Timo Geusch
> On Aug 10, 11:28 am, red floyd <no.spam.h...@example.com> wrote:
>> Peng Yu wrote:
>> > Hi,
>>
>> > I came across some discussion on that improper usage stl library could
>> > make program performance bad. Some tips are trivial, such as using the
>> > appropriate algorithm, choosing the best data structure (say, vector
>> > vs. list).
>>
>> > I'm wondering whether are less obvious tricks to make stl based
>> > program performance as good as the hard coded C program?
>>
>> Get Scott Meyer's "Effective STL".
>
> It seems that it is a little bit outdated. For example, it mentioned
> auto_ptr, but people usually use boost::shared_ptr. I'm wondering what
> are the things that have been changed since the book was written.
It's still a book that is very worthwhile to have. Not mention that
auto_ptr still exists - a boost::shared_ptr is a completely different
beast that serves a different purpose.
--
Timo Geusch
Codesmith Consulting Ltd
The lone C++ coder's blog: http://codeblog.bsdninjas.co.uk/
Joshua...@gmail.com
> On Aug 10, 11:28 am, red floyd <no.spam.h...@example.com> wrote:
> > Get Scott Meyer's "Effective STL".
>
> It seems that it is a little bit outdated. For example, it mentioned
> auto_ptr, but people usually use boost::shared_ptr. I'm wondering what
> are the things that have been changed since the book was written.
std::auto_ptr and boost::shared_ptr solve different problems. In my
work, a lot of the old APIs I have to work with return naked pointers
which the caller is responsible for freeing. I just immediately stick
the returned pointer in an auto_ptr, ensuring that I won't leak it on
the myriad of return error code paths in the 1000 line function I'm
maintaining.
boost::shared_ptr is a referenced counted shared pointer. Although it
will work for the above situation, a.k.a. it works where ever an
auto_ptr works, it has a small amount of overhead compared to the no
overhead of auto_ptr. 'shared_ptr's are used if there are multiple
owners of the object, a pseudo Garbage Collection system if you will.
Sergey P. Derevyago
> The website you mentioned in some language rather than English (maybe
> Russian). I don't understand that language. Is there an English
> version for it.
>
I explain the details in English.
In particular this one:
http://groups.google.com/group/comp.programming.threads/msg/b52ce202a371778b
--
Peng Yu
> Peng Yu <PengYu...@gmail.com> writes:
> > On Aug 10, 11:28 am, red floyd <no.spam.h...@example.com> wrote:
> >> Peng Yu wrote:
> >> > Hi,
>
> >> > I came across some discussion on that improper usage stl library could
> >> > make program performance bad. Some tips are trivial, such as using the
> >> > appropriate algorithm, choosing the best data structure (say, vector
> >> > vs. list).
>
> >> > I'm wondering whether are less obvious tricks to make stl based
> >> > program performance as good as the hard coded C program?
>
> >> Get Scott Meyer's "Effective STL".
>
> > It seems that it is a little bit outdated. For example, it mentioned
> > auto_ptr, but people usually use boost::shared_ptr. I'm wondering what
> > are the things that have been changed since the book was written.
>
> It's still a book that is very worthwhile to have. Not mention that
> auto_ptr still exists - a boost::shared_ptr is a completely different
> beast that serves a different purpose.
According to my understanding, shared_ptr can do whatever auto_ptr
does, but the vice versa is not true. Although shared_ptr has more
functionality, but it does not slow down the runtime performance as
the shared_ptr is a template and can be optimized in compile time.
Therefore, it is reasonable to use shared_ptr instead of auto_ptr as
long as the former one is available. Please correct me if my
understand is not correct.
Thanks,
Peng
--
Martin Bonner
> According to my understanding, shared_ptr can do whatever auto_ptr
> does, but the vice versa is not true.
access to the pointed-to object. That can be important when handing
pointed-to objects between threads (for example).
> Although shared_ptr has more
> functionality, but it does not slow down the runtime performance as
> the shared_ptr is a template and can be optimized in compile time.
Well, auto_ptr is a template too, so can be optimized to the same
extent.
> Therefore, it is reasonable to use shared_ptr instead of auto_ptr as
> long as the former one is available. Please correct me if my
> understand is not correct.
Your premises are false, but your conclusion is correct. In general,
I would use shared_ptr as my default pointer, just as I would use
vector as my default container (the test is, "is there a good reason
not to use this?")
Be aware that some very experienced developers (eg James Kanze) do not
share this view - with luck, one of them will explain why not.
Joshua...@gmail.com
Now, I may not be up to date on good commercial compilers and their
optimizations, but I would be happily surprised if this was the case
for most compilers. There are two reason offhand why it's probably the
case shared_ptr has more overhead than an auto_ptr.
A boost shared pointer has shared ownership of the object vs the
single ownership of an auto_ptr. An auto_ptr requires no runtime
state, whereas a boost shared pointer must maintain some state at
runtime to keep a reference count. This extra state could be optimized
away I suppose in some cases, I'm not quite sure. However, once we
start crossing function calls, and especially shared libraries,
passing ownership between one shared_ptr to another like you would
with an auto_ptr, and I'd imagine most compilers would be unable to do
anything.
Moreover, boost:shared_ptr is thread-safe. It would be a pretty
awesome compiler that could optimize away the synchronization calls
that makes shared_ptr thread-safe in any use.
Of course, I haven't actually tried any of this, so I could be wrong.
Either way, a poor / average compiler will put in overhead for
boost::shared_ptr even when you won't need it, but not for auto_ptr.
gas...@hotmail.com
> does, but the vice versa is not true. Although shared_ptr has more
> functionality, but it does not slow down the runtime performance as
> the shared_ptr is a template and can be optimized in compile time.
> Therefore, it is reasonable to use shared_ptr instead of auto_ptr as
> long as the former one is available. Please correct me if my
> understand is not correct.
I would think that boost::scoped_ptr is more closely to the
std::auto_ptr then boost::shared_ptr, if its main objective is being
the sole owner of pointer. My guess would be that scoped_ptr is simple
enough to be aggressively optimized (but I am not a compiler writer).
And why is this handy scoped_ptr not included in Tr1...
Martin Bonner
> On Aug 19, 2:53 am, Martin Bonner <martinfro...@yahoo.co.uk> wrote:
>
>
>
> > On Aug 19, 1:39 am, Peng Yu <PengYu...@gmail.com> wrote:
> > > Although shared_ptr has more
> > > functionality, but it does not slow down the runtime performance as
> > > the shared_ptr is a template and can be optimized in compile time.
>
> > Well, auto_ptr is a template too, so can be optimized to the same
> > extent.
> Now, I may not be up to date on good commercial compilers and their
> optimizations, but I would be happily surprised if this was the case
> for most compilers. There are two reason offhand why it's probably the
> case shared_ptr has more overhead than an auto_ptr.
I was responding to the suggestion that shared_ptr will be /faster/
than auto_ptr "because shared_ptr is a template". My phrasing ("to
the same extent") was misleading; I too would expect shared_ptr to be
at least as slow/memory hungry as auto_ptr.
> Moreover, boost:shared_ptr is thread-safe. It would be a pretty
> awesome compiler that could optimize away the synchronization calls
> that makes shared_ptr thread-safe in any use.
Actually, not really. Many of the synchronization calls can be
optimized away as a result of RVO and NRVO (basically, the compiler is
allowed to elide copy-constructor+destructor pairs).
Joshua...@gmail.com
> On Aug 19, 10:17 pm, JoshuaMaur...@gmail.com wrote:
>
> > On Aug 19, 2:53 am, Martin Bonner <martinfro...@yahoo.co.uk> wrote:
>
> > > On Aug 19, 1:39 am, Peng Yu <PengYu...@gmail.com> wrote:
> > > > Although shared_ptr has more
> > > > functionality, but it does not slow down the runtime performance as
> > > > the shared_ptr is a template and can be optimized in compile time.
>
> > > Well, auto_ptr is a template too, so can be optimized to the same
> > > extent.
> > Now, I may not be up to date on good commercial compilers and their
> > optimizations, but I would be happily surprised if this was the case
> > for most compilers. There are two reason offhand why it's probably the
> > case shared_ptr has more overhead than an auto_ptr.
Indeed, sorry.
> I was responding to the suggestion that shared_ptr will be /faster/
> than auto_ptr "because shared_ptr is a template". My phrasing ("to
> the same extent") was misleading; I too would expect shared_ptr to be
> at least as slow/memory hungry as auto_ptr.
>
> > Moreover, boost:shared_ptr is thread-safe. It would be a pretty
> > awesome compiler that could optimize away the synchronization calls
> > that makes shared_ptr thread-safe in any use.
>
> Actually, not really. Many of the synchronization calls can be
> optimized away as a result of RVO and NRVO (basically, the compiler is
> allowed to elide copy-constructor+destructor pairs).
Only if there is a copy constructor it can elide. Using just a single
shared_ptr on the stack as you would an auto_ptr still sets the
reference count to 1, and the destructor of the shared_ptr (probably)
does an atomic decrement to determine when to delete its owned
pointer. I doubt that the compiler can do anything to get rid of this
atomic decrement, whereas the auto_ptr has no such atomic decrement.
wasti...@gmx.net
wrote:
> I would think that boost::scoped_ptr is more closely to the
> std::auto_ptr then boost::shared_ptr, if its main objective is being
> the sole owner of pointer. My guess would be that scoped_ptr is simple
> enough to be aggressively optimized (but I am not a compiler writer).
>
> And why is this handy scoped_ptr not included in Tr1...
Because auto_ptr can do everything scoped_ptr can, except for
producing a compile error when you attempt to copy it.
And because C++0x's unique_ptr will be even better.
Sebastian
gas...@hotmail.com
>
> Because auto_ptr can do everything scoped_ptr can, except for
> producing a compile error when you attempt to copy it.
And thats exactly what I want. No scoped_ptr in vector's and no copy
ctor available when scoped_ptr is a member of your class. I would say
that it out performs the auto_ptr (except that auto_ptr has a release
mthod).
> And because C++0x's unique_ptr will be even better.
Ah maybe thats the reason.
Eugene Gershnik
> I would use shared_ptr as my default pointer,
I don't think there is such a thing as a 'default' pointer. A pointer
can represent very different design concepts such as "knows about",
"owns exclusively now but can transfer ownership", "owns exclusively",
"shares ownership" etc.
IMO one should choose the smart pointer class that most closely
represents the design concepts behind the code.
If the pointer does not represent "shared ownership" then using
shared_ptr at the very least lies to the reader much like a wrong
comment would do. At worst it may cause bugs when ownership is
accidentally shared when it shouldn't have been possible.
> just as I would use
> vector as my default container
I use deque. See http://www.gotw.ca/gotw/054.htm .
--
Eugene