Re: How did C++ beat the competition?
From: Claudio Puviani (puviani_at_hotmail.com)
Date: 03/14/04
- Next message: Victor Bazarov: "Re: sorting a multimap?!"
- Previous message: Nick Hounsome: "Re: why make non-pure virtual functions?"
- In reply to: Randy Gordon: "Re: How did C++ beat the competition?"
- Next in thread: jeffc: "Re: How did C++ beat the competition?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 14 Mar 2004 18:09:32 GMT
"Randy Gordon" <randyjg2@yahoo.nospam> wrote
> This brings up a really interesting point in language design.
> Maybe you can clear it up for me.
>
> In my algorithm books and courses,it was always said that
> performance is due more to choice of algorithm rather than
> hardware resources or the implementations language.
Asymptotically, that's correct. When dealing with small data sets,
implementation details can dominate.
> C++ seems to believe this in the design of the STL, which
> seems to specify the perfomance requirement rather than the
> actual code to be used.
It's not just C++. It's a fundamental and inescapable truth. However, note that
this doesn't mean that if a function requires an algorithm of O(n log n), the
only thing you're allowed to do is implement an O(n log n) algorithm. For
example, it's common for sorting functions to do a simple test-and-swap for
length 2, a Sedgewick 3-element sort for a length of 3, use an O(n^2) sort for
sizes 4 to some other small bound (often something between 8 and 20), and a
quicksort for anything greater. If the choice were purely theoretical, every
in-place sort function would be implemented as a heapsort.
> Very few authors write their own STL enhancements (Boost,
> Blitz, etc. and other commonly used libraries excepted) because
> the amount of work to come up with a better tuned algorithm
> than someone who specialize in such things isn't an easy task.
For the majority -- even the vast majority -- that's true, but I've been in
situations where not only enhancements but replacements of the standard
containers resulted in orders of magniture performance improvements. The reason
isn't that the container's algorithms per se are faulty (there's not much to get
wrong in a vector), but the underlying allocation mechanisms can be extremely
slow. Optimizing those is what reaps the benefits. Before someone stands up and
says, "but C++ standard containers can use custom allocators," they do, but in a
very limited fashion that isn't amenable to microtuning.
> The problem with explicit gc, as many gc algorithm writers have
> pointed out, is that memory is a common resource, and there is
> no way to know, at a local level, when gc should be performed.
> At the wrong time, it can actually reduce performance, rather than
> enhance it.
That's only partly true. A naive application may view memory as a global
resource, but more sophisticated designs often partition the memory to improve
referential locality, minimize contention, provide more efficient
sub-allocation, allow mark-and-release functionality, etc. It's perfectly
feasible to have multiple gc realms which are local, if the application is
written correctly. This is definitely not common practice, but it goes to
illustrate that the generalization isn't universal.
> Java took this advice to heart, and instead offers six different "built
> in" garbage collection algorithms in a typical JVM, carefully tuned for
> specific purposes.
>
> Each one represents a different set of tradeoffs.( Check out
> http://www-106.ibm.com/developerworks/java/library/j-jtp11253/
> for a start.) You choose which one when you start up a JVM for your
> particular application.
>
> The question is this: your comment implies that the lack of an
> explicit gc is a defect.
I can't speak for Greg, but I don't think we can call that a defect because it's
consistent with Java's philosophy of imposing policy on the programmer. Offering
that kind of option would alienate those who want that kind of behavior
legislated so that they don't have to worry about it or have to debate whether
or not to use it with other developers or managers. If gc were ever added to C++
and control were kept out of the programmer's hands, it would absolutely be a
defect because it would violate the long-standing goals and philosphy of the
language. It's all about context.
> Under what circumstances do you see explicit gc as being useful?
When dealing with local gc realms. You do a certain amount of work in a realm (a
simulation, for example), end up with a result that can be saved in another
realm, and you know for a fact that you can now reclaim most or all of the
memory from the working realm.
> Under what circumstances does writing your own gc (rather than
> using a third party library) make sense?
When the third party library doesn't satisfy the requirements. Most people would
just avoid gc rather than try to craft their own if the gc they had available
didn't satisfy their needs. Writing a gc isn't a trivial task, especially if it
needs to be integrated in a language like C++.
Claudio Puviani
- Next message: Victor Bazarov: "Re: sorting a multimap?!"
- Previous message: Nick Hounsome: "Re: why make non-pure virtual functions?"
- In reply to: Randy Gordon: "Re: How did C++ beat the competition?"
- Next in thread: jeffc: "Re: How did C++ beat the competition?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
