Array optimizing problem in C++?

[James Kanze]

Not really. At least, I've seen very few cases where either
language would have been equally applicable.

Better GUI library.

Also, GUI based code tends to be less critical, and deployed
more widely. Both considerations which argue for a VM. (The
second argues for a wide spread VM, and JVM is about the most
wide spread one you can get.)

In reality, a VM is an additional software abstraction layer
between real OS and the programming language of the VM.

Which gives it a definite advantage with regards to execution
speed.

So having native code communicating with the OS/hardware is
clearly more efficient space and run-time efficient when VMs
characteristics do not map directly with the OS/hardware
(example, a "32-bit" VM running on top of a 64-bit OS/hardware
or the opposite, or a "8-bit" VM on top of 64 bit OS/hardware
or the opposite).

The 8/16/32/64 differences aren't really a problem with byte
addressing. It's when you encounter a 36 bit 1's complement
machine that things will likely slow down. Although probably
not as much as one would expect. (Differences in the floating
point model are likely to be more significant, since it is
considerably more difficult for the JIT compiler to determine
when the "as if" rule can apply.)

This isn't bad where run-time and space efficiency are no
primary concerns.

There are examples of native code programming languages where
this is also the case, Pascal for example.

Just for information, the most widely used Pascal implementation
(UCSD) used a VM.

As I said, the design ideals of JVM and ISO C++ are different.

They definitely target different types of applications.

 

[Mark Thornton]

At first, Java is not a language designed with built-in GC. Java is a
programming language designed to use the facilities of JVM.

If there becomes a C++ compiler for JVM emitting intermediate code, and
it can happen, since VM is a virtual *machine*, why will it be slower
than Java?

Some constructs which are legal in C/C++ are difficult to implement
efficiently in the JVM.

 

[Ioannis Vranos]

Just for information, the most widely used Pascal implementation
(UCSD) used a VM.

I thought the most widely used Pascal implementation for DOS was Turbo
Pascal and for Windows, Delphi.

 

[Ioannis Vranos]

Some constructs which are legal in C/C++ are difficult to implement
efficiently in the JVM.

Well, I am talking about mapping JVM facilities to existing C++ ones
(like single inheritance), not the opposite.

 

[Stefan Ram]

Some constructs which are legal in C/C++ are difficult to
implement efficiently in the JVM.

When one does not care for efficiency, one can use
an x86-PC emulator for the JVM, such as

http://www.physics.ox.ac.uk/jpc/

, and then use a C or C++ implementation for an x86 PC.

 

[Matthias Buelow]

The big benefit of GC is memory locality. Because newly allocated

memory is adjacent to the memory recently used, it is more likely to
already be in the cache.

This is only the case for some GC/allocation schemes, the canonical
example probably being the simple copying collector from the SICP book.
However, this doesn't necessarily translate into cache efficiency, since
for example, such a collector would copy and rearrange live data,
leading to cache invalidation. Wether it is cache-efficient or not
depends on the allocation and memory use pattern.

 

[Bo Persson]

I thought the most widely used Pascal implementation for DOS was
Turbo Pascal and for Windows, Delphi.

The UCSD p-System existed before both DOS and Windows.


Bo Persson

 

[Mark Thornton]

This is only the case for some GC/allocation schemes, the canonical
example probably being the simple copying collector from the SICP book.
However, this doesn't necessarily translate into cache efficiency, since
for example, such a collector would copy and rearrange live data,
leading to cache invalidation. Wether it is cache-efficient or not
depends on the allocation and memory use pattern.

Many collectors use copying, especially for the young generation(s)
which are most relevant for the cache.

Mark Thornton

 

[Mark Thornton]

When one does not care for efficiency, one can use
an x86-PC emulator for the JVM, such as

http://www.physics.ox.ac.uk/jpc/

, and then use a C or C++ implementation for an x86 PC.

Right! ;-))

 

[Razii]

That's not what actual benchmarks show.

Csn you cite any?

----------- quote---------------
Such optimisations require the optimiser in the compiler to know the
details of the memory allocator and collector, i.e. the GC. This is
not possible if the GC has been retrofitted onto the language as a
library. The compiler's optimiser does not have the necessary
information to make the optimisations.

