Generally, are the programs written by C++ slower than written by C10% ?

[BGB]

This is exactly one of the reasons why I dislike the language so much.
The C standard library does not offer many useful tools, and the reason
for this is that the language doesn't lend itself for this. It's very
hard to implement any generic data containers or algorithms which would
be efficient, and because they will always have some compromises,
inefficiencies or other defects, most C programmers end up not using
them anyways.

"Nobody uses qsort() anyways" is just the epitome of this. Contrast it
with std::sort(), which is actually a really decent general use sorting
function, and in the vast majority of cases it's pretty useful, and it's
very commonly used in C++ in most situations where sorting is needed.
Moreover, it's very easy to use (much easier than qsort()).

however, avoiding writing little bits of code is not nearly so high on
many peoples' priority list.

Optimizing from O(n) to O(1) is far from "micro-optimizing". (And it's
not like you have to do anything in your code to achieve this.)

except when n is usually sufficiently small as to be ignorable...

how long is a typical string on which one may use strlen?...
maybe 3-20 characters...

given the compiler will typically replace it with something like "repnz
scasb" anyways, it is not usually a big deal.

long strings tend to be fairly rare in practice, and are usually the
result of something like reading in a text file as a single large string
(but, in this case, it is typically processed by being broken down into
lines or tokens, each of which tends to be much shorter).


more commonly though, string code does not use strlen, but is often
implemented more directly via good old while loops and character
operations, and one knows when the string is used up by having run into
the terminator:
s=str;
while(*s)
{
...
}


another fairly common idiom(for character-driven logic) is:
while(*s)
{
switch(*s++)
{
...
}
}

and so on...

 

[BGB]

That says it all really, C++ programmers don't have to.

it is a choice though, and probably most C programmers don't mind so
much, which is why they do it.

it is possible it may be as much a stylistic/idiomatic/... conflict as a
language one.


for example, I use C a lot mostly because I have concerns like:
being able to parse and analyze the source code with custom written tools;
being able to have a reasonably consistent ABI (for all my ASM/... to
interface with);
being able to interface easily between my native code and my scripting
language;
....


if another person doesn't have these concerns, and may well be more
motivated by saving a little effort or being able to more readily use
higher-level abstractions, then using C++ may make a lot more sense for
them.

 

[Ian Collins]

it is a choice though, and probably most C programmers don't mind so
much, which is why they do it.

Or they are forced to in order to get decent performance.

it is possible it may be as much a stylistic/idiomatic/... conflict as a
language one.

for example, I use C a lot mostly because I have concerns like:
being able to parse and analyze the source code with custom written tools;
being able to have a reasonably consistent ABI (for all my ASM/... to
interface with);
being able to interface easily between my native code and my scripting
language;
....

That's what C++ has extern "C" for. I've written PHP extensions in C++.

 

[James Kanze]

Generally, are the programs written by C++ slower than written by C
10% ?

