I have tried...I made several versions, from totally specific to Win32 using every available trick they offer, right down to the most generic portable ones. None of them really worked, as it is not possible to do it without language support.

I even submitted one to boost: boost vault

There are numerous problems:

1) if the newly created object is registered in a global list of objects and a collection is done before operator new returns, the new object will be collected.

2) there is no way to know where pointers are in objects, in stack frames and in global data. There are many tricks that can be done, but they all slow down an application unnecessarily.

3) you can not guarrantee that an object will always be allocated on the heap. In C++, an object could be on the stack. Thus operator new is not invoked in this case. How do you know when an object is on the stack or on the heap? Again, there are many tricks for that, but the performance is horrible.

My thoughts are exactly that: GC must be optional. In C++, you don't have to pay for what you don't use. But what I need is language support for it. Without language support, it is not really possible.

D enforces all objects on the heap. Not good, in my opinion.

Exactly. That's why it should be optional. But it should be there nevertheless.

It is not possible to do that. A gc_ptr can be:

1) part of the global data.
2) part of the stack.
3) part of a heap object.
4) part of a stack object.

How do you know where is your pointer? there is no way to know that.

Furthermore, you need to register a root gc_ptr in a global list. Which means that for every declaration, you need to lock a mutex in a multithreaded environment. And that means severely crippled performance.

An optimization of this is to use a thread-local-storage list. But then you have to access the TSS segment.

Then there is the problem of removing a pointer from the root set. How do you do that? the obvious answer is 'in the destructor'. But how do you know if your pointer is a root one? you have to keep that information from the constructor.

The analysis so far shows the following possible solution (a solution that I have provided in the boost submission):

class gc_ptr {
    gc_ptr() {
        is_root = magical_function_to_know_if_a_pointer_is_root(this);
        if (is_root) add_root_ptr(this);
    }

    ~gc_ptr() {
        if (is_root) remove_root_ptr(this);
    }

    void *ptr;
    bool is_root;
}

The above is totally slow if you use STL, because removing an object from a list with thousands of objects will bring your app to the halt.

One way to improve this is to use a map of pointer addresses. But then it is again very slow (I've tried it - the improvement is large, but again the app is very slow).

Another way is to keep the iterator in the pointer, so as that the removal takes constant time. The class becomes:

class gc_ptr {
    gc_ptr() {
        is_root = magical_function_to_know_if_a_pointer_is_root(this);
        if (is_root) it = add_root_ptr(this);
    }

    ~gc_ptr() {
        if (is_root) remove_root_ptr(it);
    }

    void *ptr;
    bool is_root;
    list<gc_ptr *>::iterator it;
}

But then look at the memory consumption! a pointer jumps from 4 bytes to 12 bytes on 32-bit machines. On big PCs it probably does not matter, but on smaller machines (PDAs, cell phones, controllers), it is not an option.

No, RAII is not a problem with GC in C++. Objects that are to be used in a RAII fashion are to be allocated on the stack, so there is no problem. That's why I like C++, and RAII especially, because it solves so many problems. And that is one of the reasons that I do not want to abandon C++.

EDIT:

There are other problems as well with a library implementation.

1) arrays of objects. In C++, one can not only allocate arrays of object pointers, but arrays of objects themselves. While this is efficient, there is no standardized way to walk an array of objects.

2) array of pointers. In C++, you can allocate an array of pointers on the heap/stack. A pointer inside an array does not need to register/unregister itself. You do not know if a pointer is part of an array or not in stack allocation.

What is the solution for all this? the solution is either that the C++ standard offers standardized support for GC or it offers a powerful reflection/introspection/metaprogramming facility that allows GC to be an add on.

What is needed for truly efficient precise garbage collection is to:

1) create a mark procedure for global data.
2) create different mark procedures for each object.
3) create different mark procedures for each stack frame.
4) link stack frames procedures on the stack, as functions are entered.
5) unlink stack frames procedures on the stack, as functions are exited.
6) provide an API for walking the CPU's registers.
7) provide an API for suspending / resuming threads.

The algorithm for collection then becomes trivial:

if allocated memory > allocated limit then
    suspend all threads
    mark global data
    for each thread
        invoke mark procedures of stack frames
        mark CPU context of thread
    end for
    for each GC block
        if block is not reached then
            remove block from list
            finalize block
        end if
    end for
    resume all threads

That's the easiest case, i.e. mark & sweep. The other cases that use copying are also very easy to implement, although not that trivial.

