I took a good look through all of the code. I at least skimmed over all of it if not read it in depth. The parts I'm fuzzy on is how roots work, marking after objects are deleted, and the business with trying to magically detect contained GCPointers in GCObjects.

One thing you mentioned is that reference counting is slow. I'm not sure I totally agree with that. You are managing all of these linked lists, and in addition to that running mark and sweep operations, which can cause page faults. I do agree that copying GCPointers are faster than reference counted pointers (the implementation I am thinking of when I say reference counted pointers is boost::shared_ptr). I believe that allocations of GCObjects is much slower than allocation with ref counting.

I believe that a lot of times, pointers are not copied that much outside of the objects that contain them. I suppose what I am saying is that I'm not sure the quick copy of the GCObject beats the quick creation of the reference counted pointer, because copies of managed pointers is not overly often, and using an interlocked increment routine is not as slow as you might think.

Also true garbage collection has shown in some cases to be faster in mutli-thread environments (than explicit management), but I belive this breaks down when the GC heap is greater than the size of memory allocated to the process. In this case, traversing all of the objects will cause a lot of page faulting. In reference counting, destruction is deterministic, and more often occurs to objects as they reside in memory, but this is simply a guess. Regardless, I'd expect the full GC to be more suceptible to collections pauses than reference counting.

Of course, the GC library you have handles cyclic references. If one has circular references in their design, this library of course beats ref counting hands down.

Another comment: in the operator -> for GCPointer, you throw if it is a NULL pointer. I disagree with this, at least when it is not customizeable. Why do I say this? Throwing an exception makes it harder to debug -- the stack trace is handled and the debugger didn't pick it up, unless you've happened to customize your debugger to stop on GCNullPointerException for that run of the application. In a release mode, throwing an exception can be a better thing as it will call destructors on the way out were it not caught.

Another thing is that it increases overhead by adding a check before every access of the pointer, when this check is much better and faster done in hardware. In Windows, structured exceptions are converted to C++ exceptions in MSVC, not sure about GCC. In UNIX, you can catch SIGSEV, although I'm not sure what you can do to the thread when you get that signal, but if you are just recording the error, you can do it there.

That's not to say that the exception throwing is pointless, but perhaps it is better done with a preprocessor parameter, so that one can use SEH or SEH->C++ conversion if their environment supports it if they want to avoid the overhead of the check, or they can disable it if that makes it easier to work with the debugger.

For some reason, those times sound slow to me when I am thinking about garbage collection in Java. I work on embedded systems running Java, and garbage collection is important to us.

Modern Java uses generational garbage collection, which works on the assumption that objects typically die young or die very old. Meaning that recently created objects are very likely to die, and objects that are old are likely to live. This gets around most of the problem of temporary objects used in the method.

I won't go into more detail about generational garbage collection in case you already know about it, but you can research it or ask me if you want to know more.

But the point is that for our environment, we've set the youngest generation size to be 3MB. Our system is a 300mhz Geode (x86 clone) with 128 megs of SDRAM. Minor garbage collects happen constantly, so this handles 3 megs of data, most of it which is thrown out. I estimate 100,000 objects (average object size of 30, a guess) in this 3MB range, and our collections happen fast enough we cannot discern them on our CPU graphs, so they are taking probably 100ms or less.

I'm not sure how our JVM does this, but it must as we see around 3 megs of memory freed up and the system is doing all of its work.

In your example, 100k objects took 10 seconds to collect. 100k objects sound like a lot, but 30 bytes per object doesn't sound all that crazy, either (esp in Java when you consider primitive objects), and 3MBs of memory is not all that much memory. 10 seconds sounds like a lot to collect 3 megs of memory.

What I don't get though, is why your test takes so long. If you are making x number of objects, then dumping ALL references, then running a GC, then the graph of traversable nodes has a size of 0 meaning it should take you 0 time to determine that all objects are dead, and all you have to do is delete the objects. Is that correct? Does it really take 10 seconds to delete 100k objects? What compiler/settings are you using? If you are running debug, I know some systems, in particular I know MSVC, does a lot of memory/bounds checking when compiling in debug mode.

Being as that I haven't read your code at all, could you explain this to me?

A 'circular reference' constitutes any two objects both having pointers to each other? (Node has children and parent pointers) Your GC handles that?

What order is that on your tests? It looks less than n, but I can't do any math

And I haven't seen any reference to it, but what kind of license is there? My project would use the zlib/libpng license (Allegro license + you must acredit where you got the code from); would they be compatible?

[edit]
Oh, and does "1 second" mean "about one second" or "more than one second but less than two seconds" or "1 second" or "less than one second"?

LGPL. But that's typical. If you want to use LibGC, go ahead and use it. Just don't claim it to be yours (if you use my code, that is). It is not something that you can't do yourself. If you thing that you can't use it due to the licence, let me tell you how to do it yourself.

Less than one second.

I don't, for the moment.

EDIT:

Gilius, I found a way to do an efficient GC (copying) for all types of data in C++, without linked lists, without affecting the byte size of a pointer and without classes having to inherit from special class. The only requirement is to use the template ptr class instead of *. For example:

ptr<int> data = new int[10];
ptr<Foo> foo1 = new Foo;

But I have another problem: I don't know, in Windows, how to initially allocate the GC memory pool. Which is the way to go ? do I use 'mmap'?

What I specifically want to do is to initially allocate a small amount of memory, and then be able to grow it but without the memory to be relocated. Within this memory, I will implement a copying collector.

EDIT2: never mind, I found it. First you reserve pages with VirtualAlloc and then, as memory grows, you commit the pages with VirtualAlloc again.

Now the only problem that remains is how to call destructors without having classes inherit from a special class. Is that even necessary though ?