Re: A garbage collector for C++

I think we have one fundamental disagreement here, and I know too know too little about the algorithm you are using.
 
In my view, the fundamental reason to use a garbage collector is to free the programmer from the task of deallocating memory.  (Or in the case of C++, possibly to do so only in the hard cases.)  Deallocating memory can be hard because it is often difficult to know when something is no longer needed, and hence can be deallocated.  If you could easily predict exactly when deallocation occurs, there would no longer be much of an argument for garbage collection at all.
 
Although I think programmers often have a good idea when really large data structures are being dropped, I don't think that's generally the case in large systems.  Consider an assignment x = NULL, where x is a pointer to T defined by a third party library.  A T itself may be a small object, or a small collection of small objects.  But behind the scenes, T may also maintain some large data structure, which is shared by many T instances, and becomes garbage when the last such instance disappears.  A particular client has no way of knowing whether it has the last instance, or possibly even that the large data structure exists.  The client may be a template that has no idea what T is.
 
In small systems understood by a single person such things may be predictable and controllable.  (Based on personal experience with reference counted toy programs, I'm not sure.)  And you might be able to do without a GC altogether.  In general large systems, I don't believe so.  Certainly to get to that point, interface specifications would have to say a lot more than they currently do, notably how big a data structure may be associated with each object, which negates some of the advantages of having a GC in the first place.
 
I don't believe that whether or not people can predict when an object will be destroyed has that much to do with whether it is part of a cyclic structure, though cyclic structures probably make things a little less predictable.  It has much more to do with software engineering abstraction boundaries.
 
As far as finalization is concerned, I'm no longer sure I understand what you are doing.  If you either run finalizers in the thread that removed the last reference to the object, or have that client thread wait for the GC thread to run the finalizer, then I think you have a correctness/deadlock issue.  If the finalizer runs asynchronously in the GC thread, you avoid that issue, and I agree that being able to run the destructor more promptly is generally a good thing.
 
The second model behaves a lot more like real finalizers.  As such, it is inappropriate for certain kinds of C++ destructor uses, like releasing locks.  On a uniprocessor, you'd be forcing a context switch on every lock release.  And the lock would be released by the wrong thread
 
(Since I suspect you are relying on C++ destructor semantics to remove pointers when they go out of scope, you are probably actually postponing the earliest time at which a finalizer may run relative to what Java or our collector might do, essentially by prohibiting dead variable elimination on pointers.  That's actually a large advantage of your approach, in that it gives you much cleaner semantics, though potentially at a significant performance cost.  Which is why Java did not go that route.  Whether or not that was the technically correct decision remains unclear, and is discussed periodically.)
 
There have been a number of prior on-the-fly GC systems that do not suspend application threads.  (A google search will come up with some of them, and I suspect some of the authors read this list on occasion.)  It would be nice to contrast your algorithm with theirs.
 
Hans


________________________________

	From: [email protected] [mailto:[email protected]] On Behalf Of Guo Mingnan
	Sent: Thursday, April 27, 2006 9:00 PM
	To: Boehm, Hans; [email protected]
	Subject: Re: [gclist] A garbage collector for C++
	
	
	I do not agree with you this time. 
	 
	1) In this system, the introducing garbage collector into C++ application only affects pointer assignment. Furthermore, the main difference of this system from other prior-art GC is that this system DOES NOT suspend application threads at all! The collector is merely another thread the same as other mutator threads, and the shared data structures between the collector and mutators are under control of the GC system. This means the extra-introduced lock of C++ application only held by collector, and the collector will release it very quickly and the collector does not know other application’s lock. I do not think there is a possible to cause deadlock. 
	 
	Normally, destructors are executed by collector no matter acyclic or cyclic garbage. Programmers should be aware that since a GC object is a shared among the whole system, it might be held by others and the whether to execute destructor or not should be determined by the GC system. To be compatible with Single-Thread-Apartment model, the system allows programmers to designate an object is deferred reclaimed and running destructor in a dedicated thread. Therefore, an object’s all methods can be running in a single thread. 
	 
	Anytime, people can predict the execution of destructors of acyclic garbage. The time of running circular garbage object’s destructor is depended on tracing garbage collection, and is hardly predictable.
	 
	2) Pause caused by GC system is annoyance especially it is un-controllable in real-time / kernel environment. I mean that if a function is running without any memory management operation, e.g. operator new, clear a reference, GC system might kick in and cause unpredictable pause. That is what I want to solve. In this system, even GC system kick in the worst case of latency is predictable and less than 1 microsecond. If you does not allow GC to run at critical area, you have to bear such situation that a GC has already been running and the application thread has to wait for the GC to yield the control.  
	 
	Dropping a complex data structure and cause running many destructors is the same as memory allocation and de-allocation, which are highly time-consumed operations of which programmers should be aware (Like normal memory allocation, the time spent is not a constant). These operations are predictable and controllable for application programmers, and can be optimized by using a better application model. 
	 
	Best regards,

	Mingnan G. 
	
	
	"Boehm, Hans" <[email protected]> wrote ：

		I think you're unfortunately propagating some very commonly held misconceptions here.  In particular:
		 
		1) Deterministic or synchronous finalization is NOT DESIRABLE unless the programmer knows exactly which finalizers may be run at which program point.  In particular, in a multithreaded lock-based system, you need to know which locks may be acquired where.  If you have to say that any pointer assignment may acquire any locks as a result of reference-count-driven destructor calls, there's no chance to avoid deadlock.  (If you are writing single-threaded or transactional memory programs, in this case the same issues apply, but they're slightly harder to state.)  In nearly all realistic cases, you want finalizers to run in their own thread, so that they can independently block on locks.  This is different from the usual RAII scheme for objects whose lifetimes are similar to those of a stack frame and destructor invocations are predictable and understood by the programmer.  For details, see my POPL 2003 paper.
		 
		Almost all early Java implementations initially ran finalizers in a mutator thread.  The results were occasional deadlocks or worse. We've been there and tried that.  (In spite of the fact that the original Java spec clearly disallowed running finalizers in clients.)
		 
		This is not to say that synchronous destruction is a bad idea.  If you're using a destructor to release a lock, it's exactly what you need.  But in these cases, you know where the destructor is being run.  For general finalizers, you don't.  C++ destructors and finalizers are really different.
		 
		2) Classic reference counting does exhibit substantial pauses when complex data structures are dropped.  You can avoid this by delaying deallocation and destructor invocation.  But if you really want to limit the time spent in recursive deallocation to a constant, independent of the size of objects you are allocating, you can potentially square the heap size of the process.  Unavoidably.  For details, see Bacon, Cheng, Rajan, "A Unified Theory of Garbage Collection", OOPSLA 2004, and my POPL 2004 paper.
		 
		Hans


