220 9266 article Path: news.gmane.org!not-for-mail From: Andrew Tomazos Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Precise Per-Type Cyclic Garbage Collection (DRAFT 1) Date: Tue, 11 Feb 2014 06:03:27 -0800 (PST) Lines: 590 Approved: news@gmane.org Message-ID: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_2503_26488091.1392127407450" X-Trace: ger.gmane.org 1392127404 30844 80.91.229.3 (11 Feb 2014 14:03:24 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 11 Feb 2014 14:03:24 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBD5KHQXXWYPRBMG35CLQKGQEL7PIVXA@isocpp.org Tue Feb 11 15:03:33 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qc0-f197.google.com ([209.85.216.197]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WDDvu-00030x-0U for gclcip-std-proposals@m.gmane.org; Tue, 11 Feb 2014 15:03:30 +0100 Original-Received: by mail-qc0-f197.google.com with SMTP id e16sf16633876qcx.0 for ; Tue, 11 Feb 2014 06:03:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:message-id: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=61PtzmeCNr5vKWELCfqE8G7aGKDKP9a5Y4L35Rd4SU8=; b=mp42BQe72evpuPu9Cc5yEqsTeOp7GrhVUHUF9GszJ3MZwQEeRt1cT+dFO/F2ruomst ORj09ol/vKA9fM0QCk13yyhSx7TCbol8DV1+eaIoRHmIvShuIvQVdRkxs/fiiMR1gzbU HBsUdmbvZWnf+nkGptoZR1SzwdymvaPPCCiNm6mUk+O0xeKMO+p736suGPp7bHFsB8A6 3l9OS/kK967Szv7nNdOeA5Wie/EU78tvoY003G+CrSmukv4k7CyujcDp+mN/C0IUAUuv MYDmeHx2bUR5DqL7vHKJKCmaM7e49Wj54FwFuy9NOYKbjdHlVpP2dt/4cbScPWLPXk0a PaWg== 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: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=61PtzmeCNr5vKWELCfqE8G7aGKDKP9a5Y4L35Rd4SU8=; b=mQoHnI4otChhtrrqN6uNIinvrJeDpnS2ouBwAnLrrD4db8sBXR5ejZka2cdLEZOz1i WRDxGfUCaKI8Krt6ZfTU0kuDI8RRgGwfk9A70LTwef0EwIHZWN8GxJHp2xydXxbcM21n BDvbiC+3br5mIAZnsXlg7xC9JwqOsSS1YWgDPPN8FHZDZdjUoF6r7M8NveieDt5VUKMn xmqt2hTXPgC2EvKFHuoTG4SKfOC8lSGWWfulZNc/38zIafeWw61vFaVrJ/uciBdlCGwa HJVDM4QVXt8Eu8RuFo+r9sMUIUT0E3G4l53vtEMFVOy+71gGTOXPJ9zNjXoPlqtv0xlf maUQ== X-Gm-Message-State: ALoCoQnhRJcBzviDyP16TI/qR1OHOnM16WrIqXMJzHptz4M8MpLDd2XBQUkUeFF3eVmju5nJRlV2 X-Received: by 10.236.4.136 with SMTP id 8mr10319455yhj.21.1392127409051; Tue, 11 Feb 2014 06:03:29 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.28.6 with SMTP id 6ls2492472qgy.16.gmail; Tue, 11 Feb 2014 06:03:28 -0800 (PST) X-Received: by 10.140.109.244 with SMTP id l107mr5325qgf.28.1392127408161; Tue, 11 Feb 2014 06:03:28 -0800 (PST) X-Original-Sender: andrewtomazos@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:9266 Archived-At: ------=_Part_2503_26488091.1392127407450 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hey guys, this is a design I've been toying with (in the abstract for some= =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 which= =20 the performance and timing control of manual memory management and value=20 layout are of great benefit; and (b) higher-level organizational components= =20 for which the benefit is dominated and negligble - and the convenience of= =20 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.= =20 That is, to be able to specify certain classes as being garbage collected= =20 and others to be manually managed - and to only pay for what you 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-selected= =20 types. Also, what we propose is precise garbage collection like in the=20 managed languages, as opposed to conservative collection. The reachability= =20 graph is tracked explicitly through instrumenting the type system. That=20 is, rather than scanning entire memory areas for all potential pointers to= =20 any dynamic memory, only the pointers to collected types are tracked - and= =20 they are tracked as they are initialized, assigned and destroyed. This=20 gives it a radically different performance profile, and makes it=20 proportional only to the use of collected types in the program, and not=20 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 ne= ed 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 sure= =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 be= =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 not= =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, increment= =20 or decrement of a collected pointer. It may also not be converted or cast= =20 to or from void*, and it may not be the subject or result of a reinterpret= =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 base= =20 class subobjects are assigned the null pointer value by the implementation. Given a time point at run-time of the program, we will describe a directed= =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 that= =20 is not a member subobject of an object of collected type, there is an edge= =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 the= =20 collected object of which it is a member to the complete object that is the= =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, or= =20 at the end of the program if they never become unreachable. (As a quality= =20 of implementation issue this should be as soon as reasonably possible given= =20 reasonable resources.) Implementation If a program contains a collected type, a garbage collector is linked into= =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 type= =20 would be similar to collecting pointers. Are the restrictions on storage duration necessary? Couldn=E2=80=99t colle= cted=20 objects of non-dynamic storage duration simply be ignored by the collector?= =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 deleted= =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_2503_26488091.1392127407450 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Hey guys, this is a design I've been toying with (in the abstra= ct for some time actually).  It needs a bunch of work, but I would app= reciate 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 us= er-selected class types to be cyclically garbage collected.  Constrain= ts on the usage of class types so selected, and pointers to such class type= s, are imposed to enable the implementation of fast safe precise collection= ..