"Because it is hard to move objects for C programs", i.e. retrofitting
limits choices which limits performance.
----- end -----------

"Many Java/ML/Scheme implementations have faster garbage collectors
that may move objects..." - Hans Boehm
http://www.hpl.hp.com/personal/Hans_Boehm/gc/nonmoving/html/slide_4.html

 

[James Kanze]

Can you cite any?

Sorry. I was confused with another sub-thread. What actual
benchmarks show is that garbage collection, even in C++, can be
faster than manual memory management.

----------- quote---------------
Such optimisations require the optimiser in the compiler to know the
details of the memory allocator and collector, i.e. the GC. This is
not possible if the GC has been retrofitted onto the language as a
library. The compiler's optimiser does not have the necessary
information to make the optimisations.

"Because it is hard to move objects for C programs", i.e. retrofitting
limits choices which limits performance.
----- end -----------

"Many Java/ML/Scheme implementations have faster garbage collectors
that may move objects..." - Hans Boehmhttp://www.hpl.hp.com/personal/Hans_Boehm/gc/nonmoving/html/slide_4.html

That's just a slide, so I presume that it is only a very
succinct summary of a complicated issue. Fundamentally, C/C++
does impose additional constraints on a garbage collector, since
it is impossible for the garbage collector to reliably identify
all pointers. And while additional constraints don't
necessarily make it slower, they certainly cannot make it
faster. Still (and I know that Hans is aware of this, since
he's the one who pointed it out to me), some research has been
done on mostly compacting collectors---the C/C++ compiler is
modified to provide what information it can, and the garbage
collector is able to compact most memory. So the differences
may not be as great as one might first think.

And of course, there are also applications in which compacting
doesn't really bring much. There are no simple answers here
(except very general ones, like that garbage collection is fast
enough for many applications).

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

Sorry. I was confused with another sub-thread. What actual
benchmarks show is that garbage collection, even in C++, can be
faster than manual memory management.

Under some circumstances, almost anything can be faster than almost
anything else. I once "proved" that a 50 MHz 486 was faster at floating
point math than a 300 MHz DEC Alpha. For the exact math in the
benchmark, it was true, though for the vast majority of similar work, it
was blatantly false.

Much the same seems to be true here: you can prove that GC is faster
than manual memory management. You can also prove that manual memory
management is faster than GC. IME, manual management wins on average,
though neither as often nor by as wide a margin as many people seem to
think.

[ ... ]

That's just a slide, so I presume that it is only a very
succinct summary of a complicated issue. Fundamentally, C/C++
does impose additional constraints on a garbage collector, since
it is impossible for the garbage collector to reliably identify
all pointers.

By allowing observable side-effects in constructors and destructors, C++
doesn't allow the GC as much flexibility in timing of objects being
collected as some other languages do. This doesn't necessarily affect
speed a lot, but can (for one example) when/if it substantially reduces
free memory and forces more objects to remain "live".

And while additional constraints don't
necessarily make it slower, they certainly cannot make it
faster. Still (and I know that Hans is aware of this, since
he's the one who pointed it out to me), some research has been
done on mostly compacting collectors---the C/C++ compiler is
modified to provide what information it can, and the garbage
collector is able to compact most memory. So the differences
may not be as great as one might first think.

And of course, there are also applications in which compacting
doesn't really bring much. There are no simple answers here
(except very general ones, like that garbage collection is fast
enough for many applications).

You can make more substantial statements than that. For example,
compacting the heap is _necessary_ to ensure that free memory can be
used to satisfy allocations of arbitrary size. Consider a pattern in
which the heap is completely allocated in blocks of minimum size, then
every other block is freed. Unless the heap is compacted, every
allocation larger than the minimum supported block size will fail, even
though half the memory in the heap is free.

 

[James Kanze]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

Sorry. I was confused with another sub-thread. What actual
benchmarks show is that garbage collection, even in C++, can
be faster than manual memory management.

Under some circumstances, almost anything can be faster than
almost anything else. I once "proved" that a 50 MHz 486 was
faster at floating point math than a 300 MHz DEC Alpha. For
the exact math in the benchmark, it was true, though for the
vast majority of similar work, it was blatantly false.

Much the same seems to be true here: you can prove that GC is
faster than manual memory management. You can also prove that
manual memory management is faster than GC. IME, manual
management wins on average, though neither as often nor by as
wide a margin as many people seem to think.

On average over what types of applications? GC seems to be
faster for anything involving graphs (which isn't too
surprising). I seem to recall reading somewhere that XFree also
ran faster when modified to use GC.

As you've pointed out elsewhere, of course, GC doesn't play
nearly as large a role in C++ as it does in some other
languages. Typically, I would expect that in most C++ programs,
it won't make a measurable difference, simply because the time
spent in memory management is negligible compared to the rest of
the program. On the average, there is no winner (with regards
to performance). This is corraborated by my own experience; no
noticeable difference in runtime (and a small gain in
development time, and a big gain in robustness).

[ ... ]

That's just a slide, so I presume that it is only a very
succinct summary of a complicated issue. Fundamentally, C/C++
does impose additional constraints on a garbage collector, since
it is impossible for the garbage collector to reliably identify
all pointers.

By allowing observable side-effects in constructors and
destructors, C++ doesn't allow the GC as much flexibility in
timing of objects being collected as some other languages do.

Destructors aren't really relevant for GC; the garbage collector
doesn't (or shouldn't) call them. If you need determinate
lifetime, you need something to manage lifetime, and not just
something to manage memory.

You can make more substantial statements than that. For example,
compacting the heap is _necessary_ to ensure that free memory can be
used to satisfy allocations of arbitrary size. Consider a pattern in
which the heap is completely allocated in blocks of minimum size, then
every other block is freed. Unless the heap is compacted, every
allocation larger than the minimum supported block size will fail, even
though half the memory in the heap is free.

Certainly. But this is a problem which affects both GC and
manual allocation. If you can't move objects, you clearly have
a risk of fragmentation.

 

[Jerry Coffin]

On Apr 8, 8:35 am, Jerry Coffin <[email protected]> wrote:

[ ... ]

On average over what types of applications? GC seems to be
faster for anything involving graphs (which isn't too
surprising). I seem to recall reading somewhere that XFree also
ran faster when modified to use GC.

On average over the applications I've tested. I'll openly admit,
however, that the win was too small to care much about. Only one of them
dealt with anything like a graph (a DAG, in this case).

Yes, Great Circle (I believe that's their name) bragged about having
gotten XFree to run something like 15% faster using their GC.
Unfortunately, given the nature of an X server (i.e. that it is a server
providing services to X client applications) you'd have to know quite a
bit about their testing methodology before you had any idea what that
really meant.

As you've pointed out elsewhere, of course, GC doesn't play
nearly as large a role in C++ as it does in some other
languages. Typically, I would expect that in most C++ programs,
it won't make a measurable difference, simply because the time
spent in memory management is negligible compared to the rest of
the program. On the average, there is no winner (with regards
to performance). This is corraborated by my own experience; no
noticeable difference in runtime (and a small gain in
development time, and a big gain in robustness).

My experience was that the difference in speed was measurable, though
rarely if ever enough to care about. As far as development goes, my
experience hasn't matched yours. While finished programs using GC worked
well enough for me, I found it slower and more difficult to develop them
and be certain they were really working correctly.

[ ... ]

Destructors aren't really relevant for GC; the garbage collector
doesn't (or shouldn't) call them. If you need determinate
lifetime, you need something to manage lifetime, and not just
something to manage memory.

The point is that it can't manipulate the lifetime. As the examples in
another thread showed, in most languages you're free to treat an object
as dead as soon as you can prove that nothing accesses that object any
more. In C++, if a dtor has any observable side effects, the object must
be destroyed precisely when prescribed, and when that happens, you might
as well collect its memory as well, since you certainly can't use the
object after its destruction.

 

[Jerry Coffin]

[ ... ]

Odd. Most people have the exact opposite experience - by not having to worry
so much about memory release, and by the reduced likelihood of memory leaks
due to improperly managed garbage collection, most programmers find GC-based
environments to be faster and easier to develop for.

My observation has been that _most_ of the people find it fast and easy
to produce code that never really works right.

This is also the common
claim made by the expert writers in software development, that having the GC
managed by the platform eases development and reduces difficulty and bugs.

It's a claim that's often made. _Most_ of the people I've seen make the
claim fall into two categories:
1) they have a vested interest in the claim being believed.
2) their expertise seems highly questionable.
There certainly _are_ exceptions, but they appear (to me) to be a rather
small minority.

