220 9356 article Path: news.gmane.org!not-for-mail From: Jeffrey Yasskin Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Precise Per-Type Cyclic Garbage Collection (DRAFT 1) Date: Sat, 15 Feb 2014 09:32:19 -0800 Lines: 239 Approved: news@gmane.org Message-ID: References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: ger.gmane.org 1392485553 28354 80.91.229.3 (15 Feb 2014 17:32:33 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 15 Feb 2014 17:32:33 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDDM34EO6QDRBOGJ72LQKGQELNO3LYA@isocpp.org Sat Feb 15 18:32:42 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ie0-f198.google.com ([209.85.223.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WEj6Y-00063X-0h for gclcip-std-proposals@m.gmane.org; Sat, 15 Feb 2014 18:32:42 +0100 Original-Received: by mail-ie0-f198.google.com with SMTP id at1sf15823170iec.5 for ; Sat, 15 Feb 2014 09:32:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=+350A0TmjJxIyI4finMS6bx/3CcPYrc5y22eTauUXz4=; b=dhfGvCidwR+EPHxlvbE68/TZKnpCVDuUAw+T1ZAAJzNPW3Dkx+pRAHdNJ+GjqLZGwc pR2N0EvpvnoJurP6xxemW3zqkrhC/5gn0bthaDLWunxqc3oy4EYLrKWBjxkkNMPgRab3 uF2cXlOxT+rycOaocrivHREQRjMLP0AqbckLiwVHoRZZq66VcFcC5CRNitutlP4Cb7wp oJqXjijwRbA0J0JVoUalFjdpGfCC0s4LdpQD+k6ZkeKT2LBIdHf70C3EVvIS1Gf0mv6O IKQqGnkoO8LKNnBXU6ZkuymL177fWTmrvq9j63v3zg2V65d9FbQ+yV/ZvSbvHfWJXzT4 IrTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe:content-type; bh=+350A0TmjJxIyI4finMS6bx/3CcPYrc5y22eTauUXz4=; b=OTZyMS7Zp+lYrTLEk8R0f63UJSn6/3FfPwPkkSsQSf/plNuFPFWBex/Rfv24rd6ft9 ziwyY/8mysH/WOsOoX4OCnjpF2m0vmV4ghPk8fwb0wIb/JsBHF2nO49jnZJRxidm6Pm0 LN9Tihsnl2X3o8vvwnTaui0bzTbGipYagKmQcc6xJAZmDD/YG5DPljphfELZzgplV20p JoKeeT+z2gYoUvcWDofnOthdVdbekYFiMunHPJktdP8TLHvBYMmh8/EXoFqJ54qCe+xw fIa+R6IhXYrL64ndrI8ECf49SzAWpnHNDaurdndBFhbezvvHD8vckCR/HdDVtb2Xo+gN hgVw== X-Gm-Message-State: ALoCoQlCoOR9SHjNuEiSg98XpoJarEZyZ8wb8Upcc21fGa/pWY3bsP3aG1Rfj4dPdZiPpHk2yTgr X-Received: by 10.182.16.199 with SMTP id i7mr6181032obd.42.1392485561124; Sat, 15 Feb 2014 09:32:41 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.81.20 with SMTP id e20ls415686qgd.58.gmail; Sat, 15 Feb 2014 09:32:40 -0800 (PST) X-Received: by 10.229.184.69 with SMTP id cj5mr23031708qcb.8.1392485560291; Sat, 15 Feb 2014 09:32:40 -0800 (PST) Original-Received: from mail-qc0-x22a.google.com (mail-qc0-x22a.google.com [2607:f8b0:400d:c01::22a]) by mx.google.com with ESMTPS id h93si5897323qgh.154.2014.02.15.09.32.40 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sat, 15 Feb 2014 09:32:40 -0800 (PST) Received-SPF: pass (google.com: domain of jyasskin@google.com designates 2607:f8b0:400d:c01::22a as permitted sender) client-ip=2607:f8b0:400d:c01::22a; Original-Received: by mail-qc0-f170.google.com with SMTP id e9so21968889qcy.15 for ; Sat, 15 Feb 2014 09:32:40 -0800 (PST) X-Received: by 10.140.27.103 with SMTP id 94mr21730299qgw.45.1392485560069; Sat, 15 Feb 2014 09:32:40 -0800 (PST) Original-Received: by 10.229.227.8 with HTTP; Sat, 15 Feb 2014 09:32:19 -0800 (PST) In-Reply-To: X-Original-Sender: jyasskin@google.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of jyasskin@google.com designates 2607:f8b0:400d:c01::22a as permitted sender) smtp.mail=jyasskin@google.com; dkim=pass header.i=@google.com; dmarc=pass (p=REJECT dis=NONE) header.from=google.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:9356 Archived-At: I haven't read the whole thread, but see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2297.html#cycles and http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2286.pdf On Tue, Feb 11, 2014 at 6:03 AM, Andrew Tomazos wrote: > Hey guys, this is a design 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 user-selected > class types to be cyclically garbage collected. Constraints 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 > > > Many C++ programs can be decomposed into (a) low-level components for which > the performance and timing control of manual memory management and value > layout 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 able to specify certain 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 can only be used either program-wide or not-at-all. > What we propose isolates garbage collection only to certain user-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. That is, > rather than scanning entire 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 different performance profile, and makes it proportional only to > the use of collected types in the 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 > sensible place where it can be applied to break cycles, and when it does it > is awkward to use. Shared pointer are also awkward to use with this through > enable_shared_from_this. What we propose is much cleaner and easier to use, > at the cost of the added implementation complexity of compiler support. > Under the proposed feature, the user can just use regular pointer syntax to > work with collected types, and doesn't 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 selected 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 pools, 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 specifier: > > > class foo gc > > { > > ... > > }; > > > If a class type is marked with gc, it is called a collected type. A > subclass of a collected type is also a collected type, whether or not marked > with gc. A collected type may not have any base classes that are not also > collected types. It follows that all base classes and all subclasses of a > collected type are collected types. > > > An object of collected type 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 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 > > > > A collected type may only be allocated with dynamic storage duration. It > may not be allocated with automatic, static or thread local storage > duration. Again, you can use pointers instead: > > > auto s = new foo; > > > thread_local auto t = new foo; > > > void f() > > { > > auto a = new foo; > > } > > > An object of type pointer to a collected type, is called a collecting > pointer. A collecting pointer cannot participate in pointer arithmetic. > That is, there is no builtin meaning for addition, subtraction, increment or > decrement of a collected pointer. It may also not be converted or cast to > or from void*, 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 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 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 node. For each non-null collecting pointer that > is not a member subobject of an object of collected type, there is an edge > 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 from 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 node to a > collected objects node, 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 unreachable. (As a quality > of implementation issue this should be as soon as reasonably possible given > reasonable resources.) > > > Implementation > > > If a program contains a collected type, a garbage collector is linked into > the program by the implementation. The constructor and destructor of both > collected types and collecting pointers are generated to talk to the garbage > collector. The garbage collector uses this information to track the graph. > Periodically the garbage collector searches the graph using a generational > or other garbage collection algorithm, deleting objects as appropriate. > > > Outstanding Issues > > > How do references to collected types work? References are much like > constrained pointers so the specification of a reference to collected type > would be similar to collecting pointers. > > > Are the restrictions on storage duration necessary? Couldn't collected > objects of non-dynamic storage duration simply be ignored by the collector? > What about the subobject restriction? It was initially felt that this would > 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 be 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 > "ISO C++ Standard - Future Proposals" group. > To unsubscribe from this group and stop receiving emails from it, send an > email 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/. -- --- 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 email 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/. .