Garbage collection in C++

[Matthias Buelow]

Can you blow the stack in a Java program? BTW, the error explicitly
mentioned Java heap space. Also, if its the stack, why did it not blowup
in the C++ version?

What do I know? You're comparing apples to oranges. Perhaps java is
simply using more memory for its classes and/or stack frames.

I'm running the java version on my system right now (the "java"
installed is Gnu gij) and it stabilizes at just below 256mb RSS (which
might be the preconfigured VM heap size), no crash yet but it's still
running since a couple minutes.

At best, your test only says that a) Java appears to use more memory
than a C++ program with a handcrafted allocator and b) your program,
including the handcrafted allocator, is 10x longer than the Java one.
Not very interesting results, imho.

 

[Chris M. Thomasson]

What do I know? You're comparing apples to oranges. Perhaps java is
simply using more memory for its classes and/or stack frames.

I'm running the java version on my system right now (the "java"
installed is Gnu gij) and it stabilizes at just below 256mb RSS (which
might be the preconfigured VM heap size), no crash yet but it's still
running since a couple minutes.

Set the `create_tree(22)' line to `create_tree(15)' just to give yourself
some piece of mind that the Java program does indeed work. As-is, I cannot
see anything wrong with it. Also, I don't think you can blow the stack in
Java. IIRC, it will dynamically expand it.

Should I attempt to tweak both programs so that all recursion is removed?
Personally, I don't think Java has a problem with blowing the stack. But, I
will tinker around with it anyway.

At best, your test only says that a) Java appears to use more memory
than a C++ program with a handcrafted allocator and

Yes. This is because of the GC. 256MB sustained for Java, vs 29-30mb spikes
for C++, is major difference.

b) your program,
including the handcrafted allocator, is 10x longer than the Java one.

That extra coding effort pays off in the long run.

Not very interesting results, imho.

Humm.. Well, I have to disagree for now. IMVHO, it shows how a GC language
falls short when compared to clever custom allocation scheme.

 

[Matthias Buelow]

Humm.. Well, I have to disagree for now. IMVHO, it shows how a GC
language falls short when compared to clever custom allocation scheme.

You didn't compare GC vs. non-GC. You compared Java vs. C++.
In addition, you compared a general purpose memory manager with a custom
allocator written for exactly the kind of usage pattern that your
example exhibits.
I can't really be bothered to completely list the many ways your
"comparison" is flawed, sorry.

 

[Chris M. Thomasson]

[...]

Anyway, if I change the line `create_tree(22);' to `create_tree(15)', the
Java version finally works on my platform. Here is the output I get:



C++:
________________________________________
Time: 64 ms




Java:
________________________________________
Time: 450 ms





So much for Java GC allocator being faster than well written C++
allocator!


:^D

I compile the C++ version on MINGW with full optmization using
`create_tree(15)' and I get:


Time: 216 ms


It seems like MINGW produces much slower code than a "release" build with
MSVC 2005 Express.

 

[Chris M. Thomasson]

You didn't compare GC vs. non-GC. You compared Java vs. C++.

Java is a GC lang, C++ is non-GC lang. I compare performance of memory
allocation. Apparently, the Java program is a huge memory hog, C++ program
is not.

In addition, you compared a general purpose memory manager with a custom
allocator written for exactly the kind of usage pattern that your
example exhibits.
I can't really be bothered to completely list the many ways your
"comparison" is flawed, sorry.

I compare clever manual memory management technique with automatic memory
management. The call to `g_tree_alloc.flush()' is manual management. I don't
see how its flawed. Are you saying that I should use plain 'new/delete' for
every allocation/deallocation? C++ is much more flexible than that. The GC
version cannot really compete with it...

 

[Chris M. Thomasson]

No it won't. It will be using exactly those 33 objects. What makes you
think otherwise?

Because its true.

 

[Thomas J. Gritzan]

I created a little test application for Java and C++:


http://pastebin.com/mc3e3f4e
(Java version)


http://pastebin.com/m4bf7db0a
(My C++ version)


As you can see, my C++ version uses a custom region allocation scheme I
created and posted to this group here:

