220 9293 <11d438f3-2c4c-4545-b93a-5a63090ee8ee@isocpp.org> article Path: news.gmane.org!not-for-mail From: Dain Bray Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Precise Per-Type Cyclic Garbage Collection (DRAFT 1) Date: Tue, 11 Feb 2014 12:26:07 -0800 (PST) Lines: 634 Approved: news@gmane.org Message-ID: <11d438f3-2c4c-4545-b93a-5a63090ee8ee@isocpp.org> References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_1134_24666029.1392150367173" X-Trace: ger.gmane.org 1392150363 2329 80.91.229.3 (11 Feb 2014 20:26:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 11 Feb 2014 20:26:03 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCZ7LUH52UKBBYEO5KLQKGQEVEAN4AI@isocpp.org Tue Feb 11 21:26:11 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-vc0-f200.google.com ([209.85.220.200]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WDJuD-0008Vg-Vs for gclcip-std-proposals@m.gmane.org; Tue, 11 Feb 2014 21:26:10 +0100 Original-Received: by mail-vc0-f200.google.com with SMTP id le5sf18139471vcb.3 for ; Tue, 11 Feb 2014 12:26:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe :content-type; bh=4VJU2+JGYRkyrEgGN1SNE9iQjwbC5rnnd4A9wcr/4sk=; b=CBn063cgwVd5shdXPQYcLxjHr9rnozCeFE1l487iazk0keBnIR0rFjy3oZD/HNIXtJ Dw7yWY130p2UGi6ngaY+lkyVZe0kgCLFQArh6EnEshuYfLvJtrAi1fLY4nxLywU42Mqs GuhvbCmu01W6+e27mvgDEAHZRa80F67hZST7s9n9cHnv3Wvz0zaNoYX6zuFHAzZfS1q/ +QfFrHFWm0gH4//b/k8fi7pD4R/PkmwJcYQinWXp8wCcOf7FLax/QTYsRNHf1gh0rkiW OjBpR8/xZiV5jGmIO0fCnoIBOMc+G5OiMlpRNRPZtwbT/4eEjyiqHUfl1ZFbj5X0xo1n 5BMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=4VJU2+JGYRkyrEgGN1SNE9iQjwbC5rnnd4A9wcr/4sk=; b=eGaTqsmwYCt/ZCc8zdHr6hESmpouhp7HktTTzmQZScnfxn/6gL2qyxE/AHsK6jtRDg 99Fg0neD7GpfCZ7yq7N/EUBkdLQhyYqOV+gthvf5PiW/PZNdaD7FyFPy/JXKwHs2ETx6 xNUEwEazNCZ7JLHlPvZ0Tyhzhky7R+A2PL8QD/ZVylJiBrejlg6R+Y6wOjxNxSnKAFqo CS9Yr0q0jIxYiEkPCw0D8CYfS2C+AHUjyGYco3uucG7fVvytkN993p0cFKAHbPjJF+Af EQdX1Sj4Jj4AEr4NF9vPGRjWJYESIzIE5c1suzWIiYyF2rJllVBC46taZvvTGmNL4Thh X9kw== X-Gm-Message-State: ALoCoQm2JwWgpkp2YIFLcGmJnMwQ6sS/1PxYudZizOc5aGa7zDxCKR0VEtQk3Yr7+0+u4KcNuHZZ X-Received: by 10.224.163.71 with SMTP id z7mr243860qax.5.1392150368709; Tue, 11 Feb 2014 12:26:08 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.101.70 with SMTP id t64ls2638367qge.1.gmail; Tue, 11 Feb 2014 12:26:07 -0800 (PST) X-Received: by 10.140.80.47 with SMTP id b44mr48657qgd.33.1392150367934; Tue, 11 Feb 2014 12:26:07 -0800 (PST) In-Reply-To: X-Original-Sender: dain.bray@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:9293 Archived-At: ------=_Part_1134_24666029.1392150367173 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable What you are describing sounds similar to the way C++/CLI added managed=20 classes. If you are not familiar with it, you might check that out. I'm not sure if a GC is necessary, I find shared types are rare, and=20 cyclic shared types rarer still--which weak ptr breaks well enough.. Seems= =20 like alot of complexity for little, if any gain. Perhaps this would be=20 better as a library solution? =20 =20 On Tuesday, February 11, 2014 11:03:27 AM UTC-3, Andrew Tomazos wrote: > Hey guys, this is a design I've been toying with (in the abstract for som= e=20 > time actually). It needs a bunch of work, but I would appreciate your=20 > feedback on this short draft. Also, if you are aware of any overlapping= =20 > past proposals that would be great. > > > Thanks, > > Andrew. > > > Precise Per-Type Cyclic Garbage Collection (DRAFT 1) > > Introduction / Summary > > We propose a core language feature that allows objects of user-selected= =20 > class types to be cyclically garbage collected. Constraints on the usage= =20 > of class types so selected, and pointers to such class types, are imposed= =20 > to enable the implementation of fast safe precise collection. > > Motivation > > Many C++ programs can be decomposed into (a) low-level components for=20 > which the performance and timing control of manual memory management and= =20 > value layout are of great benefit; and (b) higher-level organizational=20 > components for which the benefit is dominated and negligble - and the=20 > convenience of safe automatic cyclic garbage collection would be worth th= e=20 > tradeoff. > > It would be great to be able to get the best of both worlds in one=20 > program. That is, to be able to specify certain classes as being garbage= =20 > collected and others to be manually managed - and to only pay for what yo= u=20 > use. > > Comparison > > With Boehm Demers Weiser Collector > > The Boehm Collector can only be used either program-wide or not-at-all.= =20 > What we propose isolates garbage collection only to certain user-selecte= d=20 > types. Also, what we propose is precise garbage collection like in the= =20 > managed languages, as opposed to conservative collection. The=20 > reachability graph is tracked explicitly through instrumenting the type= =20 > system. That is, rather than scanning entire memory areas for all=20 > potential pointers to any dynamic memory, only the pointers to collected= =20 > types are tracked - and they are tracked as they are initialized, assigne= d=20 > and destroyed. This gives it a radically different performance profile,= =20 > and makes it proportional only to the use of collected types in the=20 > program, and not proportional to all dynamic memory use. > > With shared_ptr > > Shared pointers cannot deal with cycles. weak_ptr often does not have a= =20 > sensible place where it can be applied to break cycles, and when it does = it=20 > is awkward to use. Shared pointer are also awkward to use with this=20 > through enable_shared_from_this. What we propose is much cleaner and=20 > easier to use, at the cost of the added implementation complexity of=20 > compiler support. Under the proposed feature, the user can just use=20 > regular pointer syntax to work with collected types, and doesn=E2=80=99t = need to=20 > worry about any of these issues. > > With ownership and memory pools > > Ownership schemes are many times artificial. In many object models,=20 > objects do not have natural owners, and it can be challenging to impose= =20 > one. When an owner is selected the programmer must be careful to make su= re=20 > the lifetime of the owner encloses uses of the owned object. This=20 > implementation overhead and constraint is many times not worth the effort= =20 > compared to automatic memory management. > > Memory pools, which are just artificial owners, are not feasible in many= =20 > long-running programs. In many such programs the memory pool can never b= e=20 > cleared, so they are no different than simply leaking into the heap and= =20 > waste and exhaust memory. > > Specification > > Introduce a context-sensitive keyword gc that can appear in the head of a= =20 > class specifier: > > class foo gc > > { > > ... > > }; > > If a class type is marked with gc, it is called a collected type. A=20 > subclass of a collected type is also a collected type, whether or not=20 > marked with gc. A collected type may not have any base classes that are= =20 > not also collected types. It follows that all base classes and all=20 > subclasses of a collected type are collected types. > > An object of collected type is called a collected object. A collected=20 > object may only be a complete object or a base class subobject, it may no= t=20 > be a member subobject or an array element: > > foo x[10]; // ill-formed > > struct bar { foo x; } // ill-formed > > You can use pointers instead: > > foo* x[10]; // ok > > struct bar { foo* x; } // ok > > =20 > > A collected type may only be allocated with dynamic storage duration. It= =20 > may not be allocated with automatic, static or thread local storage=20 > duration. Again, you can use pointers instead: > > auto s =3D new foo; > > thread_local auto t =3D new foo; > > void f() > > { > > auto a =3D new foo; > > } > > An object of type pointer to a collected type, is called a collecting=20 > pointer. A collecting pointer cannot participate in pointer arithmetic.= =20 > That is, there is no builtin meaning for addition, subtraction, incremen= t=20 > or decrement of a collected pointer. It may also not be converted or cas= t=20 > to or from void*, and it may not be the subject or result of a reinterpre= t=20 > cast. It may only be initialized or assigned a null pointer constant or= =20 > another collected pointer (possibly dynamic or static cast from a base=20 > class or subclass). > > If a complete collected object is destroyed, any pointers to it or its=20 > base class subobjects are assigned the null pointer value by the=20 > implementation. > > Given a time point at run-time of the program, we will describe a directe= d=20 > graph as follows. There is a root node. For each complete object of=20 > collected type there is a node. For each non-null collecting pointer tha= t=20 > is not a member subobject of an object of collected type, there is an edg= e=20 > from the root node to the complete object of the subject of the pointer.= =20 > For each remaining non-null collecting pointer, there is an edge from th= e=20 > collected object of which it is a member to the complete object that is t= he=20 > subject of the pointer. If there is no path from the root node to a=20 > collected objects node, we say the collected object is unreachable. > > The implementation shall automatically destroy collected objects, at some= =20 > point between when it first was unreachable and the end of the program, o= r=20 > at the end of the program if they never become unreachable. (As a qualit= y=20 > of implementation issue this should be as soon as reasonably possible giv= en=20 > reasonable resources.) > > Implementation > > If a program contains a collected type, a garbage collector is linked int= o=20 > the program by the implementation. The constructor and destructor of both= =20 > collected types and collecting pointers are generated to talk to the=20 > garbage collector. The garbage collector uses this information to track= =20 > the graph. Periodically the garbage collector searches the graph using a= =20 > generational or other garbage collection algorithm, deleting objects as= =20 > appropriate. > > Outstanding Issues > > How do references to collected types work? References are much like=20 > constrained pointers so the specification of a reference to collected typ= e=20 > would be similar to collecting pointers. > > Are the restrictions on storage duration necessary? Couldn=E2=80=99t col= lected=20 > objects of non-dynamic storage duration simply be ignored by the collecto= r?=20 > What about the subobject restriction? It was initially felt that this= =20 > would simplify usage and make it safer - as well as easing implementation= .. > > Is the assignment of null to pointers on delete necessary or helpful?=20 > Again this was a safety feature. We wanted collecting pointers if=20 > non-null to always be pointing to a collected object. If they are delete= d=20 > manually, which would be unusual - we thought this would be because of=20 > destructor timing, and not resources - given that the performance profile= =20 > of these high-level objects is most likely not paramount. > > > --=20 ---=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa= ls/. ------=_Part_1134_24666029.1392150367173 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