What is it about your experience that makes it harder for you?

First of all, the exceptions that have to be dealt with -- RAII is more
or less taken away from you, but most of the resources it manages are no
longer managed automatically. Second, the fact that all the GC's I've
seen are just plain wrong too often, such as freeing memory that's no
longer used inside of the program, but its address has been passed to
the OS, which is still using it.

In Java you are relieved of the pressure to make that decision. Once nothing
accesses the object any more, the JVM proves it to itself.

I was talking about the example in the other thread that dealt with
collecting garbage before it went out of scope. In most languages the
compiler is free to make such optimizations but in C++ it's not.

Huh? Doesn't invoking a destructor on a C++ object release its memory by the
very definition of what a destructor does? What am I misunderstanding?

No. Deleting something invokes the dtor and frees the memory. You can invoke the dtor directly without deleting the memory if you choose to do so.

This is more or less irrelevant though -- I was talking about the
optimizations the compiler can do, not what you'd have in your source
code.

 

[James Kanze]

Huh. According to what I've read, on average about 20% of a
C++ program is devoted to memory management, in terms of run
time.

I don't think talking about an average makes any sense here. It
obviously depends enormously on the program---I had one case
where 99.8% of the runtime was spend in malloc and free
(according to the profiler), and I've also written applications
which didn't use any dynamic allocation at all (except that
hidden in the I/O bufferization). I would guess, however, that
the time spent in memory management is not critical in most C++
programs. On occasion, it has been (including the case where
99.8% of the time was in malloc and free), and with one
exception, my optimizations have involved reducing the number of
allocations and frees, rather than optimizing the allocation and
free functions.)