________________________________

			From: [email protected] [mailto:[email protected]] On Behalf Of Guo Mingnan
			Sent: Monday, April 24, 2006 5:11 PM
			To: [email protected]
			Subject: [gclist] A garbage collector for C++
			
			
			Hello everyone.
			 
			I have written a garbage collector for standard C++ application. It has following main features. 
			 
			1) Deterministic Finalization
			Providing deterministic finalization, the system can manage resources as well as objects. The programming style is clear and easy, conforming to RAII (Resource Acquisition Is Initialization) idiom of C++ programmers. The memory usage is very efficient, acyclic garbage is reclaimed when the last reference to it is removed. A well-designed application, which eliminates cyclic data structure, does not need expensive garbage collection and is always running with minimum memory usage. 
			 
			2) Accurate GC for C++
			It is a fully accurate tracing garbage collector. All garbage objects are identified by the system, no conservative stack frame guessing. Fully C++ optimization compiler support. 
			 
			3) No Pause (less than 1us)
			In this system, all application codes automatically become fully interruptible and GC-Safe. Therefore, scavenge can start at any place without rendezvous requirement. A special concurrent tracing garbage collector successfully evades root-set scanning, and does not cause suspension of any thread at all. In the worst racing case, the latency is less than one microsecond (not millisecond). It is very satisfied for real-time systems.
			 
			4) Small Overhead
			The runtime cost of application threads is far less than a normal reference counting. If there is no concurrently running scavenging action, there is no write-barrier overhead, no strong memory ordering requirement, no synchronization overhead. There is no extra code or data structure injected for GC safe point. The whole system does not require strong memory ordering, it is suitable for most modern processor architecture. Multi-processor concurrency can be further exploited by the multi-threading property of mutator and collector.
			 
			5) Compatible Object Model
			As well as conventional C++, the system supports multiple-inheritance, object as member variables, and object arrays. Support C++ raw pointer, unions, bit-fields and hidden pointers. Support C++ templates. Support native object and tracing.
			 
			6) Widely Portable
			Even conducting an accurate tracing, the system does not require any special information from compiler. Application can use any standard C++ compiler, such as Visual C++ 8 and GCC. There is no special platform requirement, such as Win32 system call: SuspendThread, GetWriteWatch, etc. Even virtual memory support is not necessary. Thus, it can be ported to a wider area.
			 
			Does anyone have any interest in this system? Any comments are welcome!
			 
			Mingnan G.
			[email protected] 
________________________________

			雅虎1G免费邮箱百分百防垃圾信 <http://cn.mail.yahoo.com/> 


	__________________________________________________
	赶快注册雅虎超大容量免费邮箱?
	http://cn.mail.yahoo.com