M= otivation


Many C++ pro= grams can be decomposed into (a) low-level components for which the perform= ance and timing control of manual memory management and value layout are of= great benefit; and (b) higher-level organizational components for which th= e benefit is dominated and negligble - and the convenience of safe automati= c 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 able to specify ce= rtain classes as being garbage collected and others to be manually managed = - and to only pay for what you use.


Comparison


With Boehm Demers Weiser Collector=


=

The Boehm Collector c= an only be used either program-wide or not-at-all.  What we propose is= olates garbage collection only to certain user-selected types.  Also, = what we propose is precise garbage collection like in the managed languages, as oppos= ed to conservative collection.  The reachability graph is tracked explicitly thr= ough instrumenting the type system.  That is, rather than scanning ent= ire memory areas for all potential pointers to any dynamic memory, only the= pointers to collected types are tracked - and they are tracked as they are= initialized, assigned and destroyed.  This gives it a radically diffe= rent performance profile, and makes it proportional only to the use of coll= ected types in the program, and not proportional to all dynamic memory use.=


=

Wi= th shared_ptr<T>


Shared pointers cannot deal with cycles.  weak_ptr often does not hav= e a sensible place where it can be applied to break cycles, and when it doe= s it is awkward to use.  Shared pointer are also awkward to use with t= his through enable_shared_from_this.  What we propose is much cleaner = and easier to use, at the cost of the added implementation complexity of co= mpiler support.  Under the proposed feature, the user can just use reg= ular pointer syntax to work with collected 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.  In many object models, objects do not have natural = owners, and it can be challenging to impose one.  When an owner is sel= ected the programmer must be careful to make sure the lifetime of the owner= encloses uses of the owned object.  This implementation overhead and = constraint is many times not worth the effort compared to automatic memory = management.


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


Specification


Introduce a context-sensitive keyword gc that can appear in the head of a class s= pecifier:


&nb= sp;  class foo gc

   {

     &= nbsp; ...

   };


If a class type is marked with gc, it is called a collecte= d type.  A= subclass of a collected type is also a collected type, whether or not mark= ed with gc.  A collected type may not have any base classes that are n= ot also collected types.  It follows that all base classes and all sub= classes of a collected type are collected types.


An object of collected type is called a collect= ed object. A collected object may only be a complete object or a base class= subobject, it may not be a member subobject or an array element:

   foo = x[10]; // ill-formed

   struct bar { foo x; } // ill-formed


You can use pointers ins= tead:


 &= nbsp; foo* x[10]; // ok

   struct bar { foo* x; } // ok

 

A collected typ= e may only be allocated with dynamic storage duration.  It may not be = allocated with automatic, static or thread local storage duration.  Ag= ain, you can use pointers instead:


   auto s =3D new foo;


<= span style=3D"font-size: 15px; font-family: 'Courier New'; color: rgb(0, 0,= 0); background-color: transparent; white-space: pre-wrap;">

   = thread_local auto t =3D new foo;


   void f()

   {

&nbs= p;      auto a =3D new foo;

   = }


An object of type po= inter to a collected type, is called a collecting pointer.  A collecti= ng pointer cannot participate in pointer arithmetic.  That is, there i= s no builtin meaning for addition, subtraction, increment or decrement of a= collected pointer.  It may also not be converted or cast to or from v= oid*, and it may not be the subject or result of a reinterpret cast.  = It may only be initialized or assigned a null pointer constant or another c= ollected pointer (possibly dynamic or static cast from a base class or subc= lass).


<= /span>

If a complete c= ollected object is destroyed, any pointers to it or its base class subobjec= ts are assigned the null pointer value by the implementation.

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 collected type there is a no= de.  For each non-null collecting pointer that is not a member subobje= ct of an object of collected type, there is an edge from the root node to t= he complete object of the subject of the pointer.  For each remaining = non-null collecting pointer, there is an edge from the collected object of = which it is a member to the complete object that is the subject of the poin= ter.  If there is no path from the root node to a collected objects no= de, we say the collected object is unreachable.


The implementation 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 u= nreachable.  (As a quality of implementation issue this should be as s= oon as reasonably possible given reasonable resources.)


Implementation<= /p>

If a program contains a col= lected type, a garbage collector is linked into the program by the implemen= tation. The constructor and destructor of both collected types and collecti= ng pointers are generated to talk to the garbage collector.   The= garbage collector uses this information to track the graph.  Periodic= ally the garbage collector searches the graph using a generational or other= garbage collection algorithm, deleting objects as appropriate.

<= br>

Outstanding Is= sues


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


Are the restrictions on storage duration necessary?  Couldn=E2=80=99t= collected objects of non-dynamic storage duration simply be ignored by the= collector?  What about the subobject restriction?  It was initia= lly felt that this would simplify usage and make it safer - as well as easi= ng implementation.


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



<= /span>

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