What you are describing sounds similar to the way C++/C= LI added managed classes. If you are not familiar with it, you might check = that out.

 I'm not sure if a GC is necessary, I find shared type= s are rare, and cyclic shared types rarer still--which weak ptr breaks well= enough.. Seems like alot of complexity for little, if any gain. Perhaps th= is would be better as a library solution?

 
 
On Tue= sday, February 11, 2014 11:03:27 AM UTC-3, Andrew Tomazos wrote:

Hey guys, this is a desi= gn I've been toying with (in the abstract for some time actually).  It= needs a bunch of work, but I would appreciate your feedback on this short = draft.  Also, if you are aware of any overlapping past proposals that = would be great.


Thanks,

Andrew.

Precise Per-Type Cyclic Garbage Collection (DRAFT 1)

Introduction / Summary


We propose a core language feature that allows objects of use= r-selected class types to be cyclically garbage collected.  Constraint= s on the usage of class types so selected, and pointers to such class types= , are imposed to enable the implementation of fast safe precise collection.=


=

Motivation


Man= y C++ programs can be decomposed into (a) low-level components for which th= e performance and timing control of manual memory management and value layo= ut are of great benefit; and (b) higher-level organizational components for= which the benefit is dominated and negligble - and the convenience of safe= automatic cyclic garbage collection would be worth the tradeoff.

