When does Fast STL Make a Difference?
Peter Olcott
Standard Template Library make a significant difference in
overall system performance? The one case that comes to mind
for me would be graphics intensive applications. This is the
case that SGI STL was developed for.
http://www.sgi.com/tech/stl/
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Mike Wahler
solid backbone of C++ content -mod/fwg}
Peter Olcott <olc...@worldnet.att.net> wrote in message
news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> In what cases would a significant difference in the speed of the
> Standard Template Library make a significant difference in
> overall system performance? The one case that comes to mind
> for me would be graphics intensive applications. This is the
> case that SGI STL was developed for.
> http://www.sgi.com/tech/stl/
The performance of an application using 'STL' will be
influenced by the performance of those 'STL' features
being used. Same goes for the impact of any other library
being used. Pretty simple. :-)
-Mike
Carl Daniel
news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> Standard Template Library make a significant difference in
> overall system performance?
>
In those cases where a significant percentage of the CPU cycles of the
program were spent running code from the STL (or the Standard Library, which
I think is what you really mean).
So what does that mean? In practice, it means that you:
1) Assume standard library components have adequate performance unless you
specifically know otherwise.
2) Develop your code.
3) Test your code for correctness.
4) Profile your code.
5) Address those performance areas which appear during profiling. If those
areas include Standard Library code, then you've identified one of those
cases you seek in your original question.
Without going through steps 1-5, you cannot know the answer to your
question - the answer will be different for every application written.
> The one case that comes to mind
> for me would be graphics intensive applications. This is the
> case that SGI STL was developed for.
> http://www.sgi.com/tech/stl/
>
Graphics applications are frequently CPU hungry, yes. Whether the
performance of the Standard Library is of any significance of course depends
on what the standard library was used for. If a 3D graphics application was
developed using std::vector<float> to represent points, it's likely that the
performance of std::vector would be important to the application. It's
also unlikely that an experienced graphics programmer would use std::vector
for such a purpose, so the significance of the example is minimal at best.
One of the huge advantages of using the C++ Standard Library, like the C
library before it, is that you, the programmer, can harness state of the art
algorithms and structures without having to craft them yourself. How often
would you, as a C programmer, write your own QuickSort? I'd guess about
once - when it was a homework problem in a C programming class. The
relevance of using better algorithms cannot be minimized. Typically,
microoptimizations such as what you've been engaged in with FastString
account for no more than a 3x difference in application performance (and
please don't reply with how your precious toy string class was 300x faster
than brand X's in some special circumstance). Algorithmic differences, on
the other hand, can easily make a 100x difference in application
performance.
The experienced developer knows to apply the right algorithms to the
problem, to avoid writing an application that's 100x slower than it should
be. If it ends up a bit slower, profiling and focused optimization will
usually bring the performance up to par with minimal effort.
-cd
Spaller
> {Please could all who choose to post to this thread ensure there is a
> solid backbone of C++ content -mod/fwg}
When was STL removed from the C++ standard?
>
>
> Peter Olcott <olc...@worldnet.att.net> wrote in message
> news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> > In what cases would a significant difference in the speed of the
> > Standard Template Library make a significant difference in
> > overall system performance? The one case that comes to mind
> > for me would be graphics intensive applications. This is the
> > case that SGI STL was developed for.
> > http://www.sgi.com/tech/stl/
>
> The performance of an application using 'STL' will be
> influenced by the performance of those 'STL' features
> being used. Same goes for the impact of any other library
> being used. Pretty simple. :-)
>
> -Mike
Except that STL is not much of a library since it's really
include files that have to be known at compile time. So
there isn't some object code one could just plop onto
a system and expect the "system" performance to
improve remarkably.
spaller
--
...
Peter Olcott
> news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> > In what cases would a significant difference in the speed of the
> > Standard Template Library make a significant difference in
> > overall system performance? The one case that comes to mind
> > for me would be graphics intensive applications. This is the
> > case that SGI STL was developed for.
> > http://www.sgi.com/tech/stl/
>
> The performance of an application using 'STL' will be
> influenced by the performance of those 'STL' features
> being used. Same goes for the impact of any other library
> being used. Pretty simple. :-)
This is not the question. Anyone can provide an
assumption. The only correct basis for this assumption
would be the exhaustive examination of every application
ever written, thus this assumption can have no basis.
What I was asking for is the single counter-example
that utterly disproves such assumptions as this one.
Peter Olcott
"Carl Daniel" <cpda...@pacbell.net> wrote in message
news:Ft5_7.24370$%4.1465...@newssvr21.news.prodigy.com...
> "Peter Olcott" <olc...@worldnet.att.net> wrote in message
> news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> > In what cases would a significant difference in the speed of the
> > Standard Template Library make a significant difference in
> > overall system performance?
> >
>
> In those cases where a significant percentage of the CPU cycles of the
> program were spent running code from the STL (or the Standard Library, which
> I think is what you really mean).
>
> So what does that mean? In practice, it means that you:
> 1) Assume standard library components have adequate performance unless you
> specifically know otherwise.
> 2) Develop your code.
> 3) Test your code for correctness.
> 4) Profile your code.
> 5) Address those performance areas which appear during profiling. If those
> areas include Standard Library code, then you've identified one of those
> cases you seek in your original question.
>
> Without going through steps 1-5, you cannot know the answer to your
> question - the answer will be different for every application written.
I have profiled some significant aspects of std::string and found it
to be as much as 300-fold slower than nesscessary in some cases.
This case was the repeated concatenation of a 64-byte long
string, by MSVC++ 6.0 compared to STLport 4.51.
> > The one case that comes to mind
> > for me would be graphics intensive applications. This is the
> > case that SGI STL was developed for.
> > http://www.sgi.com/tech/stl/
> >
>
> Graphics applications are frequently CPU hungry, yes. Whether the
> performance of the Standard Library is of any significance of course depends
> on what the standard library was used for. If a 3D graphics application was
> developed using std::vector<float> to represent points, it's likely that the
> performance of std::vector would be important to the application. It's
> also unlikely that an experienced graphics programmer would use std::vector
> for such a purpose, so the significance of the example is minimal at best.
Not necessarily. I think that the reason that Silicon Graphics Incorporated
wrote their implementation of STL called SGI STL, was so that their
programmers could have STL with performance that could be relied on
as sufficient for their needs.
> One of the huge advantages of using the C++ Standard Library, like the C
> library before it, is that you, the programmer, can harness state of the art
> algorithms and structures without having to craft them yourself. How often
> would you, as a C programmer, write your own QuickSort? I'd guess about
I tried, wasted two weeks, only to find that I couldn't even nearly
match the performance of qsort(). STL should ONLY be implemented
with this same degree of performance quality, apparently it is not,
and that is my point.
> once - when it was a homework problem in a C programming class. The
> relevance of using better algorithms cannot be minimized. Typically,
> microoptimizations such as what you've been engaged in with FastString
> account for no more than a 3x difference in application performance (and
> please don't reply with how your precious toy string class was 300x faster
> than brand X's in some special circumstance). Algorithmic differences, on
Actually FastString was only 178-fold faster, it was STLport
(not at all a toy) that was 300-fold faster.
> the other hand, can easily make a 100x difference in application
> performance.
>
> The experienced developer knows to apply the right algorithms to the
> problem, to avoid writing an application that's 100x slower than it should
> be. If it ends up a bit slower, profiling and focused optimization will
> usually bring the performance up to par with minimal effort.
Yet when this same experienced programmer uses tools such
as STL that may be far slower than necessary, he/she is often
starting from the basis of a false assumption. If we could all
count on STL being as performance optimized as qsort()
has been for many years, much fewer of us would ever bother
to roll-our-own equivalent functionality.
Carlos Moreno
Peter Olcott wrote:
>
> > would you, as a C programmer, write your own QuickSort? I'd guess about
>
> I tried, wasted two weeks, only to find that I couldn't even nearly
> match the performance of qsort(). STL should ONLY be implemented
> with this same degree of performance quality, apparently it is not,
> and that is my point.
Well, I once tried a comparison between qsort and std::sort, for an
array of doubles, to find that std::sort was 28 times faster than
qsort. (with gcc/g++ 2.95, and I think I also tried with Borland
C++ 5.5.1, but I'm not 100% sure right now...)
I don't think this is related to your original question, but I
thought I'd "auto-reply" to your comment above with these results.
> starting from the basis of a false assumption. If we could all
> count on STL being as performance optimized as qsort()
> has been for many years, much fewer of us would ever bother
> to roll-our-own equivalent functionality.
Agreed. But you have to agree that most cases (and I mean the
great great great majority of the cases) the false assumtions
are assumtion that the library's efficiency will not be sufficient;
that is, in most cases, programmers implement their own, optimised
stuff when they didn't need to -- and even more sad, in many cases,
the implementation they do is not really faster than the one from
the library... (needless to say that sometimes they don't even
get to realize that theirs is slower...)
Carlos
--
Mike Wahler
news:1103_10...@news.sf.sbcglobal.net...
> On 6 Jan 2002 15:00:46 -0500, "Mike Wahler" <mkwa...@ix.netcom.com>
wrote:
> > {Please could all who choose to post to this thread ensure there is a
> > solid backbone of C++ content -mod/fwg}
>
> When was STL removed from the C++ standard?
I wasn't 'removed', it was never defined by the
standard. My point was that the prestandardized
version of libraries that folks called 'STL'
has had most of it included in the standard C++
library, with some changes and additions.
I'm only saying that the term 'STL' is not defined
by standard C++, although what prestandard 'STL'
libraries has been mostly reproduced in what the
standard call simply 'the standard library'.
-Mike
Niklas Borson
>
> [snip]
>
> Agreed. But you have to agree that most cases (and I mean the
> great great great majority of the cases) the false assumtions
> are assumtion that the library's efficiency will not be sufficient;
> that is, in most cases, programmers implement their own, optimised
> stuff when they didn't need to -- and even more sad, in many cases,
> the implementation they do is not really faster than the one from
> the library... (needless to say that sometimes they don't even
> get to realize that theirs is slower...)
Naive benchmarking also plays a part here. A former colleage once
implemented his own heap manager because he was concerned about the
performance of malloc and ::operator new shipped with the compiler
(which was at the time MSVC 1.0 or something like that). He then
wrote a toy app that just did a bunch of allocations and deletions
and, sure enough, his very simple heap was quite a bit faster -- as
in N times faster, for some value of N which I don't remember. :-)
Now comes the interesting part. He proceded to use his "faster"
heap in a real application, and several months later a different
programmer decided to run his own test. He built two versions of
the application, one using the "fast" heap and one using the
standard heap, and -- you guessed it! -- the version that used
the standard heap provided with the compiler ran faster.
How do I account for this difference? Perhaps the standard heap
produced better locality of reference, such that the app as a whole
ran faster (due to fewer cache misses) even though the allocations
themselves were slower (due to a more complicated algorithm). Or
perhaps the performance of the simpler allocater degraded over
time due to fragmentation. I don't know, but it does suggest that
one must be cautious about inferring too much from simple
benchmarks.
Mike Wahler
> > Peter Olcott <olc...@worldnet.att.net> wrote in message
> > news:6r%Z7.28370$fe1.4...@bgtnsc06-news.ops.worldnet.att.net...
> > > In what cases would a significant difference in the speed of the
> > > Standard Template Library make a significant difference in
> > > overall system performance? The one case that comes to mind
> > > for me would be graphics intensive applications. This is the
> > > case that SGI STL was developed for.
> > > http://www.sgi.com/tech/stl/
> >
> > The performance of an application using 'STL' will be
> > influenced by the performance of those 'STL' features
> > being used. Same goes for the impact of any other library
> > being used. Pretty simple. :-)
>
> This is not the question.
So what's the question? I can only read and interpret
the meaning of the English words you used.
> Anyone can provide an
> assumption.
It's a valid assumption that the performance of code that depends upon
other code, is influenced by the performance of that other code.
e.g. one's nutrition is influenced by the quality of the food one
eats.
>The only correct basis for this assumption
> would be the exhaustive examination of every application
> ever written, thus this assumption can have no basis.
Perhaps you're assigning to me some assumption I did not
make. Otherwise you're making no sense.
> What I was asking for is the single counter-example
What example?
> that utterly disproves such assumptions as this one.
I've tried to clarify what my actual 'assumption' is
above. Your remarks here disprove it not at all.
-Mike
Donovan Rebbechi
Olcott wrote:
> > So what does that mean? In practice, it means that you:
> > 1) Assume standard library components have adequate performance unless you
> > specifically know otherwise.
> > 2) Develop your code.
> > 3) Test your code for correctness.
> > 4) Profile your code.
> > 5) Address those performance areas which appear during profiling. If those
> > areas include Standard Library code, then you've identified one of those
> > cases you seek in your original question.
> >
> > Without going through steps 1-5, you cannot know the answer to your
> > question - the answer will be different for every application written.
>
> I have profiled some significant aspects of std::string and found it
> to be as much as 300-fold slower than nesscessary in some cases.
> This case was the repeated concatenation of a 64-byte long
> string, by MSVC++ 6.0 compared to STLport 4.51.
You did not "profile" it, you *benchmarked* it. "Profiling" is when you
analyze the performance of a real-world application. This is done to
identify bottlenecks. You haven't shown any profiles that show a real
world application bottlenecked by 64 byte string catenations.
Profiling is very important, because optimising takes time and effort.
Basically, if you haven't profiled, the claims you make about impact on real
world performance are conjectural (in fact the evidence available to me
suggests that you are simply wrong, and no, I don't have time to elaborate
or debate about it.)
> Yet when this same experienced programmer uses tools such
> as STL that may be far slower than necessary, he/she is often
Speed is not the only design constraint !!! You've been told this dozens
of times, and you simply are not listening.
Speed is only an issue on operations that are performance bottlenecks. An
experienced programmer chooses classes that will perform well on operations
that are anticipated bottlenecks.
For example, an "expert" would not choose a string class if they needed
the performance guarantees offered by a vector, and didn't need those
offered by string.
> starting from the basis of a false assumption. If we could all
> count on STL being as performance optimized as qsort()
> has been for many years,
Optimised -- for what ???????
You might as well argue that a vector is "better" than a linked list, because
element accesses are faster.
--
Donovan
Richard Harter
<moreno_at_mo...@m.com> wrote:
>
>Peter Olcott wrote:
> >
>
>> > would you, as a C programmer, write your own QuickSort? I'd guess about
>>
>> I tried, wasted two weeks, only to find that I couldn't even nearly
>> match the performance of qsort(). STL should ONLY be implemented
>> with this same degree of performance quality, apparently it is not,
>> and that is my point.
>
>
>Well, I once tried a comparison between qsort and std::sort, for an
>array of doubles, to find that std::sort was 28 times faster than
>qsort. (with gcc/g++ 2.95, and I think I also tried with Borland
>C++ 5.5.1, but I'm not 100% sure right now...)
This is not surprising. I don't use C++ or std::sort but if I were
implementing std::sort I would use the best sort for datatype being
sorted. Distribution and radix sorts are markedly superior to GP
comparison sorts for sorting numbers (ints, floats, doubles).
>
>I don't think this is related to your original question, but I
>thought I'd "auto-reply" to your comment above with these results.
>
>> starting from the basis of a false assumption. If we could all
>> count on STL being as performance optimized as qsort()
>> has been for many years, much fewer of us would ever bother
>> to roll-our-own equivalent functionality.
>
>
>Agreed. But you have to agree that most cases (and I mean the
>great great great majority of the cases) the false assumtions
>are assumtion that the library's efficiency will not be sufficient;
>that is, in most cases, programmers implement their own, optimised
>stuff when they didn't need to -- and even more sad, in many cases,
>the implementation they do is not really faster than the one from
>the library... (needless to say that sometimes they don't even
>get to realize that theirs is slower...)
Just so. Being an old timer and of the old school I *like* to write
highly optimized code. It's fun. But writing optimized code is
definitely non-trivial. What is more, yesterday's clever code often
turns out to be tomorrow's dog as the technology changes.
Richard Harter, c...@tiac.net,
http://www.tiac.net/users/cri, http://www.varinoma.com
Love, no matter how pure, is the most selfish of gifts.
For that reason it is the one gift that must be given.
Peter Olcott
> > > Standard Template Library make a significant difference in
> > > overall system performance? The one case that comes to mind
> > > for me would be graphics intensive applications. This is the
> > > case that SGI STL was developed for.
> > > http://www.sgi.com/tech/stl/
> >
> > The performance of an application using 'STL' will be
> > influenced by the performance of those 'STL' features
> > being used. Same goes for the impact of any other library
> > being used. Pretty simple. :-)
> >
> > -Mike
>
> Except that STL is not much of a library since it's really
> include files that have to be known at compile time. So
> there isn't some object code one could just plop onto
> a system and expect the "system" performance to
> improve remarkably.
>
> spaller
What I am trying to evaluate here is whether or not
a ten-fold improvement in the speed of STL will be
worth the cost of providing this ten-fold improvement.
Many people whom write i/o bound applications
programs thought that a hundred-fold increase in the
speed of STL would not increase the speed of their
application by as much as 1%. What I am looking
for is a counter-example where a ten-fold increase
in the speed of STL would result in at least doubling
the speed of the application or system. I would
guess that graphics might be such a case. What
other cases might you be aware of?
Carl Daniel
> Many people whom write i/o bound applications
> programs thought that a hundred-fold increase in the
> speed of STL would not increase the speed of their
> application by as much as 1%. What I am looking
> for is a counter-example where a ten-fold increase
> in the speed of STL would result in at least doubling
> the speed of the application or system. I would
> guess that graphics might be such a case. What
> other cases might you be aware of?
I wouldn't expect graphics to be such a case, because I wouldn't expect the
"inner loops", which dominate the execution time of most graphics apps, to
make much, if any, use of STL classes. Instead, I'd expect them to use
custom-made classes designed specifically for graphics apps. They'd do so
for memory usage alone, if nothing else. Consider: if you used std::vector
to store 3D points, you'll likely use 2x -3x the memory that you would
storing them in a simple struct. You'd also lose all locality of reference
benefits which would normally accrue to am implementation using arrays of
simple structs.
Similarly, if a graphics application used std::vector<my3d_point>, it's
unlikely that the performance of std::vector will be a major factor in the
performance of the application, since most of the time spent in such
applications is spent dealing with individual points.
You could, of course, construct an application where performance of any
given standard library component will have a significant impact on the
overall application performance, but it's not clear to me that there's any
sensible generalizations that can be made about which types of applications
will necessarily (or even likely) depend significantly on the performance of
the standard library.
-cd
Carl Daniel
"Richard Harter" <c...@tiac.net> wrote in message
news:3c3bba52...@news.SullyButtes.net...
> On 8 Jan 2002 14:08:23 -0500, Carlos Moreno
> <moreno_at_mo...@m.com> wrote:
> >Well, I once tried a comparison between qsort and std::sort, for an
> >array of doubles, to find that std::sort was 28 times faster than
> >qsort. (with gcc/g++ 2.95, and I think I also tried with Borland
> >C++ 5.5.1, but I'm not 100% sure right now...)
>
> This is not surprising. I don't use C++ or std::sort but if I were
> implementing std::sort I would use the best sort for datatype being
> sorted. Distribution and radix sorts are markedly superior to GP
> comparison sorts for sorting numbers (ints, floats, doubles).
>
Actually, the speed advantage of std::sort typically comes from two places:
1. std::sort is typically implemented using IntroSort, which is faster than
QuickSort for some important cases (like nearly sorted data).
2. std::sort is a template function, and typically is used with a template
class as the compare object. This enables the compiler to inline the
comparison into the sort. qsort(), on the other hand, is required to
dispatch through a function pointer for each comparison.
-cd
Donovan Rebbechi
Olcott wrote:
> > Except that STL is not much of a library since it's really
> > include files that have to be known at compile time. So
> > there isn't some object code one could just plop onto
> > a system and expect the "system" performance to
> > improve remarkably.
> >
> > spaller
>
> What I am trying to evaluate here is whether or not
> a ten-fold improvement in the speed of STL will be
> worth the cost of providing this ten-fold improvement.
First, (again) your premise is flawed. If you choose the container that
best matches the performance requirements of the problem you've outlined,
you don't get a ten-fold improvement.
One thing you're going to find is that a poor choice of container will have
fairly severe consequences for the application.
> Many people whom write i/o bound applications
> programs thought that a hundred-fold increase in the
> speed of STL would not increase the speed of their
> application by as much as 1%. What I am looking
> for is a counter-example where a ten-fold increase
> in the speed of STL would result in at least doubling
> the speed of the application or system. I would
> guess that graphics might be such a case. What
> other cases might you be aware of?
Any application that isn't IO bound, and makes heavy use of the STL
containers. Here are a few examples I've dealt with:
(*) Custom iterators for my own containers. Doing something as simple
as optimising the comparison operator has produced two-fold speed increases.
(*) classes that make heavy use of vectors. The main issue here is that
element access must be very fast. Bounds checking is prohibitively slow.
The bottom line is, PROFILE, PROFILE, PROFILE. Find out what operations are
often used, and prove to be bottlenecks. Then make them as fast as possible,
and ignore everything else. Don't optimise things that are not *known* to
be bottlenecks. Profiling will often surprise you, because bottlenecks often
pop up in places you don't anticipate.
The "problem" is that popular versions of STL are for the most part fairly
well designed and implemented, and hence do not admit enormous performance
increases when used as intended. (Anyone can make a list look slow by
treating it as a vector, but we're ruling out that sort of thing)
Of course, if the containers are heavily used, then it's possible that even a
two-fold increase could speed up the application substantially.
At times, fine tuning a container can impact the performance constants,
and in such a situation, flexible policy based containers using the approach
proposed by Alexandrescu that allow client code to choose tradeoffs, instead
of
having to live with arbitrary choices of the library designer would prove
advantageous.
FYI, I think the biggest problem with STL at present is that
implementations tend to suffer from the classic "template bloat" problem.
As far as performance is concerned, I find the implementations do fairly
well.
--
Donovan
Gerry Quinn
>Many people whom write i/o bound applications
>programs thought that a hundred-fold increase in the
>speed of STL would not increase the speed of their
>application by as much as 1%. What I am looking
>for is a counter-example where a ten-fold increase
>in the speed of STL would result in at least doubling
>the speed of the application or system. I would
>guess that graphics might be such a case. What
>other cases might you be aware of?
A strategy game with a map based on vectors could end up suffering
badly from slow pathfinding, if the classes are inefficient. It could
also cause problems during development in debug mode, even if a lot of
function calls are optimised out in the release version.
I know this from painful experience with the MFC CArray collection class
in the game I'm working on now. Not STL, but the same considerations
would apply.
Gerry Quinn
--
http://bindweed.com
Puzzles, Arcade, Strategy, Kaleidoscope Screensaver
Download evaluation versions free - no time limits
Check out our new arcade-puzzler "Bubbler"!
John Potter
wrote:
> > On 8 Jan 2002 14:08:23 -0500, Carlos Moreno
> > <moreno_at_mo...@m.com> wrote:
> > >Well, I once tried a comparison between qsort and std::sort, for an
> > >array of doubles, to find that std::sort was 28 times faster than
> > >qsort. (with gcc/g++ 2.95, and I think I also tried with Borland
> > >C++ 5.5.1, but I'm not 100% sure right now...)
> > This is not surprising. I don't use C++ or std::sort but if I were
> > implementing std::sort I would use the best sort for datatype being
> > sorted. Distribution and radix sorts are markedly superior to GP
> > comparison sorts for sorting numbers (ints, floats, doubles).
> Actually, the speed advantage of std::sort typically comes from two places:
> 1. std::sort is typically implemented using IntroSort, which is faster than
> QuickSort for some important cases (like nearly sorted data).
Not really. The cases that IntroSort catches on a good median of three
quick sort are not these important ones. If we ignore the wierd special
cases where quick-med3 fails, it is faster than IntroSort.
> 2. std::sort is a template function, and typically is used with a template
> class as the compare object. This enables the compiler to inline the
> comparison into the sort. qsort(), on the other hand, is required to
> dispatch through a function pointer for each comparison.
Yes!
John
Karl Heinz Buchegger
Peter Olcott wrote:
>
> > So what does that mean? In practice, it means that you:
> > 1) Assume standard library components have adequate performance unless you
> > specifically know otherwise.
> > 2) Develop your code.
> > 3) Test your code for correctness.
> > 4) Profile your code.
> > 5) Address those performance areas which appear during profiling. If those
> > areas include Standard Library code, then you've identified one of those
> > cases you seek in your original question.
> >
> > Without going through steps 1-5, you cannot know the answer to your
> > question - the answer will be different for every application written.
>
> I have profiled some significant aspects of std::string and found it
> to be as much as 300-fold slower than nesscessary in some cases.
And guess what: In most applications, this simply doesn't matter.
Even if you could increase this specific operation by a factor
of 1000, then most applications out there will not be very much
faster. I said most, because undoubtly there are programs which could
benefit from this speed increase, but the majority will not.
There is only one way to figure out, if your program would
benefit: profile it!
> > Graphics applications are frequently CPU hungry, yes. Whether the
> > performance of the Standard Library is of any significance of course depends
> > on what the standard library was used for. If a 3D graphics application was
> > developed using std::vector<float> to represent points, it's likely that the
> > performance of std::vector would be important to the application. It's
> > also unlikely that an experienced graphics programmer would use std::vector
> > for such a purpose, so the significance of the example is minimal at best.
I wouldn't say so. std::vector is usually as fast as anything you can come
up by yourself. Getting fast graphics is seldom a question of having the
ultra fast container algorithms. It's much more a question of selecting
the right container for the job and applying the right geometrical trick
at the right time.
--
Karl Heinz Buchegger
kbuc...@gascad.at
Michiel Salters
says...
>Consider: if you used std::vector
>to store 3D points, you'll likely use 2x -3x the memory that you would
>storing them in a simple struct. You'd also lose all locality of reference
>benefits which would normally accrue to am implementation using arrays of
>simple structs.
Nonsense.
vector<Point> and Point[] store Point elements in the same way, such
that p[1]-p[0]==1. Ergo, the 'extra' memory use, if any, is spent in
keeping the size of vector and such things. Given that graphics usually
is about a lof of points, this difference is negligable. 1% is more
typical than 100%, and more than 100% memory overhead is basically the
case only with empty vectors.
And a real-world test showed that 'vector<Point>' was faster than
'new Point[]' (on my compiler, for my code, on my computer), which I
can only explain as a result of the allocator providing better locality
of reference when compared to the normal allocation functions.
Regards,
--
Michiel Salters
Consultant Technical Software Engineering
CMG Trade, Transport & Industry
Michiel...@cmg.nl
Richard Harter
wrote:
>
That would account for the difference. I had quite forgotten that the
library routine called qsort was that unlovely.
Richard Harter, c...@tiac.net,
http://www.tiac.net/users/cri, http://www.varinoma.com
Love, no matter how pure, is the most selfish of gifts.
For that reason it is the one gift that must be given.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Carl Daniel
"John Potter" <jpo...@falcon.lhup.edu> wrote in message
news:3c3d00de...@news.earthlink.net...
Fine. Next time I'll list them in the opposite order :) Of course #2 is by
far the more important one, in terms of performance impact.
-cd
Pete Becker
>
> On 9 Jan 2002 19:16:33 -0500, "Carl Daniel" <cpda...@pacbell.net>
> wrote:
>
> > 1. std::sort is typically implemented using IntroSort, which is faster
than
> > QuickSort for some important cases (like nearly sorted data).
>
> Not really. The cases that IntroSort catches on a good median of three
> quick sort are not these important ones. If we ignore the wierd special
> cases where quick-med3 fails, it is faster than IntroSort.
>
Right. Introsort's switch to heapsort when quicksort goes bad is like
deploying airbags in an automobile accident: you're better off if it
doesn't happen.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Klaus-Georg Adams
> In what cases would a significant difference in the speed of the
> Standard Template Library make a significant difference in
> overall system performance? The one case that comes to mind
> for me would be graphics intensive applications. This is the
> case that SGI STL was developed for.
> http://www.sgi.com/tech/stl/
IMHO it would make a significant difference in overall system
performance if the profiler tells you so. Everything else is just
guesswork and thus (again IMVHO) pointless.
--
Regards, kga
Peter Olcott
> implemented his own heap manager because he was concerned about the
> performance of malloc and ::operator new shipped with the compiler
> (which was at the time MSVC 1.0 or something like that). He then
> wrote a toy app that just did a bunch of allocations and deletions
> and, sure enough, his very simple heap was quite a bit faster -- as
> in N times faster, for some value of N which I don't remember. :-)
>
> Now comes the interesting part. He proceded to use his "faster"
> heap in a real application, and several months later a different
> programmer decided to run his own test. He built two versions of
> the application, one using the "fast" heap and one using the
> standard heap, and -- you guessed it! -- the version that used
> the standard heap provided with the compiler ran faster.
>
> How do I account for this difference? Perhaps the standard heap
> produced better locality of reference, such that the app as a whole
> ran faster (due to fewer cache misses) even though the allocations
> themselves were slower (due to a more complicated algorithm). Or
> perhaps the performance of the simpler allocater degraded over
> time due to fragmentation. I don't know, but it does suggest that
> one must be cautious about inferring too much from simple
> benchmarks.
A really good heap manager is far from trivial. I have a system
nearly fully developed that can allocate, deallocate, and reallocate
all in constant time. But back to the point what is the set of
CPU intensive software that you can derive?
(1) Graphics
(2) Operating Systems
From this above set I will attempt to estimate if any of
this stuff could benefit from a much faster STL.
Carl Daniel
news:PEd%7.11372$cD4....@www.newsranger.com...
> In article <Xv2%7.26981$pT3.229...@newssvr21.news.prodigy.com>, Carl
Daniel
> says...
> >Consider: if you used std::vector
> >to store 3D points, you'll likely use 2x -3x the memory that you would
> >storing them in a simple struct. You'd also lose all locality of
reference
> >benefits which would normally accrue to am implementation using arrays
of
> >simple structs.
>
> Nonsense.
>
Non-nonsense. You failed to realize the difference between the two cases I
outlined.
Using std::vector<float>, consistently sized at 3 to store points would be
A) highly dependent on the performance of vector, and B) a very bad design.
Using std::vector<Point> would probably not be very sensitive to the
performance of vector (other than operator[](), which is difficult to
imagine being slow in any non-malicious implementation).
> And a real-world test showed that 'vector<Point>' was faster than
> 'new Point[]' (on my compiler, for my code, on my computer), which I
> can only explain as a result of the allocator providing better locality
> of reference when compared to the normal allocation functions.
Perhaps. Perhaps your standard library uses a better std::allocator than
::operator new() (e.g. the SGI node allocator used in STLPort).
-cd
Donovan Rebbechi
> In article <Xv2%7.26981$pT3.229...@newssvr21.news.prodigy.com>, Carl
> Daniel says...
> >Consider: if you used std::vector to store 3D points, you'll likely use 2x
> >-3x the memory that you would storing them in a simple struct. You'd also
> >lose all locality of reference benefits which would normally accrue to am
> >implementation using arrays of simple structs.
>
> Nonsense.
>
> vector<Point> and Point[] store Point elements in the same way, such
> that p[1]-p[0]==1.
But std::vector aggressively allocates. This is necessary to guarantee fast
appends. This could result in a substantial amount of waste. If you don't
need to reallocate very often, std::vector is not a good choice of container.
> Ergo, the 'extra' memory use, if any, is spent in
> keeping the size of vector and such things.
No, the eager allocation strategy also potentially uses extra memory.
It is worth mentioning that vector simply is not designed to model
computational vectors. Its intended use is as a flexible dynamic array
class.
C++ provides the valarray facility for computation.
--
Donovan
Peter Olcott
> badly from slow pathfinding, if the classes are inefficient. It could
> also cause problems during development in debug mode, even if a lot of
> function calls are optimised out in the release version.
>
> I know this from painful experience with the MFC CArray collection class
> in the game I'm working on now. Not STL, but the same considerations
> would apply.
>
> Gerry Quinn
question thanks. How does a CArray compare to a standard
<vector>, and why did you choose it over standard <vector>?
Peter Olcott
> deploying airbags in an automobile accident: you're better off if it
> doesn't happen.
Quick sort only really has problems when the data is
already sorted or nearly sorted, right ? Is there a
C++ version of quick sort that will be able to inline
its code, and my comparison code ?
Gerry Quinn
"Peter Olcott" <olc...@worldnet.att.net> wrote:
>> A strategy game with a map based on vectors could end up suffering
>> badly from slow pathfinding, if the classes are inefficient. It could
>> also cause problems during development in debug mode, even if a lot of
>> function calls are optimised out in the release version.
>>
>> I know this from painful experience with the MFC CArray collection class
>> in the game I'm working on now. Not STL, but the same considerations
>> would apply.
>>
>question thanks. How does a CArray compare to a standard
> <vector>, and why did you choose it over standard <vector>?
Just familiarity. I've used MFC CList classes extensively and they work
well and efficiently. Up to now I've mostly used simple arrays. I
might well end up doing the same again this time - one of the design
reasons pushing vector classes has already been rethought and found
wanting...
I haven't really explored STL much, but I would assume that the vector
class will suffer from much the same ills as CArray.
Gerry Quinn
--
http://bindweed.com
Puzzles, Arcade, Strategy, Kaleidoscope Screensaver
Download evaluation versions free - no time limits
Check out our new arcade-puzzler "Bubbler"!
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
James Kanze
news:<slrna3s0dh....@panix2.panix.com>...
> But std::vector aggressively allocates. This is necessary to
> guarantee fast appends. This could result in a substantial amount of
> waste. If you don't need to reallocate very often, std::vector is
> not a good choice of container.
It depends on what you're doing. I use vector in a lot of cases where
I never reallocate. It's still the standard container.
If performance is critical, I don't need the reallocation features,
and the size is known at compile time, I have a static array class
where the size is a template parameter, which does no dynamic
allocation, ever. But unless the performance is really critical, I'll
stick to the standard class even in such cases, simply because my
reader presumably knows the ins and outs of the standard class, but
doesn't know them for my special, optimized class. (This isn't 100%
true; valarray is standard, but neither I nor any of my collegues have
ever used one:-).)
--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique orientée objet
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany, Tél.: +49 (0)69 19 86 27
Francis Glassborow
<hHv%7.348927$W8.13...@bgtnsc04-news.ops.worldnet.att.net>, Peter
Olcott <olc...@worldnet.att.net> writes
>Quick sort only really has problems when the data is
>already sorted or nearly sorted, right ? Is there a
>C++ version of quick sort that will be able to inline
>its code, and my comparison code ?
It has one other potentially fatal flaw, it is not a stable sort (i.e.
it makes no guarantees as to the ordering of elements that compare
equal). BTW despite its name, there is no requirement that qsort()
implement a quick sort. Indeed C places no performance requirements on
any part of its library.
--
Francis Glassborow
The Seasons best wishes to you and yours. May 2002 be better for all of us
than
2001 was for some.
Andrew Koenig
Peter> already sorted or nearly sorted, right ?
Wrong.
If quicksort is implemented correctly, it has no particular
problem with data that are already almost sorted. However,
every implementation of quicksort has some bad cases that
will engender quadratic behavior.
For details, see www.cs.dartmouth.edu/~doug/mdmspe.pdf
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark
Jerry Coffin
news.ops.worldnet.att.net>, olc...@worldnet.att.net says...
[ ... ]
> Quick sort only really has problems when the data is
> already sorted or nearly sorted, right ? Is there a
> C++ version of quick sort that will be able to inline
> its code, and my comparison code ?
Not really -- Quicksort has a problem anytime you choose a pivot
that's (nearly) the smallest or largest item in the collection. It
happens that if a collection is sorted, the first and last item
(which could otherwise be obvious choices) end up being provoking the
worst case. If (for example) you use the typical median of three
pivot selection (and, by preference sort the three you choose from
before you sort the rest of the collection) the order that produces
the worst case is more complex, and the worst case isn't _quite_ as
bad (you can't ever select the absolute worst pivot -- only the
second worst).
Nonetheless, the basic fact of the matter is that to know you're
choosing the ideal pivot, the collection has to already be sorted.
If you use a median of N selection, then the worst case is that you
chose the [N/2] worst possible pivot -- IOW, it makes little
difference in the worst case as long as N is small (and if N is
large, you're left with the recursive problem of sorting the N
elements to find the median...)
--
Later,
Jerry.
The Universe is a figment of its own imagination.
Pete Becker
>
> > Right. Introsort's switch to heapsort when quicksort goes bad is like
> > deploying airbags in an automobile accident: you're better off if it
> > doesn't happen.
>
> Quick sort only really has problems when the data is
> already sorted or nearly sorted, right ?
>
Quicksort has problems when it has problems. Simple implementations of
quicksort run into problems with nearly sorted data. More sophisticated
implementations run into problems with more sophisticated data layouts.
The worst possible approach to designing containers is to guess at
sweeping generalities. If you haven't measured it you don't understand
it.
> Is there a
> C++ version of quick sort that will be able to inline
> its code, and my comparison code ?
Every implementation of std::sort that I'm aware of inlines its code and
the comparison function if it's properly written.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
David Schwartz
> It has one other potentially fatal flaw, it is not a stable sort (i.e.
> it makes no guarantees as to the ordering of elements that compare
> equal).
There is no guarantee one could possibly make in that case. If they
compare equal, they are indisinguishable. Give me an example of what
might be a guarantee that would make sense.
DS
Donovan Rebbechi
> Donovan Rebbechi <elf...@panix.com> wrote in message
> news:<slrna3s0dh....@panix2.panix.com>...
>
>> But std::vector aggressively allocates. This is necessary to
>> guarantee fast appends. This could result in a substantial amount of
>> waste. If you don't need to reallocate very often, std::vector is
>> not a good choice of container.
>
> It depends on what you're doing. I use vector in a lot of cases where
> I never reallocate. It's still the standard container.
I agree with your point. The context of the discussion was using vectors
for fixed-dimension points in numerical computing, and in this situation,
I wouldn't use them.
Another place where I wouldn't use vector is to implement large matrices.
In this case, memory waste is the main concern.
> If performance is critical, I don't need the reallocation features,
> and the size is known at compile time, I have a static array class
> where the size is a template parameter, which does no dynamic
> allocation, ever.
This also works well, especially for the given example of modelling
n-dimensional points.
> doesn't know them for my special, optimized class. (This isn't 100%
> true; valarray is standard, but neither I nor any of my collegues have
> ever used one:-).)
valarray is a fairly specialised class, it's not a general purpose, unlike
<vector>
--
Donovan
Pete Becker
>
> If (for example) you use the typical median of three
> pivot selection (and, by preference sort the three you choose from
> before you sort the rest of the collection) the order that produces
> the worst case is more complex, and the worst case isn't _quite_ as
> bad (you can't ever select the absolute worst pivot -- only the
> second worst).
>
Just to put a period on that statement: although it has a somewhat
smaller mulitplier, the worst case is still O(n^2).
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Adam Peterson
"David Schwartz" <dav...@webmaster.com> wrote in message
news:3C3F8C89...@webmaster.com...
> Francis Glassborow wrote:
>
> > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > it makes no guarantees as to the ordering of elements that compare
> > equal).
>
> There is no guarantee one could possibly make in that case. If they
> compare equal, they are indisinguishable. Give me an example of what
> might be a guarantee that would make sense.
Stability is a known property of sorts, which some have and others don't.
It is important when you have values that compare equal but nonetheless have
different behaviors. Bubble sort is stable. Radix sort is stable. If A
and B have keys that compare equal, then the relative ordering of A and B
will not change after performing these sorts (or any other stable sort).
One use for this as an example is if you have an object with two properties
and you wish to sort them by one property, and within equality on that
property, then by the second property. One way to implement this is by
sorting on the second property, and then using a stable sort to sort on the
first property. (Fundamentally, this is how Radix sort works.)
Naturally in this instance, you could simply create a predicate that
compared both keys to give the proper ordering. But there are times when
this is undesirable or impossible. For example, if you have a container
where items are always appended at the end, you may want to sort such a
container, but have all objects with the same key left in the order they
were appended. If you use a stable sort, you get this for free. If not,
you have to find an elaborate workaround.
This is only one example. Often you don't care about stability in a sort.
But for the times when you do, it's nice to have the option.
Adam Peterson
tom_usenet
<olc...@worldnet.att.net> wrote:
>> Right. Introsort's switch to heapsort when quicksort goes bad is like
>> deploying airbags in an automobile accident: you're better off if it
>> doesn't happen.
>
>Quick sort only really has problems when the data is
>already sorted or nearly sorted, right ? Is there a
>C++ version of quick sort that will be able to inline
>its code, and my comparison code ?
Rather than trying to guess what to use why don't you benchmark the
code using qsort with a comparison function vs using std::sort with a
comparison functor?
Tom
David Schwartz
> > There is no guarantee one could possibly make in that case. If they
> > compare equal, they are indisinguishable. Give me an example of what
> > might be a guarantee that would make sense.
> Stability is a known property of sorts, which some have and others don't.
> It is important when you have values that compare equal but nonetheless have
> different behaviors. Bubble sort is stable. Radix sort is stable. If A
> and B have keys that compare equal, then the relative ordering of A and B
> will not change after performing these sorts (or any other stable sort).
In other words, A and B never compare equal. Remember, you write the
compare function, so you can easily assure that it never returns
equality.
> One use for this as an example is if you have an object with two properties
> and you wish to sort them by one property, and within equality on that
> property, then by the second property. One way to implement this is by
> sorting on the second property, and then using a stable sort to sort on the
> first property. (Fundamentally, this is how Radix sort works.)
Another way to do this is to write the comparison function correctly.
> Naturally in this instance, you could simply create a predicate that
> compared both keys to give the proper ordering. But there are times when
> this is undesirable or impossible. For example, if you have a container
> where items are always appended at the end, you may want to sort such a
> container, but have all objects with the same key left in the order they
> were appended. If you use a stable sort, you get this for free. If not,
> you have to find an elaborate workaround.
I think it's elegant that if you never want to consider two objects as
equal, you never compare them as equal.
> This is only one example. Often you don't care about stability in a sort.
> But for the times when you do, it's nice to have the option.
That's just it, you do have the option. Nobody is forcing you to ever
return equality.
DS
John Potter
wrote:
> Francis Glassborow wrote:
>
> > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > it makes no guarantees as to the ordering of elements that compare
> > equal).
>
> There is no guarantee one could possibly make in that case. If they
> compare equal, they are indisinguishable. Give me an example of what
> might be a guarantee that would make sense.
The guarantee that makes sense is stable. That means that equal items
retain their relative order after sorting. See stable_sort and
list::sort. Remember that the order relation used for sorting by a
key field induces an equivalence relation which need not be the
equivalence relation (operator==) for the items.
John
Mike Wahler
>
> > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > it makes no guarantees as to the ordering of elements that compare
> > equal).
>
> There is no guarantee one could possibly make in that case. If they
> compare equal, they are indisinguishable. Give me an example of what
> might be a guarantee that would make sense.
The comparison might be against a struct member, the
other members of which might be 'unequal', moving
data that perhaps wasn't meant to be moved.
-Mike
Pete Becker
>
> Francis Glassborow wrote:
>
> > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > it makes no guarantees as to the ordering of elements that compare
> > equal).
>
> There is no guarantee one could possibly make in that case. If they
> compare equal, they are indisinguishable. Give me an example of what
> might be a guarantee that would make sense.
>
A stable sort is one in which elements that compare equal in the sort
come out in the same relative order after the sort as they were before
it. For elements like ints this doesn't matter. For more complex types
it makes a difference, because elements that differ can still compare
equal for purposes of sorting. E-mail programs, for example, should use
stable sorts. That way you can sort by date, then sort by name, and
messages from the same person will be in order by date.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
wrote:
> In other words, A and B never compare equal. Remember, you write the
> compare function, so you can easily assure that it never returns
> equality.
You don't write the data. The secondary key is the original position
in the container. Some sorts are stable and some are not. If
stability is important, you do not use an unstable sort. If it were
not important, the standard library would not include both.
Here is a simple silly example.
typedef pair<int,int> Item;
struct MineComp {
bool operator() (Item const& lhs, Item const& rhs) {
return lhs.first < rhs.first;
}
};
struct SchwartzComp {
bool operator() (Item const& lhs, Item const& rhs) {
return // Fill this in, you get to write it.
}
};
Item gen () {
return Item(rand() % 100, rand());
}
int main () {
vector<Item> v1;
generate_n(back_inserter(v1), 1000, gen);
vector<Item> v2(v1);
stable_sort(v1.begin(), v1.end(), MineComp());
sort(v2.begin(), v2.end(), SchwartzComp());
assert(equal(v1.begin(), v1.end(), v2.begin()));
}
It is sometimes possible to stabilize an unstable sort by adding a time
stamp to the item, but that is not a general solution.
John
Francis Glassborow
<dav...@webmaster.com> writes
> That's just it, you do have the option. Nobody is forcing you to ever
>return equality.
I can only assume that you do not do much work with databases. Consider
a case where I have access to a database of 1 million names (family
name, personal name) with their dates of birth. The database is
currently organised by date of birth. I now want to sort the data
alphabetically by name. However I want people with the same name to be
listed in order of age. Your method now requires that I write a special
purpose comparison function (with plenty of room for getting it wrong -
thereby costing me time). However if I simply use a sort that is
classified as stable, I can almost certainly use STL defaults. Which
approach do you think will reach my target faster? More reliably?
We often compare complex objects for equality on the basis of a single
attribute and those that regularly deal with algorithms know exactly
what is meant by 'compare equal' and do not confuse that with 'identity'
or even 'equivalence' of the objects, only of an attribute.
--
Francis Glassborow
The Seasons best wishes to you and yours. May 2002 be better for all of us
than
2001 was for some.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> > Right. Introsort's switch to heapsort when quicksort goes bad is like
> > deploying airbags in an automobile accident: you're better off if it
> > doesn't happen.
>
> Quick sort only really has problems when the data is
> already sorted or nearly sorted, right ?
>
Quicksort has problems when it has problems. Simple implementations of
quicksort run into problems with nearly sorted data. More sophisticated
implementations run into problems with more sophisticated data layouts.
The worst possible approach to designing containers is to guess at
sweeping generalities. If you haven't measured it you don't understand
it.
> Is there a
> C++ version of quick sort that will be able to inline
> its code, and my comparison code ?
Every implementation of std::sort that I'm aware of inlines its code and
the comparison function if it's properly written.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
========= WAS CANCELLED BY =======:
Path: news.uni-stuttgart.de!dns.phoenix-ag.de!newsfeed01.sul.t-online.de!t-online.de!fr.clara.net!heighliner.fr.clara.net!newsgate.cistron.nl!amsnews01.chello.com!amsnews02.chello.com.POSTED!u-n-a-cancel
Message-ID: <cancel.3C3F8...@acm.org>
Control: cancel <3C3F8BBE...@acm.org>
Subject: cmsg cancel <3C3F8BBE...@acm.org>
From: Pete Becker <peteb...@acm.org>
Newsgroups: alt.test,comp.lang.c++
Lines: 2
Date: Sat, 12 Jan 2002 03:06:17 GMT
NNTP-Posting-Host: 212.186.189.190
X-Complaints-To: ab...@chello.com
X-Trace: amsnews02.chello.com 1010804777 212.186.189.190 (Sat, 12 Jan 2002 04:06:17 MET)
NNTP-Posting-Date: Sat, 12 Jan 2002 04:06:17 MET
Organization: chello broadband
Xref: news.uni-stuttgart.de control:40511767
autocancel
David Schwartz
> It has one other potentially fatal flaw, it is not a stable sort (i.e.
> it makes no guarantees as to the ordering of elements that compare
> equal).
There is no guarantee one could possibly make in that case. If they
compare equal, they are indisinguishable. Give me an example of what
might be a guarantee that would make sense.
DS
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
========= WAS CANCELLED BY =======:
Path: news.uni-stuttgart.de!dns.phoenix-ag.de!newsfeed01.sul.t-online.de!t-online.de!fr.clara.net!heighliner.fr.clara.net!newsgate.cistron.nl!amsnews01.chello.com!amsnews02.chello.com.POSTED!u-n-a-cancel
Message-ID: <cancel.3C3F8...@webmaster.com>
Control: cancel <3C3F8C89...@webmaster.com>
Subject: cmsg cancel <3C3F8C89...@webmaster.com>
From: David Schwartz <dav...@webmaster.com>
Newsgroups: alt.test,comp.lang.c++
Lines: 2
Date: Sat, 12 Jan 2002 03:06:13 GMT
NNTP-Posting-Host: 212.186.189.190
X-Complaints-To: ab...@chello.com
X-Trace: amsnews02.chello.com 1010804773 212.186.189.190 (Sat, 12 Jan 2002 04:06:13 MET)
NNTP-Posting-Date: Sat, 12 Jan 2002 04:06:13 MET
Organization: chello broadband
Xref: news.uni-stuttgart.de control:40511747
autocancel
David Schwartz
> > That's just it, you do have the option. Nobody is forcing you to ever
> >return equality.
> I can only assume that you do not do much work with databases.
I certainly do.
> Consider
> a case where I have access to a database of 1 million names (family
> name, personal name) with their dates of birth. The database is
> currently organised by date of birth. I now want to sort the data
> alphabetically by name. However I want people with the same name to be
> listed in order of age. Your method now requires that I write a special
> purpose comparison function (with plenty of room for getting it wrong -
> thereby costing me time). However if I simply use a sort that is
> classified as stable, I can almost certainly use STL defaults. Which
> approach do you think will reach my target faster? More reliably?
You are assuming the existence of a comparison function and you are
assuming that the comparison function doesn't have the semantics you
need. So you make the sort function more complex to work around the
limitations of a comparison function that exists only because you
assumed it. Why not assume the existence of a comparison function that
is stable and a that way you can have a faster, more efficient sort
because it doesn't try to provide stability to programs that don't need
it.
> We often compare complex objects for equality on the basis of a single
> attribute
This is inappropriate if you want a stable sort. So if you want a
stable sort, don't do that.
> and those that regularly deal with algorithms know exactly
> what is meant by 'compare equal' and do not confuse that with 'identity'
> or even 'equivalence' of the objects, only of an attribute.
I would not describe two different records as "comparing equal" unless
I considered them interchangeable. This is a very bad choice of
language.
DS
David Schwartz
> > There is no guarantee one could possibly make in that case. If they
> > compare equal, they are indisinguishable. Give me an example of what
> > might be a guarantee that would make sense.
> >
> A stable sort is one in which elements that compare equal in the sort
> come out in the same relative order after the sort as they were before
> it. For elements like ints this doesn't matter. For more complex types
> it makes a difference, because elements that differ can still compare
> equal for purposes of sorting. E-mail programs, for example, should use
> stable sorts. That way you can sort by date, then sort by name, and
> messages from the same person will be in order by date.
I think you're missing my point. If you want a stable sort, then when
you might return equal, return a value based upon which is currently
before the other.
There should be no such thing as "elements that compare equal" in a
stable sort. In a stable sort, no two elements are ever equal.
DS
Tom Plunket
read clc++ also?
Donovan Rebbechi wrote:
> Another place where I wouldn't use vector is to implement large matrices.
> In this case, memory waste is the main concern.
Exactly; that's the sort of thing that valarray is perfect for.
Especially when combined with the power of slice and gslice,
well, it's really slick and only as much overhead as a single
vector (if that)...
> > doesn't know them for my special, optimized class. (This isn't 100%
> > true; valarray is standard, but neither I nor any of my collegues have
> > ever used one:-).)
>
> valarray is a fairly specialised class, it's not a general purpose, unlike
> <vector>
valarray, in my experience, can trivially be used as a fixed-size
vector. Reinventing the wheel doesn't save time for anyone. :)
-tom!
--
Tom Plunket to...@fancy.org
PlayStation2/3D Studio geek
Few people realize that pieces of coral, when
painted brown and attached to the skull with wood
screws, can make a child look like a deer.
Tom Plunket
> A strategy game with a map based on vectors could end up suffering
> badly from slow pathfinding, if the classes are inefficient.
What if the map was based on some other structure and the classes
were inefficient? What if the map was based on vectors but the
classes were terribly efficient?
> It could also cause problems during development in debug mode,
> even if a lot of function calls are optimised out in the release
> version.
MFC might cause problems during development in debug mode, but
the Standard Library acts exactly the same way.
> I know this from painful experience with the MFC CArray
> collection class in the game I'm working on now. Not STL, but
> the same considerations would apply.
If we all agreed that the Standard Library were the same sort of
crap that MS is peddling as "Foundation Classes," you're right.
We'd be in trouble. Fortunately, we aren't. :)
David Schwartz
> The guarantee that makes sense is stable. That means that equal items
> retain their relative order after sorting. See stable_sort and
> list::sort. Remember that the order relation used for sorting by a
> key field induces an equivalence relation which need not be the
> equivalence relation (operator==) for the items.
If they have a "relative order" then they aren't equal.
DS
David Schwartz
> > There is no guarantee one could possibly make in that case. If they
> > compare equal, they are indisinguishable. Give me an example of what
> > might be a guarantee that would make sense.
> The comparison might be against a struct member, the
> other members of which might be 'unequal', moving
> data that perhaps wasn't meant to be moved.
First of all, your comparison function compares the structures, not "a
struct member". If two objects are unequal and you returned an equal
indication from your comparison function, then your comparison function
is broken.
If two structures are not equal and your comparison function says they
are equal, you are lying to the sorter. If they really are equal, they
are indistinguishable, and there's no difference whether you move one or
not.
DS
Adam Peterson
> > attribute
>
> This is inappropriate if you want a stable sort. So if you want a
> stable sort, don't do that.
I would say, if you want a stable sort, use a stable sorting algorithm.
There are sorts that by their very nature provide stability. When using
such a sort, you can rely on this property, and it is often easier to
formulate the comparison predicate. This is not a minus.
If you insist on using an unstable sort, this is your choice. This is fine,
and may be a choice that I might make similarly. You have to weigh the pros
and cons of a perhaps less than ideal (but often asymptotically comparable)
sort with a potentially ugly comparison function (especially if there's
nothing in the object that indicates its relative ordering in the list).
There are pros and cons, and weighing these is part of any software
engineer's job.
Just like many other types of algorithms, sorting algorithms have
mathematical properties that when using them you can count on. Examples of
such properties are: expected time complexity, worst case time complexity,
expected/worst case number of exchanges/moves/compares, stability, etc. You
choose an algorithm that has the properties that your design calls for.
(This is as true for sorting as it is for any other class of algorithms.)
Or, in the case of the language standard, you chose the algorithm or
function that provides the guarantees that your design calls for. You can
either design so that stability is not an issue, or you can choose an
algorithm/function where stability is guaranteed.
Perhaps I don't understand your objection to stability.
Donovan Rebbechi
> Adam Peterson wrote:
> Another way to do this is to write the comparison function
correctly.
What do you mean by "correctly" ? There's nothing "incorrect" about an
order that cannot distinguish between all elements of a given set.
Not only does your definition of "correct" make little sense, it's also
not terribly useful. To require this makes code more confusing, because
it obscures intent (maybe I only *want* to sort by name, and simply don't
care about other fields), and forces the code to do more work.
> I think it's elegant that if you never want to consider two objects
> as equal, you never compare them as equal.
The notion of "compare them as equal" is bogus, and it appears that you are
using loaded language upfront to jump to your conclusion (that "all orders
should be anti-symmetric"). They are not "compared as equal", they are merely
indistinguishable to the chosen order.
The property of anti-symmetry is certainly useful in some settings (indeed,
it's part of the definition of a partial order), but it is not necessary to
perform a sort, or even a stable sort.
--
Donovan
Donovan Rebbechi
> Pete Becker wrote:
>> A stable sort is one in which elements that compare equal in the sort
>> come out in the same relative order after the sort as they were before
>> it. For elements like ints this doesn't matter. For more complex types
>> it makes a difference, because elements that differ can still compare
>> equal for purposes of sorting. E-mail programs, for example, should use
>> stable sorts. That way you can sort by date, then sort by name, and
>> messages from the same person will be in order by date.
>
> I think you're missing my point. If you want a stable sort, then when
> you might return equal,
Again, this notion of "return equal" only makes sense if you assume
anti-symmetry. Since the merits of anti-symmetry are the topic of discussion,
your persistent use of this misleading terminology strikes me as a
transparent attempt to manipulate the debate with linguistic sophistry.
Why you consider it necessary that all comparisons be anti-symmetric escapes
reason.
> return a value based upon which is currently
> before the other.
But that's an intrusive design, because it requires the class designer to
"build in" an order parameter.
> There should be no such thing as "elements that compare equal" in a
There is no such thing as "elements that compare equal", unless you have an
anti-symmetric comparison.
--
Donovan
Donovan Rebbechi
> assuming that the comparison function doesn't have the semantics you
> need.
It's a hypothetical. He's allowed to assume that.
> So you make the sort function more complex to work around the
> limitations of a comparison function that exists only because you
> assumed it. Why not assume the existence of a comparison function that
> is stable and a that way you can have a faster, more efficient sort
> because it doesn't try to provide stability to programs that don't need
> it.
This is where pragmatism kicks in. The fact is that it's easier to write
a generic sort function than it is to write a generic comparison function.
You can't just assume comparison functions into existence, they need to
be written on a case by case basis. In contrast, the sorting algorithm only
needs to be implemented once. It simply makes more sense to put *more* work
into the code that is more likely to be reused.
>> We often compare complex objects for equality on the basis of a single
>> attribute
>
> This is inappropriate if you want a stable sort. So if you want a
> stable sort, don't do that.
It's easier to do it that way. That in itself strikes me as being a perfectly
good reason to do that.
> I would not describe two different records as "comparing equal" unless
> I considered them interchangeable. This is a very bad choice of
> language.
This I agree with.
--
Donovan
Homer Meyer
> Pete Becker wrote:
>
> > > There is no guarantee one could possibly make in that case. If
they
> > > compare equal, they are indisinguishable. Give me an example of what
> > > might be a guarantee that would make sense.
> > >
>
> > A stable sort is one in which elements that compare equal in the sort
> > come out in the same relative order after the sort as they were before
> > it. For elements like ints this doesn't matter. For more complex types
> > it makes a difference, because elements that differ can still compare
> > equal for purposes of sorting. E-mail programs, for example, should use
> > stable sorts. That way you can sort by date, then sort by name, and
> > messages from the same person will be in order by date.
>
> I think you're missing my point. If you want a stable sort, then when
> you might return equal, return a value based upon which is currently
> before the other.
That wouldn't prevent a non-stable sort from getting the elements out of
order. Take a typical quicksort that uses "median of three" to determine
the pivot. The implementation looks at the first, last, and middle
elements, and chooses the median of the three for the pivot. It then swaps
this median element with the last element. Now, suppose the first two
elements before the sort had been equal on the sort key. Let's call the two
elements A and B respctively. Before the sort they are in order "AB".
Suppose the first pivot chosen is the first element. After swapping with
the last element, the relative order of these two elements is "BA". Your
comparison algorithm would not have changed the result.
Tom Plunket
> You are assuming the existence of a comparison function and you are
> assuming that the comparison function doesn't have the semantics you
> need. So you make the sort function more complex to work around the
> limitations of a comparison function that exists only because you
> assumed it. Why not assume the existence of a comparison function that
> is stable and a that way you can have a faster, more efficient sort
> because it doesn't try to provide stability to programs that don't need
> it.
Why not? What is equality? What does it mean to sort things?
Maybe what it means to sort names in the phone book is to sort
them based on Last Name, First Name. That two names compare
equal does not imply that the records are themselves equivalent,
it just means that in the sort that you are currently doing that
the order of the two (or more) items that compare equal is
indeterminant.
It just seems naive to me to say, "why would you ever need that?"
Who cares if *you* can see a need for something? The fact
remains that other people have perfectly valid reasons for
wanting something, and often coming up with a comparison function
to guarantee stability is considerably more work (for the
programmer and the computer) than just having an easy comparison
function and knowing that the sort algorithm is stable.
> > We often compare complex objects for equality on the basis of a
> > single attribute
>
> This is inappropriate if you want a stable sort. So if
> you want a stable sort, don't do that.
Oh, the words came down from on high, they must be true!
> I would not describe two different records as "comparing
> equal" unless I considered them interchangeable.
You'd be correct in that statement. Where you are wholly off
target is by asserting that people shouldn't ever need some
facility that has been researched and used for many years simply
because it doesn't live up to some golden standards. Hey- I live
in the real world. If I come up to legacy data and need to write
software to do a sort, and if I need the sort to be stable but
there's nothing in the record data that I can use to guarantee
that during the sort stability is maintained, I'm not going to
tell the client that I won't work on the problem- I'll just whip
up a solution using the tools at my disposal.
Tom Plunket
> There should be no such thing as "elements that compare
> equal" in a stable sort. In a stable sort, no two elements are
> ever equal.
Ahh- now you understand. Good show. I'm glad that "the point"
of stable sorts is now fully understood.
-tom!
--
Tom Plunket to...@fancy.org
PlayStation2/3D Studio geek
Few people realize that pieces of coral, when
painted brown and attached to the skull with wood
screws, can make a child look like a deer.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Donovan Rebbechi
> John Potter wrote:
>
>> The guarantee that makes sense is stable. That means that equal items
>> retain their relative order after sorting. See stable_sort and
>> list::sort. Remember that the order relation used for sorting by a
>> key field induces an equivalence relation which need not be the
>> equivalence relation (operator==) for the items.
>
> If they have a "relative order" then they aren't equal.
Relative order is a property of the state of the container, not the items
it contains.
--
Donovan
Donovan Rebbechi
> Mike Wahler wrote:
>
>> > There is no guarantee one could possibly make in that case. If they
>> > compare equal, they are indisinguishable. Give me an example of what
>> > might be a guarantee that would make sense.
>
>> The comparison might be against a struct member, the
>> other members of which might be 'unequal', moving
>> data that perhaps wasn't meant to be moved.
>
> First of all, your comparison function compares the structures, not "a
> struct member". If two objects are unequal and you returned an equal
> indication from your comparison function, then your comparison function
> is broken.
It is not broken. You assume without justification that all comparisons must
be antisymmetric.
Here, I will attempt to explain why I think we should allow asymmetry.
> If two structures are not equal and your comparison function says they
> are equal, you are lying to the sorter.
No you are not. The sorter does not require the comparison function to
decide whether two elements are equal.
Here is a practical reason why one might want stable sorts.
Suppose you have a structure with several fields, say 10. I can write 10
comparison operators, for example:
bool compare (object&x,object& y){ return x.age < y.age; }
in fact if I'm smart about it, I could use mem_fun_ref to get comparisons
with any fields (if it's a class)
template <class obj, class member_function> struct compare_field
{ ..... }
and client code can then easily sort by any criteria.
But to do it your way, you would need to write 10 factorial different
comparisons, and each of those would be 10 times as long.
The advantage of separating these sorts is that when you take the stable
approach, you are factoring code into operations that are in a sense more
atomic. This leads to functions that have a clearer purpose (ie don't
try to do too much), and it offers more flexibility. For example,
my way, I could sort be age and weight, age only, or height, then weight,
then age without doing any more than calling sort functions in different
orders.
--
Donovan
David Schwartz
> That wouldn't prevent a non-stable sort from getting the elements out of
> order. Take a typical quicksort that uses "median of three" to determine
> the pivot. The implementation looks at the first, last, and middle
> elements, and chooses the median of the three for the pivot. It then swaps
> this median element with the last element. Now, suppose the first two
> elements before the sort had been equal on the sort key. Let's call the two
> elements A and B respctively. Before the sort they are in order "AB".
> Suppose the first pivot chosen is the first element. After swapping with
> the last element, the relative order of these two elements is "BA". Your
> comparison algorithm would not have changed the result.
There's the point that demolishes my argument! Thank you. I now see the
error of my ways.
One could, hypothetically, write a comparison function that, where it
would normally return equal will return which one came first before the
sort began. But that is definitely too much work to expect in a
comparison function.
I still think that if you're only going to have one sort function built
generically, it should be a non-stable sort. Stability is not required
often enough to justify the overhead. Of course, if you can make a sort
stable without compromising performance, then you certainly should.
DS
Carl Daniel
> Francis Glassborow wrote:
>
> > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > it makes no guarantees as to the ordering of elements that compare
> > equal).
>
> There is no guarantee one could possibly make in that case. If they
> compare equal, they are indisinguishable. Give me an example of what
> might be a guarantee that would make sense.
>
That their relative order within the container is not changed by the sort.
If A is equivalent to B and if A preceeded B before the sort, A must preceed
B after the sort. That is what is meant by a stable sort.
You're still overlooking the fact that the comparison being performed may
not examine the entirety of the objects being compared - it may examine only
a single field.
struct person
{
std::string m_name;
long m_birthdate;
};
struct person_name_order
{
bool operator ()(const person& lhs, const person& rhs) const
{
return lhs.m_name < rhs.m_name;
}
};
struct person_age_order
{
bool operator ()(const person& lhs, const person& rhs) const
{
return lhs.m_birthdate < rhs.m_birthdate;
}
};
vector<person> vp;
// insert some persons into vp
std::sort(vp.begin(),vp.end(),person_name_order());
// vp is now sorted by name
std::stable_sort(vp.begin(),vp.end(),person_age_order());
// vp is now sorted by age, and persons with the same age are (still) sorted
by name
-cd
Adam Peterson
> choosing the ideal pivot, the collection has to already be sorted.
Technically, this is not quite true. To know you're choosing the ideal
pivot, you have to have some information about the ordering of the data in
the container that allows you to locate the ideal pivot. Likewise, to know
you're choosing a "reasonable" pivot, you have to have some information that
allows you to guarantee that you always pick a reasonable pivot.
Pragmatically, however, you can almost never get such information unless the
collection is already sorted or nearly so. Other distributions that grant
such guarantees are almost never encountered, and almost purely of academic
interest.
David Schwartz
> > > It has one other potentially fatal flaw, it is not a stable sort (i.e.
> > > it makes no guarantees as to the ordering of elements that compare
> > > equal).
> > There is no guarantee one could possibly make in that case. If they
> > compare equal, they are indisinguishable. Give me an example of what
> > might be a guarantee that would make sense.
> That their relative order within the container is not changed by the sort.
If they have a "relative order within the container" then they are not
equivalent and so should not compare equivalent.
> You're still overlooking the fact that the comparison being performed may
> not examine the entirety of the objects being compared - it may examine only
> a single field.
If that's so, and you want a stable sort, your comparison is broken.
However, this argument is now academic.
DS
Adam Peterson
> generically, it should be a non-stable sort. Stability is not required
> often enough to justify the overhead. Of course, if you can make a sort
> stable without compromising performance, then you certainly should.
I would probably agree with this. Those that care about stability can
always implement their own sort from any number of known good stable sorting
algorithms available. This allows those who need fewer guarantees to
potentially have no impairment on performance, where the hit would only
occur to those who need it.
However, I think the C++ standard made the correct choice in providing both
functions. Note that if the best known sort also happens to be stable, a
vendor can simply implement sort inline in terms of stable sort. Thus we
are provided with both speed and flexibility.
Gerry Quinn
>Carl Daniel wrote:
>
>> > > It has one other potentially fatal flaw, it is not a stable sort (i.e.
>> > > it makes no guarantees as to the ordering of elements that compare
>> > > equal).
>
>> > There is no guarantee one could possibly make in that case. If they
>> > compare equal, they are indisinguishable. Give me an example of what
>> > might be a guarantee that would make sense.
>
>> That their relative order within the container is not changed by the sort.
>
> If they have a "relative order within the container" then they are not
>equivalent and so should not compare equivalent.
A sort algorithm requiring an explicit comparison function that returns
a result based on the order before the sort would be quite useless in
most situations, irrespective of whether this comparison allowed it to
achieve stability.
- Gerry Quinn
Gerry Quinn
>Gerry Quinn wrote:
>
>> A strategy game with a map based on vectors could end up suffering
>> badly from slow pathfinding, if the classes are inefficient.
>
>What if the map was based on some other structure and the classes
>were inefficient? What if the map was based on vectors but the
>classes were terribly efficient?
What, indeed. Then something other than Fast STL would make a
difference, and we would be discussing it in a different thread.
>> It could also cause problems during development in debug mode,
>> even if a lot of function calls are optimised out in the release
>> version.
>
>MFC might cause problems during development in debug mode, but
>the Standard Library acts exactly the same way.
The STL runs almost as fast in debug mode as in release mode? The
'problem' I alluded to is that debug mode was over twenty times slower
than release. I could have lived with the usual factor of 2 or 3.
My guess is that STL would have been no better, and that this is a
generic vectors thing.
>> I know this from painful experience with the MFC CArray
>> collection class in the game I'm working on now. Not STL, but
>> the same considerations would apply.
>
>If we all agreed that the Standard Library were the same sort of
>crap that MS is peddling as "Foundation Classes," you're right.
>We'd be in trouble. Fortunately, we aren't. :)
Vectors are vectors.
Gerry Quinn
--
http://bindweed.com
Puzzles, Arcade, Strategy, Kaleidoscope Screensaver
Download evaluation versions free - no time limits
Check out our new arcade-puzzler "Bubbler"!
Pete Becker
>
> Pete Becker wrote:
>
> > > There is no guarantee one could possibly make in that case. If they
> > > compare equal, they are indisinguishable. Give me an example of what
> > > might be a guarantee that would make sense.
> > >
>
> > A stable sort is one in which elements that compare equal in the sort
> > come out in the same relative order after the sort as they were before
> > it. For elements like ints this doesn't matter. For more complex types
> > it makes a difference, because elements that differ can still compare
> > equal for purposes of sorting. E-mail programs, for example, should use
> > stable sorts. That way you can sort by date, then sort by name, and
> > messages from the same person will be in order by date.
>
> I think you're missing my point.
Nope.
> If you want a stable sort, then when
> you might return equal, return a value based upon which is currently
> before the other.
>
Fine, if you want to build knowledge of the underlying container into a
comparison function. Most folks would rather not limit comparison
functions in this way, so they only have to write it once.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Peter Olcott
> > compare equal, they are indisinguishable. Give me an example of what
> > might be a guarantee that would make sense.
>
> other members of which might be 'unequal', moving
> data that perhaps wasn't meant to be moved.
>
Add these other members to the sorting criteria iff
they sort to be equal. It won't cost any CPU cycles,
unless they are equal.
Peter Olcott
> retain their relative order after sorting. See stable_sort and
> list::sort. Remember that the order relation used for sorting by a
> key field induces an equivalence relation which need not be the
> equivalence relation (operator==) for the items.
>
Its trivial to add this, merely put the pointer address as the
last item of the sorting criteria.
Peter Olcott
> >already sorted or nearly sorted, right ? Is there a
> >C++ version of quick sort that will be able to inline
> >its code, and my comparison code ?
>
> Rather than trying to guess what to use why don't you benchmark the
> code using qsort with a comparison function vs using std::sort with a
> comparison functor?
>
> Tom
I could do this but you still did not answer my direct question.
Does C++ have a non "C" Quick Sort() ?
I am sold on the inlining of the sort and comparison function.
Francis Glassborow
<q6Y%7.350520$W8.13...@bgtnsc04-news.ops.worldnet.att.net>, Peter
Olcott <olc...@worldnet.att.net> writes
>I could do this but you still did not answer my direct question.
>Does C++ have a non "C" Quick Sort() ?
>I am sold on the inlining of the sort and comparison function.
The answer to that is exactly the same as that for C, which does not
have any guarantee as to what algorithm will be used by qsort (despite
its name).
Unlike C, C++ place certain performance requirements on its various
sorts (even then it does not specify the algorithm, nor should it)
--
Francis Glassborow
The Seasons best wishes to you and yours. May 2002 be better for all of us
than
2001 was for some.
Adam Peterson
"Peter Olcott" <olc...@worldnet.att.net> wrote in message
news:I7Y%7.350523$W8.13...@bgtnsc04-news.ops.worldnet.att.net...
> > The guarantee that makes sense is stable. That means that equal items
> > retain their relative order after sorting. See stable_sort and
> > list::sort. Remember that the order relation used for sorting by a
> > key field induces an equivalence relation which need not be the
> > equivalence relation (operator==) for the items.
> >
> > John
> Its trivial to add this, merely put the pointer address as the
> last item of the sorting criteria.
This is far from trivial. In an unstable algorithm (and even some stable
ones) the address bounces all around the memory space, or at least the
container during the sort. The current address tells you nothing about the
original address. The only way I think you could guarantee this is if you
augmented the data structure and stored the address (or something else that
indicated original relative ordering). This is unfeasible in many cases.
Bill Wade
> Does C++ have a non "C" Quick Sort() ?
> I am sold on the inlining of the sort and comparison function.
Neither language has a quicksort in the standard.
C and C++ have qsort() which is typically implemented in terms of some
variant of quicksort. Many implementations do not inline the comparison
function or the body of the sort code.
C++ has std::sort which is typically implemented in terms of some variant of
quicksort. Many implementations will inline both the comparison function
and the body of the sort code.
HTH
Stephen Howe
> > The guarantee that makes sense is stable. That means that equal items
> > retain their relative order after sorting. See stable_sort and
> > list::sort. Remember that the order relation used for sorting by a
> > key field induces an equivalence relation which need not be the
> > equivalence relation (operator==) for the items.
> >
> > John
> Its trivial to add this, merely put the pointer address as the
> last item of the sorting criteria.
Not at all. That might work for vector, it would not necessarily work for
deque.
Stephen Howe
David Schwartz
> A sort algorithm requiring an explicit comparison function that returns
> a result based on the order before the sort would be quite useless in
> most situations, irrespective of whether this comparison allowed it to
> achieve stability.
I completely agree with this, however, I still stand by my original
argument that if two objects are not equivalent and you do not wish to
so treat them, your comparison function should not return equality
(unless you are specifically using a stable sort).
DS
Adam Peterson
I think most of us are actually in agreement, even if we express different
first preferences. Let me rephrase what you said above in another way.
If two objects are not equivalent and you wish the original order to
distinguish them after the sort, you should use a stable sort if available
(unless you craft a predicate that imposes a total ordering, when the option
of which type of sort is freely yours).
Failure to follow one of the above rules (which I think are equivalent) will
result in incorrect results.
Adam Peterson
David Schwartz
> If two objects are not equivalent and you wish the original order to
> distinguish them after the sort, you should use a stable sort if available
> (unless you craft a predicate that imposes a total ordering, when the option
> of which type of sort is freely yours).
Yes, and I would add that the only case where a stable sort really
offers significant advantages over an unstable sort is when it's very
difficult to craft a comparison function that imposes the total
ordering. Of course, if you can make a sort stable without compromising
performance in those cases where stability isn't needed, you certainly
should.
DS
Mike Wahler
> Gerry Quinn wrote:
>
> > A sort algorithm requiring an explicit comparison function that returns
> > a result based on the order before the sort would be quite useless in
> > most situations, irrespective of whether this comparison allowed it to
> > achieve stability.
>
> I completely agree with this, however, I still stand by my original
> argument that if two objects are not equivalent and you do not wish to
> so treat them,
But *I* decide (in any given context) what 'equivalent'
means.
> your comparison function should not return equality
> (unless you are specifically using a stable sort).
Suppose I want to sort the array 'people'
below by last name:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Person
{
char firstname[20];
char lastname[20];
} people[] =
{
{"James", "Smith"},
{"John", "Doe"},
};
/* what I need, but what you say is 'wrong': */
int comp_last(const void *left, const void *right)
{
return strcmp(((struct Person*)left)->lastname,
((struct Person*)right)->lastname);
}
/* what you say I must do to be 'correct': */
int comp_all(const void *left, const void *right)
{
return memcmp(left, right, sizeof *people);
}
/* visual check: */
void show(const char *text, const struct Person *p, size_t count)
{
size_t i = 0;
printf("%s", text);
for(i = 0; i < count; ++i)
printf("%s %s\n", p[i].firstname, p[i].lastname);
puts("");
}
int main()
{
size_t psize = sizeof *people;
size_t pcount = sizeof people / sizeof *people;
show("Before:\n", people, pcount);
puts("");
printf("sorting by last name ...");
qsort(people, pcount, psize, comp_last); /* by last name */
printf("\n\n");
show("After:\n", people, pcount);
puts("");
/* the above gives me what I want */
/* Your 'fixed' method of comparison: */
printf("sorting by whole struct ...");
qsort(people, pcount, psize, comp_all); /* compare whole struct */
printf("\n\n");
show("After:\n", people, pcount);
/* this does *not* give me what I want */
return 0;
}
Output:
Before:
James Smith
John Doe
sorting by last name ...
After:
John Doe
James Smith
sorting by whole struct ...
After:
James Smith
John Doe
The first 'After' is what I want.
The second 'After' is what I get if I follow your
arbitrary demand that I compare the whole struct,
or my compare function is somehow 'wrong'.
A function is 'correct' when it yields the desired
result, not due to some arbitrary 'rule'.
-Mike
Tom Plunket
> Tom Plunket wrote:
>
> >Gerry Quinn wrote:
> >
> >> A strategy game with a map based on vectors could end up suffering
> >> badly from slow pathfinding, if the classes are inefficient.
> >
> >What if the map was based on some other structure and the classes
> >were inefficient? What if the map was based on vectors but the
> >classes were terribly efficient?
>
> What, indeed. Then something other than Fast STL would make a
> difference, and we would be discussing it in a different thread.
Umm, ok. I didn't realize that there was a product called Fast
STL. My bad.
> >> It could also cause problems during development in debug mode,
> >> even if a lot of function calls are optimised out in the release
> >> version.
> >
> >MFC might cause problems during development in debug mode, but
> >the Standard Library acts exactly the same way.
>
> The STL runs almost as fast in debug mode as in release mode?
> The 'problem' I alluded to is that debug mode was over twenty
> times slower than release. I could have lived with the usual
> factor of 2 or 3.
"Causing problems" != "running slow". The word "problems"
implies some erroneous output. Just because it takes longer to
arrive at the same solution doesn't mean that the slow
computation is wrong.
In any event, I have found the speed difference between optimized
and non-optimized of my apps, which rely heavily on the Standard
Library, to be significant but not even a factor of 2.
The standard library code may indeed run considerably slower in
non-optimized builds, but the speed of the app overall? The
algorithms are what make up the real difference ime.
> My guess is that STL would have been no better, and that this is
> a generic vectors thing.
What's a generic vector then? You mean this is a problem that
plagues both std::vector and pre-standard vector and CArray and
any other variably-sized array class on the planet?
> >> I know this from painful experience with the MFC CArray
> >> collection class in the game I'm working on now. Not STL, but
> >> the same considerations would apply.
> >
> >If we all agreed that the Standard Library were the same sort of
> >crap that MS is peddling as "Foundation Classes," you're right.
> >We'd be in trouble. Fortunately, we aren't. :)
>
> Vectors are vectors.
std::vectors are not MFC CArrays, though. Ditch CArray and live
a long and healthy life.
David Schwartz
> /* what you say I must do to be 'correct': */
> int comp_all(const void *left, const void *right)
> {
> return memcmp(left, right, sizeof *people);
> }
> sorting by whole struct ...
> The first 'After' is what I want.
> The second 'After' is what I get if I follow your
> arbitrary demand that I compare the whole struct,
> or my compare function is somehow 'wrong'.
You can't have misunderstood me this completely could you? Simply put,
your comparison function should specify whatever ordering you want.
DS
CBFalconer
A simple example, even using only text files, is when one field
should be sorted as alphabetic, and another as numeric.
Meanwhile, all we have to hand is the system sort program, which
can only handle one field at a time, but is smart enough to be
able to choose between alpha and numeric sorts. If it is stable,
no problem. If not, it is time to hire me at $100/hour to build
the sort program.
If you are relying on the sort that comes with W9x and MsDos, for
example, you need me. If you are using Ben Bakers qsort, then I
starve.
So, never, ever, make a sort program stable. Do have it spit out
my address.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Gerry Quinn
>Gerry Quinn wrote:
>> >
>> >> A strategy game with a map based on vectors could end up suffering
>> >> badly from slow pathfinding, if the classes are inefficient.
>> >
>> >What if the map was based on some other structure and the classes
>> >were inefficient? What if the map was based on vectors but the
>> >classes were terribly efficient?
>>
>> What, indeed. Then something other than Fast STL would make a
>> difference, and we would be discussing it in a different thread.
>
>Umm, ok. I didn't realize that there was a product called Fast
>STL. My bad.
Not sure if you're joking - anyway see the thread title.
>> The STL runs almost as fast in debug mode as in release mode?
>> The 'problem' I alluded to is that debug mode was over twenty
>> times slower than release. I could have lived with the usual
>> factor of 2 or 3.
>
>"Causing problems" != "running slow". The word "problems"
>implies some erroneous output. Just because it takes longer to
>arrive at the same solution doesn't mean that the slow
>computation is wrong.
It doesn't imply that to me. It just implies anything that gets in my
way.
>In any event, I have found the speed difference between optimized
>and non-optimized of my apps, which rely heavily on the Standard
>Library, to be significant but not even a factor of 2.
>
>The standard library code may indeed run considerably slower in
>non-optimized builds, but the speed of the app overall? The
>algorithms are what make up the real difference ime.
Sure. But some applications, like a strategy game in which the AI has
to do a lot of pathfinding, can expose a particular problem.
>> My guess is that STL would have been no better, and that this is
>> a generic vectors thing.
>
>What's a generic vector then? You mean this is a problem that
>plagues both std::vector and pre-standard vector and CArray and
>any other variably-sized array class on the planet?
I think function calls and bounds checking for array access will slow
down non-optimised builds for any such type.
>std::vectors are not MFC CArrays, though. Ditch CArray and live
>a long and healthy life.
Maybe I will - CArray is a bit of a pain. (In fairness, though, CList
has never given me trouble...)
Tom Plunket
> Tom Plunket wrote:
>
> >Gerry Quinn wrote:
> >
> >> What, indeed. Then something other than Fast STL would make a
> >> difference, and we would be discussing it in a different thread.
> >
> >Umm, ok. I didn't realize that there was a product called Fast
> >STL. My bad.
>
> Not sure if you're joking - anyway see the thread title.
Not joking. I thought "Fast STL" meant some "faster"
implementation of the standard library than some other
implementation that was deemed too slow. Now I realize that it
is a product.
> >The standard library code may indeed run considerably slower in
> >non-optimized builds, but the speed of the app overall? The
> >algorithms are what make up the real difference ime.
>
> Sure. But some applications, like a strategy game in which the AI has
> to do a lot of pathfinding, can expose a particular problem.
What problem? If you're running in debug mode then you know
you're not getting the performance that you will get, so no
problem is exposed related to speed. If you're running in
fully-optimized mode, then the problems that you see will also be
there in the debug build.
> >> My guess is that STL would have been no better, and that this is
> >> a generic vectors thing.
> >
> >What's a generic vector then? You mean this is a problem that
> >plagues both std::vector and pre-standard vector and CArray and
> >any other variably-sized array class on the planet?
>
> I think function calls and bounds checking for array access will slow
> down non-optimised builds for any such type.
Why would you use different methods for accessing your array in
debug and optimized builds? Or are you not aware that
std::vector does not do bounds checking unless you ask it to (and
it does it even in optimized builds)?
> >std::vectors are not MFC CArrays, though. Ditch CArray and live
> >a long and healthy life.
>
> Maybe I will - CArray is a bit of a pain. (In fairness, though, CList
> has never given me trouble...)
std::list will give you even less trouble. ;)
Peter Olcott
> > last item of the sorting criteria.
>
> This is far from trivial. In an unstable algorithm (and even some stable
> ones) the address bounces all around the memory space, or at least the
> container during the sort. The current address tells you nothing about the
> original address. The only way I think you could guarantee this is if you
> augmented the data structure and stored the address (or something else that
> indicated original relative ordering). This is unfeasible in many cases.
When I am using qsort(), I pass it an array of pointers,
although these pointers may move all around in this array as
qsort() continues to work, the values of these pointers
themselves stays the same, thus making the comparison
of these pointers themselves, as the last criterion of
comparison, forces the sort in a single consistent ordering.
For databases, this could use the record number.
Adam Peterson
> > > Its trivial to add this, merely put the pointer address as the
> > > last item of the sorting criteria.
> >
> > This is far from trivial. In an unstable algorithm (and even some
stable
> > ones) the address bounces all around the memory space, or at least the
> > container during the sort. The current address tells you nothing about
the
> > original address. The only way I think you could guarantee this is if
you
> > augmented the data structure and stored the address (or something else
that
> > indicated original relative ordering). This is unfeasible in many
cases.
>
> When I am using qsort(), I pass it an array of pointers,
> although these pointers may move all around in this array as
> qsort() continues to work, the values of these pointers
> themselves stays the same, thus making the comparison
> of these pointers themselves, as the last criterion of
> comparison, forces the sort in a single consistent ordering.
>
> For databases, this could use the record number.
This assumes you are sorting indirectly. When this is the case (and when
you can assume that your references can be ordered properly), it can be
done. I seldom sort indirectly, though.
qsort() assumes your memory is continuous and linearly addressed. This is
not necessarily the case for C++ sorts.
Peter Olcott
> implementation of the standard library than some other
> implementation that was deemed too slow. Now I realize that it
> is a product.
FastString is a freeware product.
http://home.att.net/~olcott/fast.html
It has come along way since Tom authored the lazy evaluation
expression templates. I started this thread to see if there was
market potential for a highly optimized implementation of STL.
It looks like no one cares at all if STL is as much as 500 fold
slower than necessary. I haven't encountered even one person
that cared at all about the speed of STL. All the code that
could use a faster STL ignores STL and is written from scratch.
As a direct result of FastString, MSVC++ STL has been made
much faster. P. J. Plauger changed shrink to fit on assignment to
the current standard of shrink to fit when specified by reserve().
This one change eliminated all of the huge delays, and now MSVC++
STL's std::string will function at quite reasonable speeds. FastString
is still 500-fold faster on the one operation that I need it for, (repeated
concatenation of a single byte with automatic memory expansion)
on the compiler that I need to use, Borland C++ Builder 4.0.
Also FastString is a many-fold better implementation than I
could have developed without the help of its many contributors.
Gerry Quinn
>> >STL. My bad.
>>
>> Not sure if you're joking - anyway see the thread title.
>
>Not joking. I thought "Fast STL" meant some "faster"
>implementation of the standard library than some other
>implementation that was deemed too slow. Now I realize that it
>is a product.
Actually I don't think it is! Mind you, I popped into the thread in
midstream. I thought we were just discussing what a faster STL might do
for programmers.
>>
>> Sure. But some applications, like a strategy game in which the AI has
>> to do a lot of pathfinding, can expose a particular problem.
>
>What problem? If you're running in debug mode then you know
>you're not getting the performance that you will get, so no
>problem is exposed related to speed.
That's (usually, but not always) well and good when the slowdown is a
factor of two, but not when it's twenty. Games require real time
output, even in debug mode. Sure, it's not a project killer, but it
definitely can be an obstacle in one's path. (I'm over it,
incidentally, I am just speaking theoretically at this point.)
>Why would you use different methods for accessing your array in
>debug and optimized builds?
Because the way I have written access may be optimised into something
else.
Jon Bills
news:SrT08.26941$8s4.1...@news.indigo.ie...
> In article <0qg64u0dh7v065ubc...@4ax.com>, Tom Plunket <to...@fancy.org> wrote:
> >Gerry Quinn wrote:
> >> >Umm, ok. I didn't realize that there was a product called Fast
> >> >STL. My bad.
> >>
> >> Not sure if you're joking - anyway see the thread title.
> >
> >Not joking. I thought "Fast STL" meant some "faster"
> >implementation of the standard library than some other
> >implementation that was deemed too slow. Now I realize that it
> >is a product.
>
> Actually I don't think it is! Mind you, I popped into the thread in
> midstream. I thought we were just discussing what a faster STL might do
> for programmers.
Peter Olcott appears to judge speed as being the only criteria in determining
whether code is "good". The question "when does fast STL make a difference?"
is part of his need to justify that world view. The simple answer to the
question is "we don't know", since the difference is only important when
we need it, and we don't have a situation in which we can decide that we need
a difference or how a difference might come about. Peter has already decided
that the STL is "too slow", whatever that means, and is seeking to find some
support for that unprovable hypothesis.
[snip]
Jon.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
CBFalconer
>
> > > Its trivial to add this, merely put the pointer address as the
> > > last item of the sorting criteria.
> >
> > This is far from trivial. In an unstable algorithm (and even some stable
> > ones) the address bounces all around the memory space, or at least the
> > container during the sort. The current address tells you nothing about the
> > original address. The only way I think you could guarantee this is if you
> > augmented the data structure and stored the address (or something else that
> > indicated original relative ordering). This is unfeasible in many cases.
>
> When I am using qsort(), I pass it an array of pointers,
> although these pointers may move all around in this array as
> qsort() continues to work, the values of these pointers
> themselves stays the same, thus making the comparison
> of these pointers themselves, as the last criterion of
> comparison, forces the sort in a single consistent ordering.
In general, this is totally undefined behaviour. I don't think I
want to use your libraries.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Tom Plunket
> >> >Umm, ok. I didn't realize that there was a product called Fast
> >> >STL. My bad.
> >>
> >> Not sure if you're joking - anyway see the thread title.
> >
> >Not joking. I thought "Fast STL" meant some "faster"
> >implementation of the standard library than some other
> >implementation that was deemed too slow. Now I realize that it
> >is a product.
>
> Actually I don't think it is!
Ok, then why this bit of the thread?
> >What if the map was based on some other structure and the classes
> >were inefficient? What if the map was based on vectors but the
> >classes were terribly efficient?
>
> What, indeed. Then something other than Fast STL would make a
> difference, and we would be discussing it in a different thread.
I made a statement based on my assumption that we were talking
about the Standard Library, and I get "corrected" that the thread
is about "Fast STL". That's all.
> >What problem? If you're running in debug mode then you know
> >you're not getting the performance that you will get, so no
> >problem is exposed related to speed.
>
> That's (usually, but not always) well and good when the slowdown
> is a factor of two, but not when it's twenty. Games require real
> time output, even in debug mode.
Not true, if you have proper tools.
> >Why would you use different methods for accessing your array in
> >debug and optimized builds?
>
> Because the way I have written access may be optimised into
> something else.
Oh- so you're compiling different code in the two modes. Well
obviously then the issue lies with the fact that different code
is being compiled, not that the same facilities change
fundamentally when compiled with optimization or not.
Peter Olcott
> Peter Olcott appears to judge speed as being the only criteria in determining
> whether code is "good".
Not at all, everything else being equal more efficient is better.
I have discovered cases where std::string was hundreds fold
slower than necessary. Apparently this was because of very
conservative memory growth, always grow to size. A memory
growth factor for std::string of 1.5, has proven to be an
excellent tradeoff between space and speed. It only makes
a slight difference when the strings become much longer
than is typical for a string. It slows down to 1/3 slower
on the repeated append of a 10,000 byte string, as compared
to a memory growth factor of 2.0.
> The question "when does fast STL make a difference?"
> is part of his need to justify that world view. The simple answer to the
> question is "we don't know", since the difference is only important when
> we need it, and we don't have a situation in which we can decide that we need
> a difference or how a difference might come about. Peter has already decided
> that the STL is "too slow", whatever that means, and is seeking to find some
> support for that unprovable hypothesis.
When any aspect of STL if 500-fold slower than necessary,
then the fact that it is too slow can be reasonably inferred.
All of these threads were based on the fact that I needed
a really fast append a single byte to a string. I was originally
seeking to merely replace strcat() with a C++ class that
would be much faster because it kept track of where the
last byte is. What I eventually derived was a subset of
all of the most fundamental features of std::string that
has exactly the same behavior and interface as std::string
for those features that it implements, provides the strong
exception safety guarantee, provides the best thread safety
guarantee that is available in a standard C++ source code
distribution, and beats every other std::string on a
comprehensive set of fifty five benchmarks.
http://home.att.net/~olcott/fast.html
The crux of all of this is that I was looking for a quick
way to append to a ASCIIZ string, without automatic
resizing, and ended up with a way that is 500-fold faster
than my compiler Borland Visual C++ 4.0, even when
FastString must handle all memory allocation.
> [snip]
>
> Jon.
Peter Olcott
> >and non-optimized of my apps, which rely heavily on the Standard
> >Library, to be significant but not even a factor of 2.
> >
> >The standard library code may indeed run considerably slower in
> >non-optimized builds, but the speed of the app overall? The
> >algorithms are what make up the real difference ime.
Yet this is not the question.
Try using a really slow STL like Borland C++ Builder 4.0
against a really fast STL like STLport 4.51.
Or if you don't have the Borland compiler then
try STLport against whatever you do have.
David Schwartz
> Peter Olcott appears to judge speed as being the only criteria in determining
> whether code is "good". The question "when does fast STL make a difference?"
> is part of his need to justify that world view. The simple answer to the
> question is "we don't know", since the difference is only important when
> we need it, and we don't have a situation in which we can decide that we need
> a difference or how a difference might come about. Peter has already decided
> that the STL is "too slow", whatever that means, and is seeking to find some
> support for that unprovable hypothesis.
I will say that as a general rule, we *always* need performance, even
when we think we don't. The reason is that speed is something we can
tradeoff for a lot of things, and the more of it we have that we don't
need, the more of it we can tradeoff for other things we might need. If
our STL is very fast and that gives us speed we don't need, we can trade
that speed off for:
1) Size. We can make more size/speed tradeoffs in favor of size. This
reduces our resource consumption and makes those who use our code
happier.
2) Simplicity. We may be able to avoid optimizing more of our code
because we're already fast enough. This will make our code easier to
write, more maintainable, and perhaps have fewer bugs.
3) Features. We may be able to add resource intensive features that our
users want. They'll cost us some performance, but that's okay if we're
already overperforming.
So I'd say that speed is a fairly significant criteria when judging any
library that you're going to use. The more that it can affect your
application performance, the more important this is.
We can even tolerate more complexity and risk of bugs in our STL than
in our regular code. It's so important that it's worth thoroughly
reviewing by many people to ensure that it's as bug free as practical.
Then we don't change it and we can rely on it. So we can tolerate more
complexity and intricacy in lower-level code that will be more heavily
reviewed, used, and re-used than we can in everyday code.
The only things that I would prioritize over speed in STL code is
correctness and thoroughness of testing.
DS
Ruslan Abdikeev
news:3C43AD39...@yahoo.com...
> Peter Olcott wrote:
> > > > Its trivial to add this, merely put the pointer address as the
> > > > last item of the sorting criteria.
> > > This is far from trivial. In an unstable algorithm (and even some
stable
> > > ones) the address bounces all around the memory space, or at least
the
> > > container during the sort. The current address tells you nothing
about the
> > > original address. The only way I think you could guarantee this is
if you
> > > augmented the data structure and stored the address (or something
else that
> > > indicated original relative ordering). This is unfeasible in many
cases.
> > When I am using qsort(), I pass it an array of pointers,
> > although these pointers may move all around in this array as
> > qsort() continues to work, the values of these pointers
> > themselves stays the same, thus making the comparison
> > of these pointers themselves, as the last criterion of
> > comparison, forces the sort in a single consistent ordering.
> In general, this is totally undefined behaviour. I don't think I
> want to use your libraries.
Totally agreed.
I see two ways to build comparison criterion:
relational operators on pointers and casting of pointers to integral types.
1. There is no way to define criterion of comparison based on
relational operators that forces any consistent ordering (5.9/2).
2. Comparison criterion based on reinterpret_casting pointers
to integral types might yield "unsurprising" results (5.2.10/4),
but not in general, as
standard does not require an implementation
to have an integral type that is large enough to hold a pointer (5.2.10/5).
If no any such exists, "unsurprising" results are not guaranteed.
Sincerely,
Ruslan Abdikeev
Gerry Quinn
>
>> >What if the map was based on some other structure and the classes
>> >were inefficient? What if the map was based on vectors but the
>> >classes were terribly efficient?
>>
>> What, indeed. Then something other than Fast STL would make a
>> difference, and we would be discussing it in a different thread.
>
>I made a statement based on my assumption that we were talking
>about the Standard Library, and I get "corrected" that the thread
>is about "Fast STL". That's all.
Perhaps I should have put quotation marks in the sentence above, to make
the implicit quotation of the thread title clear.
>> >What problem? If you're running in debug mode then you know
>> >you're not getting the performance that you will get, so no
>> >problem is exposed related to speed.
>>
>> That's (usually, but not always) well and good when the slowdown
>> is a factor of two, but not when it's twenty. Games require real
>> time output, even in debug mode.
>
>Not true, if you have proper tools.
Such as a time machine that can freeze a player to simulate a continuous
play experience? Unfortunately I don't have one of those to hand.
[Restored for context:]
>>>>I think function calls and bounds checking for array access will slow
>>>>down non-optimised builds for any such type.
>
>> >Why would you use different methods for accessing your array in
>> >debug and optimized builds?
>>
>> Because the way I have written access may be optimised into
>> something else.
>
>Oh- so you're compiling different code in the two modes. Well
>obviously then the issue lies with the fact that different code
>is being compiled, not that the same facilities change
>fundamentally when compiled with optimization or not.
No - because the optimiser may remove function calls etc. The code I
write is the same. The methods (usage as in general English) used by
compiled code may vary with the degree of optimisation.
Jon Bills
> Jon Bills wrote:
>
> > Peter Olcott appears to judge speed as being the only criteria in determining
> > whether code is "good". The question "when does fast STL make a difference?"
> > is part of his need to justify that world view. The simple answer to the
> > question is "we don't know", since the difference is only important when
> > we need it, and we don't have a situation in which we can decide that we need
> > a difference or how a difference might come about. Peter has already decided
> > that the STL is "too slow", whatever that means, and is seeking to find some
> > support for that unprovable hypothesis.
>
> I will say that as a general rule, we *always* need performance, even
> when we think we don't. The reason is that speed is something we can
> tradeoff for a lot of things, and the more of it we have that we don't
> need, the more of it we can tradeoff for other things we might need. If
> our STL is very fast and that gives us speed we don't need, we can trade
> that speed off for:
Yes, but you don't know how fast is "fast enough". You can't decide something
is not fast enough based on some aribtrary hypothetical criteria.
[snip]
> The only things that I would prioritize over speed in STL code is
> correctness and thoroughness of testing.
Precisely. Lack of correctness makes performance a somewhat moot point. There
is no reason to ask the standard library vendors to invest their efforts
on performance optimisations for an ever diminishing return when so many people
favour abstraction and compliance. There's been no indication in these threads
of a general requirement for a "faster" STL, let alone a second rate string
class which is said to perform "faster" than std::string by some perverted
performance criteria.
> DS