C/C++ question about dynamic "static struct"

[Öö Tiib]

Now I'm curious. Is there any fundamental reason why "C/C++ standard
allocator tends to have horrendous efficiency" (leaving aside the
compacting bit)? I'm sure people have put a lot of wisdom and work into
standard allocators, why would my custom allocator on top of the standard
one behave better?

I can give some statistics that may variate from OS and compiler and hardware but rough about average desktop computer:
* allocating million of little objects takes about half a second.
* destroying million of little objects takes about 5 seconds.
* allocating little object takes at least 32 bytes of memory.
So it is clearly bad idea to allocate lot of < 32 byte objects separately.
Better is to pool them somehow and/or to use intrusive containers, intrusive reference counting and/or to pass < 32 byte objects by value.

I think that Juha has had bad experience with that above. On the flip-side he
probably has no experience how Java's garbage collector also hangs an application for 15 minutes with 6GB of application's memory used. So allocating
lot of little crap is harmful for both languages, just that C++ has more and better ways how to climb out of the hole.

 

[Öö Tiib]

On the flip-side he probably has no experience how Java's garbage collector
also hangs an application for 15 minutes with 6GB of application's memory
used.

To clarify: I see that what I wrote might leave impression that one collection
takes so long. No. Not GC alone, but an algorithm that does lots of little
allocations. The profiling shows that majority of the effort goes to GC.
Getting rid of dynamic allocations would give order of magnitude speedup. That
is very difficult to achieve with Java where idiomatic code has 'new' every
third line.

 

[Juha Nieminen]

Now I'm curious. Is there any fundamental reason why "C/C++ standard
allocator tends to have horrendous efficiency" (leaving aside the
compacting bit)? I'm sure people have put a lot of wisdom and work into
standard allocators, why would my custom allocator on top of the standard
one behave better?

According to my tests, the two major reasons for the slowness are
cache inefficiency and thread-safety.

Especially in situations where little random-sized blocks of memory
are constantly being allocated and deallocated pretty at random (at
least from the allocator's point of view, which obviously doesn't see
any logic, just the allocation requests), the memory gets more and
more fragmented, and the list of free blocks gets more and more
randomized. This means that after a little while most memory blocks
will be located at wildly random locations, causing lots of cache misses
(both when allocated and deallocated, and also when accesses from the
program).

This is where memory compaction could help a lot. Even if the compaction
takes some resources, the end result is that after the process subsequent
allocations will be enormously faster (because they are much more cache
friendly.) The overall speed of the program could see significant increases
(depending a lot on the program, of course.)

Cache optimality is not something to be dismissed lightly. Even inside
your own code you can achieve enormous speedups by organizing the
memory usage such that it becomes more cache-efficient (by increasing
cache locality.) A program can become several times faster just because
of this.

The other reason is that the C standard allocator (also used by C++) is
thread-safe: It's ready as-is to be used in multithreaded programs. This
inevitably causes overhead (which would be unneeded especially in a
single-threaded program.)

While according to my experiments it has got a lot better (perhaps
because of development, or because of better hardware, or possibly
a combination of both), it still causes a quite measurable slowdown.