The point is, however, that a C++ program will (or should) make
much less use of dynamic memory than a Java program or a Lisp
program.

 

[James Kanze]

Actually, the articles put 20% as the low end of the average
for common C++ applications, not ones whose primary purpose is
memory management, and stated that it could be up to 35-40%.

It seems as I research these articles that I was mistaken in
calling this a run-time issue. These resources speak of
development time. That actually is the larger cost for most
software. With an area as tricky as memory management is to
get right, that would also be the area with the highest risk
of bugs, especially for an aspect that is not the primary
purpose of the program.

Exactly. Personally, even in development time, I suspect that
the variance is too large for the average to mean much. My
somewhat subjective impression is that in well designed
projects, the amount of time spent managing and debugging memory
is less than 20%, generally significantly less. On the other
hand, I've definitely seen poorly designed projects where the
programmers literally spent years trying to track down some
vicious memory leaks.

There are no simple answers, because there are too many "it
depends". My own experience with garbage collection (in what I
would consider well designed code) is that it typically saves
some 10% in programming time, and a little less in design. And
that it basically has no impact on testing and debugging. But
that's at least partially due to the development environment: if
you're careless in design and coding, you can easily end up with
garbage collection having a very big impact in debugging,
because it allows identifying dangling pointers immediately, and
eliminates most memory leaks automatically. (An interesting
sidelight is that with the exception of Jerry, most of the
people I've seen arguing against it are those who are the most
careless in design and coding, and who would benefit the most
from it.)

 

[James Kanze]

[concerning garbage collection...]

The point is that it can't manipulate the lifetime. As the
examples in another thread showed, in most languages you're
free to treat an object as dead as soon as you can prove that
nothing accesses that object any more. In C++, if a dtor has
any observable side effects, the object must be destroyed
precisely when prescribed, and when that happens, you might as
well collect its memory as well, since you certainly can't use
the object after its destruction.