Adding garbage collection to C++ will open a vast new opportunity for C++ in the business sector. Stack-based allocation is too important a feature to leave it out, in performance and correctness. It will also allow many new frameworks to be written for C++ in domains that C++ is severely lacking.

No, my method is different. Here are the differences:

1) my collector is precise. It scans only pointer classes and uses various tricks in constructors, destructors and operators new/delete to find where pointers are. Boehm's collector is not precise: it scans all the data of a stack, globals and heap, and it uses various heuristics to find pointers.

2) my collector uses the global operator new and delete to allocate and delete data. The Boehm's collector uses a custom allocator which plays with the page file.

3) my collector is 'mark&sweep', whereas Boehm's collector can be configured to use copying.

4) since my collector uses C++ and pthreads, it does not stop the world, but it blocks on mutexes (a separate mutex for each thread). Therefore, as long as a thread does not use GC, it runs without being stopped. I haven't tested it fully though, due to lack of time. Boehm's collector can be 'stop the world' or incremental.

5) my collector has weak pointers! I consider weak pointers as necessary in any garbage collection system, because it allows listeners to be disconnected from models automatically. I do not think it is possible to make weak pointers with Boehm's collector (although my understanding is not that good in this).

The Boehm's collector is a very proffesional work that spans more then 20,000 lines of code which dips in very low levels of each operating system that it runs on. It is also a work of many people over many years.

But it still requires effort from the programmer in order to be fast (you have to declare the mark routines yourself), and it still does not solve the problem of accurately tracking pointers.

You can view the problem from two sides:

a) pointer hiding should not be allowed within a GC context.

b) it does not matter as long as there is at least one other non-hidden strong pointer to an object that keeps it for being collected.

RAII is your friend here. By coding the appropriate RAII classes, there shouldn't be any problem. For example, closing a handle could be automated by a RAII class that closes handles at its destructor.

Indeed, but from the language perspective, all that it has to be done is

a) declare which procedure is a thread.
b) declare a suspend/resume mechanism for the thread.

Then it does not matter what threading model is used. The compiler could use the information declared by the programmer to properly suspend/resume threads.

For example:

The proposal adopts a block structure like a try-catch-finally block. There can be many solutions to this; imagination is only the limit.

You can have generations, but in C++ it is only long-lived objects that are usually allocated on the heap; most, if not all, temporary structures, are allocated on the stack.

The Boehm's GC can do that, as well as a number of other frameworks.

If it is no longer referenced, then why keep it around?

Not an option if you have a large amount of data to handle and don't want to make it a global variable.

Of course. Allocating and deallocating chunks of memory on the fly is a performance killer.

I wouldn't be surprized if apache/whatever coders would end up using a memory pool, so all of the required memory is allocated only once, and freed only once. Just overload the new/delete operators to ask/return memory from/to the pool instead of from/to the operating system, and you have effectively avoided the overhead of malloc/free (which is where the speed hit for new/delete comes from) for every object you have created. Of course, if you don't create a crapload of a particular object on the heap, you will probably not see that much benefit from this approach...

This is another reason why I'm liking C++ less. Sure, it stops (or warns) you from returning a pointer to a local object from a function/method, but it doesn't stop things like this:

Square* p;
{
   Square s;
   p = &s;
}
p->display(screen);

The designers of Java must have realised that one of the implications of a having a good garbage collector is that the benefit of stack allocated objects over heap allocated objects would be marginal compared to a non-gc language like C++. On this basis - and for simplicity - they would have decided not to have stack-allocated objects.

I have to completely disagree with you axilmar.

For example, gl4java is a native library, and hardly recommended for production stuff. I am not sure why you are using it (the fact that it needs integer ids like that is just poor design). In Java 1.5 you do not need to create new Integer objects, as it's all transparent in the language. It does not create a new Integer object for each cast, but instead uses Integer.valueOf which has a bit more intelligent mapping.

That aside, creating stuff on the heap in Java is completely different from C++. Because Java has full control over all pointers and memory, it can do it a lot smarter and reuse memory many times more effectively than you could in C++. The point needs to be understood that it is cheaper to throw more hardware at a problem than to throw more programmers at it. The Java GC/VM is only going to get better, faster, and more efficient, and if you are a java programmer, you do not even have to do any work to get that efficiency. If you are writing in C++, you have to do all the optimization yourself. It's not worth the time for 99% of projects.

Marcello

With a little language level support wouldn't it be possible to have similar benefits in C++.