http://groups.google.com/group/comp.lang.c++/msg/3e8dc967c7ddba7c

It's a bit unfair to compare one algorithm in one language and another
algo in another language. You can find a test program that shows that
whatever you want is better than whatever you want.

To make it a little bit more fair, you could run the Java GC the same
time you flush the region allocator in C++:
http://pastebin.com/m40d757b7

By the way, how is your region allocator different from the pool
allocator in boost?

 

[Stefan Ram]

I suppose what I don't get is why you would ever want to create
objects on the stack. It's something you can't do in Java,

I just read this in »comp.lang.java.programmer«:

John B. Matthews wrote in <[email protected]>:
|I was pleasantly surprised by the speed of the JScience
|library, possibly due to stack-based allocation afforded
|by Javolution, on which Jscience is based. (...)
|
|<http://jscience.org/>
|<http://javolution.org/>

(End of quotation from »comp.lang.java.programmer«.)

»Objects can be allocated on the "stack" and transparently
recycled. With Javolution , your application is busy doing
the real work not memory management (e.g. Javolution
RealtimeParser is 3-5x faster than conventional XML
parsers only because it does not waste 2/3 of the CPU
doing memory allocation/garbage collection).«

http://javolution.org/

I do not really understand how Javolution does stack
allocation for objects in Java. A hint might be:

»This implementation uses thread-local pools.
RTSJ alternative implementations could use
ScopedMemory for their stack allocations.«

http://javolution.org/api/javolution/context/StackContext.html

Also, a JVM might do »escape analysis«: When a JVM can prove
that a reference to an object created within a block or method
can not escape this block or method, it can allocate the
object on the stack. It seems that Sun's JVM does not do this
today, but might do it in the future.

http://google.to/search?q=JVM+"escape+analysis"

 

[Noah Roberts]

Java is a GC lang, C++ is non-GC lang. I compare performance of memory
allocation. Apparently, the Java program is a huge memory hog, C++
program is not.

To compare fairly, did you compile the Java version with the GCC native
compiler? If not then you're comparing a native byte code program to
one running in a VM.

Although I imagine it's possible to do this within Java, or any GC'd
language, I also imagine it wouldn't translate as cleanly...it would be
harder.

