Re: A garbage collector for C++

I'll concur your clarification on (2) (let's see if Hans does as  
well) but I think his points on (1) are that
	a) finalization is not necessarily destruction
	b) finalization is not necessarily resource deallocation
	c) destruction is often resource deallocation
	d) deallocation may require locks to ensure it is safe
	e) those locks may result in deadlock with other threads

You seem to be saying something about those with your following  
statements:

>> 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.

This suggests it is the programmer's responsibility to ensure that  
those deadlocks not occur by ensuring that finalization order doesn't  
impose a deallocation order that would result in a lock/unlock  
sequence resulting in deadlock.

While I think this flexibility is a nice feature, I'd like to hear if  
it can be set to be the default that destructors run in their own  
threads when invoked by the collector. Under such conditions, I am  
curious how well the claim of determinist finalization can still be  
achieved especially when reclaiming large acyclic data structures  
that are dags and some multiple of the elements in them may already  
have locks on some multiple of their referenced objects (some of  
which may or not be garbage).
	
Also, if possible to set as the default that destructors run in their  
own threads when invoked by the collector, I'm curious if the pause  
times also remain 1us.

Also, how does your system deal with object "resurrection" (where the  
destructor places a pointer to itself into the root set)? Or is this  
disallowed?

Also, if possible to set as the default that destructors run in their  
own threads when invoked by the collector, for garbage dag data  
structures, if object destructors/finalizers ("same thing" in C++)  
are run in their own threads, do you wait for first(top) level  
destructors/finalizers to finish before then calling the destructors/ 
finalizers in the second level, and then wait for those threads to  
finish before then calling the destructors/finalizers in the third  
level, and so on, for however deep the dag is?

Not trying to be picky here, just curious about how all this works out.

--
Andrew Chen

On Apr 27, 2006, at 11:00 PM, Guo Mingnan wrote:

> 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:owner- 
> [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