www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Heap allocation and internal pointers

reply "monarch_dodra" <monarchdodra gmail.com> writes:
What is the "stance" on objects that reside on the heap, and 
internal pointers?

I understand that for stack objects, it leads to data corruption, 
due to data being bit-moved when passed around.

But what about heap data? Currently, our GC doesn't move data 
around, but what if it did? Would internal pointers be a problem? 


My usecase is pretty trivial: A linked list. This is often 
implemented as a "single" sentinel that serves as both 
pre-head/post-tail. When the list is empty, the sentinel simply 
points to itself.

Would this be legal in D? The alternative would simply be to have 
two separate sentinels. It wouldn't change the design much, but 
I'd like to avoid doing it if at all possible...
Jan 19 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/19/14 8:18 AM, monarch_dodra wrote:
 What is the "stance" on objects that reside on the heap, and internal
 pointers?

 I understand that for stack objects, it leads to data corruption, due to
 data being bit-moved when passed around.

 But what about heap data? Currently, our GC doesn't move data around,

 handle such cases?

 My usecase is pretty trivial: A linked list. This is often implemented
 as a "single" sentinel that serves as both pre-head/post-tail. When the
 list is empty, the sentinel simply points to itself.

 Would this be legal in D? The alternative would simply be to have two
 separate sentinels. It wouldn't change the design much, but I'd like to
 avoid doing it if at all possible...
A moving collector should preserve the semantics of your object. Andrei
Jan 19 2014
prev sibling next sibling parent reply "Dicebot" <public dicebot.lv> writes:
Quick dlang.org investigation has found this:



Note:
Evaluating pointsTo(x, x) checks whether x has internal pointers. 
This should only be done as an assertive test, as the language is 
free to assume objects don't have internal pointers (TDPL 
7.1.3.5).

I guess you may want to check mentioned TDPL part ;)
Jan 20 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 20 January 2014 at 12:27:41 UTC, Dicebot wrote:
 Quick dlang.org investigation has found this:



 Note:
 Evaluating pointsTo(x, x) checks whether x has internal 
 pointers. This should only be done as an assertive test, as the 
 language is free to assume objects don't have internal pointers 
 (TDPL 7.1.3.5).

 I guess you may want to check mentioned TDPL part ;)
Yeah, I remember the pull that added that comment. As a matter of fact, it was I that brought up said part in the original pull. It basically says "dmd assumes no internal pointers for its move semantics" :/
Jan 20 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 20 Jan 2014 14:22:34 -0500, monarch_dodra <monarchdodra gmail.com>  
wrote:

 On Monday, 20 January 2014 at 12:27:41 UTC, Dicebot wrote:
 Quick dlang.org investigation has found this:



 Note:
 Evaluating pointsTo(x, x) checks whether x has internal pointers. This  
 should only be done as an assertive test, as the language is free to  
 assume objects don't have internal pointers (TDPL 7.1.3.5).

 I guess you may want to check mentioned TDPL part ;)
Yeah, I remember the pull that added that comment. As a matter of fact, it was I that brought up said part in the original pull. It basically says "dmd assumes no internal pointers for its move semantics" :/
Um.. that should only apply to stack-allocated items. Heap allocated items are fine to point to themselves, even structs. Consider that cycles are allowed, and planned for, in the GC. An internal pointer is essentially a 1 element cycle! A simple logical evaluation of how a moving GC would work reveals that it should update internal pointers as well as all other pointers. -Steve
Jan 20 2014
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
20-Jan-2014 23:41, Steven Schveighoffer пишет:
 On Mon, 20 Jan 2014 14:22:34 -0500, monarch_dodra
 <monarchdodra gmail.com> wrote:

 On Monday, 20 January 2014 at 12:27:41 UTC, Dicebot wrote:
 Quick dlang.org investigation has found this:



 Note:
 Evaluating pointsTo(x, x) checks whether x has internal pointers.
 This should only be done as an assertive test, as the language is
 free to assume objects don't have internal pointers (TDPL 7.1.3.5).

 I guess you may want to check mentioned TDPL part ;)
