I was teaching D to this guy, and by the time we were at doubly linked lists, the issue of discarding the list arose. I told him that in the spirit of D, all you'd have to do is to null all references to the list (list, current, etc. pointers), or to just have them go out of scope.

But then I got unsure whether this works today in D.

So, does one really have to walk the list and null all the references between the items, or does the GC understand about "linked islands"?

I want 2 answers: what's it today, and what's it gonna be the day everything is Right?

Walter's garbage collector is a mark-and-sweep collector.  Basically, what this means is that it starts by scanning the range of data that it knows is not garbage (global variables and the stack(s)).  It finds there all the values that might conceivably be pointers and marks the things they point to as "not garbage."  It continues on, scanning things known to be "not garbage," until it doesn't find anything new.  At that point, all memory that has not been scanned is assumed to be garbage.

What that means is that it will realize that your doubly-linked list is an island and will garbage collect it.  Since nobody ever points in to any of the objects in the list, they will never be marked "not garbage" and will get collected.

One of the downsides of this type of collector, however, is that it can get false positives; if one object in your doubly-linked list is at address 0xdeadbeef, and you happen to have an integer somewhere in your program that has the value 0xdeadbeef, then the garbage collector will assume that it is a pointer.  (The garbage collector doesn't know about  the types of the variables it is scanning.)  In that case, the doubly-linked list will not get garbage collected immediately; however, whenever your integer value changes, then the next gc pass will clean it up.

Georg Wrede wrote:
> I was teaching D to this guy, and by the time we were at
> doubly linked lists, the issue of discarding the list
> arose. I told him that in the spirit of D, all you'd have
> to do is to null all references to the list (list, current,
> etc. pointers), or to just have them go out of scope.
> 
> But then I got unsure whether this works today in D.
> 
> So, does one really have to walk the list and null all the
> references between the items, or does the GC understand
> about "linked islands"?
> 
> I want 2 answers: what's it today, and what's it gonna be
> the day everything is Right?
> 
> 
> 

In article <bubrab$2kqb$1@digitaldaemon.com>, Russ Lewis says...
>
>What that means is that it will realize that your doubly-linked list is an island and will garbage collect it.  Since nobody ever points in to any of the objects in the list, they will never be marked "not garbage" and will get collected.

Whew, I won't get caught for lying!

>One of the downsides of this type of collector, however, is that it can get false positives; if one object in your doubly-linked list is at address 0xdeadbeef, and you happen to have an integer somewhere in your program that has the value 0xdeadbeef, then the garbage collector will assume that it is a pointer.  (The garbage collector doesn't know about
>  the types of the variables it is scanning.)  In that case, the
>doubly-linked list will not get garbage collected immediately; however, whenever your integer value changes, then the next gc pass will clean it up.

Wow! This means it doesn't care about the structure of things, it just assumes everything is 32-bit, and then looks for matching bit patterns? From this follows that if I have a tightly packed struct that contains bytes at the beginning, then this 0xdeadbeef might just appear as the pattern composed of several unrelated bytes in the structure?

Not that I think this is a practical problem. As you say, chances are the bit pattern will probably change before long.

How often and when is the GC ran ?( good description btw ).

C
"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
news:bubrab$2kqb$1@digitaldaemon.com...
> Walter's garbage collector is a mark-and-sweep collector.  Basically, what this means is that it starts by scanning the range of data that it knows is not garbage (global variables and the stack(s)).  It finds there all the values that might conceivably be pointers and marks the things they point to as "not garbage."  It continues on, scanning things known to be "not garbage," until it doesn't find anything new.  At that point, all memory that has not been scanned is assumed to be garbage.
>
> What that means is that it will realize that your doubly-linked list is an island and will garbage collect it.  Since nobody ever points in to any of the objects in the list, they will never be marked "not garbage" and will get collected.
>
> One of the downsides of this type of collector, however, is that it can
> get false positives; if one object in your doubly-linked list is at
> address 0xdeadbeef, and you happen to have an integer somewhere in your
> program that has the value 0xdeadbeef, then the garbage collector will
> assume that it is a pointer.  (The garbage collector doesn't know about
>   the types of the variables it is scanning.)  In that case, the
> doubly-linked list will not get garbage collected immediately; however,
> whenever your integer value changes, then the next gc pass will clean it
up.
>
> Georg Wrede wrote:
> > I was teaching D to this guy, and by the time we were at doubly linked lists, the issue of discarding the list arose. I told him that in the spirit of D, all you'd have to do is to null all references to the list (list, current, etc. pointers), or to just have them go out of scope.
> >
> > But then I got unsure whether this works today in D.
> >
> > So, does one really have to walk the list and null all the references between the items, or does the GC understand about "linked islands"?
> >
> > I want 2 answers: what's it today, and what's it gonna be the day everything is Right?
> >
> >
> >
>

> How often and when is the GC ran ?( good description btw ).

When memory is low.

I recently put out a suggestion that DMD creates and activates a low-priority thread if any additional (over and above the main) thread is created, i.e. the program is multi-threaded. Being low priority (e.g. THREAD_PRIORITY_IDLE on Win32) it would not inconvenience any other thread/process, but would cause memory to be cleaned when the machine's idle and, more importantly, will cause the destructors of objects to be called, potentially freeing resources far more scarce than memory.

However, no-one seemed particularly keen, so it's not going anywhere for the moment. I think this'll only float when we've got meaty apps out there, and we can performance test the two variants.

>
> C
> "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
> news:bubrab$2kqb$1@digitaldaemon.com...
> > Walter's garbage collector is a mark-and-sweep collector.  Basically, what this means is that it starts by scanning the range of data that it knows is not garbage (global variables and the stack(s)).  It finds there all the values that might conceivably be pointers and marks the things they point to as "not garbage."  It continues on, scanning things known to be "not garbage," until it doesn't find anything new.  At that point, all memory that has not been scanned is assumed to be garbage.
> >
> > What that means is that it will realize that your doubly-linked list is an island and will garbage collect it.  Since nobody ever points in to any of the objects in the list, they will never be marked "not garbage" and will get collected.
> >
> > One of the downsides of this type of collector, however, is that it can
> > get false positives; if one object in your doubly-linked list is at
> > address 0xdeadbeef, and you happen to have an integer somewhere in your
> > program that has the value 0xdeadbeef, then the garbage collector will
> > assume that it is a pointer.  (The garbage collector doesn't know about
> >   the types of the variables it is scanning.)  In that case, the
> > doubly-linked list will not get garbage collected immediately; however,
> > whenever your integer value changes, then the next gc pass will clean it
> up.
> >
> > Georg Wrede wrote:
> > > I was teaching D to this guy, and by the time we were at doubly linked lists, the issue of discarding the list arose. I told him that in the spirit of D, all you'd have to do is to null all references to the list (list, current, etc. pointers), or to just have them go out of scope.
> > >
> > > But then I got unsure whether this works today in D.
> > >
> > > So, does one really have to walk the list and null all the references between the items, or does the GC understand about "linked islands"?
> > >
> > > I want 2 answers: what's it today, and what's it gonna be the day everything is Right?
> > >
> > >
> > >
> >
>
>

In article <bubrab$2kqb$1@digitaldaemon.com>, Russ Lewis says...
>
>Walter's garbage collector is a mark-and-sweep collector.  Basically,
..
>One of the downsides of this type of collector, however, is that it can get false positives; if one object in your doubly-linked list is at address 0xdeadbeef, and you happen to have an integer somewhere in your program that has the value 0xdeadbeef, then the garbage collector will assume that it is a pointer.

DMD 0.76 docs say:

"Do not store pointers into int variables using casts and other tricks. The garbage collector does not scan non-pointer types for roots."

This would contradict the 0xdeadbeef example problem. That is, according to the documentation such a problem does not exist!?

Georg Wrede <Georg_member@pathlink.com> wrote in news:budo3m$2krn$1@digitaldaemon.com:

> In article <bubrab$2kqb$1@digitaldaemon.com>, Russ Lewis says...
>>
>>Walter's garbage collector is a mark-and-sweep collector.  Basically,
> ..
>>One of the downsides of this type of collector, however, is that it can get false positives; if one object in your doubly-linked list is at address 0xdeadbeef, and you happen to have an integer somewhere in your program that has the value 0xdeadbeef, then the garbage collector will assume that it is a pointer.
> 
> DMD 0.76 docs say:
> 
> "Do not store pointers into int variables using casts and other tricks. The garbage collector does not scan non-pointer types for roots."
> 
> This would contradict the 0xdeadbeef example problem. That is, according to the documentation such a problem does not exist!?


Not necessarily.  It is specified this way to
allow for smarter D complilers.  A smart compiler
might generate information about root pointers
that the GC could use to make a smart scan of the
global space and the stack.  If compiler does
not generate this type of information the GC can
just scan the entire global space and stack.

I don't think Walter's DMD generates this type of information yet but in the future it could. Other D compilers could too.  So it's a smart idea not to store pointers in non pointer types.

When you try to allocate memory but the allocator doesn't have any free memory regions, then it runs the GC *before* it asks the OS for more memory.

I don't know of any other situations when it runs...but there might be some, or there might be some new ones in the future.

Russ

C wrote:
> How often and when is the GC ran ?( good description btw ).
> 
> C
> "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
> news:bubrab$2kqb$1@digitaldaemon.com...
> 
>>Walter's garbage collector is a mark-and-sweep collector.  Basically,
>>what this means is that it starts by scanning the range of data that it
>>knows is not garbage (global variables and the stack(s)).  It finds
>>there all the values that might conceivably be pointers and marks the
>>things they point to as "not garbage."  It continues on, scanning things
>>known to be "not garbage," until it doesn't find anything new.  At that
>>point, all memory that has not been scanned is assumed to be garbage.
>>
>>What that means is that it will realize that your doubly-linked list is
>>an island and will garbage collect it.  Since nobody ever points in to
>>any of the objects in the list, they will never be marked "not garbage"
>>and will get collected.
>>
>>One of the downsides of this type of collector, however, is that it can
>>get false positives; if one object in your doubly-linked list is at
>>address 0xdeadbeef, and you happen to have an integer somewhere in your
>>program that has the value 0xdeadbeef, then the garbage collector will
>>assume that it is a pointer.  (The garbage collector doesn't know about
>>  the types of the variables it is scanning.)  In that case, the
>>doubly-linked list will not get garbage collected immediately; however,
>>whenever your integer value changes, then the next gc pass will clean it
> 
> up.
> 
>>Georg Wrede wrote:
>>
>>>I was teaching D to this guy, and by the time we were at
>>>doubly linked lists, the issue of discarding the list
>>>arose. I told him that in the spirit of D, all you'd have
>>>to do is to null all references to the list (list, current,
>>>etc. pointers), or to just have them go out of scope.
>>>
>>>But then I got unsure whether this works today in D.
>>>
>>>So, does one really have to walk the list and null all the
>>>references between the items, or does the GC understand
>>>about "linked islands"?
>>>
>>>I want 2 answers: what's it today, and what's it gonna be
>>>the day everything is Right?

While it was 18/1/04 4:13 pm throughout the UK, Patrick Down sprinkled little black dots on a white screen, and they fell thus:

<snip>
>>"Do not store pointers into int variables using casts and other
>>tricks. The garbage collector does not scan non-pointer types for
>>roots." 
<snip>
> Not necessarily.  It is specified this way to
> allow for smarter D complilers.  A smart compiler
> might generate information about root pointers
> that the GC could use to make a smart scan of the
> global space and the stack.  If compiler does
> not generate this type of information the GC can
> just scan the entire global space and stack.
> 
> I don't think Walter's DMD generates this type of information yet but in the future it could. Other D compilers could too.  So it's a smart idea not to store pointers in non pointer types.

Makes sense, though I'm still a bit puzzled, as it also says:
"#  Do not store integer values into pointers.
# Do not store magic values into pointers, other than null."

What would be the consequence of this?  Speaking of which, are Windows API handles really pointers, as the type definitions imply?

"# If you must share the same storage location between pointers and non-pointer types, use a union to do it so the garbage collector knows about it."

How would the GC know about it, unless the union keeps a record of which member is 'active'?

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

In article <burget$j36$1@digitaldaemon.com>, Stewart Gordon says...
>
>While it was 18/1/04 4:13 pm throughout the UK, Patrick Down sprinkled little black dots on a white screen, and they fell thus:
>
><snip>
>>>"Do not store pointers into int variables using casts and other tricks. The garbage collector does not scan non-pointer types for roots."
><snip>
>> Not necessarily.  It is specified this way to
>> allow for smarter D complilers.  A smart compiler
>> might generate information about root pointers
>> that the GC could use to make a smart scan of the
>> global space and the stack.  If compiler does
>> not generate this type of information the GC can
>> just scan the entire global space and stack.
>> 
>> I don't think Walter's DMD generates this type of information yet but in the future it could. Other D compilers could too.  So it's a smart idea not to store pointers in non pointer types.
>
>Makes sense, though I'm still a bit puzzled, as it also says:
>"#  Do not store integer values into pointers.
># Do not store magic values into pointers, other than null."
>
>What would be the consequence of this?  Speaking of which, are Windows API handles really pointers, as the type definitions imply?
>
>"# If you must share the same storage location between pointers and non-pointer types, use a union to do it so the garbage collector knows about it."
>
>How would the GC know about it, unless the union keeps a record of which member is 'active'?

I'm not sure, I don't know much about the inner workings of D, but it would probably scan it even if the non-pointer type is being used.  After all, the real danger isn't that the GC will scan non-pointers, it's that it'll miss scanning pointers and collect memory that's still being used.