I compare clever manual memory management technique with automatic
memory management. The call to `g_tree_alloc.flush()' is manual
management. I don't see how its flawed. Are you saying that I should use
plain 'new/delete' for every allocation/deallocation? C++ is much more
flexible than that. The GC version cannot really compete with it...

You can very likely write an allocation pool in Java. A fair comparison
would do that. Then you could compare the difficulty of the task,
writing a fast manager in C++ vs. in a GC environment hell bent on doing
it for you. Then weigh the benefits of each with the frequency in which
such a task is necessary.

 

[James Kanze]

I just read this in »comp.lang.java.programmer«:

John B. Matthews wrote in <[email protected]>:
|I was pleasantly surprised by the speed of the JScience
|library, possibly due to stack-based allocation afforded
|by Javolution, on which Jscience is based. (...)

(End of quotation from »comp.lang.java.programmer«.)

»Objects can be allocated on the "stack" and transparently
recycled. With Javolution , your application is busy doing
the real work not memory management (e.g. Javolution
RealtimeParser is 3-5x faster than conventional XML
parsers only because it does not waste 2/3 of the CPU
doing memory allocation/garbage collection).«

I'm not sure that this is quite relevant to the original
question. The poster said that he didn't get "why *you* would
ever want to create objects on the stack". In Java, you can't
create objects on the stack. The compiler, of course, works
under more or less the same "as if" rule as a C++ compiler; it
can do more or less anything it wants, as long as the output of
your program doesn't change. Including allocating variables on
the stack, even if you've written "new" in your code. (Note
that a C++ could theoretically do this as well. But trying to
identify cases where it would be applicable is probably wasted
effort on the part of the compiler, because if the object could
have been on the stack, the programmer wouldn't have used
"new".)

 

[James Kanze]

Exactly. The current support becomes a lot more awkward if
the cleanup code needs to access local variables.
[...]
the references out in the generated code.) A lambda
function would be nothing more than a functional object
which derived from such a class; a lambda expression would
wrap the expression in a lambda function, then generate the
object. Cleanup, above would be derived from the class as
well, except that the code would define the destructor,
rather than an operator()().

What you want seems to be a "scope guard".

Yeh. Why be simple when you can be complicated. (Of course,
"lambda", "scope guard", and "cleanup" are just arbitrary names.
But if by "scope guard" you mean the complex mixture of
templates and macros that are needed to achieve this end in
current C++---the cure is worse than the disease.)

A Lambda-based scope guard
could be used like this:

template<typename F> requires Callable<F> && MoveConstructible<F>
class scope_guard { /* ... library magic ... */ };

template<typename F> requires Callable<F> && MoveConstructible<F>
scope_guard<F> make_scope_guard(F f);

double* example()
{
double* p = new double[123];
auto && sg = make_scope_guard( [p]{delete[] p;} );
// compute data or throw exception here
sg.cancel(); // makes dtor do nothing
return p;
}

There's no derivation, no virtual functions and no dynamically
allocated function object involved.

But there's library magic required, in order for the scoper
guard to be able to access local variables. If this is possible
as you've written it with the current lambda proposal, fine. If
not, it's basically what I'm asking for, modulo the exact
syntax. Except that I think it's a lot more convenient if I
don't have to invent a name (sg, in your example) for the
variable.

Of course, the example's purpose was ONLY to demonstrate the
how lambdas can be used to make arbitrary scope guards. In
this particular instance managing the dynamically allocated
array should be done differently. At least something like
this:

unique_ptr<double[]> example2()
{
unique_ptr<double[]> p (new double[123]);
// compute data or throw exception here
return p;
}

Actually,
std::vector< double > p( 123 ) ;
does the trick very well. Nothing more is needed. (But of
course, I understood it as just an example. There are times
when no convenient ready-made solution is available.)

It comes with the benefit of the function's declaration being
self- explanatory w.r.t. the life-time management of the
allocated array. It gets even better if you stick with
std::vector which will become movable in C++0x:

std::vector<double> example3();

This works in C++99. I do it all the time.

It seems that the library solution is as convenient and
flexible as a dedicated language feature would be. So, a
"clean up" core language feature is hardly justified.

I've yet to see a library solution which works. But then, I've
yet to see much actual code which uses the lambda proposal.
Until we know what "library magic" you were referring to, we
can't judge whether this needs to be supported at the core level
or not.

 

[James Kanze]

It's beginning to resemble Perl, though.

You've noticed that too. The syntax, despite having some real
problems of its own, is still not nearly as bad as Perl, and we
haven't abandoned static type checking completely, but it's
definitely becoming a case of many different ways of doing
something (all equally unreadable).

 

[James Kanze]

First, I don't know if what you say is true. Second, I have no
clue. Probably for a similar reason why I'm programming in
C++; that's not because I like the language.

Yes. Often, the choice is really only between C, C++ and Java
(with maybe a possibility of Fortran thrown in on the side).

Still, when push comes to shove---I don't really like C++ that
much, but I like the other languages I've seen even less. C++
seems to lack simplicity and elegance; the other languages lack
expressivity. And with enough expressivity, it's possible to
hide the lack of simplicity and elegance.

 

[James Kanze]

On Nov 19, 1:44 pm, "Chris M. Thomasson" <[email protected]>
wrote:

The quantity of memory your application needs is your
application's own business. GC simply _manages_ how much you
create.

The quantity of memory your application actually needs is
determined by many things. No memory management has zero
overhead. By avoiding fragmentation, a copying collector may
actually reduce that overhead. But typically, the overhead of a
garbage collecting manager is significantly higher than that of
malloc/free, at least for a number of implementations of
malloc/free. (I've seen some malloc/free which had very high
space overhead as well. In return for being an order of
magnitude faster.)

In the end, there are a number of factors which you might have
to consider: total runtime, latency, space, development cost,
time to market.... Depending on the application, they will have
different weights. Typically, "naïvelly" using garbage
collection instead of "naïve" manual management will not change
the runtime significantly, will improve latency, will increase
the space noticeably, and reduce development const and time to
market significantly. At least for the types of applications
I've worked on. (By "naïve", in the preceding sentence, I mean
using the tool "out of the box", without tuning. Tuning always
implies increased development cost and time to market; how much
depends on how much tuning is necessary, but garbage collection
typically offers some very inexpensive possibilities, e.g.
explicitly triggering the collector at the right moment.)

 

[James Kanze]

The point I was trying to make is that the sample pseudo-code
program only needed to have less than 33 foo objects allocated
at any one time. This cannot be guaranteed with GC because of
its non-deterministic nature. Your program will be using more
memory than it has to. The GC will most likely let you
allocate a shi%load of foo objects before it decides to run a
scan. Likely, the scan will only be run once the internal
heap of the current generation is exhausted. This is a
side-effect of letting the GC handle everything for you.

Now you're missing the point. If the program has a maximum of
33 live objects, it has a maximum of 33 live objects.
Regardless of how memory is managed. Beyond that, it's memory
that is free to be reallocated, whether you've called free or
are using garbage collection.

In both cases, of course, the actual memory required to run the
program will be more than just 33*sizeof(object), because all
memory management systems have overhead of their own. And if
you dimension the garbage collection pool to the minimum size
that will work, then there's even a good chance that it will
require less memory than malloc/free. At a severe cost in
runtime. (This obviously depends on the implementation of
malloc/free; I've used one malloc/free which had a very high
space overhead. But was extremely fast.)

 

[James Kanze]

Juha was saying that certain applications (or algorithms, in
general) can't be run in a GC'd environment on the same
problem size as they can in a manually managed environment,
which is just plain false.

It's not just plain false. In fact, it's not false at all;
there are certainly applications for which manual memory
management will increase the possible problem size, given a
fixed upper limit of available memory. Obviously, you can make
them work for the same size problem with garbage collection by
triggering the collector at each allocation, but that generally
comes out to being unacceptably expensive in terms of runtime.

I'm actually rather surprised how often I have to repeat this
here: there is no silver bullet. Garbage collection offers a
number of advantages for a number of programs, but it won't make
a silk purse out of a sow's ear, and it's not a universal
solution, applicable everywhere. It's simply one more tool to
be considered; in the end, whether it is applicable depends on
the engineering trade-offs involved.

Of course a, say, Unix process may have some more memory
mapped to it if that's still in the GC's memory pool
internally just as it also happens with some malloc
implementations which don't free their stuff in a timely
fashion. This is, however, irrelevant to the application
itself.

Yes and no. It's not irrelevant if the implementation of the
allocator requires that memory to be mapped, for whatever
reasons.

Well, a GC-managed environment can always be turned into a
manually managed environment much easier than the other way
round.

You'll have to explain that too me. If the code works with
manual management, just replace malloc with gc_malloc, #define
free to nothing, recompile, and it works with garbage
collection. The reverse is not so obvious.

Application specialities and implementation details.

Which may be relevant to your problem.

 

[James Kanze]

Java is a GC lang, C++ is non-GC lang.

Java is not C++ with garbage collection. Java and C++ are
different languages, with different idioms. The fact that
garbage collection is mandatory in Java, and optional in C++, is
only one difference among many.

I compare performance of memory allocation.

No. You compare performance of two specific implementations of
two specific very different languages.

Apparently, the Java program is a huge memory hog, C++ program
is not.

No. Apparently, the Java implemention you used is a huge memory
hog. Or maybe there was something about the way you used it.
Who knows.

I compare clever manual memory management technique with
automatic memory management.

You compare investing a lot of time and effort (read cost) in
custom memory management with just using something out of the
box.

The call to `g_tree_alloc.flush()' is manual management. I
don't see how its flawed. Are you saying that I should use
plain 'new/delete' for every allocation/deallocation?