I don't know exactly how a JVM memory allocator solves both problems,
but seemingly they tend to be pretty good at it (helped by the fact
that Java's semantics allows for things like memory compaction.)

 

[Juha Nieminen]

I think that Juha has had bad experience with that above. On the
flip-side he probably has no experience how Java's garbage collector
also hangs an application for 15 minutes with 6GB of application's
memory used. So allocating lot of little crap is harmful for both
languages, just that C++ has more and better ways how to climb out
of the hole.

I'm not saying there aren't situations in Java when the GC engine
becomes a real resource hog, but in typical-sized programs handling
typical amounts of data it's not very usual, AFAIK.

I suppose that both in Java and C++ you need to know how to optimize
your memory usage if you want maximum efficiency.

 

[Juha Nieminen]

Reasonable people can disagree about the merits of C viz-a-viz C++. But
reasonable people cannot disagree that C is still very much in use in all
the same places that C++ is used, for both new and old code. It's not
relegated to device drivers and embedded work, by any stretch of the
imagination.

It's just that in an environment where both C and C++ are equally
viable options (which is most of the environments where you would
want to use either one), most experienced C++ programmers can't think
of any reason why they should limit themselves to C. Because, to be
frank, that would be quite a serious limitation.

C++ might be big and have tons and tons of features, but once you become
really experienced with it, it just becomes so much *esier* to do things
with it than with C. Just the standard library alone makes life so much
easier (no matter if you are just making a quick 50-line test program
or a large 50k-line serious project.)

 

[Ian Collins]

I'm not saying there aren't situations in Java when the GC engine
becomes a real resource hog, but in typical-sized programs handling
typical amounts of data it's not very usual, AFAIK.

The same could be said for C++ and the standard allocator. In both
languages it is extreme cases that cause problems. I guess with it's
greater flexibility, C++ offers more opportunities for optimisation.

I suppose that both in Java and C++ you need to know how to optimize
your memory usage if you want maximum efficiency.

Indeed.

 

[James Kuyper]

On 10/19/2012 05:29 PM, Juha Nieminen wrote:
....

It's just that in an environment where both C and C++ are equally
viable options (which is most of the environments where you would
want to use either one), most experienced C++ programmers can't think
of any reason why they should limit themselves to C. Because, to be
frank, that would be quite a serious limitation.

I'm sure that's quite normal thinking for anyone who would label
themselves a "C++ programmer". However, you should not be surprised to
find very different thinking among the people frequenting comp.lang.c,
where this message is also cross-posted. Anyone bothering to monitor
comp.lang.c (and there's a fair number of us) can reasonably be expected
to choose the simplicity of C over the complexity of C++ in at least
some circumstances. You might question the validity of that choice, but
you can't expect such questions to go over very well in that newsgroup.

 

[Ian Collins]

On 10/19/2012 05:29 PM, Juha Nieminen wrote:
....

I'm sure that's quite normal thinking for anyone who would label
themselves a "C++ programmer". However, you should not be surprised to
find very different thinking among the people frequenting comp.lang.c,
where this message is also cross-posted. Anyone bothering to monitor
comp.lang.c (and there's a fair number of us) can reasonably be expected
to choose the simplicity of C over the complexity of C++ in at least
some circumstances. You might question the validity of that choice, but
you can't expect such questions to go over very well in that newsgroup.

A one who works with and enjoys both languages, the statement "choose
the simplicity of C over the complexity of C++" is one I have trouble
with. C is undoubtedly a simpler language, but the the solutions to
many day to day problems are undoubtedly simpler in C++.

So the choice is often "do I want the simple solution in a more complex
language, or the more complex solution in a simple language?".

 

[Fritz Wuehler]

understanding of the language. Thanks to Noob and others I got the code
to work. So, even if the answers given were "vague, incorrect and
outright incompetent", they got me on the right track.

Didn't go through the thread but just because code seems to work doesn't
mean it's good code. There are plenty of bad ways to get code to produce
correct results.

 

[Juha Nieminen]

A one who works with and enjoys both languages, the statement "choose
the simplicity of C over the complexity of C++" is one I have trouble
with. C is undoubtedly a simpler language, but the the solutions to
many day to day problems are undoubtedly simpler in C++.

So the choice is often "do I want the simple solution in a more complex
language, or the more complex solution in a simple language?".

That's also the problem I find with the "argument from simplicity",
as one could call it.

When talking about C, making the simplicity argument is basically a
category error. The argument is trying to appeal to the notion that
simpler higher-level languages (such as Lisp) are generally considered
better than overly complex languages. In those languages it is often
so that the same thing can be expressed in a much simpler and more
brief manner, and the result is much "leaner and cleaner" code than
in overly complicated languages. (For example the language specification
of Lisp is relatively short, yet the language itself is incredibly
expressive and powerful.)

In other words, a simple language helps writing simple programs (that
are nevertheless very expressive.)

However, in the case of C the "simplicity" is not actually a factor
that helps writing simple programs. On the contrary, the "simplicity"
of the language is actually a limiting factor. Rather than help, it
impedes the writing of simple programs, requiring many of even the
simplest tasks to have complex and error-prone implementations. It
often requires following strict coding conventions to avoid mistakes,
coding conventions that are completely unnecessary in truly simple
languages. Truly simple languages allow the programmer to concentrate
purely on the task at hand, without having to pay any attention to such
trivial and inconsequential matters as memory management and such.
C isn't that kind of language. In C the "simplicity" forces the
programmer to write complex programs that need to constantly be careful
about things that should normally be non-issues.

This doesn't mean that C++ is a simple language in this regard.
However, C++ is a lot *better* in this regard than C. Yes, there are
coding conventions that need to be followed eg. because of memory
management reasons, but those conventions are simpler and easier to
follow, and much of the work is done automatically by the compiler.
C++ also offers many tools (in both native syntax and in the form of
the standard library) that makes many, many tasks a lot easier and
simpler than in C.

The typical arguments that C++ is so much larger and more complex
than C, and that it requires significantly more learning, ring quite
hollow to the experienced C++ programmer. Why would it matter to me
in the least bit if the language is large and requires a lot of
learning? That's completely inconsequential to me. It may be relevant
if we were talking about what a newbie programmer should learn, but
it's completely irrelevant to me. I know how to use the language
efficiently, and when given the choice between C or C++, there's just
no choice to make, because it's obvious. I choose the one that allows
me to implement the task at hand more easily, ie. C++.

 

[Stuart]

Umm, my question (which started this whole sub-thread) was not meant to
critisize C programmers. I rather think that every C programmer is
already a C++ programmer in disguise, since (mostly) all he has to do is
to rename the source file from .c to .cpp/.cc/.mm. He can't do that if
the project at hand forbids this. I was more or less interested whether
C programmers deliberately chose C over C++ or whether they had no other
choice.

[snip]

That's also the problem I find with the "argument from simplicity",
as one could call it.

When talking about C, making the simplicity argument is basically a
category error. The argument is trying to appeal to the notion that
simpler higher-level languages (such as Lisp) are generally considered
better than overly complex languages. In those languages it is often
so that the same thing can be expressed in a much simpler and more
brief manner, and the result is much "leaner and cleaner" code than
in overly complicated languages. (For example the language specification
of Lisp is relatively short, yet the language itself is incredibly
expressive and powerful.)

In other words, a simple language helps writing simple programs (that
are nevertheless very expressive.)

However, in the case of C the "simplicity" is not actually a factor
that helps writing simple programs. On the contrary, the "simplicity"
of the language is actually a limiting factor. Rather than help, it
impedes the writing of simple programs, requiring many of even the
simplest tasks to have complex and error-prone implementations. It
often requires following strict coding conventions to avoid mistakes,
coding conventions that are completely unnecessary in truly simple
languages. Truly simple languages allow the programmer to concentrate
purely on the task at hand, without having to pay any attention to such
trivial and inconsequential matters as memory management and such.
C isn't that kind of language. In C the "simplicity" forces the
programmer to write complex programs that need to constantly be careful
about things that should normally be non-issues.

This doesn't mean that C++ is a simple language in this regard.
However, C++ is a lot *better* in this regard than C. Yes, there are
coding conventions that need to be followed eg. because of memory
management reasons, but those conventions are simpler and easier to
follow, and much of the work is done automatically by the compiler.
C++ also offers many tools (in both native syntax and in the form of
the standard library) that makes many, many tasks a lot easier and
simpler than in C.

The typical arguments that C++ is so much larger and more complex
than C, and that it requires significantly more learning, ring quite
hollow to the experienced C++ programmer. Why would it matter to me
in the least bit if the language is large and requires a lot of
learning? That's completely inconsequential to me. It may be relevant
if we were talking about what a newbie programmer should learn, but
it's completely irrelevant to me. I know how to use the language
efficiently, and when given the choice between C or C++, there's just
no choice to make, because it's obvious. I choose the one that allows
me to implement the task at hand more easily, ie. C++.

Nicely put, almost textbook.

There is another argument that could convince me to use C instead of
C++: If the simplicity of the language C allowed it to be both compiled
as well as interpreted, then I would favour C (AFAIK, Java's syntax was
deliberately kept "simple" so that code can be added at run-time,
something that would be real nightmare under C++). However, there is no
such C interpreter (at least I don't know one).

Just a side note: Apparently Apple thinks that C++ is so much more
complicated than C that their Xcode IDE refuses to refactor ObjectiveC++
code whereas it accepts ObjectiveC code just fine. Strange, but true.

Regards,
Stuart

 

[Ben Bacarisse]

There is another argument that could convince me to use C instead of
C++: If the simplicity of the language C allowed it to be both
compiled as well as interpreted, then I would favour C (AFAIK, Java's
syntax was deliberately kept "simple" so that code can be added at
run-time, something that would be real nightmare under C++). However,
there is no such C interpreter (at least I don't know one).

Well, there's TinyCC. Not exactly an interpreter, but a very fast
compiler built as a library so you can embed C in other applications.
E.g. you can compile and run a string.

<snip>

 

[BartC]

Scripting can also be a good argument against C++. Although there are
efforts to provide C++ scripting environments, this is probably too
difficult a task for the open-source community (and the industry does not
seem to be bothered with such a thing). I have only ever seen BGB who
designed a language called BGBScript that resembles C and can be either
compiled and interpreted, but chances are little that his language will
become main-stream.

There's a language called C++Script
(http://calumgrant.net/cppscript/index.html#).

According to the docs, you can use this to write dynamically-typed scripting
programs very easily, and yet the result will compile under C++.

(That C++ makes this possible ought to be impressive; but to me it shows
that C++ is too much about language-building features, rather than
programming.)

The BGBScript project I believe was supposed to be a version of
ECMA/Javascript; I guess you could call these 'mainstream'.

 

[James Kuyper]

On 10/19/2012 07:13 PM, Ian Collins wrote:
....

A one who works with and enjoys both languages, the statement "choose
the simplicity of C over the complexity of C++" is one I have trouble
with. C is undoubtedly a simpler language, but the the solutions to
many day to day problems are undoubtedly simpler in C++.

So the choice is often "do I want the simple solution in a more complex
language, or the more complex solution in a simple language?".

I've seen C++ used to create complex solutions to simple problems. My
favorite example is use of the Singleton pattern to produce code with
precisely the same potential dangers as would occur if a global variable
was used, and much greater complexity. Because of course, global
variables are "evil", and use of a named "pattern" is "good".

Of course, overly complex solutions can also be created in C, and good
programmers will produce better solutions, regardless of the language
they use. However, I think the larger feature set of C++ does more to
encourage this particular type of bad programming than C does.

 

[Nick Keighley]

On 10/18/12 James Kuyper wrote:
[snip]> I'm primarily a C programmer, so I may be

missing out some elegant C++ way of doing that, but the following
inelegant (and untested) code should do the job:

[snip]

I'm intrigued. I have never ever met someone who described himself as a
C programmer. May I ask what kind of business you are in? My guess is
your line of work includes either device drivers, embedded devices,
kernel code or something else that forces you to write C instead of C++.
In all these years I have never met someone who used C instead of C++
unless he was forced to do so.

seriously? I know quite a few people who are C programmers. Most are
embedded but not all.

I can see the appeal. I know pretty much all of C. I only know a large
percentage of C++. I haven't got round to the new C++ standard. I
don't know every little corner of the standard library and I certainly
don't know boost! Do you write exception safe code?

Please don't mention template-meta-programming...

 

[Nick Keighley]

On 10/19/12 James Kuyper wrote:
On 10/20/12 Juha Nieminen wrote:

Umm, my question (which started this whole sub-thread) was not meant to
critisize C programmers. I rather think that every C programmer is
already a C++ programmer in disguise, since (mostly) all he has to do is
to rename the source file from .c to .cpp/.cc/.mm. He can't do that if
the project at hand forbids this. I was more or less interested whether
C programmers deliberately chose C over C++ or whether they had no other
choice.

bizzare definition of "C++ programmer". Many of the people I classify
as "C programmers" *you'd* classify as "C++ programmers"!. Some of
these people were actually using a C++ compiler and sometimes weren't
aware they were using C++ (using true and false for instance); but
nevertheless they were C programmers. To be a C++ programmer I submit
you have to use a significant part of non-C C++.

I'm not sure I agree

I'm not sure I'd call Common Lisp "simple"... Scheme maybe.

I simply disagree

for instance?

I'm not aware of these coding conventions

I'm more aware of the coding conventions required in C++ (RAII for
instance)

 

[Öö Tiib]

On 10/19/2012 07:13 PM, Ian Collins wrote:
...

I've seen C++ used to create complex solutions to simple problems. My
favorite example is use of the Singleton pattern to produce code with
precisely the same potential dangers as would occur if a global variable
was used, and much greater complexity. Because of course, global
variables are "evil", and use of a named "pattern" is "good".

I think that Singleton design pattern is as terribly out of fashion as Waterfall
process pattern. I see more often stateless objects enwrapping access to common
state instead of Singletons or global state in C++.

Of course, overly complex solutions can also be created in C, and good
programmers will produce better solutions, regardless of the language
they use. However, I think the larger feature set of C++ does more to
encourage this particular type of bad programming than C does.

Trouble with C++ is cheapness to perceptually hide the costs of such bloat that you
describe. Expensive implicit conversion constructors, expensive overloaded operators and
such. Nothing to do ... we just teach novices how not to ... and they learn.

 

[Les Cargill]

It's just that in an environment where both C and C++ are equally
viable options (which is most of the environments where you would
want to use either one), most experienced C++ programmers can't think
of any reason why they should limit themselves to C. Because, to be
frank, that would be quite a serious limitation.

Unless you put some serious time on on non-C++ 'C', you will
think rather differently than someone who has. Path dependence
is path dependent.

C++ might be big and have tons and tons of features, but once you become
really experienced with it, it just becomes so much *esier* to do things
with it than with C.

I really do not know about that. Just the general schism over string
types alone makes life much more difficult. The whole subject is
fraught with massive observer bias.

Just the standard library alone makes life so much
easier (no matter if you are just making a quick 50-line test program
or a large 50k-line serious project.)

Or you get an old version of STL that's buggy and there's an observed
problem that takes up to a *year* ( off and on - not continuous
pushing ) to resolve. Which you do by replacing an stl::map() with
a bleeding-edge string table in a 'C' fashion

Also, I once had a ... data structure that I built with a need
for associativity ( think arrays indexed by strings ) where it
was twice the code* and half the performance to use STL than
bash something out in 'C'. Oh, if STL had only had "foreach"
from the start....

*no, I am not going to specify how that figure was arrived at...

What we do is settle on classes of solutions, and stay there.

 

[Les Cargill]

That's also the problem I find with the "argument from simplicity",
as one could call it.

When talking about C, making the simplicity argument is basically a
category error.

Almost all arguments from "category error" are themselves category
errors. So "mu". I've seen Oxford dons make massive piles of steaming
nonsense out of "category error".

The argument is trying to appeal to the notion that
simpler higher-level languages (such as Lisp) are generally considered
better than overly complex languages. In those languages it is often
so that the same thing can be expressed in a much simpler and more
brief manner, and the result is much "leaner and cleaner" code than
in overly complicated languages. (For example the language specification
of Lisp is relatively short, yet the language itself is incredibly
expressive and powerful.)

In other words, a simple language helps writing simple programs (that
are nevertheless very expressive.)

No, the thing about lisp is that it is *interpretive*.

However, in the case of C the "simplicity" is not actually a factor
that helps writing simple programs. On the contrary, the "simplicity"
of the language is actually a limiting factor. Rather than help, it
impedes the writing of simple programs, requiring many of even the
simplest tasks to have complex and error-prone implementations. It
often requires following strict coding conventions to avoid mistakes,
coding conventions that are completely unnecessary in truly simple
languages. Truly simple languages allow the programmer to concentrate
purely on the task at hand, without having to pay any attention to such
trivial and inconsequential matters as memory management and such.

C++ is much *worse* for memory management than is 'C' - in that
the possibility of memory leaks goes up. Absent writing GUI code,
it's entirely possible to write entire deployable systems that use no
dynamic memory at all in 'C'. indeed, that's been the shop
standard most places I have worked.

C isn't that kind of language. In C the "simplicity" forces the
programmer to write complex programs that need to constantly be careful
about things that should normally be non-issues.

This doesn't mean that C++ is a simple language in this regard.
However, C++ is a lot *better* in this regard than C. Yes, there are
coding conventions that need to be followed eg. because of memory
management reasons, but those conventions are simpler and easier to
follow, and much of the work is done automatically by the compiler.

Not... really. Let's not confuse our preferences for facts, shall we?
The subject is sufficiently complex that you have to figure out how to
measure the thing being discussed - you can't constructively assert
superiority with out doing a lot of work, and that's pretty boring
work. It's actually both boring and terrifying.

C++ also offers many tools (in both native syntax and in the form of
the standard library) that makes many, many tasks a lot easier and
simpler than in C.

To my eye, the solutions there are uglier, and a choice like Tcl
or Python makes C++ less interesting. Because interpreters provide
a much better suite of "furniture".

The typical arguments that C++ is so much larger and more complex
than C, and that it requires significantly more learning, ring quite
hollow to the experienced C++ programmer.

Because experienced programmer is experienced. The very basis for
determining whether the language features are improvements is
really complex and usually such discussions are simply people
exposing biases.

Why would it matter to me
in the least bit if the language is large and requires a lot of
learning? That's completely inconsequential to me.

Just... wow. It's a *huge* problem. I'm not "into languages"
to be into languages, I am into them to be able to operate on teams
that produce deployable systems that work without causing anybody
any problems.

A novice can really get 95% of everything they need to know
about 'C' in a matter of months, while being productive
under supervision. I am not sure there is a collection
of ten people on the planet who , between them , know everything
there is to know about C++.

 

[Ian Collins]

C++ is much *worse* for memory management than is 'C' - in that
the possibility of memory leaks goes up. Absent writing GUI code,
it's entirely possible to write entire deployable systems that use no
dynamic memory at all in 'C'. indeed, that's been the shop
standard most places I have worked.

You can do and some embedded code I've worked on does the same in C++.
C simply can't do RAII, so C++ has a built in advantage when it comes to
memory (or any other resource) management. The ability to automatically
manage resources also removes the last excuse to use goto, but that's
another story!

Not... really. Let's not confuse our preferences for facts, shall we?

Just compare code using automatic resource management with code that
does it by hand. Pay particular attention to the clean up code if the
nth allocation in a function fails....