Yeah, I remember the pull that added that comment. As a matter of fact, it was I that brought up said part in the original pull. It basically says "dmd assumes no internal pointers for its move semantics" :/
Um.. that should only apply to stack-allocated items. Heap allocated items are fine to point to themselves, even structs. Consider that cycles are allowed, and planned for, in the GC. An internal pointer is essentially a 1 element cycle!
Makes sense... Then allocating on GC heap is fine.
 A simple logical evaluation of how a moving GC would work reveals that
 it should update internal pointers as well as all other pointers.

 -Steve
-- Dmitry Olshansky
Jan 20 2014
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
19-Jan-2014 20:18, monarch_dodra пишет:
 What is the "stance" on objects that reside on the heap, and internal
 pointers?

 I understand that for stack objects, it leads to data corruption, due to
 data being bit-moved when passed around.

 But what about heap data? Currently, our GC doesn't move data around,

 handle such cases?
 My usecase is pretty trivial: A linked list. This is often implemented
 as a "single" sentinel that serves as both pre-head/post-tail. When the
 list is empty, the sentinel simply points to itself.
You could use internal pointers for this case as long as: a) The struct will never get copied and/or moved. No pass by value, only pointers. b) It's out of GC control and in particular GC-allocated built-in arrays. This means you don't have that much of choice beyond things like: MyObject* node = (MyObject*)malloc(MyObject.sizeof); And only ever using pointers. -- Dmitry Olshansky
Jan 20 2014
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
20-Jan-2014 20:35, Dmitry Olshansky пишет:
 19-Jan-2014 20:18, monarch_dodra пишет:
 My usecase is pretty trivial: A linked list. This is often implemented
 as a "single" sentinel that serves as both pre-head/post-tail. When the
 list is empty, the sentinel simply points to itself.
You could use internal pointers for this case as long as: a) The struct will never get copied and/or moved. No pass by value, only pointers. b) It's out of GC control and in particular GC-allocated built-in arrays. This means you don't have that much of choice beyond things like: MyObject* node = (MyObject*)malloc(MyObject.sizeof);
s/(MyObject*)/cast(MyObject*)/ Too much of C on me lately ;) -- Dmitry Olshansky
Jan 20 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 20 January 2014 at 16:35:26 UTC, Dmitry Olshansky 
wrote:
 You could use internal pointers for this case as long as:
 a) The struct will never get copied and/or moved. No pass by 
 value, only pointers.
 b) It's out of GC control and in particular GC-allocated 
 built-in arrays.

 This means you don't have that much of choice beyond things 
 like:
 MyObject* node = (MyObject*)malloc(MyObject.sizeof);

 And only ever using pointers.
Hum... well this contradicts Andrei's:
 A moving collector should preserve the semantics of your object.
I want to do: //---- Node* root = new Node; root._next = root; root._prev = root; //---- So in this case, it would perfectly go with your "A" recommendation. It's "B" I'm unsure of :/
Jan 20 2014
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 20 Jan 2014 11:35:10 -0500, Dmitry Olshansky  =

<dmitry.olsh gmail.com> wrote:

 19-Jan-2014 20:18, monarch_dodra =D0=BF=D0=B8=D1=88=D0=B5=D1=82:
 My usecase is pretty trivial: A linked list. This is often implemente=
d
 as a "single" sentinel that serves as both pre-head/post-tail. When t=
he
 list is empty, the sentinel simply points to itself.
You could use internal pointers for this case as long as: a) The struct will never get copied and/or moved. No pass by value, on=
ly =
 pointers.
 b) It's out of GC control and in particular GC-allocated built-in arra=
ys. I think this is somewhat too general. It can be GC allocated, even = GC-array allocated. The GC will not move around your array unexpectedly = = without updating the pointers. What you cannot do is array *operations* that might copy the data for th= at = reference/slice. So aside from the original 'new' call, you cannot use = .dup, .idup, .length +=3D, ~ or ~=3D, .reserve. That being said, avoiding using an array is likely to be a better choice= :) As a hint, dcollections does exactly what you want to do, and I've never= = had a problem with it. -Steve
Jan 20 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 20 January 2014 at 19:48:01 UTC, Steven Schveighoffer 
wrote:
 On Mon, 20 Jan 2014 11:35:10 -0500, Dmitry Olshansky 
 <dmitry.olsh gmail.com> wrote:

 19-Jan-2014 20:18, monarch_dodra пишет:
 My usecase is pretty trivial: A linked list. This is often 
 implemented
 as a "single" sentinel that serves as both 
 pre-head/post-tail. When the
 list is empty, the sentinel simply points to itself.