That's the idiomatic way of doing things in the language. It's
also the cheapest way (in terms of cost).

C++ is much more flexible than that.

So is Java, when it comes down to it.

 

[SG]

Yeh. Why be simple when you can be complicated. (Of course,
"lambda", "scope guard", and "cleanup" are just arbitrary names.

Well, the term "scope guard" is just much more popular for this C++
idiom than "cleanup".

But if by "scope guard" you mean the complex mixture of
templates and macros that are needed to achieve this end in
current C++---the cure is worse than the disease.)

No. By scope guard I refer to a common C++ idiom. There's nothing
complex about it. It won't require macros or any compiler specific
hacks. The scope_guard template class doesn't even need any C++0x
features. But what does the implemtation matter? This scope_guard
thingy is just an #include away ...

double* example()
{
double* p = new double[123];
auto && sg = make_scope_guard( [p]{delete[] p;} );
// compute data or throw exception here
sg.cancel(); // makes dtor do nothing
return p;
}
There's no derivation, no virtual functions and no dynamically
allocated function object involved.

But there's library magic required, in order for the scoper
guard to be able to access local variables. If this is possible
as you've written it with the current lambda proposal, fine.

The scope_guard template class implementation doesn't care about what
the function object knows or does. It shouldn't throw an exception
though The scope_guard contains this function object that happens
to be a lambda function object in this case. The lambda function
object captured the local pointer p by value. That's where a C++0x
feature comes into play.