I think this is the key. And I think you're confusing a C++
implementation detail with a design issue. Regardless of the
language, some objects have definite lifetimes, and others
don't. If an object has a definite lifetime, accessing it after
that lifetime has ended is an error, regardless of whether the
function which terminated its lifetime was invoked via "delete"
(as in C++), or by "object.dispose()", or some other function.
Garbage collection is useful here, but only for error detection;
you still need to explicitly manage that lifetime, and call
delete, object.dispose() or whatever at the proper time. For
objects without definite lifetimes, however, the only reason you
need a destructor in C++ is for memory management; it makes
perfect sense, for example, for the the text in a string to live
"forever", and simply "disappear" (and have its memory recycled)
when it is no longer reachable.

The potential gains vary enormously depending on the
application. I have some where they would be very limited, and
others where garbage collection would simplify things a lot.

 

[James Kanze]

Odd. Most people have the exact opposite experience - by not
having to worry so much about memory release, and by the
reduced likelihood of memory leaks due to improperly managed
garbage collection, most programmers find GC-based
environments to be faster and easier to develop for. This is
also the common claim made by the expert writers in software
development, that having the GC managed by the platform eases
development and reduces difficulty and bugs.

What is it about your experience that makes it harder for you?

In Java you are relieved of the pressure to make that
decision. Once nothing accesses the object any more, the JVM
proves it to itself.

Huh? Doesn't invoking a destructor on a C++ object release its
memory by the very definition of what a destructor does? What
am I misunderstanding?

No. A destructor terminates the object's lifetime. When
running C++ with garbage collection, a destructor has nothing to
do with freeing memory.

Part of the problem in C++ is that delete has a double function,
terminating the object's lifetime and freeing its memory. And
that because there is no non-determinate means of recovering
memory, we are forced to bind the memory to the object lifetime,
and force definite lifetimes on objects which don't otherwise
need them.

 

[James Kanze]

[ ... ]

Odd. Most people have the exact opposite experience - by
not having to worry so much about memory release, and by the
reduced likelihood of memory leaks due to improperly managed
garbage collection, most programmers find GC-based
environments to be faster and easier to develop for.

My observation has been that _most_ of the people find it fast
and easy to produce code that never really works right.

Which is, of course, why it is so difficult to find concrete
evidence (for either side) for programs which are correct.

It's a claim that's often made. _Most_ of the people I've seen
make the claim fall into two categories:
1) they have a vested interest in the claim being believed.
2) their expertise seems highly questionable.
There certainly _are_ exceptions, but they appear (to me) to
be a rather small minority.

I'm not sure about that. Most of the people I've seen making
claims for garbage collection wouldn't know a correct program if
it hit them in the face. But the same thing holds for most of
the people arguing against it. As you said above: most people
find it easy to produce code that isn't really correct. With or
without garbage collection.

First of all, the exceptions that have to be dealt with --
RAII is more or less taken away from you,

That's simply false. I've used garbage collection in a few
applications, and RAII played exactly the same (important) role
it played without garbage collection. RAII is concerned with on
stack objects (with very, very few exceptions), and garbage
collection changes absolutely nothing with regards to on stack
objects.

but most of the resources it manages are no longer managed
automatically. Second, the fact that all the GC's I've seen
are just plain wrong too often, such as freeing memory that's
no longer used inside of the program, but its address has been
passed to the OS, which is still using it.

That sounds more like an OS problem than a garbage collection
problem, and I don't see how manual memory management would
change anything. But perhaps if you'd give a concrete
example... (I've never encountered this.)

No. Deleting something invokes the dtor and frees the memory.
You can invoke the dtor directly without deleting the memory
if you choose to do so.

You can also free the memory without invoking the destructor, if
you choose to do so.

This is more or less irrelevant though -- I was talking about
the optimizations the compiler can do, not what you'd have in
your source code.

I didn't see that other thread. I know that there are
optimizations which a compiler can do which would invalidate
garbage collection. I also know that the compilers I use, on
the platforms I work on, don't do them, and of course, if
garbage collection were part of the standard, a conforming
compiler couldn't make such optimizatons. So where's the
problem?