Dear boost developers, the following proposal is about a small library for multithreaded garbage collection using only boost threads. The major issues for a garbage collection system in C++ are the following: 1) knowing the root set of pointers. 2) knowing which objects are garbage collected. 3) performance of the collector in relation to multithreading. 4) the garbage collection algorithm. I believe it is possible to make a garbage collection system using standard C++ and boost threads only. The following paragraphs analyse the issues and the proposed solutions. -------------------------------------------------------------------------------------------------------- 1) knowing the root set of pointers. The root set of pointers is composed of: a) the set of global pointers of the main thread. b) the set of pointers allocated on the stack of each thread. Since it is not possible to know where the stack of each thread is without using low-level non-portable techniques, I propose the following: a) each garbage-collected thread shall have its own pointer stack allocated as thread-local-storage. The size of the pointer stack shall be analogous to the size of the hardware stack for the size of pointer of the machine. b) a special pointer class will: 1) push itself in the current thread's pointer stack mentioned above, on construction and 2) pop itself from the current thread's pointer stack, on destruction. The above solution makes it possible to: a) know exactly where root pointers are: in the pointer stack of a garbage-collected thread. b) be quite fast, since there is not going to be any synchronization: each thread will take care of its own pointer stack. -------------------------------------------------------------------------------------------------------- 2) knowing which objects are garbage collected. The usual approach to knowing which objects are garbage-collected is to add each garbage-collected object to a global list of objects. But that solution is slower than what it could be, since access to the global list of objects must be serialized for all active threads. My proposal is to have one thread-specific linked list of garbage collected objects; a special object class will provide 'operator new' that adds the allocated block to a thread-specific linked list of garbage collected objects. This class will also provide 'operator delete', in order to have manual object deallocation as well as automatic one. -------------------------------------------------------------------------------------------------------- 3) performance of the collector in relation to multithreading. Since my proposal utilises thread local storage, there is no serialization penalty; therefore, the system can have as many threads as needed, without impact on performance. -------------------------------------------------------------------------------------------------------- 4) the garbage collection algorithm. My proposal for the garbage collection algorithm is the following: step 1: suspend all known garbage collected threads, except the current one. step 2: traverse the root set of pointers of all known threads; mark reachable objects. step 3: delete unreachable objects. step 4: resume all previously suspended threads. The algorithm should be invoked from inside 'operator new' when the amount of allocated memory exceeds a user-defined limit. I propose a simple stop-the-world, then mark-and-sweep algorithm for the following reasons: a) it is easy to implement. b) it does not require access to the platform-specific stuff. -------------------------------------------------------------------------------------------------------- In this section I present the proposed solution in the form of C++ code mixed with pseudo-code and comments, in order to understand the proposal better. class gc_thread : public boost::thread { public: gc_thread() { allocate thread-specific pointer stack allocate thread-specific object list place the thread-specific object list in a global list of object lists add thread in the global list of garbage-collected threads } ~gc_thread() { delete the thread-specific pointer stack } }; template <class T> class gc_ptr { public: gc_ptr() { push this pointer to the current thread's pointer stack } gc_ptr(const gc_ptr<T> &ptr) { push this pointer to the current thread's pointer stack } ~gc_ptr() { pop this pointer from the current thread's pointer stack } }; class gc_object { public: virtual ~gc_object() { } void *operator new(size_t size) { if (gc_memory_size > gc_max_memory_size) collect_garbage(); block *result = ::operator new(size + sizeof(block)); block->iterator = insert new block in the current thread's list of objects block->size = size; return result; } void operator delete(void *ptr) { erase iterator of block from current thread's list of objects if the current thread's list of objects is orphan (i.e. the thread has finished) and the list is empty, delete the list ::operator delete(ptr); } static void collect_garbage() { suspend all garbage-collected threads (except this) //change the mark flag in order to catch unreachable objects gc_mark = !gc_mark; //mark phase for each pointer stack S of each garbage-collected thread { for each pointer P in S { if P != null { mark(P); } } } //sweep phase for each block B of each object list of each garbage collected thread { if (B.mark != gc_mark) delete B; } resume all garbage collected threads (except this) } private: struct block { block_iterator it; size_t size; bool mark; }; static bool gc_mark = false; static size_t gc_memory_size = 0; static size_t gc_max_memory_size = GC_DEFAULT_MEMORY_SIZE; static void mark(block *b) { if (b->mark == gc_mark) return; //block already marked b->mark = gc_mark; for each pointer P in block { if P is pointer then { mark(p); } } } }; -------------------------------------------------------------------------------------------------------- Thank you for your attention. Achilleas Margaritis