It would be great to be = able to get the best of both worlds in one program.  That is, to be ab= le to specify certain classes as being garbage collected and others to be m= anually managed - and to only pay for what you use.


Comparison

=

With Boe= hm Demers Weiser Collector


The Boehm Collector can only be used either program-wide or not-a= t-all.  What we propose isolates garbage collection only to certain us= er-selected types.  Also, what we propose is precise garbage collection like in = the managed languages, as opposed to conservative collection.  The reachability = graph is tracked explicitly through instrumenting the type system.  Th= at is, rather than scanning entire memory areas for all potential pointers = to any dynamic memory, only the pointers to collected types are tracked - a= nd they are tracked as they are initialized, assigned and destroyed.  = This gives it a radically different performance profile, and makes it propo= rtional only to the use of collected types in the program, and not proporti= onal to all dynamic memory use.


With shared_ptr<T>


Shared pointers cannot deal with = cycles.  weak_ptr often does not have a sensible place where it can be= applied to break cycles, and when it does it is awkward to use.  Shar= ed pointer are also awkward to use with this through enable_shared_from_thi= s.  What we propose is much cleaner and easier to use, at the cost of = the added implementation complexity of compiler support.  Under the pr= oposed feature, the user can just use regular pointer syntax to work with c= ollected types, and doesn=E2=80=99t need to worry about any of these issues= ..