No. In general, if performance matters, programs written in C++
are significantly faster than those written in C. (And if it
doesn't matter, who cares.) C++ offers better encapsulation,
and better encapsulation makes it significantly easier to
exploit the profiler output.

 

[James Kanze]

innews:fa40b251-1e2d-49f1-8d52-af2bf47fbc30@p37g2000prp.googlegroups.com:

0% ?

[...]

2. In runtime, the speed of the program written by C++ is <= the same
program written by C

This does not follow. Both languages are Turing complete and apply the
"do-not-pay-for-what's-not-used" policy, so if some program+input data
combination happens to be slower in one language on some platform, one
can always tune the code until the performance is the same.

Not necessarily, at least not practically. Tuning often
involves modifications in the data structures, and unless the
variables involved are private, the amount of work involved
generally makes the tuning impractical. If there's any chance
that performance will be an issue, you almost have to use C++,
rather than C, because it is very, very difficult to tune C.

[...]

For writing fast code in C++ one must be quite familiar with
the language so that one knows what's going on under the hood.

Yes and no. Most of the time, the largest speed gains are
achieved by using a different algorithm (which may require
diffrerent data structures to support it), or by caching data
(which, of course, only works if all accesses to the data go
through specified functions). Neither of these require any real
knowledge of what's going on under the hood.

Writing fast code in C is in principle easier as there are fewer high
level constructs which could potentially cause slowdowns.

Writing fast code in C is significantly harder, because of the
lack of encapsulation.

[...]

So, to give some concrete suggestions:

Large program, good C++ skills: use C++.
Small program, bad C++ skills: use C.
Large program, bad C++ skills: screwed both ways, use C++ to get a slow
and working program.
Small program, good C++ skills: doesn't matter, use C++ for convenience.

I'd say:

Speed important: use C++, regardless of the size.
Speed not important, large program: use C++.
Speed not important, (very) small program: use a more dynamic
language,
like Python.

Other issues may also be involved: C++ (used correctly) is far
more robust than most of the readily available alternatives, for
example; for a critical application, it's certainly preferrable
to C (or to Python, or to Java).

As for the level of C++ skills: if the solution is to use C++,
and you have bad C++ skills, improve them. It's better to take
the time to learn C++ correctly than to use a less appropriate
language.

 

[James Kanze]

On 9/2/2011 10:51 PM, Juha Nieminen wrote:
[...]
also, just how many people really use "qsort()" anyways?...

Not very many, because not very many people write applications
which might need it in C.

In earlier days, it was widely used.

IME, it is more often one of those largely forgotten functions (it is
there, but more often people write out their own sort logic manually).

That is, of course, complete bullshit. Any competent C
programmer will use it if he has to sort something.

(actually, it seems to be fairly common practice in C land for people to
largely ignore much of the standard library, and to write their own
logic for doing things).

Only among incompetent C programmers.

it is also not clear that std::string would be, in general, faster, and
having an O(1) ability to fetch the length may turn out to be moot if
most other operations tend towards being more expensive. not that
worrying about micro-optimizing string operations is usually all that
relevant though anyways.

from what I can gather from checking online (via Google), it seems where
people have tried testing, the performance differences have tended to be
negligible.

From my concrete experience, in several different applications
(including one where two separate teams implemented the same
thing, one in C and one in C++), when performance matters, C++
is usually a magnitude faster than C, if not more.

some other tests have apparently shown std::string operations to be
about 4x slower than C-style strings.

Never trust a benchmark you haven't rigged yourself. I would
have no problem writing a benchmark to prove whichever side I
wished.

In real applications, where performance matters, C++ is
significantly faster than C.

 

[BGB]

Or they are forced to in order to get decent performance.


That's what C++ has extern "C" for. I've written PHP extensions in C++.

yes, but this is only really more convenient (than just using C) if one
is doing a decent amount of logic code in C++, rather than the fairly
common case where the library is often mostly thin wrapper functionality
passing control off somewhere else (to other library code, to another
library, or to the OS), or performing at most trivial operations (the
gains in language usability in this case may not necessarily outweigh
some of the added inconveniences).


granted, yes, I have used 'extern "C"' in a few places, but typically it
is a minority of the code as a whole.

for example, for my physics library I did use C++ and 'extern "C"', but
a physics library is a special case in that it has lots of very
dense/involved logic code, and a reasonably "low surface area" API (as
in, most of the complexity of the library is in its internal logic,
rather than the number and variety of API functions one is providing).

in this sort of case, C++ makes a lot more sense.

where it makes not as much sense though is the far more typical:
void FOO_FooFunc(int x)
{ BAR_BarFunc(x, 0); }
style of code...


however, if the internal logic code is in C++ and uses OOP, then one may
end up with a lot of:
void FOO_Func(fooObject obj, int x)
{ ((FooObject *)obj)->func(x); }

granted, it is roughly a similar case for providing wrapper classes so
that C++ code can have a class-based interface to some pieces of library
functionality (even if, albeit, the abstraction will start to fall apart
about as soon as one wants to overload the class and wonders why their
new fields/methods/... don't work as expected).


or such...

 

[BGB]

On 9/2/2011 10:51 PM, Juha Nieminen wrote:
[...]
also, just how many people really use "qsort()" anyways?...

Not very many, because not very many people write applications
which might need it in C.

In earlier days, it was widely used.

possibly...

IME, it is more often one of those largely forgotten functions (it is
there, but more often people write out their own sort logic manually).

That is, of course, complete bullshit. Any competent C
programmer will use it if he has to sort something.

not from what I have seen.

Only among incompetent C programmers.

value judgements aside, it is a question of which is more common, not
which is more "competent".


most of the code I have seen has generally been in things like
game-engines and VMs, which are generally my main interest areas.


common in game engines (especially the Quake series and most similar or
derived engines) is in-fact to wrap much of the OS (for example,
everything from the filesystem to memory management to networking to ...
is generally somewhat wrapped, or implemented clean).

if one goes and looks at other things, such as GTK+, one finds yet more
wrapping and custom-written logic.

and, if one goes and looks into the core of Mono... well, then one just
finds terror...

also, many projects end up largely not using "malloc()"/"free()" either,
and instead use garbage collectors such as Boehm, or other custom memory
managers.


so, from what all I have seen, wrapping and reimplementation seems to be
common practice, with the standard library usually being used in a "pick
and choose" manner, often with many parts of it, or much of it, being
ignored.

From my concrete experience, in several different applications
(including one where two separate teams implemented the same
thing, one in C and one in C++), when performance matters, C++
is usually a magnitude faster than C, if not more.

from what all I have seen, in personal experience and in common
benchmarks, they usually come out more or less about the same.

granted, a lot likely comes down to coding practices, and one can write
faster or slower code in either language.

Never trust a benchmark you haven't rigged yourself. I would
have no problem writing a benchmark to prove whichever side I
wished.

In real applications, where performance matters, C++ is
significantly faster than C.

depends on what one means exactly by a "real application".


granted, it would be hard to really test this one way or another, as one
would need otherwise equivalent apps written in each language, and not
(as is far more common IME) an ad-hoc mix of both languages (and absent
external factors, such as potentially notable implementation differences).


for example, my own project would be excluded because it is, in fact,
written with parts in C, parts in C++, parts in ASM, and parts in other
languages (namely some Java, and some parts in a custom language).

project size is maybe "medium" at about 815 kloc (a "large" project
would be something more like GCC, FireFox, or the Linux kernel, each of
which is solidly in the Mloc range).

by this scale though, Quake would be a "small" project, being approx 30
kloc IIRC, and was itself written primarily in C (other parts were ASM
and QuakeC), much as were Quake2 and Quake3 (ASM and C).

so, one can debate:
would Quake 1 or 2 have gotten faster framerates had they been instead
written in C++?...

or, for that matter, would the Linux kernel likely go faster?...

or, maybe, would GCC itself compile code faster?...


or such...

 

[BGB]

inom:

Generally, are the programs written by C++ slower than written
by C 1
0% ?
[...]
2. In runtime, the speed of the program written by C++ is<= the
same
program written by C

This does not follow. Both languages are Turing complete and apply
the "do-not-pay-for-what's-not-used" policy, so if some program+input
data combination happens to be slower in one language on some
platform, one can always tune the code until the performance is the
same.

Not necessarily, at least not practically. Tuning often
involves modifications in the data structures, and unless the
variables involved are private, the amount of work involved
generally makes the tuning impractical. If there's any chance
that performance will be an issue, you almost have to use C++,
rather than C, because it is very, very difficult to tune C.

I agree that tuning C code could easily mean rewriting large parts of the
program. Yet this can be done if the program is small. If it is practical
or not is another question.

a lot depends on how code is structured and organized as well...

[...]

For writing fast code in C++ one must be quite familiar with
the language so that one knows what's going on under the hood.

Yes and no. Most of the time, the largest speed gains are
achieved by using a different algorithm (which may require
diffrerent data structures to support it), or by caching data
(which, of course, only works if all accesses to the data go
through specified functions). Neither of these require any real
knowledge of what's going on under the hood.

Passing a STL container to a function by a copy instead of a reference or
using a copy where swap() would work - these are easy mistakes to make
and would qualify as a change in the algorithm (O(1)->O(N)). If one is
doing this all over the place, the profiler might not even bring it out
in non-critical paths, meaning that all the code would be just somewhat
slower than necessary.

OTOH, in C it takes some extra effort to pass an array into a function by
copy, so nobody would do this accidentally.

yep.

depending as well on how things are structured, one can often change the
algorithms used internally without impacting its interface.

Only if one tries to emulate encapsulation by using means of non-zero
runtime cost, like dynamically allocated data structures accessed via
opaque pointers. If one does not attempt to have any encapsulation, then
there is nothing which would get in the way of having fast code. Of
course, ensuring that this fast code is also *correct* and *robust* and
*maintainable* is significantly harder in C, unless the project is really
small.

agreed.

however, it is worth nothing that C and C++ better lend themselves to,
and thus traditionally use, notably different ways of achieving abstraction.

one language is not the other.


C++ more traditionally uses structural abstractions (templates being a
major example, also classes), where basically one has "something" which
can be interacted with, but hides its internal workings from view.

these common structures are then often shared over large portions of the
codebase, and it is assumed that some level of commonality is achieved
by consistent use of the same structures and abstractions across much of
the program.

hence, code reuse and uniformity are somewhat emphasized in this style.


C more traditionally is abstracted regionally, more like a large number
of brick-walled cities. all sorts of things can happen within a given
set of walls, and what happens outside is "none of anyone's business"
(typically, at any particular location, the level of abstraction is
fairly low, with bit-twiddling and mucking around with pointers and
pointer-arithmetic being "the business of the day").

typically, at the high-level, abstraction is achieved by essentially
enforcing these walls, and limiting or prohibiting interactions between
disparate systems ("action at a distance").

typically, this is done at a much coarser level than in traditional OOP
(say, an individual component could be easily anywhere from 10 to 50 kloc).


even though similar algorithms/... may be used in different places, it
is usually against-policy to access them directly, and in-fact it is
more common to simply copy/paste/edit the code into the new location,
specifically as this will avoid creating a dependency between otherwise
unrelated components (any such dependency may limit the ability for one
part to be changed independent of the other, compromising flexibility).

so, typically components are only allowed to directly interact with
"adjacent" components, and usually then "through a brick wall" (a set of
public API functions).

often, OS facilities are fit into the model in roughly a similar manner,
so code in one place may be allowed to use certain OS facilities, and in
another place, doing so will be forbidden.

which data-types, API calls, ... will also depend very much on where the
code is located (every city has, to a large extent, its own local rules
and customs, which may be strictly enforced).


other cases, where a more fluid structuring is needed, typically one may
have APIs which simply serve to redirect somewhere else or to something
else (basically, APIs serving a role mostly to ease communication
between components while at the same time attempting to avoid
compromising borders).

typically the goal of such an API is to provide a common interface to
functionality exposed by several different components. however, its own
local conventions are unique to itself (and similar rules apply as
before, it itself may be subject to only being allowed in certain code
regions).

sometimes, the combinations of the above may lead to a certain amount of
indirection (FWIW, interface-routing APIs, namely exposing an API to
allow certain functionality in a region of code where otherwise it would
not have been allowed).

....



but, these differences may lead to very different views WRT things like
ideal system architecture and development practices.

I don't personally believe any of this to be matters of "good" vs "bad"
(or "competent" vs "incompetent", or "smart" vs "stupid") or anything of
the sort, rather, the ultimate higher goal is "what works best in a
given situation".


or such...

 

[Bo Persson]

however, avoiding writing little bits of code is not nearly so high
on many peoples' priority list.



except when n is usually sufficiently small as to be ignorable...

how long is a typical string on which one may use strlen?...
maybe 3-20 characters...

given the compiler will typically replace it with something like
"repnz scasb" anyways, it is not usually a big deal.

Ok, so being 10% slower or faster isn't that important after all?


Bo Persson

 

[BGB]

Ok, so being 10% slower or faster isn't that important after all?

not usually.


sometimes, it may well also be preferable to intern all of ones strings
into a strings table, which is one case where null terminated strings
work fairly well (the strings may be packed end-to-end in a reasonably
memory-compact manner).

interned string types may be itself a significant use-case FWIW (along
with UTF-8).


it is also fairly common, OTOH, for people so pass std::string objects
by-value, which may in turn eat a lot of cycles simply copying the
things around.


so, it can probably go either way.


probably far more significant may well be ones' choice of compiler and
compiler settings, say code compiled with "/O2 /Oi /Oy" is different
than "/Z7 /ZI /Ge"

nevermind if someone throws a "/clrure" or similar in the mix...

or, in GCC terms: "-O3" vs "-g -pg" or similar.


these types of options often have a more notable effect on overall
performance.

 

[James Kanze]

in
[...]

Writing fast code in C is significantly harder, because of the
lack of encapsulation.

Only if one tries to emulate encapsulation by using means of non-zero
runtime cost, like dynamically allocated data structures accessed via
opaque pointers. If one does not attempt to have any encapsulation, then
there is nothing which would get in the way of having fast code. Of
course, ensuring that this fast code is also *correct* and *robust* and
*maintainable* is significantly harder in C, unless the project is really
small.

The fact that the maintainability is significantly harder means
that modifying the code to improve its performance is
significantly harder. That's precisely my point.

 

[Juha Nieminen]

however, avoiding writing little bits of code is not nearly so high on
many peoples' priority list.

Implementing a fast comparison-based sort function which is efficient
with all possible inputs isn't just a "little bit of code". It's actually
pretty complicated. (Quicksort is a relatively short algorithm, although
not many people can implement correctly it on the spot, without looking
somewhere the details. However, quicksort has worst-case scenarios that
make it extremely inefficient. To make it efficient in all cases you need
to use optimizations which are much more laborious to implement. Or use
some other sorting algorithm, which will either be slower than quicksort
(such as heap sort) or consume a lot more memory (such as merge sort).)

Doing a binary search on a sorted array, while extremely small piece
of code, is surprisingly hard to get correct on-the-spot. I remember a
study that showed that something like over half of experienced professional
programmers implemented it incorrectly when they couldn't look for a
reference. (Off-by-one errors can be pretty annoying.)

When you need a more complex algorithm or data container, the amount
of work can be daunting. For example implementing a balanced binary tree
is far from trivial.

Anyways, why should one have to write algorithms always from scratch?
If I want to sort an array, I don't want to write a sorting algorithm each
time, no matter if it takes just three lines of code. There's no need.
There *shouldn't* be no need.

In fact, it's not just a question of convenience. It's a question of
code correctness. When the algorithm implementation has been tested for
years by millions of people, you can be pretty certain that it's correct.
If you implement it yourself, there's a good chance that there will be a
bug that might not be immediately apparent, and might kick in unexpectedly.

 

[Keith H Duggar]

however, avoiding writing little bits of code is not nearly so high on
many peoples' priority list.

  Implementing a fast comparison-based sort function which is efficient
with all possible inputs isn't just a "little bit of code". It's actually
pretty complicated.

[snip sort details]

  Anyways, why should one have to write algorithms always from scratch?
If I want to sort an array, I don't want to write a sorting algorithm each
time, no matter if it takes just three lines of code. There's no need.
There *shouldn't* be no need.

  In fact, it's not just a question of convenience. It's a question of
code correctness. When the algorithm implementation has been tested for
years by millions of people, you can be pretty certain that it's correct.
If you implement it yourself, there's a good chance that there will be a
bug that might not be immediately apparent, and might kick in unexpectedly.

Furthermore code reuse is the only remaining practical way to
dramatically increase programmer productivity beyond what has
already been achieved with language improvement. The language
that will win the future is the one that best supports coding
modular easily reusable /high performance/ libraries. The C++
template based generic programming model, as ugly as it might
be, has hybridized with other C++ features to yield a strange
crossbreed that is proving revolutionary is this regard.

KHD

 

[BGB]

Implementing a fast comparison-based sort function which is efficient
with all possible inputs isn't just a "little bit of code". It's actually
pretty complicated. (Quicksort is a relatively short algorithm, although
not many people can implement correctly it on the spot, without looking
somewhere the details. However, quicksort has worst-case scenarios that
make it extremely inefficient. To make it efficient in all cases you need
to use optimizations which are much more laborious to implement. Or use
some other sorting algorithm, which will either be slower than quicksort
(such as heap sort) or consume a lot more memory (such as merge sort).)

Doing a binary search on a sorted array, while extremely small piece
of code, is surprisingly hard to get correct on-the-spot. I remember a
study that showed that something like over half of experienced professional
programmers implemented it incorrectly when they couldn't look for a
reference. (Off-by-one errors can be pretty annoying.)

typically, this is where one uses their memory.

it is not about having to re-design it every time, but one has seen or
written it previously, so it is kept in memory until it is needed again.


granted, I guess there are variations in memory abilities, much like how
sometimes it can be bewildering just trying to remember what was going
on the previous day. I guess it is conceivable that a person could
remember the previous day better than they can keep a pile of
source-code in memory for an extended period of time.

When you need a more complex algorithm or data container, the amount
of work can be daunting. For example implementing a balanced binary tree
is far from trivial.

things like AVL trees, ... are not all that complicated.


there are much worse things to implement by hand, such as the code to
build a BSP tree or perform rigid-body physics type stuff. but, then,
once one has done it once, they then have a much better understanding of
the algorithms, and is much more likely to be able to do similar again
later, or experiment with variations on the algorithms, ...


but, if they don't learn the algorithm in the first place (by
implementing it themselves), how can they really hope to fully
understand it?

it is like, an algorithm is often never really fully understood until
one writes it for themselves.

also, reusing code written by others' may deprive one of the experience
of having done it themselves (and beating on and debugging code can be
an otherwise fairly enjoyable experience, sort of like a puzzle of sorts
or similar), ...

like "why does this not work?", so one grabs their hat and their net and
goes hunting for bugs (or clues as to the nature of said bugs, as one
tracks them down and fixes them...).

Anyways, why should one have to write algorithms always from scratch?
If I want to sort an array, I don't want to write a sorting algorithm each
time, no matter if it takes just three lines of code. There's no need.
There *shouldn't* be no need.

usually one does it this way because "this is how it is done".

depending on specifics though, it is usually more about 50 to 100 lines
(both for the basic quicksort, and for the fallback sort for the n^2 case).

In fact, it's not just a question of convenience. It's a question of
code correctness. When the algorithm implementation has been tested for
years by millions of people, you can be pretty certain that it's correct.
If you implement it yourself, there's a good chance that there will be a
bug that might not be immediately apparent, and might kick in unexpectedly.

this may or may not matter.
for many apps, if it breaks, one goes and debugs it.

granted, yes, sometimes there are subtle bugs here and there that are
difficult to track down, like one wondering why every once in a great
while their custom implementation of deflate or JPEG will randomly fail
(producing garbage output, or the Huffman decoder randomly going berserk).

but, with enough use, typically bugs will get beaten out, or one is
eventually forced to give in and resort to living with a library
dependency (a very sad day these can be, as on is defeated and shown a
task beyond their' abilities).

 

[Nick Keighley]

On 9/2/2011 10:51 PM, Juha Nieminen wrote



this again, comes down to coding practices...

also, just how many people really use "qsort()" anyways?...

If I'm coding in C and I want to sort something. My first thought
would be qsort()! If it was too slow only then would I consider hand
coding it. Surely any constructively lazy person would use an existing
facility rather hand-roll their own!

IME, it is more often one of those largely forgotten functions (it is
there, but more often people write out their own sort logic manually).

why?! There must be nearly as many badly written sort routines as
there are badly implemented linked lists!

(actually, it seems to be fairly common practice in C land for people to
largely ignore much of the standard library, and to write their own
logic for doing things).

not in my part of C land. I use the available libraries and encourage
other's to do the same.

Yes the C libraries are far less rich than the C++ libraries but
they're still there and provide some basic fucntionality.

it is also not clear that std::string would be, in general, faster, and
having an O(1) ability to fetch the length may turn out to be moot if
most other operations tend towards being more expensive.

are they?

 

[Juha Nieminen]

but, if they don't learn the algorithm in the first place (by
implementing it themselves), how can they really hope to fully
understand it?

I have never implemented a balanced binary tree myself, but I know
pretty well how a red-black tree works (which is the most common way of
implementing std::set and std::map), how fast it is, and what kind of
advantages and disadvantages it has (in terms of speed and memory usage).
I have a good grasp of asymptotical behavior, as well as an understanding
of the major constant factor bottlenecks of such a tree (the largest one
by far being the memory allocation done to each individual node).

Also, I have never implemented a full introspective sort (which is the
most typical implementation of std::sort) myself, but I know what it's
composed of (quicksort, insertion sort and heap sort) and I have actually
measured its speed against typical "vanilla" sorting algorithms. (std::sort
is really hard to beat.)

I don't need to implement these things myself to know how they work,
how fast they are and what their strenghs and weaknesses are.

usually one does it this way because "this is how it is done".

Please don't take this the wrong way, but can't you see that you are
making excuses to defend the language for no other reason that the language
is lacking, yet nevertheless very popular?

(And I'm not saying that C++ is not lacking. It certainly is. However,
it's much less so than C.)

 

[BGB]

I have never implemented a balanced binary tree myself, but I know
pretty well how a red-black tree works (which is the most common way of
implementing std::set and std::map), how fast it is, and what kind of
advantages and disadvantages it has (in terms of speed and memory usage).
I have a good grasp of asymptotical behavior, as well as an understanding
of the major constant factor bottlenecks of such a tree (the largest one
by far being the memory allocation done to each individual node).

Also, I have never implemented a full introspective sort (which is the
most typical implementation of std::sort) myself, but I know what it's
composed of (quicksort, insertion sort and heap sort) and I have actually
measured its speed against typical "vanilla" sorting algorithms. (std::sort
is really hard to beat.)

I don't need to implement these things myself to know how they work,
how fast they are and what their strenghs and weaknesses are.

but, this is only understanding their surface behavior, but there are
likely many subtleties in the algorithms which may be missed this way.

it is like, a person who simply uses a compiler, but never writes one,
may be stuck perpetually in a world of "well, it takes source code, and
gives me EXE files".

but, in implementing it themselves, one can understand the various
tradeoffs made, possible nifty variations and alternate possibilities, ...


for example, after I learned the Qucksort algo, I realized I could
combine it with a BSP building algo (replacing my prior set of O(n^2)
BSP algos), the result being able to rebuild a BSP tree in O(n log2 n)
time, or essentially, in realtime.

(nevermind that my 3D engine later ended up using a Doom3-like lighting
strategy, which has some of its own drawbacks...).

but, anyways, if one does not know the algorithms, they can't make use
of them in new ways.


granted, there is some possible overlap with psychology here, like SP
(Sensing Perciever) vs NT (Intuituve Thinker) or similar.

or "learn by doing" vs "learn by reading lots of crap and pondering" or
similar.

Please don't take this the wrong way, but can't you see that you are
making excuses to defend the language for no other reason that the language
is lacking, yet nevertheless very popular?

as I see it, it is likely a statement of fact, much as how there are
still plenty of people who use C.

lots of people use C;
lots of people who use C do so by reimplementing things.

(And I'm not saying that C++ is not lacking. It certainly is. However,
it's much less so than C.)

in terms of usability, maybe.
there is more to the world than usability though.


this is, FWIW, why many projects make use of scripting languages as well.

then one has a lower-level language (such as C) for most of the
down-to-the-metal parts of the project, and resorts to the scripting
language for higher-level parts of the project (say: user interface,
application logic / behavior, ...).

 

[BGB]

If I'm coding in C and I want to sort something. My first thought
would be qsort()! If it was too slow only then would I consider hand
coding it. Surely any constructively lazy person would use an existing
facility rather hand-roll their own!

different styles for different sorts...


actually, in my case I would probably far more likely copy-paste it and
then edit it to the new use.

copy-paste is a powerful tool which is often disparaged and overlooked.

but, one would typically write it themselves initially (before
subjecting it to endless copy-paste).

why?! There must be nearly as many badly written sort routines as
there are badly implemented linked lists!

if people were not doing it, then one would not be encountering them.

that one is encountering so many "badly written sort functions" means
that there are equally many (probably actually, far more) people off
writing them.

hence, the case stands...

not in my part of C land. I use the available libraries and encourage
other's to do the same.

Yes the C libraries are far less rich than the C++ libraries but
they're still there and provide some basic fucntionality.

it is the case though in many parts of C land I have seen though (mostly
GPL/FOSS/... style projects, FWIW commercial C code could look very
different, but I wouldn't know because much more of it is kept behind
locked doors).

but, if initially commercial projects count, such as Quake 1/2/3, it
appears to be not that much different (apparently for Doom3 John Carmack
used C++ though, but why would be a subject of further investigation).


actually, to some extent a lot of my "initially learning programming"
stuff came from looking at things like a lot of Carmack's code and the
Linux kernel and similar (and hacking on the Quake engine and similar).

but, yes, all of this was a great many years ago...


interestingly, I remember in the past at one point where a person had
commented that my coding style somewhat resembled Carmack's, which I
guess stands to reason...

are they?

from what I have seen, people tend to pass them around by-value.

apparently, the by-value vs by-reference thing makes a bit of a
difference WRT performance.

apparently, their performance characteristics also differ some between
GCC and MSVC, with the ones in MSVC apparently tending to be more expensive.

granted, I haven't personally looked into all of this in-depth though.


there are also plenty of things often done with C strings as well that
can make them faster, such as interning them so that one can check
string equality using '==' on the pointers, rather than using
"!strcmp()", ...


in my case, I tend to avoid "stdrup()" as well, as generally "strdup()"
is a good way to "make bad things happen" (slow, tears through huge
amounts of memory, leaves the program responsible to free them, ...), so
preferable IMO is interning them into string-tables (a big glob of
memory where they are packed end-to-end).

then one can free the whole string table as part of a "teardown" process.

another strategy (used elsewhere) is to allocate the strings in the
garbage-collected heap (I use GC), and then manage them using a weak
hash (entries will be reset to NULL whenever any are reclaimed by the GC).


also, == and != work provided both strings are in the same string-table.


but, then, this is turning more into details of "how does one use them?"
than "which is faster?"...

 

[Ian Collins]

different styles for different sorts...


actually, in my case I would probably far more likely copy-paste it and
then edit it to the new use.

copy-paste is a powerful tool which is often disparaged and overlooked.

Rightly so. C has things call functions that enable code to be reused
and C++ has function templates that remove the last excuse for copy and
paste.

but, one would typically write it themselves initially (before
subjecting it to endless copy-paste).

Not if they were being paid to deliver software.

from what I have seen, people tend to pass them around by-value.

Most C++ code passes strings by const reference.

apparently, the by-value vs by-reference thing makes a bit of a
difference WRT performance.

apparently, their performance characteristics also differ some between
GCC and MSVC, with the ones in MSVC apparently tending to be more expensive.

granted, I haven't personally looked into all of this in-depth though.

With some compilers in some modes, passing a string by value will be
quicker if the string object (typically a pair of pointers) is small
enough to pass in registers.

there are also plenty of things often done with C strings as well that
can make them faster, such as interning them so that one can check
string equality using '==' on the pointers, rather than using
"!strcmp()", ...

In other words, wrapping them like std::string...

in my case, I tend to avoid "stdrup()" as well, as generally "strdup()"
is a good way to "make bad things happen" (slow, tears through huge
amounts of memory, leaves the program responsible to free them, ...), so
preferable IMO is interning them into string-tables (a big glob of
memory where they are packed end-to-end).

then one can free the whole string table as part of a "teardown" process.

another strategy (used elsewhere) is to allocate the strings in the
garbage-collected heap (I use GC), and then manage them using a weak
hash (entries will be reset to NULL whenever any are reclaimed by the GC).


also, == and != work provided both strings are in the same string-table.

Or save a whole lot of pain and use std::string.