You could use internal pointers for this case as long as: a) The struct will never get copied and/or moved. No pass by value, only pointers. b) It's out of GC control and in particular GC-allocated built-in arrays.
I think this is somewhat too general. It can be GC allocated, even GC-array allocated. The GC will not move around your array unexpectedly without updating the pointers. What you cannot do is array *operations* that might copy the data for that reference/slice. So aside from the original 'new' call, you cannot use .dup, .idup, .length +=, ~ or ~=, .reserve. That being said, avoiding using an array is likely to be a better choice :) As a hint, dcollections does exactly what you want to do, and I've never had a problem with it. -Steve
Most awesome. Thanks for all the info. It's basically what I *thought*, but wanted confirmation from people with actual knowledge.
Jan 20 2014
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
20-Jan-2014 23:48, Steven Schveighoffer пишет:
 On Mon, 20 Jan 2014 11:35:10 -0500, Dmitry Olshansky
 <dmitry.olsh gmail.com> wrote:

 19-Jan-2014 20:18, monarch_dodra пишет:
 My usecase is pretty trivial: A linked list. This is often implemented
 as a "single" sentinel that serves as both pre-head/post-tail. When the
 list is empty, the sentinel simply points to itself.
You could use internal pointers for this case as long as: a) The struct will never get copied and/or moved. No pass by value, only pointers. b) It's out of GC control and in particular GC-allocated built-in arrays.
I think this is somewhat too general. It can be GC allocated, even GC-array allocated. The GC will not move around your array unexpectedly without updating the pointers.
But a moving collector will happily assume there are no internal pointers when moving and won't update them I bet. -- Dmitry Olshansky
Jan 20 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 20 Jan 2014 14:58:12 -0500, Dmitry Olshansky  =

<dmitry.olsh gmail.com> wrote:

 20-Jan-2014 23:48, Steven Schveighoffer =D0=BF=D0=B8=D1=88=D0=B5=D1=82=
:
 I think this is somewhat too general. It can be GC allocated, even
 GC-array allocated. The GC will not move around your array unexpected=
ly
 without updating the pointers.
But a moving collector will happily assume there are no internal =
 pointers when moving and won't update them I bet.
If we have a moving GC, then we must have precise type info on every pie= ce = of memory that points at the target, otherwise it cannot possibly move = data unsolicited. Why wouldn't that include the internal pointer? -Steve
Jan 20 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Monday, 20 January 2014 at 20:20:01 UTC, Steven Schveighoffer 
wrote:
 On Mon, 20 Jan 2014 14:58:12 -0500, Dmitry Olshansky 
 <dmitry.olsh gmail.com> wrote:

 20-Jan-2014 23:48, Steven Schveighoffer пишет:
 I think this is somewhat too general. It can be GC allocated, 
 even
 GC-array allocated. The GC will not move around your array 
 unexpectedly
 without updating the pointers.
But a moving collector will happily assume there are no internal pointers when moving and won't update them I bet.
If we have a moving GC, then we must have precise type info on every piece of memory that points at the target, otherwise it cannot possibly move data unsolicited. Why wouldn't that include the internal pointer? -Steve
I thought internal pointer were forbidden so that we can elide postblits etc. when moving r-values? What about this use case?
Jan 24 2014
parent "Tobias Pankrath" <tobias pankrath.net> writes:
On Friday, 24 January 2014 at 12:40:44 UTC, Tobias Pankrath wrote:
 On Monday, 20 January 2014 at 20:20:01 UTC, Steven 
 Schveighoffer wrote:
 On Mon, 20 Jan 2014 14:58:12 -0500, Dmitry Olshansky 
 <dmitry.olsh gmail.com> wrote:

 20-Jan-2014 23:48, Steven Schveighoffer пишет:
 I think this is somewhat too general. It can be GC 
 allocated, even
 GC-array allocated. The GC will not move around your array 
 unexpectedly
 without updating the pointers.
But a moving collector will happily assume there are no internal pointers when moving and won't update them I bet.
If we have a moving GC, then we must have precise type info on every piece of memory that points at the target, otherwise it cannot possibly move data unsolicited. Why wouldn't that include the internal pointer? -Steve
I thought internal pointer were forbidden so that we can elide postblits etc. when moving r-values? What about this use case?
Got it myself m(
Jan 24 2014