With ownership and memory pools


Ownership schemes are many times artificial.  I= n many object models, objects do not have natural owners, and it can be cha= llenging to impose one.  When an owner is selected the programmer must= be careful to make sure the lifetime of the owner encloses uses of the own= ed object.  This implementation overhead and constraint is many times = not worth the effort compared to automatic memory management.

Memory pools, which are just a= rtificial owners, are not feasible in many long-running programs.  In = many such programs the memory pool can never be cleared, so they are no dif= ferent than simply leaking into the heap and waste and exhaust memory.


Sp= ecification


Intro= duce a context-sensitive keyword gc that can appear in the head of a class specifier:<= /span>


<= p style=3D"line-height: 1.15; margin-top: 0pt; margin-bottom: 0pt;" dir=3D"= ltr">  &n= bsp; class foo gc

   {

    =    ...

   };


If a class type is marked with gc, it is calle= d a collected type.  A subclass of a collected type is also a collected type, wh= ether or not marked with gc.  A collected type may not have any base c= lasses that are not also collected types.  It follows that all base cl= asses and all subclasses of a collected type are collected types.

An object of collected t= ype is called a collected object. A collected object may only be a complete= object or a base class subobject, it may not be a member subobject or an a= rray element:


   foo x[10]; // ill-formed

   struc= t bar { foo x; } // ill-formed


You can use pointers instead:


   foo* x[10]; // ok

=    struct bar { foo* x; } // ok

 

A collected type may only be al= located with dynamic storage duration.  It may not be allocated with a= utomatic, static or thread local storage duration.  Again, you can use= pointers instead:


   auto s =3D new foo;


   thread= _local auto t =3D new foo;


   void f()

   = {

       auto a =3D new foo;

&nbs= p;  }


A= n object of type pointer to a collected type, is called a collecting pointe= r.  A collecting pointer cannot participate in pointer arithmetic. &nb= sp;That is, there is no builtin meaning for addition, subtraction, incremen= t or decrement of a collected pointer.  It may also not be converted o= r cast to or from void*, and it may not be the subject or result of a reint= erpret cast.  It may only be initialized or assigned a null pointer co= nstant or another collected pointer (possibly dynamic or static cast from a= base class or subclass).


If a complete collected object is destroyed, any pointers to it or= its base class subobjects are assigned the null pointer value by the imple= mentation.


Given = a time point at run-time of the program, we will describe a directed graph = as follows.  There is a root node.  For each complete object of c= ollected type there is a node.  For each non-null collecting pointer t= hat is not a member subobject of an object of collected type, there is an e= dge from the root node to the complete object of the subject of the pointer= ..  For each remaining non-null collecting pointer, there is an edge fr= om the collected object of which it is a member to the complete object that= is the subject of the pointer.  If there is no path from the root nod= e to a collected objects node, we say the collected object is unreachable.<= /span>


<= p style=3D"line-height: 1.15; margin-top: 0pt; margin-bottom: 0pt;" dir=3D"= ltr">The implementatio= n shall automatically destroy collected objects, at some point between when= it first was unreachable and the end of the program, or at the end of the = program if they never become unreachable.  (As a quality of implementa= tion issue this should be as soon as reasonably possible given reasonable r= esources.)


Implementation


If a program contains a collected type, a garbage collector is l= inked into the program by the implementation. The constructor and destructo= r of both collected types and collecting pointers are generated to talk to = the garbage collector.   The garbage collector uses this informat= ion to track the graph.  Periodically the garbage collector searches t= he graph using a generational or other garbage collection algorithm, deleti= ng objects as appropriate.


Outstanding Issues


How do references to collected types work?=  References are much like constrained pointers so the specification o= f a reference to collected type would be similar to collecting pointers.


Are the restriction= s on storage duration necessary?  Couldn=E2=80=99t collected objects o= f non-dynamic storage duration simply be ignored by the collector?  Wh= at about the subobject restriction?  It was initially felt that this w= ould simplify usage and make it safer - as well as easing implementation.


Is the assignment = of null to pointers on delete necessary or helpful?  Again this was a = safety feature.  We wanted collecting pointers if non-null to always b= e pointing to a collected object.  If they are deleted manually, which= would be unusual - we thought this would be because of destructor timing, = and not resources - given that the performance profile of these high-level = objects is most likely not paramount.



--
 
---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
------=_Part_1134_24666029.1392150367173-- .