No one suggests to make C++ more like Java. Adding garbage collection to C++ does not make C++ a Java-like language. Lots of languages have garbage collection, so the argument could be "why make C++ more like Smalltalk" for example, which sounds and is silly.

That Java and C++ do not overlap, it is a myth. Java is used for many desktop client apps, just like C++. It is even used in soft real-time apps, like C++ (disclaimer: I work on such apps). Java and C++ are used in mobile apps and embedded controller apps as well.

The only reason Java and C++ do not overlap in some domains is because C++ does not have garbage collection. Put GC in C++, and let's forget Java alltogether.

Garbage collection is hardly the only thing that Java has that makes it easier/better to work with than C++.

The standard Java libraries are far better/easier to use than STL and boost.
Templates in C++ are evil.
C++ has to be compiled separately for each platform (windows/mac/linux/etc.).
Dynamic/reflective coding is near-impossible in C++.
C++ cannot be run in a sandbox/secure "jail".
DLL hell.
bloody. fucking. segmentation faults.

And don't get me started on all the syntactical issues that make C++ such a "pleasure" to work with. There's a lot of repeated code to write classes in C++ (.hpp/.cpp).

Griping aside , doesn't managed C++ with .NET or whatever have garbage collection? I've never used that stuff so I'm not sure on the specifics, but that's my only guess as to what the "managed" means.

Marcello

Absolutely it does: in fact two different versions of it. Anyone interested in adding GC to C++ should take a good look at this, both to see the first failed attempt and then the second version that works rather well.

The original Managed C++ (from .NET 1.1) added a bunch of attributes to indicate which types were garbage collected and which used regular C++ semantics. It worked, but the syntax was incredibly ugly and confusing to use.

As a result, they hired Herb Sutter (very smart guy from the C++ standard committee) to design a better replacement. This new language is called C++/CLI, and ships with .NET 2.0. Instead of using attributes on types, it adds a new symbol ^, so you have:

int *x; // a manually managed pointer to an int
int ^x; // a garbage collected pointer to an int

And it gets lots of nice typesafety like not being able to accidentally assign manually managed memory to garbage collected types, or vice versa.

It's really rather good. But not as good as C# :-)

C# 3.0 is my new favorite language.

C# 1.0 was ok, but a little bit too close to Java for my taste. It did add a few nice C++ things that Java is missing, like operator overloading, stack allocated structures, and the ability to do unsafe pointer arithmetic where you really need to optimize the crap out of performance critical inner loops, but the vast majority of day to day C# code felt very much like Java.

C# 2.0 got a whole bunch better with the addition of generics. While not as powerful as C++ templates, they are still very cool and enabled some really nice System.Collections.Generic collection types, easily on a par with STL for power and niceness. It also added anonymous delegates, which are incredibly sexy but have a clunky syntax.

C# 3.0 fixes the anonymous delegate syntax to allow really nice lambda expressions, and adds a whole bunch more functional style goodness. For me it really does combine the best of C++, Java, and ML (yes, ML: it's about time some of those cool functional ideas made their way into a mainstream production language, and I'm very happy this is finally starting to happen).

The .NET Framework 2.0 SDK (http://msdn.microsoft.com/netframework/) is free (as in beer), and includes commandline compilers for C#, J#, VB.NET, and JScript.NET.

If you want an IDE, Visual C# Express (http://msdn.microsoft.com/vstudio/express/visualcsharp/) is also free as beer.

And of course Mono is free (as both speech and beer).

At the moment there is almost no use of managed / jitted languages on console. Everyone seems to shoot straight from low level binary compiled languages (mostly C++) to mega dynamic bytecode languages (Lua or Python), skipping the intermediate level of jitted languages like C# or Java.

I think this is mostly down to lack of suitable execution environments. The console makers tend to spend a fairly minimal amount of time just getting gcc to work, which gives you the low level C++ support. Then when game teams realise they need something higher level and more dynamic, it is easy for them to port Lua or Python because those are implemented in such a clean way that the C bytecode interpreter can run on pretty much any machine without changes. It tends to be a case of each individual team throwing together their own port of the bytecode interpreter, and they don't have the resources to port anything complicated like a JVM or .NET runtime.

Which strikes me as a great pity, because these sort of jitted managed environments really do seem to be the sweet spot for enabling rapid software development (lots of nice high level features like reflection, late bound method invocation, and garbage collection) while still running at a decent clip (a good jitter can be surprisingly competitive against native code, and an order of magnitude faster than any of the bytecode languages).