If
not, it's basically what I'm asking for, modulo the exact
syntax. Except that I think it's a lot more convenient if I
don't have to invent a name (sg, in your example) for the
variable.

Haven't you noticed that the ability to refer to the scope guard later
on can be very useful? Think of transactions for example.

unique_ptr<double[]> example2()
[...]
It comes with the benefit of the function's declaration being
self- explanatory w.r.t. the life-time management of the
allocated array. It gets even better if you stick with
std::vector which will become movable in C++0x:
std::vector<double> example3();

This works in C++99. I do it all the time.

The difference is that the language standard doesn't force compilers
to do return value optimization as far as I know. Also, it works only
for the first one or two levels of passing that vector around --
assuming RVO + function call that takes its argument by value: func
(example3()).

I've yet to see a library solution which works. But then, I've

I sketched one. I'm 100% certain that the example usage code will be
possible in C++0x.

yet to see much actual code which uses the lambda proposal.
Until we know what "library magic" you were referring to, we

Actually it's not at all magic. I just didn't consider it to be
interesting enough for this thread. I'm confident that you -- as a
professional -- are able to implement it by yourself in no time.


Cheers!
SG

 

[Juha Nieminen]

By the way, how is your region allocator different from the pool
allocator in boost?

According to my own tests boost::fast_pool_allocator is not all that
fast. Just slightly faster than the default allocator (at least in my
linux system).

 

[Matthias Buelow]

That's the point. A mark-and-sweep garbage collector waits until more
memory is "needed," or until a hint is provided to indicate that the
time is ripe for cleanup. GC is guaranteed not to free anything that's
still in use by the program, but is not guaranteed to free resources as
soon as they cease to be in use. In contrast, the latter guarantee is
supported (though not imposed) by resource management techniques based
on deterministic destruction.

That is true _if_ your objects go out of scope in a timely fashion (that
is, in the case of indeterminate scope, if you destruct them properly as
soon as you don't need them anymore.) Otherwise, it's basically the same
problem as with the lazy deallocation of a GC (only you don't really
have much control over it in that case unless you know how the GC works
and can use that knowledge in your program -- with basically defeats the
"don't have to think about it" advantage; however, one can probably
defer that kind of bother until a (memory) profiling phase, if
necessary.)

Non-GC C++ programs will therefore tend
to have better resource retention times than programs that use GC but
lack deterministic destruction.

Yes but does it matter? In what situation, for example? Please note that
for simplification, I'm looking at this mostly from the egocentrical
view of the program in question, which doesn't really care for anyone
else (for example, other processes in a multitasking environment. C++
doesn't know anything about processes, anyway. ) And the library's
allocator (the one behind new/delete or malloc/free) will most likely be
ignorant of any language details, too.

Tying the management of non-memory resources to the automatic,
scope-based memory management that was already present in C was, IMO,
a stroke of genius on Bjarne Stroustrup's part.

Hmm.. not sure about that part.