Hello,

I'm interested in writing a generational garbage collector in C++. This is for a Python-like programming language project. I have used Boehm's garbage collector before, but I'm worried that it will have noticeable pause times (unacceptable for interactive programs). Since I can't really find any other C++ established GCs out there, I have been thinking of simply writing my own.

However, there are two essential ingredients I need for this:
- Some kind of write barrier mechanism that will notify my collector when something is written to a part of the heap
- A way for me to know the addresses and sizes of the stack, heap and global storage (the root sets)

Would anyone happen to know how to implement write barriers (and how to get the stack, heap and global storage information) on the Linux platform?

As an alternative, if you know of C++ GCs other than Boehm, I would also be interested.

Is there a reason why you cannot use the system's garbage collection? Linux will clean up the mess when the program shuts down or abends.

If you have to ask that, you probably don't know what I mean by garbage collection.

I'm implementing a scripting language with built-in garbage collection (as with Java or Python). Active collection of unreferenced objects is required. Otherwise, a long running program will just fill the heap. See:

http://en.wikipedia.org/wiki/Garbage...puter_science)

If you are implementing a scripting language wouldn't the "stack" be stored as a variable in the C++ interpreter? And wouldn't the interpreter know when it interprets an instruction that writes to the "heap" or "stack"? Otherwise I guess you could use mprotect and catch the segfaults.

Maybe you could consider using auto_ptr, rather than a full blown garbage collector? I think that this would work so long as you restrict your project to avoid some of the messier things that you can do in C++ such as changing the type dereferencing them hiding the pointer in a union etc. But if you can control how your pointers are used then this could be a start. There is a boost library (smart pointers) that you may want to look at.

The website of the Boehm's GC (http://www.hpl.hp.com/personal/Hans_Boehm/gc/) states that it works with pthreads under Irix, Linux, Solaris, HP-UX and TRU64, as well as the native threads on Windows and OS X. So to eliminate pauses, you could just push Boehm's into another thread and let the OS handle the multitasking for you. After all, your program would experience some stalls from the fact that the PC is running other programs, and splitting the GC into another thread will keep GC "pauses" in that same time scale - imperceptible to the user.

Yes and no. For one, I'm implementing a JIT compiler and not just an interpreter. That makes it slightly more complicated. Another issue is that I may want to, say, use C++'s std::vector<> or std::string<> to implement some of my core language types (I would then use a special GC allocator). These types, however, will not notify me when they write to specific memory areas. In general, I think it's just more convenient when your garbage collector can work as a replacement for "new". Otherwise you need to keep track of different kind of "pointer" objects all the time.

That could work but it sounds kind of slow. How do you actually catch segfaults? If you need some kind of event loop, then it's out of the question.

The problem with smart pointers and reference counting is that objects forming cycles of references will never be deallocated. This approach only works for "toy" programming languages, or scripts that only run for a short time.

I'm pretty sure Boehm's GC will just pause every thread (but itself) during a collection phase.

Ok, well, I did some more research. It seems mprotect might be a viable option. However, I'm still not sure which signal to catch, and how to handle it. I need to know which page a write has been attempted to, and I need to somehow allow the write to proceed normally after that. Help with this would be appreciated.

As for the heap, stack and global storage bounds. It seems the /proc/self/maps contains some of that information... There's a file marked [stack], whose upper address I assume is the permanent stack top address for the process. I know my own heap bounds because I will allocate a gc-managed "sub-heap" myself. I also assume that the globally stored variables never change address. Hence, the global storage addresses should be whatever is writable and not executable and not marked [stack] or [heap]. Does anyone see a flaw in this reasoning?

It is still the case that the JIT compiler knows which instructions it generates write to the "heap/stack".

Maybe you would have to wrap them.

If you want a GC like that use Boehms's. In general I think it's more convenient to use an existing scripting language/garbage collector than invent a new one, but if you feel you need it, nobody can stop you.

Not an event loop, unix signals are asynchronous. When there is a write attempt to a protected page the program gets a segfault signal (also when it dereferences a NULL pointer), you can install a signal handler with sigaction

