Topic: Precise Per-Type Cyclic Garbage Collection
Author: =?ISO-8859-1?Q?David_Rodr=EDguez_Ibeas?= <dibeas@ieee.org>
Date: Tue, 11 Feb 2014 13:13:43 -0500
Raw View
--089e013cba969ebe3904f2256a08
Content-Type: text/plain; charset=ISO-8859-1
The problem, Andrew, is that if you build a data structure with a cycle,
say a circular list, using shared_ptr the first node has a count of 2
(original pointer to the list, and last element in the list) while the rest
of the nodes might have a count of 1. Now the list goes out of scope, and
the external reference is dropped, the count of the head of the list drops
from 2 to 1, but it cannot be released yet as the tail of the list still
holds a valid shared_ptr. At this point each node in the list holds the
next node alive even though the program cannot access any of the elements.
On Tue, Feb 11, 2014 at 12:55 PM, Andrew Sandoval <
sandoval@netwaysglobal.com> wrote:
> On Tuesday, February 11, 2014 11:12:01 AM UTC-6, Matthew Woehlke wrote:
>>
>> On 2014-02-11 09:43, Andrew Sandoval wrote:
>> > I'm also not sure you've made the case for why shared_ptr is
>> > insufficient. It, like unique_ptr, gives you exact control over the
>> > lifetime of pointers. They are tied to scope and reference counts as
>> they
>> > are actually used. I may be slow, but I don't understand what you mean
>> by "Shared
>> > pointers cannot deal with cycles." What cycles?
>>
>> Let's say that A and B are classes that each keep a record of other
>> objects referencing them... Now say we have:
>>
>> pa = make_shared<A>();
>> pb = make_shared<b>();
>> // both pa and pb have refcount 1
>> pa->connect(pb);
>> // *pa now has an sptr ref to *pb, likewise *pb to *pa
>> // refcount of pa, pb is 2
>>
>> Now if pa and pb go out of scope, the objects are inaccessible to the
>> program but still reference each other, and so are not freed by
>> shared_ptr. The above may be a contrived example, but that's the idea of
>> a self-referential cycle. Any useful GC needs to be able to detect such
>> cycles.
>>
>> Basically, "reachable memory" is not a function of refcounts but of what
>> memory is accessible, directly or indirectly, via all variables
>> currently in scope.
>>
>> --
>> Matthew
>>
>> I still don't see it. if pa and pb go out of scope, the reference count
> should drop to zero. connect() should either have a shared_ptr at it's
> scope or use one at the class scope and either way when the destructor
> fires (at scope exit) the reference count should drop. If not I would
> think there is a design flaw.
>
> More importantly, the whole thing can probably be simplified to start with
> so that one or both do not need to be dynamically created. I might be
> alone in this, but I find that I very rarely ever use new outside of
> singletons. Almost everything is best kept owned within a particular
> scope. On the rare occasions that new is needed, the results always go to
> a shared_ptr, either at local scope or in container at class scope, etc.
>
> I'm not trying to pick on the idea, I just don't see it. And maybe I'm
> overstating this a little bit, but I really think that the languages that
> use GC have fundamental flaws that hurt the quality of code written with
> them. Way back when Java first came out, GC was the salvation from
> pointers. The problem is that they just made a mess of something that was
> never that bad to start with. So, instead of leaks you get crashes due to
> lifetime issues. It's a lot easier to catch a leak than to solve
> a free-after-use crash. Objective-C, C#, they all have that problem still,
> and they sort of ruin the whole meaning of scope. RAII is a much better
> way IMO.
>
> -Andrew
>
> --
>
> ---
> 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/.
--089e013cba969ebe3904f2256a08
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">The problem, Andrew, is that if you build a data structure=
with a cycle, say a circular list, using shared_ptr the first node has a c=
ount of 2 (original pointer to the list, and last element in the list) whil=
e the rest of the nodes might have a count of 1. Now the list goes out of s=
cope, and the external reference is dropped, the count of the head of the l=
ist drops from 2 to 1, but it cannot be released yet as the tail of the lis=
t still holds a valid shared_ptr. At this point each node in the list holds=
the next node alive even though the program cannot access any of the eleme=
nts.</div>
<div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Tue, Feb 1=
1, 2014 at 12:55 PM, Andrew Sandoval <span dir=3D"ltr"><<a href=3D"mailt=
o:sandoval@netwaysglobal.com" target=3D"_blank">sandoval@netwaysglobal.com<=
/a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div class=3D"h5">On T=
uesday, February 11, 2014 11:12:01 AM UTC-6, Matthew Woehlke wrote:<blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;padding-left:1e=
x;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-styl=
e:solid">
On 2014-02-11 09:43, Andrew Sandoval wrote:
<br>> I'm also not sure you've made the case for why shared_ptr =
is
<br>> insufficient. =A0It, like unique_ptr, gives you exact control over=
the
<br>> lifetime of pointers. =A0They are tied to scope and reference coun=
ts as they
<br>> are actually used. =A0I may be slow, but I don't understand wh=
at you mean by "Shared
<br>> pointers cannot deal with cycles." =A0What cycles?
<br>
<br>Let's say that A and B are classes that each keep a record of other=
=20
<br>objects referencing them... Now say we have:
<br>
<br>pa =3D make_shared<A>();
<br>pb =3D make_shared<b>();
<br>// both pa and pb have refcount 1
<br>pa->connect(pb);
<br>// *pa now has an sptr ref to *pb, likewise *pb to *pa
<br>// refcount of pa, pb is 2
<br>
<br>Now if pa and pb go out of scope, the objects are inaccessible to the=
=20
<br>program but still reference each other, and so are not freed by=20
<br>shared_ptr. The above may be a contrived example, but that's the id=
ea of=20
<br>a self-referential cycle. Any useful GC needs to be able to detect such=
=20
<br>cycles.
<br>
<br>Basically, "reachable memory" is not a function of refcounts =
but of what=20
<br>memory is accessible, directly or indirectly, via all variables=20
<br>currently in scope.
<br>
<br>--=20
<br>Matthew
<br>
<br></blockquote></div></div><div>I still don't see it.=A0 if pa and pb=
go out of scope, the reference count should drop to zero.=A0 connect() sho=
uld either have a shared_ptr at it's scope or use one at the class scop=
e and either way when the destructor fires (at scope exit) the reference co=
unt should drop.=A0 If not I=A0would think there is a design flaw.</div>
<div><br></div><div>More importantly, the whole thing can probably be simpl=
ified to start with so that one or both do not need to be dynamically creat=
ed.=A0 I might be alone in this, but I find that I very rarely ever use new=
outside of singletons.=A0 Almost everything is best kept owned within a pa=
rticular scope.=A0 On the rare occasions that new is needed, the results al=
ways go to a shared_ptr, either at local scope or in container at class sco=
pe, etc.</div>
<div><br></div><div>I'm not trying to pick on the idea, I just don'=
t see it.=A0 And maybe I'm overstating this a little bit, but I really =
think that the languages that use GC have fundamental flaws that hurt the q=
uality of code written with them.=A0 Way back when Java first came out, GC =
was the salvation from pointers.=A0 The problem is that they just made a me=
ss of something that was never that bad to start with.=A0 So, instead of le=
aks you get crashes due to lifetime issues.=A0 It's a lot easier to cat=
ch a leak than to solve a=A0free-after-use crash.=A0 Objective-C, C#, they =
all have that problem still, and they sort of ruin the whole meaning of sco=
pe.=A0 RAII is a much better way IMO.</div>
<span class=3D"HOEnZb"><font color=3D"#888888"><div><br></div><div>-Andrew<=
/div><div><br></div></font></span></div><div class=3D"HOEnZb"><div class=3D=
"h5">
<p></p>
-- <br>
=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--089e013cba969ebe3904f2256a08--
.
Author: Nevin Liber <nevin@eviloverlord.com>
Date: Tue, 11 Feb 2014 12:33:25 -0600
Raw View
--f46d043c7de680fd2a04f225b3b7
Content-Type: text/plain; charset=ISO-8859-1
On 11 February 2014 11:55, Andrew Sandoval <sandoval@netwaysglobal.com>wrote:
>
> I still don't see it. if pa and pb go out of scope, the reference count
> should drop to zero.
>
Here is a trivial example:
struct A {
shared_ptr<A> p;
};
int main() {
auto a = make_shared<A>(); // refcount == 1
a->p = a; // refcount == 2
} // refcount == 1
The refcount never goes to zero, so you have a leak.
More details at <
http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/shared_ptr.htm>.
While people do use GC as a crutch, there are some data structures (such as
lock free) which are significantly easier to implement and reason about if
you have GC. Check out <
http://www.drdobbs.com/lock-free-data-structures/184401865> for a more
in-depth description.
--
Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
--
---
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/.
--f46d043c7de680fd2a04f225b3b7
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On 11 February 2014 11:55, Andrew Sandoval <span dir=3D"lt=
r"><<a href=3D"mailto:sandoval@netwaysglobal.com" target=3D"_blank">sand=
oval@netwaysglobal.com</a>></span> wrote:<br><div class=3D"gmail_extra">=
<div class=3D"gmail_quote">
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div><di=
v class=3D"h5"><br></div></div><div>I still don't see it.=A0 if pa and =
pb go out of scope, the reference count should drop to zero.=A0</div>
</div></blockquote><div><br></div><div>Here is a trivial example:<br><br></=
div><div>struct A {<br></div><div>=A0=A0=A0 shared_ptr<A> p;<br></div=
><div>};<br><br></div><div>int main() {<br></div><div>=A0=A0=A0 auto a =3D =
make_shared<A>();=A0 // refcount =3D=3D 1<br>
</div><div>=A0=A0=A0 a->p =3D a;=A0 // refcount =3D=3D 2<br></div><div>}=
=A0 // refcount =3D=3D 1<br></div><div><br></div><div>The refcount never go=
es to zero, so you have a leak.<br><br></div><div dir=3D"ltr">More details =
at <<a href=3D"http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/share=
d_ptr.htm">http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/shared_ptr.h=
tm</a>>.<br>
<br></div><div dir=3D"ltr">While people do use GC as a crutch, there are so=
me data structures (such as lock free) which are significantly easier to im=
plement and reason about if you have GC.=A0 Check out <<a href=3D"http:/=
/www.drdobbs.com/lock-free-data-structures/184401865">http://www.drdobbs.co=
m/lock-free-data-structures/184401865</a>> for a more in-depth descripti=
on.<br>
</div></div>-- <br>=A0Nevin ":-)" Liber=A0 <mailto:<a href=3D"=
mailto:nevin@eviloverlord.com" target=3D"_blank">nevin@eviloverlord.com</a>=
>=A0 (847) 691-1404
</div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--f46d043c7de680fd2a04f225b3b7--
.
Author: Andrew Sandoval <sandoval@netwaysglobal.com>
Date: Tue, 11 Feb 2014 12:13:14 -0800 (PST)
Raw View
------=_Part_1271_2075578.1392149594677
Content-Type: text/plain; charset=UTF-8
On Tuesday, February 11, 2014 12:33:25 PM UTC-6, Nevin ":-)" Liber wrote:
>
> On 11 February 2014 11:55, Andrew Sandoval <sand...@netwaysglobal.com<javascript:>
> > wrote:
>
>>
>> I still don't see it. if pa and pb go out of scope, the reference count
>> should drop to zero.
>>
>
> Here is a trivial example:
>
> struct A {
> shared_ptr<A> p;
> };
>
> int main() {
> auto a = make_shared<A>(); // refcount == 1
> a->p = a; // refcount == 2
> } // refcount == 1
>
> The refcount never goes to zero, so you have a leak.
>
> More details at <
> http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/shared_ptr.htm>.
>
> While people do use GC as a crutch, there are some data structures (such
> as lock free) which are significantly easier to implement and reason about
> if you have GC. Check out <
> http://www.drdobbs.com/lock-free-data-structures/184401865> for a more
> in-depth description.
> --
> Nevin ":-)" Liber <mailto:ne...@eviloverlord.com <javascript:>> (847)
> 691-1404
>
Okay, I can see that. I just wonder if we can't find a way to solve the
specific problem rather than add a language feature that is likely to be
used as a crutch. Probably just prejudice on my part from seeing too many
developers go after the quick and sloppy.
-Andrew
--
---
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/.
------=_Part_1271_2075578.1392149594677
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Tuesday, February 11, 2014 12:33:25 PM UTC-6, Nevin ":-=
)" Liber wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0=
px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204, 204); border-=
left-width: 1px; border-left-style: solid;"><div dir=3D"ltr">On 11 February=
2014 11:55, Andrew Sandoval <span dir=3D"ltr"><<a onmousedown=3D"this.h=
ref=3D'javascript:';return true;" onclick=3D"this.href=3D'javascript:';retu=
rn true;" href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"k=
729slmKWW0J">sand...@netwaysglobal.com</a>></span> wrote:<br><div><div c=
lass=3D"gmail_quote">
<blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; paddi=
ng-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px=
; border-left-style: solid;"><div dir=3D"ltr"><div><div><br></div></div><di=
v>I still don't see it. if pa and pb go out of scope, the reference c=
ount should drop to zero. </div>
</div></blockquote><div><br></div><div>Here is a trivial example:<br><br></=
div><div>struct A {<br></div><div> shared_ptr<A> p;=
<br></div><div>};<br><br></div><div>int main() {<br></div><div> =
auto a =3D make_shared<A>(); // refcount =3D=3D 1<br>
</div><div> a->p =3D a; // refcount =3D=3D 2<br>=
</div><div>} // refcount =3D=3D 1<br></div><div><br></div><div>The re=
fcount never goes to zero, so you have a leak.<br><br></div><div dir=3D"ltr=
">More details at <<a onmousedown=3D"this.href=3D'http://www.google.com/=
url?q\75http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2F1_55_0%2Flibs%2Fsmart_ptr=
%2Fshared_ptr.htm\46sa\75D\46sntz\0751\46usg\75AFQjCNFGzKEvP7G_sK6LhSc0XUs5=
gWnM9w';return true;" onclick=3D"this.href=3D'http://www.google.com/url?q\7=
5http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2F1_55_0%2Flibs%2Fsmart_ptr%2Fshar=
ed_ptr.htm\46sa\75D\46sntz\0751\46usg\75AFQjCNFGzKEvP7G_sK6LhSc0XUs5gWnM9w'=
;return true;" href=3D"http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/=
shared_ptr.htm" target=3D"_blank">http://www.boost.org/doc/<wbr>libs/1_55_0=
/libs/smart_ptr/<wbr>shared_ptr.htm</a>>.<br>
</div></div></div></div></blockquote><div> </div><blockquote class=3D"=
gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-=
left-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: =
solid;"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><div dir=3D"ltr"><=
/div><div dir=3D"ltr">While people do use GC as a crutch, there are some da=
ta structures (such as lock free) which are significantly easier to impleme=
nt and reason about if you have GC. Check out <<a onmousedown=3D"t=
his.href=3D'http://www.google.com/url?q\75http%3A%2F%2Fwww.drdobbs.com%2Flo=
ck-free-data-structures%2F184401865\46sa\75D\46sntz\0751\46usg\75AFQjCNGjcz=
SaAcv7nrHQvVdj6Z0cr0IEow';return true;" onclick=3D"this.href=3D'http://www.=
google.com/url?q\75http%3A%2F%2Fwww.drdobbs.com%2Flock-free-data-structures=
%2F184401865\46sa\75D\46sntz\0751\46usg\75AFQjCNGjczSaAcv7nrHQvVdj6Z0cr0IEo=
w';return true;" href=3D"http://www.drdobbs.com/lock-free-data-structures/1=
84401865" target=3D"_blank">http://www.drdobbs.com/lock-<wbr>free-data-stru=
ctures/184401865</a><wbr>> for a more in-depth description.<br>
</div></div>-- <br> Nevin ":-)" Liber <mailto:<a onmousedown=
=3D"this.href=3D'javascript:';return true;" onclick=3D"this.href=3D'javascr=
ipt:';return true;" href=3D"javascript:" target=3D"_blank" gdf-obfuscated-m=
ailto=3D"k729slmKWW0J">ne...@eviloverlord.com</a><wbr>> (847) 691-=
1404
</div></div></blockquote><div>Okay, I can see that. I just wonder if =
we can't find a way to solve the specific problem rather than add a languag=
e feature that is likely to be used as a crutch. Probably just p=
rejudice on my part from seeing too many developers go after the quick and =
sloppy.</div><div>-Andrew</div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_1271_2075578.1392149594677--
.
Author: xavi <gratal@gmail.com>
Date: Tue, 11 Feb 2014 21:21:24 +0100
Raw View
--001a11c1301047da1604f2273314
Content-Type: text/plain; charset=ISO-8859-1
2014-02-11 Matthew Woehlke <mw_triad@users.sourceforge.net>:
> On 2014-02-11 14:13, xavi wrote:
>
>> My main concern is whether a language extension is really necessary or it
>> could be implemented as a library.
>>
>
> I believe there are already libraries in the wild that do this. IIRC, VTK (
> http://vtk.org) is one...
>
> See also http://www.aosabook.org/en/vtk.html and http://www.vtk.org/doc/
> release/5.10/html/classvtkGarbageCollector.html.
>
>
> There might be certain things missing in the language:
>> - Being able to forbid automatic storage for certain types.
>> - Having some mechanism so that objects can only be created inside a
>> smart pointer. Without inheritance, it's easy, by making the constructors
>> private and make_ptr (or something similar) a friend.
>>
>
> These days you probably just want to friend std::make_shared.
>
> Intrusive reference-counting is more efficient, and makes a lot of sense
for objects which are always supposed to be reference-counted. It also
allows easily creating new "connected" shared pointers from references,
which seems like a reasonable thing to do. Also, befriending make_shared is
a tricky issue, and it makes *all* your constructors effectively public.
>
> With inheritance things get much more complicated, so the language
>> might need to be changed there.
>>
>
> I'm not sure a technical solution to this problem is required. If someone
> wants to shoot themselves in the foot by bypassing a base class that is
> intended to only ever be constructed into a shared_ptr...
>
> Every constructor would need to be protected, and then every derived class
will need to make their own constructors protected and friend the pointer
maker, and so on... it's easy to make mistakes, and there is some
repetition.
>
> - Maybe tweak virtual inheritance so that it's possible to inherit
>> from
>> two ref-counted classes without significant overhead.
>>
>
> Is this a problem in cases other than non-virtual inheritance from an
> intrusive pointer class? (Do I miss why this would be an issue with plain
> old std::shared_ptr?)
It is an issue the moment you want to enable_shared_from_this.
>
>
> --
> Matthew
>
>
> --
>
> --- 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/.
--001a11c1301047da1604f2273314
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><br><div class=3D"gmail=
_quote">2014-02-11 Matthew Woehlke <span dir=3D"ltr"><<a href=3D"mailto:=
mw_triad@users.sourceforge.net" target=3D"_blank">mw_triad@users.sourceforg=
e.net</a>></span>:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">On 2014-02-11 14:13, xavi =
wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
My main concern is whether a language extension is really necessary or it<b=
r>
could be implemented as a library.<br>
</blockquote>
<br></div>
I believe there are already libraries in the wild that do this. IIRC, VTK (=
<a href=3D"http://vtk.org" target=3D"_blank">http://vtk.org</a>) is one...<=
br>
<br>
See also <a href=3D"http://www.aosabook.org/en/vtk.html" target=3D"_blank">=
http://www.aosabook.org/en/<u></u>vtk.html</a> and <a href=3D"http://www.vt=
k.org/doc/release/5.10/html/classvtkGarbageCollector.html" target=3D"_blank=
">http://www.vtk.org/doc/<u></u>release/5.10/html/<u></u>classvtkGarbageCol=
lector.html</a>.<div class=3D"im">
<br>
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
There might be certain things missing in the language:<br>
=A0 =A0 - Being able to forbid automatic storage for certain types.<br>
=A0 =A0 - Having some mechanism so that objects can only be created inside =
a<br>
smart pointer. Without inheritance, it's easy, by making the constructo=
rs<br>
private and make_ptr (or something similar) a friend.<br>
</blockquote>
<br></div>
These days you probably just want to friend std::make_shared.<div class=3D"=
im"><br></div></blockquote><div>Intrusive reference-counting is more effici=
ent, and makes a lot of sense for objects which are always supposed to be r=
eference-counted. It also allows easily creating new "connected" =
shared pointers from references, which seems like a reasonable thing to do.=
Also, befriending make_shared is a tricky issue, and it makes *all* your c=
onstructors effectively public.</div>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
With inheritance things get much more complicated, so the language<br>
might need to be changed there.<br>
</blockquote>
<br></div>
I'm not sure a technical solution to this problem is required. If someo=
ne wants to shoot themselves in the foot by bypassing a base class that is =
intended to only ever be constructed into a shared_ptr...<div class=3D"im">
<br></div></blockquote><div>Every constructor would need to be protected, a=
nd then every derived class will need to make their own constructors protec=
ted and friend the pointer maker, and so on... it's easy to make mistak=
es, and there is some repetition.</div>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
=A0 =A0 - Maybe tweak virtual inheritance so that it's possible to inhe=
rit from<br>
two ref-counted classes without significant overhead.<br>
</blockquote>
<br></div>
Is this a problem in cases other than non-virtual inheritance from an intru=
sive pointer class? (Do I miss why this would be an issue with plain old st=
d::shared_ptr?)</blockquote><div><br></div><div>It is an issue the moment y=
ou want to enable_shared_from_this.=A0</div>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><span class=3D"HOEnZb"><font color=3D"#88888=
8"><br>
<br>
-- <br>
Matthew</font></span><div class=3D"HOEnZb"><div class=3D"h5"><br>
<br>
-- <br>
<br>
--- You received this message because you are subscribed to the Google Grou=
ps "ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@<u></u>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/<u></u>isocpp.=
org/group/std-<u></u>proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--001a11c1301047da1604f2273314--
.
Author: hun.nemethpeter@gmail.com
Date: Tue, 11 Feb 2014 15:58:20 -0800 (PST)
Raw View
------=_Part_5255_2079418.1392163100473
Content-Type: text/plain; charset=UTF-8
I think the real question here is can we detect shared_ptr cycles in
compile time?
On Tuesday, February 11, 2014 7:33:25 PM UTC+1, Nevin ":-)" Liber wrote:
>
> On 11 February 2014 11:55, Andrew Sandoval <sand...@netwaysglobal.com<javascript:>
> > wrote:
>
>>
>> I still don't see it. if pa and pb go out of scope, the reference count
>> should drop to zero.
>>
>
> Here is a trivial example:
>
> struct A {
> shared_ptr<A> p;
> };
>
> int main() {
> auto a = make_shared<A>(); // refcount == 1
> a->p = a; // refcount == 2
> } // refcount == 1
>
> The refcount never goes to zero, so you have a leak.
>
> More details at <
> http://www.boost.org/doc/libs/1_55_0/libs/smart_ptr/shared_ptr.htm>.
>
> While people do use GC as a crutch, there are some data structures (such
> as lock free) which are significantly easier to implement and reason about
> if you have GC. Check out <
> http://www.drdobbs.com/lock-free-data-structures/184401865> for a more
> in-depth description.
> --
> Nevin ":-)" Liber <mailto:ne...@eviloverlord.com <javascript:>> (847)
> 691-1404
>
--
---
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/.
------=_Part_5255_2079418.1392163100473
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I think the real question here is can we detect shared_ptr=
cycles in compile time?<br><br>On Tuesday, February 11, 2014 7:33:25 PM UT=
C+1, Nevin ":-)" Liber wrote:<blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><=
div dir=3D"ltr">On 11 February 2014 11:55, Andrew Sandoval <span dir=3D"ltr=
"><<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"k7=
29slmKWW0J" onmousedown=3D"this.href=3D'javascript:';return true;" onclick=
=3D"this.href=3D'javascript:';return true;">sand...@netwaysglobal.com</a>&g=
t;</span> wrote:<br><div><div class=3D"gmail_quote">
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div><di=
v><br></div></div><div>I still don't see it. if pa and pb go out of s=
cope, the reference count should drop to zero. </div>
</div></blockquote><div><br></div><div>Here is a trivial example:<br><br></=
div><div>struct A {<br></div><div> shared_ptr<A> p;=
<br></div><div>};<br><br></div><div>int main() {<br></div><div> =
auto a =3D make_shared<A>(); // refcount =3D=3D 1<br>
</div><div> a->p =3D a; // refcount =3D=3D 2<br>=
</div><div>} // refcount =3D=3D 1<br></div><div><br></div><div>The re=
fcount never goes to zero, so you have a leak.<br><br></div><div dir=3D"ltr=
">More details at <<a href=3D"http://www.boost.org/doc/libs/1_55_0/libs/=
smart_ptr/shared_ptr.htm" target=3D"_blank" onmousedown=3D"this.href=3D'htt=
p://www.google.com/url?q\75http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2F1_55_0=
%2Flibs%2Fsmart_ptr%2Fshared_ptr.htm\46sa\75D\46sntz\0751\46usg\75AFQjCNFGz=
KEvP7G_sK6LhSc0XUs5gWnM9w';return true;" onclick=3D"this.href=3D'http://www=
..google.com/url?q\75http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2F1_55_0%2Flibs=
%2Fsmart_ptr%2Fshared_ptr.htm\46sa\75D\46sntz\0751\46usg\75AFQjCNFGzKEvP7G_=
sK6LhSc0XUs5gWnM9w';return true;">http://www.boost.org/doc/<wbr>libs/1_55_0=
/libs/smart_ptr/<wbr>shared_ptr.htm</a>>.<br>
<br></div><div dir=3D"ltr">While people do use GC as a crutch, there are so=
me data structures (such as lock free) which are significantly easier to im=
plement and reason about if you have GC. Check out <<a href=3D"htt=
p://www.drdobbs.com/lock-free-data-structures/184401865" target=3D"_blank" =
onmousedown=3D"this.href=3D'http://www.google.com/url?q\75http%3A%2F%2Fwww.=
drdobbs.com%2Flock-free-data-structures%2F184401865\46sa\75D\46sntz\0751\46=
usg\75AFQjCNGjczSaAcv7nrHQvVdj6Z0cr0IEow';return true;" onclick=3D"this.hre=
f=3D'http://www.google.com/url?q\75http%3A%2F%2Fwww.drdobbs.com%2Flock-free=
-data-structures%2F184401865\46sa\75D\46sntz\0751\46usg\75AFQjCNGjczSaAcv7n=
rHQvVdj6Z0cr0IEow';return true;">http://www.drdobbs.com/lock-<wbr>free-data=
-structures/184401865</a><wbr>> for a more in-depth description.<br>
</div></div>-- <br> Nevin ":-)" Liber <mailto:<a href=3D"java=
script:" target=3D"_blank" gdf-obfuscated-mailto=3D"k729slmKWW0J" onmousedo=
wn=3D"this.href=3D'javascript:';return true;" onclick=3D"this.href=3D'javas=
cript:';return true;">ne...@eviloverlord.com</a><wbr>> (847) 691-1=
404
</div></div>
</blockquote></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_5255_2079418.1392163100473--
.
Author: Patrick Michael Niedzielski <patrickniedzielski@gmail.com>
Date: Wed, 12 Feb 2014 00:52:22 +0000
Raw View
--=-4JWPT1PgcYWPX2DZt6jN
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On mar, 2014-02-11 at 15:58 -0800, hun.nemethpeter@gmail.com wrote:
> I think the real question here is can we detect shared_ptr cycles in=20
> compile time?
Not in the general case, because you'd run into the halting problem.
What a given shared_ptr<> points to is not known always known at
compile-time. To know whether there is a shared_ptr cycle at any point
during the duration of the program, you have to do static analysis on
the program with all possible inputs. The problem with that, though, is
that you can't know whether a given program will halt on some given set
of inputs, so you can't even guarantee that your compilation will
finish.
(As a side note, the way the standard deals with the halting problem at
compile time probably wouldn't work here. In cases like template
recursion and preprocessor macros, which are often said to be
"Turing-complete", the standard places an implementation-defined limit
on the maximum recursion depth. This makes them not Turing-complete,
technically, although that's generally not important.)
In trivial cases, you may be able to detect them, but that won't help
much, and doesn't solve the problem. It may be a useful diagnostic,
though.
Cheers,
Patrick Niedzielski
--=-4JWPT1PgcYWPX2DZt6jN
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part
Content-Transfer-Encoding: 7bit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
iQIcBAABCgAGBQJS+sXGAAoJEJ5dAi8Pze/myK8QALasG8dWRNg2sqKslfFbvAEo
7IxSMXw/1z4ZNCAv/2D/r3BKWDeGS2axLfoD6x0crWGvWvmftvOWUX4A8T8sWtGL
jBL0qxaYaawA9JT/VtD6zA3ack1OFLfSIrSjwC5Ex+2GyG/lud7JlY8fWIvFQomZ
wFmZ9vhtgBUToPYV+0YA1mE3YIb5k+g+9LNOL0rRfidBcsfRG3xnPfECxSzA87rE
9iuc+BoM32bTeCL/uW3ttMwZHFfnmWtKePa4z+nXWfTntzfBWHuYj+nKkNv4RTqA
W0XUevTDsmygIIN2lCMSfMhoMZJIOpJyQ+3CBl24dnuekdv+Oc/T4BI04k1lSn8r
iHhtxB4YXIVvqdxiWhskCBXMMaRHu1/L+jEdzoHYlZ5wtf7+FDpdjI/nVKwhLk1C
djQzhmnshYfAqy2ZICM2eXTUU9M3b72fnQvM7HcHLLL9pcsrapZMXWl17ZB3bFNX
hPFTaTJdFoE+hkzhPj80vUMviaIFEoKFNxJ4VnUfrGGAzvDrmLeVSwklLsOmmu2n
fFzgO7b+xwNhW3uiR8ns0CURPBVh3LzXqmjoHIM058F5sFrnpXlpWeQEbn9v37TE
Cvzs+7u1k5nywgWrwKHGdLyVn0p0f9NfOemUliNe32D2N4WhVs75G33pnWAwYWKc
qazhKFOQz1rW2Ii1bmNB
=2LuN
-----END PGP SIGNATURE-----
--=-4JWPT1PgcYWPX2DZt6jN--
.
Author: Geoffrey Romer <gromer@google.com>
Date: Tue, 11 Feb 2014 16:59:29 -0800
Raw View
--047d7beb961ec1a4d404f22b153c
Content-Type: text/plain; charset=UTF-8
On Tue, Feb 11, 2014 at 4:52 PM, Patrick Michael Niedzielski <
patrickniedzielski@gmail.com> wrote:
>
>
> On mar, 2014-02-11 at 15:58 -0800, hun.nemethpeter@gmail.com wrote:
> > I think the real question here is can we detect shared_ptr cycles in
> > compile time?
>
> Not in the general case, because you'd run into the halting problem.
> What a given shared_ptr<> points to is not known always known at
> compile-time. To know whether there is a shared_ptr cycle at any point
> during the duration of the program, you have to do static analysis on
> the program with all possible inputs. The problem with that, though, is
> that you can't know whether a given program will halt on some given set
> of inputs, so you can't even guarantee that your compilation will
> finish.
>
Here's a simple example:
struct s {
shared_ptr<s> ptr;
}
shared_ptr<s> f(int n) {
static map<int, shared_ptr<s>> ptrs = {{1, {nullptr}}};
if (ptrs.find(n) == ptrs.end()) {
if (n %2 == 0) {
ptrs.emplace(n, f(n/2));
} else {
ptrs.emplace(n, f(3*n + 1));
}
}
return ptrs[n];
}
int main() {
int n;
cin >> n;
f(n);
return 0;
}
If your compiler can tell you whether this program contains any reference
cycles, it has just solved a problem that has defeated some of the world's
greatest mathematicians, called the Collatz conjecture.
>
> (As a side note, the way the standard deals with the halting problem at
> compile time probably wouldn't work here.
There's no "probably" about it; this will not work.
> In cases like template
> recursion and preprocessor macros, which are often said to be
> "Turing-complete", the standard places an implementation-defined limit
> on the maximum recursion depth. This makes them not Turing-complete,
> technically, although that's generally not important.)
>
> In trivial cases, you may be able to detect them, but that won't help
> much, and doesn't solve the problem. It may be a useful diagnostic,
> though.
>
> Cheers,
> Patrick Niedzielski
>
--
---
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/.
--047d7beb961ec1a4d404f22b153c
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Feb 11, 2014 at 4:52 PM, Patrick Michael Niedzielski <span dir=3D"l=
tr"><<a href=3D"mailto:patrickniedzielski@gmail.com" target=3D"_blank">p=
atrickniedzielski@gmail.com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div class=3D""><br>
<br>
On mar, 2014-02-11 at 15:58 -0800, <a href=3D"mailto:hun.nemethpeter@gmail.=
com">hun.nemethpeter@gmail.com</a> wrote:<br>
> I think the real question here is can we detect shared_ptr cycles in<b=
r>
> compile time?<br>
<br>
</div>Not in the general case, because you'd run into the halting probl=
em.<br>
What a given shared_ptr<> points to is not known always known at<br>
compile-time. =C2=A0To know whether there is a shared_ptr cycle at any poin=
t<br>
during the duration of the program, you have to do static analysis on<br>
the program with all possible inputs. =C2=A0The problem with that, though, =
is<br>
that you can't know whether a given program will halt on some given set=
<br>
of inputs, so you can't even guarantee that your compilation will<br>
finish.<br></blockquote><div><br></div><div>Here's a simple example:</d=
iv><div><br></div><div><div>struct s {</div><div>=C2=A0 shared_ptr<s>=
ptr;</div><div>}</div><div><br></div><div>shared_ptr<s> f(int n) {</=
div>
<div>=C2=A0 static map<int, shared_ptr<s>> ptrs =3D {{1, {nullp=
tr}}};</div><div>=C2=A0 if (ptrs.find(n) =3D=3D ptrs.end()) {</div><div>=C2=
=A0 =C2=A0 if (n %2 =3D=3D 0) {</div><div>=C2=A0 =C2=A0 =C2=A0 ptrs.emplace=
(n, f(n/2));</div><div>=C2=A0 =C2=A0 } else {</div>
<div>=C2=A0 =C2=A0 =C2=A0 ptrs.emplace(n, f(3*n + 1));</div><div>=C2=A0 =C2=
=A0 }</div><div>=C2=A0 }</div><div>=C2=A0 return ptrs[n];</div><div>}</div>=
<div><br></div><div>int main() {</div><div>=C2=A0 int n;</div><div>=C2=A0 c=
in >> n;</div><div>=C2=A0 f(n);</div><div>
=C2=A0 return 0;</div><div>}</div><div><br></div><div>If your compiler can =
tell you whether this program contains any reference cycles, it has just so=
lved a problem that has defeated some of the world's greatest mathemati=
cians, called the Collatz conjecture.</div>
</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bo=
rder-left-style:solid;padding-left:1ex">
<br>
(As a side note, the way the standard deals with the halting problem at<br>
compile time probably wouldn't work here.</blockquote><div><br></div><d=
iv>There's no "probably" about it; this will not work.</div><=
div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0=
px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-le=
ft-style:solid;padding-left:1ex">
=C2=A0In cases like template<br>
recursion and preprocessor macros, which are often said to be<br>
"Turing-complete", the standard places an implementation-defined =
limit<br>
on the maximum recursion depth. =C2=A0This makes them not Turing-complete,<=
br>
technically, although that's generally not important.)<br>
<br>
In trivial cases, you may be able to detect them, but that won't help<b=
r>
much, and doesn't solve the problem. =C2=A0It may be a useful diagnosti=
c,<br>
though.<br>
<br>
Cheers,<br>
Patrick Niedzielski<br>
</blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--047d7beb961ec1a4d404f22b153c--
.
Author: Patrick Michael Niedzielski <patrickniedzielski@gmail.com>
Date: Wed, 12 Feb 2014 02:06:00 +0000
Raw View
--=-ZXdd4Ce/x7SFDJ0TbLpE
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On mar, 2014-02-11 at 16:59 -0800, Geoffrey Romer wrote:
> Here's a simple example:
>=20
> struct s {
> shared_ptr<s> ptr;
> }
>=20
> shared_ptr<s> f(int n) {
> static map<int, shared_ptr<s>> ptrs =3D {{1, {nullptr}}};
> if (ptrs.find(n) =3D=3D ptrs.end()) {
> if (n %2 =3D=3D 0) {
> ptrs.emplace(n, f(n/2));
> } else {
> ptrs.emplace(n, f(3*n + 1));
> }
> }
> return ptrs[n];
> }
>=20
> int main() {
> int n;
> cin >> n;
> f(n);
> return 0;
> }
>=20
> If your compiler can tell you whether this program contains any reference
> cycles, it has just solved a problem that has defeated some of the world'=
s
> greatest mathematicians, called the Collatz conjecture.
You're right in that that's an example of an undecidable program, but
there's a strategy to tell that this program will not have reference
cycles. The ptr inside s can only point to nullptr, because it is only
set during construction, and never changed. Every time you emplace, you
are constructing a shared_ptr<s> based on another shared_ptr<s>. The
only shared_ptr<s> that can originally be constructed from has a nullptr
in its ptr member. Assuming std::map's emplace member function doesn't
do any magic (which it shouldn't, for obvious reasons), all
shared_ptr<s> in the map will point to the same object of type s, who
has a null shared_ptr<s>. In other words, no reference cycles, found in
a way that avoids the halting problem altogether.
That said, that's not an easy thing to get a compiler to do that, and
it's not worth it. Furthermore, it doesn't solve the problem in
general, so this still can't be done.
> > (As a side note, the way the standard deals with the halting problem at
> > compile time probably wouldn't work here.
>=20
> There's no "probably" about it; this will not work.
Okay, I should clarify. For using a strategy I hinted below your
response (i.e., doing what template recursion and preprocessor macros do
by placing an implementation-defined limit on the maximum depth of the
construct), there is no "probably" about, yes. It *will definitely*
work. Limiting the theoretical Turing completeness of the language with
an analogous implementation-defined limit on recursion depth and looping
count/depth would cause this to be solvable in O(n) time, based on the
number of loops or recursive calls total (each loop/recursive function
call could be checked in O(1) time, with a sufficiently large constant
based on the implementation-defined limit).
The "probably" was a polite way of saying "this is obviously
non-solution". At least, I hope it's obvious why.
Cheers,
Patrick
--=-ZXdd4Ce/x7SFDJ0TbLpE
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part
Content-Transfer-Encoding: 7bit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
iQIcBAABCgAGBQJS+tcIAAoJEJ5dAi8Pze/m79wQAJs3F0ezuqDCzdvZSGUDCD14
WOqK9SUikUGBQ4xY8teXfys3VafLPeFt9VdnftjFIzNgMoUAr5eNdzMdFdRxfPfr
ImCGk4mlM/BW3Fj1SiDkIHP1YTFB8SJbm23uH93QcUI0+psMUtG8ORsEgtpXgv/9
rS6Ttgc6F7b96gxgNuk28aFzYlWAAHj7H6yLHu4h3VhnWtcmwI8rWQ/kaFIjShES
ZjqUmKNFYML/RCOz86kQwUjCZh/7YWPneb4jS3DSkYJSCmdan0XnXbVJiaX9N3kY
TagqpCp/6vIoxTVTX6u077I9JuPVR3hQxLVDlWkh0N8GFrlIyow3LkxZQei40A4J
60Be0USUWul2GinCacH1TKqk+aMQj2dzYu2vmG8TAel0TyUH1mJTPUZR8elpSiKF
/h18cuOqP85T07+23QF7O1xybyEX3Vgqye30VTHdc5yD9gglUI2Uf5dYM5IpCqvk
LkIeQ0KPS8rypO0/mUyLpKQZgwNuac0ID5S/81oWEK2uHbzG5RuyIkYQkNG4t4Y/
FO7e1iQfLYY4yOAxpfPLhoJEfuY7Lavl5TDcth7ku4gPRGfY50qhBQT85uZpfrdu
GomP0nywBBfwNBaUX9eeGzzJKbcYcexfutoYXk9qCCu9MYsngobmY18qcKYjPfJV
UT68miMNHZM3H4+xFDDJ
=25ev
-----END PGP SIGNATURE-----
--=-ZXdd4Ce/x7SFDJ0TbLpE--
.
Author: Andrew Tomazos <andrewtomazos@gmail.com>
Date: Tue, 11 Feb 2014 19:56:38 -0800 (PST)
Raw View
------=_Part_5355_2740755.1392177398315
Content-Type: text/plain; charset=UTF-8
On Wednesday, February 12, 2014 12:58:20 AM UTC+1, hun.nem...@gmail.com
wrote:
>
> I think the real question here is can we detect shared_ptr cycles in
> compile time?
>
Garbage collection has been a topic of intense study in academia for
decades and is on-going. If you are interested I would encourage you to
read up on it. Section 7.5 to 7.8 in the dragon book 2nd edition has a
good primer.
The important thing to understand is that to do better than shared_ptr,
which cannot even detect cycles at run-time, much less compile-time - we
need to be able to expose the full reachability graph to the garbage
collection algorithm. A shared_ptr cannot see the whole graph - it can
only see the inbound-side of edges, not the outbound-side. That is, each
shared_ptr is an edge of the graph, and it can see who it is pointing to,
but it doesn't know who it belongs to. Under the proposal the full graph
is tracked by instrumenting the constructors of collected types and
collecting pointers.
--
---
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/.
------=_Part_5355_2740755.1392177398315
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Wednesday, February 12, 2014 12:58:20 AM UTC+1, hun.nem=
....@gmail.com wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;ma=
rgin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">I think the real question here is can we detect shared_ptr cycles =
in compile time?</div></blockquote><div><br></div><div>Garbage collection h=
as been a topic of intense study in academia for decades and is on-going. &=
nbsp;If you are interested I would encourage you to read up on it. Se=
ction 7.5 to 7.8 in the dragon book 2nd edition has a good primer.</div><di=
v><br></div><div>The important thing to understand is that to do better tha=
n shared_ptr, which cannot even detect cycles at run-time, much less compil=
e-time - we need to be able to expose the full reachability graph to the ga=
rbage collection algorithm. A shared_ptr cannot see the whole graph -=
it can only see the inbound-side of edges, not the outbound-side. Th=
at is, each shared_ptr is an edge of the graph, and it can see who it is po=
inting to, but it doesn't know who it belongs to. Under the proposal =
the full graph is tracked by instrumenting the constructors of collected ty=
pes and collecting pointers.</div><div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_5355_2740755.1392177398315--
.
Author: hun.nemethpeter@gmail.com
Date: Tue, 11 Feb 2014 21:01:49 -0800 (PST)
Raw View
------=_Part_5255_4471275.1392181309349
Content-Type: text/plain; charset=UTF-8
On Wednesday, February 12, 2014 1:59:29 AM UTC+1, Geoffrey Romer wrote:
>
>
> On Tue, Feb 11, 2014 at 4:52 PM, Patrick Michael Niedzielski <
> patrickni...@gmail.com <javascript:>> wrote:
>
>>
>>
>> On mar, 2014-02-11 at 15:58 -0800, hun.nem...@gmail.com <javascript:>wrote:
>> > I think the real question here is can we detect shared_ptr cycles in
>> > compile time?
>>
>> Not in the general case, because you'd run into the halting problem.
>>
> And what about the non-general case?
>
> struct s {
> shared_ptr<s> ptr;
> }
>
>
This S struct refers to S as a shared_ptr.
Is it possible to create a safe struct pattern, where cycle is not
possible? This is smaller goal then a generic one.
So my idea is introducing a new attribute, called [[cycle_free]] or
[[acyclic]] or whatever that can be attached to a class.
so
[[cycle_free]]
struct S {
shared_ptr<S> ptr;
};
will gives a warning because a cycle is possible with this. And a
cycle_free class only contains cycle_free ones.
--
---
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/.
------=_Part_5255_4471275.1392181309349
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br>On Wednesday, February 12, 2014 1:59:29 AM UTC+1, Geof=
frey Romer wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr"><div><br><div class=3D"gmail_quote">On Tue, Feb 11, 2014 at 4:52 PM, Pa=
trick Michael Niedzielski <span dir=3D"ltr"><<a href=3D"javascript:" tar=
get=3D"_blank" gdf-obfuscated-mailto=3D"e6Sy5cx_CoEJ" onmousedown=3D"this.h=
ref=3D'javascript:';return true;" onclick=3D"this.href=3D'javascript:';retu=
rn true;">patrickni...@gmail.com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div><br>
<br>
On mar, 2014-02-11 at 15:58 -0800, <a href=3D"javascript:" target=3D"_blank=
" gdf-obfuscated-mailto=3D"e6Sy5cx_CoEJ" onmousedown=3D"this.href=3D'javasc=
ript:';return true;" onclick=3D"this.href=3D'javascript:';return true;">hun=
..nem...@gmail.com</a> wrote:<br>
> I think the real question here is can we detect shared_ptr cycles in<b=
r>
> compile time?<br>
<br>
</div>Not in the general case, because you'd run into the halting problem.<=
br></blockquote></div></div></div></blockquote><div>And what about the non-=
general case?<br> </div><blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><=
div dir=3D"ltr"><div><div class=3D"gmail_quote"><br><div><div>struct s {</d=
iv><div> shared_ptr<s> ptr;</div><div>}</div><div><br></div></d=
iv></div></div></div></blockquote><div> </div>This S struct refers to =
S as a shared_ptr. <br><br>Is it possible to create a safe struct pattern, =
where cycle is not possible? This is smaller goal then a generic one.<br><b=
r>So my idea is introducing a new attribute, called [[cycle_free]] or [[acy=
clic]] or whatever that can be attached to a class.<br><br>so<br><br><div c=
lass=3D"prettyprint" style=3D"background-color: rgb(250, 250, 250); border-=
color: rgb(187, 187, 187); border-style: solid; border-width: 1px; word-wra=
p: break-word;"><code class=3D"prettyprint"><div class=3D"subprettyprint"><=
span style=3D"color: #660;" class=3D"styled-by-prettify">[[</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">cycle_free</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">]]</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #=
008;" class=3D"styled-by-prettify">struct</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> S </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br> shared_ptr</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify"><</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">S</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">></span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> ptr</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">};</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"><br></span></div></code>=
</div><br>will gives a warning because a cycle is possible with this. And a=
cycle_free class only contains cycle_free ones.<br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_5255_4471275.1392181309349--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Tue, 11 Feb 2014 21:02:32 -0800
Raw View
Em ter 11 fev 2014, =E0s 20:36:57, Andrew Tomazos escreveu:
> It should be clear that such a system as a pure library solution is=20
> extremely awkward to use and unsafe. Under the proposal, this graph=20
> tracking is instrumented automatically by the compiler. Given the=20
> extremely high demand for this feature, it should be clear that a core=20
> language addition is warranted.=20
Can it wait for compile-time reflection support and simply use that to dete=
ct=20
which members are collecting pointers?
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--=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/.
.
Author: Geoffrey Romer <gromer@google.com>
Date: Tue, 11 Feb 2014 21:23:17 -0800
Raw View
--001a11c15af22d997204f22ec504
Content-Type: text/plain; charset=UTF-8
On Tue, Feb 11, 2014 at 6:06 PM, Patrick Michael Niedzielski <
patrickniedzielski@gmail.com> wrote:
>
>
> On mar, 2014-02-11 at 16:59 -0800, Geoffrey Romer wrote:
> > Here's a simple example:
> >
> > struct s {
> > shared_ptr<s> ptr;
> > }
> >
> > shared_ptr<s> f(int n) {
> > static map<int, shared_ptr<s>> ptrs = {{1, {nullptr}}};
> > if (ptrs.find(n) == ptrs.end()) {
> > if (n %2 == 0) {
> > ptrs.emplace(n, f(n/2));
> > } else {
> > ptrs.emplace(n, f(3*n + 1));
> > }
> > }
> > return ptrs[n];
> > }
> >
> > int main() {
> > int n;
> > cin >> n;
> > f(n);
> > return 0;
> > }
> >
> > If your compiler can tell you whether this program contains any reference
> > cycles, it has just solved a problem that has defeated some of the
> world's
> > greatest mathematicians, called the Collatz conjecture.
>
> You're right in that that's an example of an undecidable program,
Well, strictly speaking it's not known to be undecidable (and I wouldn't be
surprised if it was decidable), it's just evidently _extremely hard_ to
decide.
> but
> there's a strategy to tell that this program will not have reference
> cycles. The ptr inside s can only point to nullptr, because it is only
> set during construction, and never changed. Every time you emplace, you
> are constructing a shared_ptr<s> based on another shared_ptr<s>. The
> only shared_ptr<s> that can originally be constructed from has a nullptr
> in its ptr member. Assuming std::map's emplace member function doesn't
> do any magic (which it shouldn't, for obvious reasons), all
> shared_ptr<s> in the map will point to the same object of type s, who
> has a null shared_ptr<s>. In other words, no reference cycles, found in
> a way that avoids the halting problem altogether.
>
Argh, you're right, but that's a bug in my example, not a fundamental
point. I think this fixes it:
shared_ptr<s> f(int n) {
static map<int, shared_ptr<s>> ptrs = {{1, {nullptr}}};
if (n != 1 && ptrs[n].ptr == nullptr) {
if (n %2 == 0) {
ptrs[n].ptr = f(n/2);
} else {
ptrs[n].ptr = f(3*n + 1);
}
}
return ptrs[n];
}
The point of the code is that it produces a reference cycle if and only if
the "hailstone sequence" starting with the input number contains a cycle
other than (4, 2, 1), so determining at compile time if this code can
produce a reference cycle requires deciding whether there exists a cycle
other than (4, 2, 1) in the hailstone sequence of any number, which would
be tantamount to solving the Collatz conjecture.
>
> That said, that's not an easy thing to get a compiler to do that, and
> it's not worth it. Furthermore, it doesn't solve the problem in
> general, so this still can't be done.
>
>
> > > (As a side note, the way the standard deals with the halting problem at
> > > compile time probably wouldn't work here.
> >
> > There's no "probably" about it; this will not work.
>
> Okay, I should clarify. For using a strategy I hinted below your
> response (i.e., doing what template recursion and preprocessor macros do
> by placing an implementation-defined limit on the maximum depth of the
> construct), there is no "probably" about, yes. It *will definitely*
> work. Limiting the theoretical Turing completeness of the language with
> an analogous implementation-defined limit on recursion depth and looping
> count/depth would cause this to be solvable in O(n) time, based on the
> number of loops or recursive calls total (each loop/recursive function
> call could be checked in O(1) time, with a sufficiently large constant
> based on the implementation-defined limit).
>
> The "probably" was a polite way of saying "this is obviously
> non-solution". At least, I hope it's obvious why.
>
> Cheers,
> Patrick
>
--
---
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/.
--001a11c15af22d997204f22ec504
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Feb 11, 2014 at 6:06 PM, Patrick Michael Niedzielski <span dir=3D"l=
tr"><<a href=3D"mailto:patrickniedzielski@gmail.com" target=3D"_blank">p=
atrickniedzielski@gmail.com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div class=3D""><br>
<br>
On mar, 2014-02-11 at 16:59 -0800, Geoffrey Romer wrote:<br>
> Here's a simple example:<br>
><br>
> struct s {<br>
> =C2=A0 shared_ptr<s> ptr;<br>
> }<br>
><br>
> shared_ptr<s> f(int n) {<br>
> =C2=A0 static map<int, shared_ptr<s>> ptrs =3D {{1, {nullp=
tr}}};<br>
> =C2=A0 if (ptrs.find(n) =3D=3D ptrs.end()) {<br>
> =C2=A0 =C2=A0 if (n %2 =3D=3D 0) {<br>
> =C2=A0 =C2=A0 =C2=A0 ptrs.emplace(n, f(n/2));<br>
> =C2=A0 =C2=A0 } else {<br>
> =C2=A0 =C2=A0 =C2=A0 ptrs.emplace(n, f(3*n + 1));<br>
> =C2=A0 =C2=A0 }<br>
> =C2=A0 }<br>
> =C2=A0 return ptrs[n];<br>
> }<br>
><br>
> int main() {<br>
> =C2=A0 int n;<br>
> =C2=A0 cin >> n;<br>
> =C2=A0 f(n);<br>
> =C2=A0 return 0;<br>
> }<br>
><br>
> If your compiler can tell you whether this program contains any refere=
nce<br>
> cycles, it has just solved a problem that has defeated some of the wor=
ld's<br>
> greatest mathematicians, called the Collatz conjecture.<br>
<br>
</div>You're right in that that's an example of an undecidable prog=
ram,</blockquote><div><br></div><div>Well, strictly speaking it's not k=
nown to be undecidable (and I wouldn't be surprised if it was decidable=
), it's just evidently _extremely hard_ to decide.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"> but<br>
there's a strategy to tell that this program will not have reference<br=
>
cycles. =C2=A0The ptr inside s can only point to nullptr, because it is onl=
y<br>
set during construction, and never changed. =C2=A0Every time you emplace, y=
ou<br>
are constructing a shared_ptr<s> based on another shared_ptr<s>=
.. =C2=A0The<br>
only shared_ptr<s> that can originally be constructed from has a null=
ptr<br>
in its ptr member. =C2=A0Assuming std::map's emplace member function do=
esn't<br>
do any magic (which it shouldn't, for obvious reasons), all<br>
shared_ptr<s> in the map will point to the same object of type s, who=
<br>
has a null shared_ptr<s>. =C2=A0In other words, no reference cycles, =
found in<br>
a way that avoids the halting problem altogether.<br></blockquote><div><br>=
</div><div>Argh, you're right, but that's a bug in my example, not =
a fundamental point. I think this fixes it:</div><div><br></div><div><div s=
tyle=3D"font-family:arial,sans-serif;font-size:13px">
shared_ptr<s> f(int n) {</div><div style=3D"font-family:arial,sans-se=
rif;font-size:13px">=C2=A0 static map<int, shared_ptr<s>> ptrs =
=3D {{1, {nullptr}}};</div><div style=3D"font-family:arial,sans-serif;font-=
size:13px">
=C2=A0 if (n !=3D 1 && ptrs[n].ptr =3D=3D nullptr) {</div><div styl=
e=3D"font-family:arial,sans-serif;font-size:13px">=C2=A0 =C2=A0 if (n %2 =
=3D=3D 0) {</div><div style=3D"font-family:arial,sans-serif;font-size:13px"=
>=C2=A0 =C2=A0 =C2=A0 ptrs[n].ptr =3D f(n/2);</div>
<div style=3D"font-family:arial,sans-serif;font-size:13px">=C2=A0 =C2=A0 } =
else {</div><div style=3D"font-family:arial,sans-serif;font-size:13px">=C2=
=A0 =C2=A0 =C2=A0 ptrs[n].ptr =3D f(3*n + 1);</div><div style=3D"font-famil=
y:arial,sans-serif;font-size:13px">
=C2=A0 =C2=A0 }</div><div style=3D"font-family:arial,sans-serif;font-size:1=
3px">=C2=A0 }</div><div style=3D"font-family:arial,sans-serif;font-size:13p=
x">=C2=A0 return ptrs[n];</div><div style=3D"font-family:arial,sans-serif;f=
ont-size:13px">}</div>
</div><div><div style=3D"font-family:arial,sans-serif;font-size:13px"><br><=
/div></div><div style=3D"font-family:arial,sans-serif;font-size:13px">The p=
oint of the code is that it produces a reference cycle if and only if the &=
quot;hailstone sequence" starting with the input number contains a cyc=
le other than (4, 2, 1), so determining at compile time if this code can pr=
oduce a reference cycle requires deciding whether there exists a cycle othe=
r than (4, 2, 1) in the hailstone sequence of any number, which would be ta=
ntamount to solving the Collatz conjecture.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex">
<br>
That said, that's not an easy thing to get a compiler to do that, and<b=
r>
it's not worth it. =C2=A0Furthermore, it doesn't solve the problem =
in<br>
general, so this still can't be done.<br>
<div class=3D""><br>
<br>
> > (As a side note, the way the standard deals with the halting prob=
lem at<br>
> > compile time probably wouldn't work here.<br>
><br>
> There's no "probably" about it; this will not work.<br>
<br>
</div>Okay, I should clarify. =C2=A0For using a strategy I hinted below you=
r<br>
response (i.e., doing what template recursion and preprocessor macros do<br=
>
by placing an implementation-defined limit on the maximum depth of the<br>
construct), there is no "probably" about, yes. =C2=A0It *will def=
initely*<br>
work. =C2=A0Limiting the theoretical Turing completeness of the language wi=
th<br>
an analogous implementation-defined limit on recursion depth and looping<br=
>
count/depth would cause this to be solvable in O(n) time, based on the<br>
number of loops or recursive calls total (each loop/recursive function<br>
call could be checked in O(1) time, with a sufficiently large constant<br>
based on the implementation-defined limit).<br>
<br>
The "probably" was a polite way of saying "this is obviously=
<br>
non-solution". =C2=A0At least, I hope it's obvious why.<br>
<br>
Cheers,<br>
Patrick<br>
</blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--001a11c15af22d997204f22ec504--
.
Author: Geoffrey Romer <gromer@google.com>
Date: Tue, 11 Feb 2014 22:10:30 -0800
Raw View
--001a11c300a607663404f22f6e84
Content-Type: text/plain; charset=UTF-8
On Tue, Feb 11, 2014 at 9:01 PM, <hun.nemethpeter@gmail.com> wrote:
>
> On Wednesday, February 12, 2014 1:59:29 AM UTC+1, Geoffrey Romer wrote:
>>
>>
>> On Tue, Feb 11, 2014 at 4:52 PM, Patrick Michael Niedzielski <
>> patrickni...@gmail.com> wrote:
>>
>>
>>>
>>> On mar, 2014-02-11 at 15:58 -0800, hun.nem...@gmail.com wrote:
>>> > I think the real question here is can we detect shared_ptr cycles in
>>> > compile time?
>>>
>>> Not in the general case, because you'd run into the halting problem.
>>>
>> And what about the non-general case?
>
>
>>
>> struct s {
>> shared_ptr<s> ptr;
>> }
>>
>>
> This S struct refers to S as a shared_ptr.
>
> Is it possible to create a safe struct pattern, where cycle is not
> possible? This is smaller goal then a generic one.
>
> So my idea is introducing a new attribute, called [[cycle_free]] or
> [[acyclic]] or whatever that can be attached to a class.
>
> so
>
> [[cycle_free]]
> struct S {
> shared_ptr<S> ptr;
> };
>
> will gives a warning because a cycle is possible with this. And a
> cycle_free class only contains cycle_free ones.
>
First, a meta point: the problem of cycles in reference-counting is very
well-known, and has been studied by a lot of very smart people. That
doesn't mean there are no good solutions left to be found, but it does mean
that you should be very skeptical of any solution that didn't take a lot of
effort to find, or that doesn't contain an identifiable deep insight that
all those smart people could plausibly have missed.
As for this specific proposal, would shared_ptr have a [[cycle_free]]
annotation? I don't believe there's any way to selectively annotate some
instantiations of a template but not others, so you have to pick once and
for all. If it doesn't have that annotation, then [[cycle_free]] types
can't contain shared_ptrs, which makes the annotation trivial and
completely useless. On the other hand, if it does have that annotation,
you've basically destroyed the usefulness of shared_ptr: situations where
you need objects to point to other objects of the same type are just too
commonplace for this to be viable. For example, it's basically the only way
to represent any sort of linked data structure, such as a list, tree, or
graph.
Worse, reference cycles can involve reference types other than shared_ptr;
any kind of ownership relationship can participate in a cycle, so you face
the same dilemma about e.g. whether to annotate unique_ptr. You've also
glossed over how this interacts with separate compilation: when you compile
something like
struct X {
shared_ptr<Y> y;
Z* z;
};
Y and Z may be incomplete types, in which case the compiler has no way of
knowing if they're annotated or not. That might be solvable, but only by
making [[cycle_free]] even more restrictive and useless.
--
>
> ---
> 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/.
--001a11c300a607663404f22f6e84
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Feb 11, 2014 at 9:01 PM, <span dir=3D"ltr"><<a href=3D"mailto:h=
un.nemethpeter@gmail.com" target=3D"_blank">hun.nemethpeter@gmail.com</a>&g=
t;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr"><br>On Wednesday, February 12, 2014 1:59:=
29 AM UTC+1, Geoffrey Romer wrote:<blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20=
4,204,204);border-left-style:solid;padding-left:1ex">
<div dir=3D"ltr"><div><br><div class=3D"gmail_quote">On Tue, Feb 11, 2014 a=
t 4:52 PM, Patrick Michael Niedzielski <span dir=3D"ltr"><<a>patrickni..=
..@gmail.com</a>></span> wrote:<div class=3D""><br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div><br>
<br>
On mar, 2014-02-11 at 15:58 -0800, <a>hun.nem...@gmail.com</a> wrote:<br>
> I think the real question here is can we detect shared_ptr cycles in<b=
r>
> compile time?<br>
<br>
</div>Not in the general case, because you'd run into the halting probl=
em.<br></blockquote></div></div></div></div></blockquote><div>And what abou=
t the non-general case?<br>=C2=A0</div><div class=3D""><blockquote class=3D=
"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;borde=
r-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir=3D"ltr"><div><div class=3D"gmail_quote"><br><div><div>struct s {</=
div><div>=C2=A0 shared_ptr<s> ptr;</div><div>}</div><div><br></div></=
div></div></div></div></blockquote><div>=C2=A0</div></div>This S struct ref=
ers to S as a shared_ptr. <br>
<br>Is it possible to create a safe struct pattern, where cycle is not poss=
ible? This is smaller goal then a generic one.<br><br>So my idea is introdu=
cing a new attribute, called [[cycle_free]] or [[acyclic]] or whatever that=
can be attached to a class.<br>
<br>so<br><br><div style=3D"background-color:rgb(250,250,250);border:1px so=
lid rgb(187,187,187);word-wrap:break-word"><code><div><span style=3D"color:=
rgb(102,102,0)">[[</span><span style>cycle_free</span><span style=3D"color:=
rgb(102,102,0)">]]</span><span style><br>
</span><span style=3D"color:rgb(0,0,136)">struct</span><span style> S </spa=
n><span style=3D"color:rgb(102,102,0)">{</span><span style><br>=C2=A0 share=
d_ptr</span><span style=3D"color:rgb(102,102,0)"><</span><span style>S</=
span><span style=3D"color:rgb(102,102,0)">></span><span style> ptr</span=
><span style=3D"color:rgb(102,102,0)">;</span><span style><br>
</span><span style=3D"color:rgb(102,102,0)">};</span><span style><br></span=
></div></code></div><br>will gives a warning because a cycle is possible wi=
th this. And a cycle_free class only contains cycle_free ones.</div></block=
quote>
<div><br></div><div>First, a meta point: the problem of cycles in reference=
-counting is very well-known, and has been studied by a lot of very smart p=
eople. That doesn't mean there are no good solutions left to be found, =
but it does mean that you should be very skeptical of any solution that did=
n't take a lot of effort to find, or that doesn't contain an identi=
fiable deep insight that all those smart people could plausibly have missed=
..</div>
<div><br></div><div>As for this specific proposal, would shared_ptr have a =
[[cycle_free]] annotation? I don't believe there's any way to selec=
tively annotate some instantiations of a template but not others, so you ha=
ve to pick once and for all. If it doesn't have that annotation, then [=
[cycle_free]] types can't contain shared_ptrs, which makes the annotati=
on trivial and completely useless. On the other hand, if it does have that =
annotation, you've basically destroyed the usefulness of shared_ptr: si=
tuations where you need objects to point to other objects of the same type =
are just too commonplace for this to be viable. For example, it's basic=
ally the only way to represent any sort of linked data structure, such as a=
list, tree, or graph.</div>
<div><br></div><div>Worse, reference cycles can involve reference types oth=
er than shared_ptr; any kind of ownership relationship can participate in a=
cycle, so you face the same dilemma about e.g. whether to annotate unique_=
ptr. You've also glossed over how this interacts with separate compilat=
ion: when you compile something like</div>
<div><br></div><div>struct X {</div><div>=C2=A0 shared_ptr<Y> y;</div=
><div>=C2=A0 Z* z;</div><div>};</div><div><br></div><div>Y and Z may be inc=
omplete types, in which case the compiler has no way of knowing if they'=
;re annotated or not. That might be solvable, but only by making [[cycle_fr=
ee]] even more restrictive and useless.</div>
<div><br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,=
204);border-left-style:solid;padding-left:1ex"><div dir=3D"ltr"></div><div =
class=3D"">
<div class=3D"h5">
<p></p>
-- <br>
=C2=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--001a11c300a607663404f22f6e84--
.
Author: Andrew Tomazos <andrewtomazos@gmail.com>
Date: Tue, 11 Feb 2014 22:54:06 -0800 (PST)
Raw View
------=_Part_1625_16303766.1392188046714
Content-Type: text/plain; charset=UTF-8
On Wednesday, February 12, 2014 7:10:30 AM UTC+1, Geoffrey Romer wrote:
>
> First, a meta point: the problem of cycles in reference-counting is very
> well-known, and has been studied by a lot of very smart people. That
> doesn't mean there are no good solutions left to be found, but it does mean
> that you should be very skeptical of any solution that didn't take a lot of
> effort to find, or that doesn't contain an identifiable deep insight that
> all those smart people could plausibly have missed.
>
Actually, contrary to popular belief, and quite fascinatingly, reference
counting garbage collection algorithms can breaking cycles quite easily.
See this paper from our friends at IBM:
Concurrent Cycle Collection in Reference Counted Systems, David F. Bacon
and V.T. Rajan
https://www.cs.purdue.edu/homes/hosking/690M/Bacon01Concurrent.pdf
In fact there are some that claim reference counting with such
cycle-breaking is more performant than the trace / mark-and-sweep style
algorithms - and there are some major VMs that are considering changing to
it.
The problem for our purposes is, like tracing, these cycle-breaking
reference counted algorithms need access to the full graph. shared_ptr
doesn't give us the outbound-side of edges.
As for, can we detect potential cycles at compile-time? - who cares... We
want to be able to have cycles, we just want them to be collected.
--
---
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/.
------=_Part_1625_16303766.1392188046714
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Wednesday, February 12, 2014 7:10:30 AM UTC+1, Geoffrey=
Romer wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">=
<div><div class=3D"gmail_quote"><div>First, a meta point: the problem of cy=
cles in reference-counting is very well-known, and has been studied by a lo=
t of very smart people. That doesn't mean there are no good solutions left =
to be found, but it does mean that you should be very skeptical of any solu=
tion that didn't take a lot of effort to find, or that doesn't contain an i=
dentifiable deep insight that all those smart people could plausibly have m=
issed.</div></div></div></div></blockquote><div> </div><div>Actually, =
contrary to popular belief, and quite fascinatingly, reference counting gar=
bage collection algorithms can breaking cycles quite easily. See this=
paper from our friends at IBM:</div><div><br></div><div><div> =
Concurrent Cycle Collection in Reference Counted Systems, David F. Bacon an=
d V.T. Rajan</div></div><div> https://www.cs.purdue.edu/homes/h=
osking/690M/Bacon01Concurrent.pdf<br></div><div><br></div><div>In fact ther=
e are some that claim reference counting with such cycle-breaking is more p=
erformant than the trace / mark-and-sweep style algorithms - and there are =
some major VMs that are considering changing to it.</div><div><br></div><di=
v>The problem for our purposes is, like tracing, these cycle-breaking refer=
ence counted algorithms need access to the full graph. shared_ptr doe=
sn't give us the outbound-side of edges.</div><div><br></div><div>As for, c=
an we detect potential cycles at compile-time? - who cares... We want=
to be able to have cycles, we just want them to be collected.</div><div><b=
r></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_1625_16303766.1392188046714--
.
Author: hun.nemethpeter@gmail.com
Date: Wed, 12 Feb 2014 00:09:08 -0800 (PST)
Raw View
------=_Part_84_30984730.1392192548717
Content-Type: text/plain; charset=UTF-8
>
>
>
> As for this specific proposal, would shared_ptr have a [[cycle_free]]
> annotation?
>
Good question. Maybe we should mark it as a [[link]] that links a
[[cycle_free]] struct.
> I don't believe there's any way to selectively annotate some
> instantiations of a template but not others, so you have to pick once and
> for all. If it doesn't have that annotation, then [[cycle_free]] types
> can't contain shared_ptrs, which makes the annotation trivial and
> completely useless. On the other hand, if it does have that annotation,
> you've basically destroyed the usefulness of shared_ptr: situations where
> you need objects to point to other objects of the same type are just too
> commonplace for this to be viable. For example, it's basically the only way
> to represent any sort of linked data structure, such as a list, tree, or
> graph.
>
I don't think so. For example a Html class that has a Header and Body, and
Body has h1, ul and other elements... I think cycle is not possible in an
Html document. Do we really need so generic list, tree graph data
structures these days? They are basically list<T>, TreeNode<T>,
GraphNode<T> nowadays and we should just state that GraphNode<T> can't link
a GraphNode<T>.
>
> Worse, reference cycles can involve reference types other than shared_ptr;
> any kind of ownership relationship can participate in a cycle, so you face
> the same dilemma about e.g. whether to annotate unique_ptr. You've also
> glossed over how this interacts with separate compilation: when you compile
> something like
>
> struct X {
> shared_ptr<Y> y;
> Z* z;
> };
>
> Y and Z may be incomplete types, in which case the compiler has no way of
> knowing if they're annotated or not. That might be solvable, but only by
> making [[cycle_free]] even more restrictive and useless.
>
> if
Y is struct Y { int a; };
and
Z is struct Z { char* a };
then this struct hierarchy is safe, isn't it? If this is safe we should
extend this pattern to maximum level.
This check can be performed after the compilation. In this case a central
data file is generated, where every [[cycle_free]] and [[link]] is
collected.
This approach is start from a safe core pattern where cycle is not possible
and should be carefully extended.
--
---
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/.
------=_Part_84_30984730.1392192548717
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr"><div><div class=3D"gmail_quote"><br><div><br></div><div>As for this spe=
cific proposal, would shared_ptr have a [[cycle_free]] annotation? </div></=
div></div></div></blockquote><div>Good question. Maybe we should mark it as=
a [[link]] that links a [[cycle_free]] struct.<br> </div><blockquote =
class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1p=
x #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_=
quote"><div>I don't believe there's any way to selectively annotate some in=
stantiations of a template but not others, so you have to pick once and for=
all. If it doesn't have that annotation, then [[cycle_free]] types can't c=
ontain shared_ptrs, which makes the annotation trivial and completely usele=
ss. On the other hand, if it does have that annotation, you've basically de=
stroyed the usefulness of shared_ptr: situations where you need objects to =
point to other objects of the same type are just too commonplace for this t=
o be viable. For example, it's basically the only way to represent any sort=
of linked data structure, such as a list, tree, or graph.</div></div></div=
></div></blockquote><div></div><div>I don't think so. For example a Html cl=
ass that has a Header and Body, and Body has h1, ul and other elements... I=
think cycle is not possible in an Html document. Do we really need so gene=
ric list, tree graph data structures these days? They are basically list<=
;T>, TreeNode<T>, GraphNode<T> nowadays and we should just s=
tate that GraphNode<T> can't link a GraphNode<T>.<br> </di=
v><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;b=
order-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div c=
lass=3D"gmail_quote">
<div><br></div><div>Worse, reference cycles can involve reference types oth=
er than shared_ptr; any kind of ownership relationship can participate in a=
cycle, so you face the same dilemma about e.g. whether to annotate unique_=
ptr. You've also glossed over how this interacts with separate compilation:=
when you compile something like</div>
<div><br></div><div>struct X {</div><div> shared_ptr<Y> y;</div=
><div> Z* z;</div><div>};</div><div><br></div><div>Y and Z may be inc=
omplete types, in which case the compiler has no way of knowing if they're =
annotated or not. That might be solvable, but only by making [[cycle_free]]=
even more restrictive and useless.</div><br></div></div></div></blockquote=
><div>if <br>Y is struct Y { int a; };<br>and<br>Z is struct Z { char* a };=
<br>then this struct hierarchy is safe, isn't it? If this is safe we should=
extend this pattern to maximum level.<br><br>This check can be performed a=
fter the compilation. In this case a central data file is generated, where =
every [[cycle_free]] and [[link]] is collected.<br><br>This approach is sta=
rt from a safe core pattern where cycle is not possible and should be caref=
ully extended.<br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_84_30984730.1392192548717--
.
Author: Geoffrey Romer <gromer@google.com>
Date: Wed, 12 Feb 2014 10:52:10 -0800
Raw View
--001a1132f03cff67dc04f23a11e7
Content-Type: text/plain; charset=UTF-8
On Wed, Feb 12, 2014 at 12:09 AM, <hun.nemethpeter@gmail.com> wrote:
>
>>
>> As for this specific proposal, would shared_ptr have a [[cycle_free]]
>> annotation?
>>
> Good question. Maybe we should mark it as a [[link]] that links a
> [[cycle_free]] struct.
>
>
>> I don't believe there's any way to selectively annotate some
>> instantiations of a template but not others, so you have to pick once and
>> for all. If it doesn't have that annotation, then [[cycle_free]] types
>> can't contain shared_ptrs, which makes the annotation trivial and
>> completely useless. On the other hand, if it does have that annotation,
>> you've basically destroyed the usefulness of shared_ptr: situations where
>> you need objects to point to other objects of the same type are just too
>> commonplace for this to be viable. For example, it's basically the only way
>> to represent any sort of linked data structure, such as a list, tree, or
>> graph.
>>
> I don't think so. For example a Html class that has a Header and Body, and
> Body has h1, ul and other elements... I think cycle is not possible in an
> Html document.
>
A cycle is not possible in an HTML document, but that's because the nodes
form a tree structure, and trees have no cycles. This is enforced by the
grammatical structure of HTML as a context-free language, not by any kind
of type system requirement on nodes. What you're proposing is different:
you want the node *types* to form a strict hierarchy, with nodes not
permitted to link to other nodes whose types have the same or a higher
level. HTML definitely does not have that property; for example, you can
have a <ul> that contains <li> nodes, that themselves contain <ul> nodes.
> Do we really need so generic list, tree graph data structures these days?
> They are basically list<T>, TreeNode<T>, GraphNode<T> nowadays and we
> should just state that GraphNode<T> can't link a GraphNode<T>.
>
How on earth do you represent a graph of more than one node using a
GraphNode<T> type that can't link to other GraphNode<T>s?
More fundamentally, the fact is that some graphs have cycles. Either your
node type can represent those graphs, and so can potentially contain
reference cycles, or it can't represent those graphs, and so isn't a
general graph node type. I don't see how you can square that circle.
>
>
>>
>> Worse, reference cycles can involve reference types other than
>> shared_ptr; any kind of ownership relationship can participate in a cycle,
>> so you face the same dilemma about e.g. whether to annotate unique_ptr.
>> You've also glossed over how this interacts with separate compilation: when
>> you compile something like
>>
>> struct X {
>> shared_ptr<Y> y;
>> Z* z;
>> };
>>
>> Y and Z may be incomplete types, in which case the compiler has no way of
>> knowing if they're annotated or not. That might be solvable, but only by
>> making [[cycle_free]] even more restrictive and useless.
>>
>> if
> Y is struct Y { int a; };
> and
> Z is struct Z { char* a };
> then this struct hierarchy is safe, isn't it? If this is safe we should
> extend this pattern to maximum level.
>
> This check can be performed after the compilation. In this case a central
> data file is generated, where every [[cycle_free]] and [[link]] is
> collected.
>
> This approach is start from a safe core pattern where cycle is not
> possible and should be carefully extended.
>
This pattern is safe, but extremely narrow, and fundamentally cannot be
extended to support general computation in a useful way.
> --
>
> ---
> 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/.
--001a1132f03cff67dc04f23a11e7
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Wed, Feb 12, 2014 at 12:09 AM, <span dir=3D"ltr"><<a href=3D"mailto:=
hun.nemethpeter@gmail.com" target=3D"_blank">hun.nemethpeter@gmail.com</a>&=
gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D""><blockquote=
class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px =
#ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><div class=3D"gmail_quote"><br><div><br></div><div>As=
for this specific proposal, would shared_ptr have a [[cycle_free]] annotat=
ion? </div></div></div></div></blockquote></div><div>Good question. Maybe w=
e should mark it as a [[link]] that links a [[cycle_free]] struct.<br>
=C2=A0</div><div class=3D""><blockquote class=3D"gmail_quote" style=3D"marg=
in:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div di=
r=3D"ltr"><div><div class=3D"gmail_quote"><div>I don't believe there=
9;s any way to selectively annotate some instantiations of a template but n=
ot others, so you have to pick once and for all. If it doesn't have tha=
t annotation, then [[cycle_free]] types can't contain shared_ptrs, whic=
h makes the annotation trivial and completely useless. On the other hand, i=
f it does have that annotation, you've basically destroyed the usefulne=
ss of shared_ptr: situations where you need objects to point to other objec=
ts of the same type are just too commonplace for this to be viable. For exa=
mple, it's basically the only way to represent any sort of linked data =
structure, such as a list, tree, or graph.</div>
</div></div></div></blockquote><div></div></div><div>I don't think so. =
For example a Html class that has a Header and Body, and Body has h1, ul an=
d other elements... I think cycle is not possible in an Html document. </di=
v>
</div></blockquote><div><br></div><div>A cycle is not possible in an HTML d=
ocument, but that's because the nodes form a tree structure, and trees =
have no cycles. This is enforced by the grammatical structure of HTML as a =
context-free language, not by any kind of type system requirement on nodes.=
What you're proposing is different: you want the node *types* to form =
a strict hierarchy, with nodes not permitted to link to other nodes whose t=
ypes have the same or a higher level. HTML definitely does not have that pr=
operty; for example, you can have a <ul> that contains <li> nod=
es, that themselves contain <ul> nodes.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Do we=
really need so generic list, tree graph data structures these days? They a=
re basically list<T>, TreeNode<T>, GraphNode<T> nowadays =
and we should just state that GraphNode<T> can't link a GraphNode=
<T>.<br>
</div></div></blockquote><div><br></div><div>How on earth do you represent =
a graph of more than one node using a GraphNode<T> type that can'=
t link to other GraphNode<T>s?</div><div><br></div><div>More fundamen=
tally, the fact is that some graphs have cycles. Either your node type can =
represent those graphs, and so can potentially contain reference cycles, or=
it can't represent those graphs, and so isn't a general graph node=
type. I don't see how you can square that circle.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>=C2=
=A0</div><div class=3D""><blockquote class=3D"gmail_quote" style=3D"margin:=
0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><div class=3D"gmail_quote">
<div><br></div><div>Worse, reference cycles can involve reference types oth=
er than shared_ptr; any kind of ownership relationship can participate in a=
cycle, so you face the same dilemma about e.g. whether to annotate unique_=
ptr. You've also glossed over how this interacts with separate compilat=
ion: when you compile something like</div>
<div><br></div><div>struct X {</div><div>=C2=A0 shared_ptr<Y> y;</div=
><div>=C2=A0 Z* z;</div><div>};</div><div><br></div><div>Y and Z may be inc=
omplete types, in which case the compiler has no way of knowing if they'=
;re annotated or not. That might be solvable, but only by making [[cycle_fr=
ee]] even more restrictive and useless.</div>
<br></div></div></div></blockquote></div><div>if <br>Y is struct Y { int a;=
};<br>and<br>Z is struct Z { char* a };<br>then this struct hierarchy is s=
afe, isn't it? If this is safe we should extend this pattern to maximum=
level.<br>
<br>This check can be performed after the compilation. In this case a centr=
al data file is generated, where every [[cycle_free]] and [[link]] is colle=
cted.=C2=A0</div></div></blockquote><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><br>This approach is start from a safe core pattern w=
here cycle is not possible and should be carefully extended.<br></div></div=
></blockquote><div><br></div><div>This pattern is safe, but extremely narro=
w, and fundamentally cannot be extended to support general computation in a=
useful way.</div>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div></div></div><div class=
=3D"HOEnZb"><div class=3D"h5">
<p></p>
-- <br>
=C2=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--001a1132f03cff67dc04f23a11e7--
.
Author: hun.nemethpeter@gmail.com
Date: Wed, 12 Feb 2014 12:02:38 -0800 (PST)
Raw View
------=_Part_6550_20903190.1392235359013
Content-Type: text/plain; charset=UTF-8
>
>
>
> A cycle is not possible in an HTML document, but that's because the nodes
> form a tree structure, and trees have no cycles. This is enforced by the
> grammatical structure of HTML as a context-free language, not by any kind
> of type system requirement on nodes. What you're proposing is different:
> you want the node *types* to form a strict hierarchy, with nodes not
> permitted to link to other nodes whose types have the same or a higher
> level. HTML definitely does not have that property; for example, you can
> have a <ul> that contains <li> nodes, that themselves contain <ul> nodes.
>
Yep.. You are right, this approach looks like a no-go. I have no idea now
how to enforce tree like, no-cycle structure on type level but it would be
useful.
>
>
>> Do we really need so generic list, tree graph data structures these days?
>> They are basically list<T>, TreeNode<T>, GraphNode<T> nowadays and we
>> should just state that GraphNode<T> can't link a GraphNode<T>.
>>
>
> How on earth do you represent a graph of more than one node using a
> GraphNode<T> type that can't link to other GraphNode<T>s?
>
> More fundamentally, the fact is that some graphs have cycles. Either your
> node type can represent those graphs, and so can potentially contain
> reference cycles, or it can't represent those graphs, and so isn't a
> general graph node type. I don't see how you can square that circle.
>
Looks like just a type attribute is not good enough here.
But we need a "value hierarchy level" thing. So a value can accept only new
stand-alone, or lower-level values. That result in a tree like structure.
But I don't know how to use it in a compile-time check.
>
>>
>>
>>>
>>> Worse, reference cycles can involve reference types other than
>>> shared_ptr; any kind of ownership relationship can participate in a cycle,
>>> so you face the same dilemma about e.g. whether to annotate unique_ptr.
>>> You've also glossed over how this interacts with separate compilation: when
>>> you compile something like
>>>
>>> struct X {
>>> shared_ptr<Y> y;
>>> Z* z;
>>> };
>>>
>>> Y and Z may be incomplete types, in which case the compiler has no way
>>> of knowing if they're annotated or not. That might be solvable, but only by
>>> making [[cycle_free]] even more restrictive and useless.
>>>
>>> if
>> Y is struct Y { int a; };
>> and
>> Z is struct Z { char* a };
>> then this struct hierarchy is safe, isn't it? If this is safe we should
>> extend this pattern to maximum level.
>>
>> This check can be performed after the compilation. In this case a central
>> data file is generated, where every [[cycle_free]] and [[link]] is
>> collected.
>>
>
>> This approach is start from a safe core pattern where cycle is not
>> possible and should be carefully extended.
>>
>
> This pattern is safe, but extremely narrow, and fundamentally cannot be
> extended to support general computation in a useful way.
>
I agree. I have no idea how to extend this pattern now.
--
---
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/.
------=_Part_6550_20903190.1392235359013
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr"><div><div class=3D"gmail_quote"><br><div><br></div><div>A cycle is not =
possible in an HTML document, but that's because the nodes form a tree stru=
cture, and trees have no cycles. This is enforced by the grammatical struct=
ure of HTML as a context-free language, not by any kind of type system requ=
irement on nodes. What you're proposing is different: you want the node *ty=
pes* to form a strict hierarchy, with nodes not permitted to link to other =
nodes whose types have the same or a higher level. HTML definitely does not=
have that property; for example, you can have a <ul> that contains &=
lt;li> nodes, that themselves contain <ul> nodes.</div></div></div=
></div></blockquote><div>Yep.. You are right, this approach looks like a no=
-go. I have no idea now how to enforce tree like, no-cycle structure on typ=
e level but it would be useful.<br> </div><blockquote class=3D"gmail_q=
uote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;pad=
ding-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_quote">
<div> </div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Do we=
really need so generic list, tree graph data structures these days? They a=
re basically list<T>, TreeNode<T>, GraphNode<T> nowadays =
and we should just state that GraphNode<T> can't link a GraphNode<=
T>.<br>
</div></div></blockquote><div><br></div><div>How on earth do you represent =
a graph of more than one node using a GraphNode<T> type that can't li=
nk to other GraphNode<T>s?</div><div><br></div><div>More fundamentall=
y, the fact is that some graphs have cycles. Either your node type can repr=
esent those graphs, and so can potentially contain reference cycles, or it =
can't represent those graphs, and so isn't a general graph node type. I don=
't see how you can square that circle.</div></div></div></div></blockquote>=
<div>Looks like just a type attribute is not good enough here.<br><br>But w=
e need a "value hierarchy level" thing. So a value can accept only new stan=
d-alone, or lower-level values. That result in a tree like structure. But I=
don't know how to use it in a compile-time check.<br><br></div><blockquote=
class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1=
px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail=
_quote">
<div> </div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div> =
;</div><div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left=
:0.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><div class=3D"gmail_quote">
<div><br></div><div>Worse, reference cycles can involve reference types oth=
er than shared_ptr; any kind of ownership relationship can participate in a=
cycle, so you face the same dilemma about e.g. whether to annotate unique_=
ptr. You've also glossed over how this interacts with separate compilation:=
when you compile something like</div>
<div><br></div><div>struct X {</div><div> shared_ptr<Y> y;</div=
><div> Z* z;</div><div>};</div><div><br></div><div>Y and Z may be inc=
omplete types, in which case the compiler has no way of knowing if they're =
annotated or not. That might be solvable, but only by making [[cycle_free]]=
even more restrictive and useless.</div>
<br></div></div></div></blockquote></div><div>if <br>Y is struct Y { int a;=
};<br>and<br>Z is struct Z { char* a };<br>then this struct hierarchy is s=
afe, isn't it? If this is safe we should extend this pattern to maximum lev=
el.<br>
<br>This check can be performed after the compilation. In this case a centr=
al data file is generated, where every [[cycle_free]] and [[link]] is colle=
cted. </div></div></blockquote><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><br>This approach is start from a safe core pattern w=
here cycle is not possible and should be carefully extended.<br></div></div=
></blockquote><div><br></div><div>This pattern is safe, but extremely narro=
w, and fundamentally cannot be extended to support general computation in a=
useful way.</div></div></div></div></blockquote><div>I agree. I have no id=
ea how to extend this pattern now. <br></div><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_6550_20903190.1392235359013--
.
Author: inkwizytoryankes@gmail.com
Date: Thu, 13 Feb 2014 12:46:57 -0800 (PST)
Raw View
------=_Part_47_16314384.1392324417589
Content-Type: text/plain; charset=UTF-8
Its "easy" :> const variables cant create cycles. Its because to create
cycle you need modify existing pointer to point new object (constructor is
only exception there). This have big draw back, modify data require coping
lot of data.
I once created naive Lisp implementation, everything work as excepted until
I try add variables. This break constnes of data structure and introduce
cycles again because variables are indented do point any data.
If noconst data stored in that structure cant reference elements of that
structure its still impossible possible to create cyclic data.
On Wednesday, February 12, 2014 9:02:38 PM UTC+1, hun.nem...@gmail.com
wrote:
>
>
>>
>> A cycle is not possible in an HTML document, but that's because the nodes
>> form a tree structure, and trees have no cycles. This is enforced by the
>> grammatical structure of HTML as a context-free language, not by any kind
>> of type system requirement on nodes. What you're proposing is different:
>> you want the node *types* to form a strict hierarchy, with nodes not
>> permitted to link to other nodes whose types have the same or a higher
>> level. HTML definitely does not have that property; for example, you can
>> have a <ul> that contains <li> nodes, that themselves contain <ul> nodes.
>>
> Yep.. You are right, this approach looks like a no-go. I have no idea now
> how to enforce tree like, no-cycle structure on type level but it would be
> useful.
>
--
---
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/.
------=_Part_47_16314384.1392324417589
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Its "easy" :> const variables cant create cycles. Its b=
ecause to create cycle you need modify existing pointer to point new object=
(constructor is only exception there). This have big draw back, modify dat=
a require coping lot of data.<br>I once created naive Lisp implementation, =
everything work as excepted until I try add variables. This break constnes =
of data structure and introduce cycles again because variables are indented=
do point any data.<br>If noconst data stored in that structure cant refere=
nce elements of that structure its still impossible possible to create cycl=
ic data.<br><br>On Wednesday, February 12, 2014 9:02:38 PM UTC+1, hun.nem..=
..@gmail.com wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;marg=
in-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"=
ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div cla=
ss=3D"gmail_quote"><br><div><br></div><div>A cycle is not possible in an HT=
ML document, but that's because the nodes form a tree structure, and trees =
have no cycles. This is enforced by the grammatical structure of HTML as a =
context-free language, not by any kind of type system requirement on nodes.=
What you're proposing is different: you want the node *types* to form a st=
rict hierarchy, with nodes not permitted to link to other nodes whose types=
have the same or a higher level. HTML definitely does not have that proper=
ty; for example, you can have a <ul> that contains <li> nodes, =
that themselves contain <ul> nodes.</div></div></div></div></blockquo=
te><div>Yep.. You are right, this approach looks like a no-go. I have no id=
ea now how to enforce tree like, no-cycle structure on type level but it wo=
uld be useful. <br></div></div></blockquote></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_47_16314384.1392324417589--
.
Author: Andrew Tomazos <andrewtomazos@gmail.com>
Date: Fri, 14 Feb 2014 06:07:00 -0800 (PST)
Raw View
------=_Part_608_3221953.1392386820820
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, February 12, 2014 6:02:32 AM UTC+1, Thiago Macieira wrote:
>
> Em ter 11 fev 2014, =C3=A0s 20:36:57, Andrew Tomazos escreveu:=20
> > It should be clear that such a system as a pure library solution is=20
> > extremely awkward to use and unsafe. Under the proposal, this graph=20
> > tracking is instrumented automatically by the compiler. Given the=20
> > extremely high demand for this feature, it should be clear that a core=
=20
> > language addition is warranted.=20
>
> Can it wait for compile-time reflection support and simply use that to=20
> detect=20
> which members are collecting pointers?=20
>
Sorry Thiago, I wasn't ignoring your good question, I just needed some time=
=20
to think about it.
If we imagine a pure library solution in which there are two classes=20
provided:
std::collected_type
std::collecting_ptr<T>
Deriving from std::collected_type marks the type as a collected type.=20
std::collecting_ptr<T> is a collecting pointer where T must be a collected=
=20
type.
First, I think that even if we could implement these, the interface may be=
=20
unacceptably inferior to a core language feature. For example,=20
"gc-unaware" raw pointers and references to collected types are still=20
possible under this scheme, and I think we would like this ill-formed for=
=20
safety. Likewise, one could multiply inherit from a collected type and a=
=20
non-collected type.
Putting that aside, how would we implement these classes with reflection?=
=20
In the constructor of std::collected_type we don't know what the (dynamic)=
=20
derived type of the complete object we are in is, so even if we had a=20
reflection facility that allowed us to iterate data members, we can't get a=
=20
handle on the complete type. I think the instrumentation needs to take=20
place at the kind of level in the implementation that works with generating=
=20
vtables and similar, and I don't think any of the (even in the abstract)=20
reflection mechanisms are planned to be so powerful.
--=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_608_3221953.1392386820820
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Wednesday, February 12, 2014 6:02:32 AM UTC+1, Thiago M=
acieira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Em ter 11 fev 20=
14, =C3=A0s 20:36:57, Andrew Tomazos escreveu:
<br>> It should be clear that such a system as a pure library solution i=
s=20
<br>> extremely awkward to use and unsafe. Under the proposal, thi=
s graph=20
<br>> tracking is instrumented automatically by the compiler. Give=
n the=20
<br>> extremely high demand for this feature, it should be clear that a =
core=20
<br>> language addition is warranted.=20
<br>
<br>Can it wait for compile-time reflection support and simply use that to =
detect=20
<br>which members are collecting pointers?
<br>
</blockquote><div><br></div><div>Sorry Thiago, I wasn't ignoring your good =
question, I just needed some time to think about it.</div><div><br></div><d=
iv>If we imagine a pure library solution in which there are two classes pro=
vided:</div><div><br></div><div> std::collected_type</di=
v><div> std::collecting_ptr<T></div><div><br></div=
><div>Deriving from std::collected_type marks the type as a collected type.=
std::collecting_ptr<T> is a collecting pointer where T must be=
a collected type.</div><div><br></div><div>First, I think that even if we =
could implement these, the interface may be unacceptably inferior to a core=
language feature. For example, "gc-unaware" raw pointers and referen=
ces to collected types are still possible under this scheme, and I think we=
would like this ill-formed for safety. Likewise, one could multiply =
inherit from a collected type and a non-collected type.</div><div><br></div=
><div>Putting that aside, how would we implement these classes with reflect=
ion? In the constructor of std::collected_type we don't know what the=
(dynamic) derived type of the complete object we are in is, so even if we =
had a reflection facility that allowed us to iterate data members, we can't=
get a handle on the complete type. I think the instrumentation needs=
to take place at the kind of level in the implementation that works with g=
enerating vtables and similar, and I don't think any of the (even in the ab=
stract) reflection mechanisms are planned to be so powerful.</div><div><br>=
</div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_608_3221953.1392386820820--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Fri, 14 Feb 2014 09:27:51 -0800
Raw View
Em sex 14 fev 2014, =E0s 06:07:00, Andrew Tomazos escreveu:
> In the constructor of std::collected_type we don't know what the (dynami=
c)=20
> derived type of the complete object we are in is, so even if we had a
> reflection facility that allowed us to iterate data members, we can't get=
a
> handle on the complete type. I think the instrumentation needs to take
> place at the kind of level in the implementation that works with generati=
ng
> vtables and similar, and I don't think any of the (even in the abstract)
> reflection mechanisms are planned to be so powerful.
Is it necessary at the time of the constructor? Or is it only necessary whe=
n=20
something begins collecting the type?
If I create a collectable type on the stack, it can't get be GC'ed.
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--=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/.
.
Author: Philipp Maximilian Stephani <p.stephani2@gmail.com>
Date: Sat, 15 Feb 2014 16:38:39 +0000
Raw View
--089e0122aa5c0ad2c304f2748e08
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Another bad thing about reference counting is that it forces atomic
operations, which can kill performance in multi-threaded applications. The
problem gets worse the more cores per machine we get.
The problem I see is that garbage collection in managed languages can only
get better, and simplistic attempts like reference counting can only get
worse. I don't have data, but I'd expect typical Java programs to
outperform equivalent reference-counted C++ programs even today or in the
near future.
On Fri Feb 14 2014 at 18:27:56, Thiago Macieira <thiago@macieira.org> wrote=
:
> Em sex 14 fev 2014, =C3=A0s 06:07:00, Andrew Tomazos escreveu:
> > In the constructor of std::collected_type we don't know what the
> (dynamic)
> > derived type of the complete object we are in is, so even if we had a
> > reflection facility that allowed us to iterate data members, we can't
> get a
> > handle on the complete type. I think the instrumentation needs to take
> > place at the kind of level in the implementation that works with
> generating
> > vtables and similar, and I don't think any of the (even in the abstract=
)
> > reflection mechanisms are planned to be so powerful.
>
> Is it necessary at the time of the constructor? Or is it only necessary
> when
> something begins collecting the type?
>
> If I create a collectable type on the stack, it can't get be GC'ed.
>
> --
> Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
> Software Architect - Intel Open Source Technology Center
> PGP/GPG: 0x6EF45358; fingerprint:
> E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
>
> --
>
> ---
> 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/.
>
--=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/.
--089e0122aa5c0ad2c304f2748e08
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Another bad thing about reference counting is that it forces atomic operati=
ons, which can kill performance in multi-threaded applications. The problem=
gets worse the more cores per machine we get.<br><div>The problem I see is=
that garbage collection in managed languages can only get better, and simp=
listic attempts like reference counting can only get worse. I don't hav=
e data, but I'd expect typical Java programs to outperform equivalent r=
eference-counted C++ programs even today or in the near future.</div>
<br><div>On Fri Feb 14 2014 at 18:27:56, Thiago Macieira <<a href=3D"mai=
lto:thiago@macieira.org">thiago@macieira.org</a>> wrote:</div><blockquot=
e class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc sol=
id;padding-left:1ex">
Em sex 14 fev 2014, =C3=A0s 06:07:00, Andrew Tomazos escreveu:<br>
> =C2=A0In the constructor of std::collected_type we don't know what=
the (dynamic)<br>
> derived type of the complete object we are in is, so even if we had a<=
br>
> reflection facility that allowed us to iterate data members, we can=
9;t get a<br>
> handle on the complete type. =C2=A0I think the instrumentation needs t=
o take<br>
> place at the kind of level in the implementation that works with gener=
ating<br>
> vtables and similar, and I don't think any of the (even in the abs=
tract)<br>
> reflection mechanisms are planned to be so powerful.<br>
<br>
Is it necessary at the time of the constructor? Or is it only necessary whe=
n<br>
something begins collecting the type?<br>
<br>
If I create a collectable type on the stack, it can't get be GC'ed.=
<br>
<br>
--<br>
Thiago Macieira - thiago (AT) <a href=3D"http://macieira.info" target=3D"_b=
lank">macieira.info</a> - thiago (AT) <a href=3D"http://kde.org" target=3D"=
_blank">kde.org</a><br>
=C2=A0 =C2=A0Software Architect - Intel Open Source Technology Center<br>
=C2=A0 =C2=A0 =C2=A0 PGP/GPG: 0x6EF45358; fingerprint:<br>
=C2=A0 =C2=A0 =C2=A0 E067 918B B660 DBD1 105C =C2=A0966C 33F5 F005 6EF4 535=
8<br>
<br>
--<br>
<br>
---<br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@<u></u>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/<u></u>isocpp.=
org/group/std-<u></u>proposals/</a>.<br>
</blockquote>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--089e0122aa5c0ad2c304f2748e08--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Sat, 15 Feb 2014 09:51:38 -0800
Raw View
Em s=E1b 15 fev 2014, =E0s 16:38:39, Philipp Maximilian Stephani escreveu:
> Another bad thing about reference counting is that it forces atomic
> operations, which can kill performance in multi-threaded applications. Th=
e
> problem gets worse the more cores per machine we get.
> The problem I see is that garbage collection in managed languages can onl=
y
> get better, and simplistic attempts like reference counting can only get
> worse. I don't have data, but I'd expect typical Java programs to
> outperform equivalent reference-counted C++ programs even today or in the
> near future.
I think you're generalising based on sketchy information. You've confessed =
to=20
having no data to prove your theory, so I can make the opposite claim with=
=20
equally little data and we'd be no better off.
Modern CPUs share data in block units of cache lines. In order to execute a=
n=20
atomic operation, CPUs need to somehow ensure that other execution units in=
=20
the system don't modify the same cacheline at the same time. And there are=
=20
multiple techniques to do that, some used by very high performance servers =
and=20
designed for this very kind of contentious sharing. You're also discounting=
=20
advances in hardware techniques that could improve performance, as you can =
see=20
from the intel TSX extensions.
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--=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/.
.
Author: David Krauss <potswa@gmail.com>
Date: Tue, 18 Feb 2014 18:02:28 +0800
Raw View
--Apple-Mail=_71FF8E99-6A06-44F3-BC92-9DBD2BADD3B0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8
On Feb 18, 2014, at 4:57 PM, Evgeny Panasyuk <evgeny.panasyuk@gmail.com> wr=
ote:
> 11 Feb 2014 =D0=B3., 18:03:27 UTC+4 Andrew Tomazos:
> We propose a core language feature that allows objects of user-selected c=
lass 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.
>=20
> I think it, or maybe most part of it, can be implemented as library-only=
solution.
> Refer following examples:
> http://www.codeproject.com/Articles/912/A-garbage-collection-framework-fo=
r-C
> http://sourceforge.net/projects/smieciuch/
He acknowledges that already, but the core language feature is supposed to =
improve the interface by hooking the constructors to the collector.
It would be nice to see the specific library Andrew has in mind, though. Un=
conditional registration by the constructor isn=E2=80=99t usually called GC=
..
Many models are possible. I=E2=80=99ve made one intrusive GC where the root=
pointers were registered, and used to seed a mark-and-sweep, and one where=
all the managed pointers were registered, and instead of mark-and-sweep it=
just checked whether each allocation arena was occupied at all. Both provi=
ded significant gains, and it seems like this proposal is based on somethin=
g completely different. I wonder how it works, how generally applicable it =
is, and what are the gains.
A general intrusive GC facility would ideally accommodate several models. B=
ut which rough edges need to be smoothed has to be spelled out specifically=
, since reasonable libraries do already essentially work.
I wish I understood how the C++11 GC support features (reachable and safely=
-derived pointers) are supposed to enable non-intrusive implementations=E2=
=80=A6 or had an available implementation to play with.
--=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/.
--Apple-Mail=_71FF8E99-6A06-44F3-BC92-9DBD2BADD3B0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;"><br><div><div>On Feb 18, 2014=
, at 4:57 PM, Evgeny Panasyuk <<a href=3D"mailto:evgeny.panasyuk@gmail.c=
om">evgeny.panasyuk@gmail.com</a>> wrote:</div><br class=3D"Apple-interc=
hange-newline"><blockquote type=3D"cite"><div dir=3D"ltr">11 Feb 2014 =
=D0=B3., 18:03:27 UTC+4 Andrew Tomazos:<blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;"><div dir=3D"ltr"><span><p dir=3D"ltr" style=3D"line-height:1.15;ma=
rgin-top:0pt;margin-bottom:0pt"><span style=3D"font-size: 15px; font-family=
: Arial; background-color: transparent; font-weight: bold; white-space: pre=
-wrap;"></span></p><span style=3D"font-size: 15px; font-family: Arial; back=
ground-color: transparent; white-space: pre-wrap;"></span><div style=3D"lin=
e-height: 1.15; margin-top: 0pt; margin-bottom: 0pt;"><span style=3D"font-s=
ize: 15px; font-family: Arial; background-color: transparent; white-space: =
pre-wrap;">We propose a core language feature that allows objects of user-s=
elected class types to be cyclically garbage collected. Constraints o=
n the usage of class types so selected, and pointers to such class types, a=
re imposed to enable the implementation of fast safe precise collection.</s=
pan></div></span></div></blockquote><div><br> I think it, or maybe mos=
t part of it, can be implemented as library-only solution.<br>Refer followi=
ng examples:<br><a href=3D"http://www.codeproject.com/Articles/912/A-garbag=
e-collection-framework-for-C">http://www.codeproject.com/Articles/912/A-gar=
bage-collection-framework-for-C</a><br>http://sourceforge.net/projects/smie=
ciuch/<br></div></div></blockquote><div><br></div><div>He acknowledges that=
already, but the core language feature is supposed to improve the interfac=
e by hooking the constructors to the collector.</div><div><br></div><div>It=
would be nice to see the specific library Andrew has in mind, though. Unco=
nditional registration by the constructor isn=E2=80=99t usually called GC.<=
/div><div><br></div><div>Many models are possible. I=E2=80=99ve made one in=
trusive GC where the root pointers were registered, and used to seed a mark=
-and-sweep, and one where all the managed pointers were registered, and ins=
tead of mark-and-sweep it just checked whether each allocation arena was oc=
cupied at all. Both provided significant gains, and it seems like this prop=
osal is based on something completely different. I wonder how it works, how=
generally applicable it is, and what are the gains.</div><div><br></div><d=
iv>A general intrusive GC facility would ideally accommodate several models=
.. But which rough edges need to be smoothed has to be spelled out specifica=
lly, since reasonable libraries do already essentially work.</div><div><br>=
</div><div>I wish I understood how the C++11 GC support features (reachable=
and safely-derived pointers) are supposed to enable non-intrusive implemen=
tations=E2=80=A6 or had an available implementation to play with.</div><div=
><br></div></div></body></html>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--Apple-Mail=_71FF8E99-6A06-44F3-BC92-9DBD2BADD3B0--
.