Perhaps this message on the gcc mailing list will be of interest to you:
#2 is the mprotect method, I was suggesting #3, #1 doesn't really make sense when you have an interpreter and runtime code generation.

This is not possible if the threads are native OS threads, user space cannot control the kernel scheduler. Of course, if you have a single core only one thread is running at a time, but the GC thread can still be time-sliced during the collection phase.

I don't have a definitive answer, but I don't believe the Boehm's GC could stop other threads. Some pthreads implementations do have pthread_suspend() to pause other threads, but the dominant Linux implementation is not one of those, and Boehm's explicitly claims to support pthreads on Linux. I'm not certain what kind of pessimizations a GC would have to make in such a concurrent environment, but Boehms is either making those pessimizations or they are doing something very hackish to pause other threads.

Pretty sure they're going with the "hackish" approach. Their concurrent GC, as far as I know, is a multithreaded GC (uses multiple threads to perform collection). It can't run at the same time as the mutator threads. Their incremental GC mode also needs to pause the mutator threads every once in a while.

In a Python-like language, you (as language implementor) should be in more control of pointers and/or references. You should use that control to do something much better than a write barrier to detect changed references.

How big a pause would be noticable? "interactive" covers a wide range. For some kinds of interactive a 100ms pause would be OK; for other kinds a 10ms pause would be a problem.

Even if you write your own, avoiding the pause may be very hard. What is the central concept of the method you would use to avoid a pause?

What fraction of the writes do you expect to be pointer updates vs. what fraction of the heap do you expect to need a write barrier at typical times?

In a language (like Python) with much less flexible pointer manipulation than C, it would be much simpler to load all pointer writes rather than load a heap position based subset of all writes. The load per write would also be much lower. Unless you expect the barrier to cover only a tiny fraction of writes, working at the pointer level would be faster as well as simpler.

That would seem to be entirely in your control. Why would you want to rewrite something as hard as a GC without taking control of the memory pools. But if you do take control of the memory pools, you trivially know where they are. That also lets you exclude a lot of built in memory use (that you can manage more efficiently yourself) from the GC.

If you want a general GC for use in a language as flexible (rat pointer math) as C, do you really expect to be able to do better than Boehm's? If you want to make use of whatever ways your language has less pointer flexibility than C, then you need some focus on that.

I would expect such cycles to be very rare. Certainly, you can't just ignore them and let lost memory build up when cycles occur. But it is a shame to load an entire design with large performance/complexity costs just to cover an obscure case.

It should be simpler to create a system based mostly on reference counting with a background GC (cooperating with the reference counting) to pick up memory lost to cycles.

In addition to catching almost all disconnected memory (so the GC would have much less work to do) the reference counting could also eliminate the need for anything like a write barrier.

Like I said, that only works for objects I have control over... It's also somewhat error-prone (what if someone forgets to handle this properly somewhere, how hard will that be to trace), and finally, it might actually be slower in practice (I only need write barriers for the older generations).

Think Quake, the pause time should probably be in the range of 10-20ms of less. Boehm does offer a "target" pause time, but only in incremental mode with multithreaded collection disabled...

Generational collection. Frequent but fast collections of the younger generations. Slower but rare collections of older generations (which could possibly be multithreaded at some point).

Only the older generations need write barriers. These write barriers can possibly be disabled once a page has been found to be "dirty" (it becomes part of the root set). I don't expect the pointer updates to be very frequent.

It may be not be faster nor simpler.

Obviously, whatever memory the VM allocates for other uses than program data does not need to be garbage collected.

I don't know if it can be faster for collections, but I'm pretty sure I can have smaller pause times and almost completely sure I can have faster allocation times.

Cycles are not "an obscure case". If you're storing any kind of graph in memory, you're very likely to have cycles.

AFAIK in Perl unreferenced objects are destroyed when their scope is left. If this understanding is correct, garbage collector as 'new' replacement doesn't quite work.

It's worth mentioning that Bjarne Stroustrup himself cites the Boehm GC in his latest book, Programming: Principles and Practice Using C++:

http://www.research.att.com/~bs/C++.html

IMHO .. PSM