www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How Garbage Collector works?

reply "Borneq" <borneq antyspam.hidden.pl> writes:
Unlike Java, in D there are pointers and structs. Did not prevent it from 
operation of Garbage Collector? Where is described garbage collection 
algorithm ?
Aug 11 2010
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Borneq" <borneq antyspam.hidden.pl> wrote in message 
news:i3vt2q$285d$1 digitalmars.com...

 Unlike Java, in D there are pointers and structs. Did not prevent it from 
 operation of Garbage Collector? Where is described garbage collection 
 algorithm ?


Most things that are frequently believed to require a sandboxed VM langauge 
like the JVM are misconceptions. There's nothing about pointers that 
prevents garbage collection. The pointers do cause some complication, 
though. For instance, D's GC is a conservative one, and therefore is prone 
to false pointers occasionally preventing an object from being collected.

As for the specifics of D's GC, I don't know much about it. Someone else 
will have to answer that.
Aug 11 2010
next sibling parent reply "Borneq" <borneq antyspam.hidden.pl> writes:
U¿ytkownik "Nick Sabalausky" <a a.a> napisa³ w wiadomo¶ci 
news:i3vv48$2j19$1 digitalmars.com...

 langauge  like the JVM are misconceptions. There's nothing about
 pointers that  prevents garbage collection. The pointers do cause some


We have array and pointer that not points at start array. When we have want 
to free memory we mantain 4 bytes pointer+ 4 bytes array positions = 8 bytes 
(=16 bytes on 64 bits !) ?
How can free block when pointer not points to begin of block?
Aug 12 2010
parent reply "Nick Sabalausky" <a a.a> writes:
"Borneq" <borneq antyspam.hidden.pl> wrote in message 
news:i4074v$187r$1 digitalmars.com...

 U¿ytkownik "Nick Sabalausky" <a a.a> napisa³ w wiadomo¶ci 
 news:i3vv48$2j19$1 digitalmars.com...

 langauge  like the JVM are misconceptions. There's nothing about
 pointers that  prevents garbage collection. The pointers do cause some


 We have array and pointer that not points at start array. When we have 
 want to free memory we mantain 4 bytes pointer+ 4 bytes array positions = 
 8 bytes (=16 bytes on 64 bits !) ?
 How can free block when pointer not points to begin of block?


The GC keeps track of the starting address and the length of each 
allocation.
Aug 12 2010
parent reply "Borneq" <borneq antyspam.hidden.pl> writes:
U¿ytkownik "Nick Sabalausky" <a a.a> napisa³ w wiadomo¶ci 
news:i40b9m$1ti5$1 digitalmars.com...

 The GC keeps track of the starting address and the length of each 
 allocation.


How to deal with:
1.alloc 1000 bytes to pointer
2.increment pointer by 500 bytes
3.checking if block 1000 bytes is reachable but only pointer is in roots
Aug 12 2010
parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Thu, 12 Aug 2010 10:44:51 +0200, Borneq wrote:


 Użytkownik "Nick Sabalausky" <a a.a> napisał w wiadomości
 news:i40b9m$1ti5$1 digitalmars.com...

 The GC keeps track of the starting address and the length of each
 allocation.


 
 How to deal with:
 1.alloc 1000 bytes to pointer
 2.increment pointer by 500 bytes
 3.checking if block 1000 bytes is reachable but only pointer is in roots


Since the GC keeps track of the length of the memory block, it can also 
tell whether the pointer is inside the memory block.

  if (pointer >= startOfBlock && pointer < startOfBlock + blockLength)
      doNotCollect();

-Lars
Aug 12 2010
parent reply "Borneq" <borneq antyspam.hidden.pl> writes:
Użytkownik "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> napisał w 
wiadomości news:i40dhi$55q$1 digitalmars.com...

 Since the GC keeps track of the length of the memory block, it can also
 tell whether the pointer is inside the memory block.
  if (pointer >= startOfBlock && pointer < startOfBlock + blockLength)
      doNotCollect();


How compute startOfBlock ? GC keep startOfBlock for each pointer (pointer 
consits of actual pointer and pointer to startOfBlock)?
or search for pointer such Block that pointer betwen 
startOfBlock..startOfBlock + blockLength ?
Aug 12 2010
next sibling parent Leandro Lucarella <luca llucax.com.ar> writes:
Borneq, el 12 de agosto a las 11:44 me escribiste:

 Użytkownik "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet>
 napisał w wiadomości news:i40dhi$55q$1 digitalmars.com...

Since the GC keeps track of the length of the memory block, it can also
tell whether the pointer is inside the memory block.
 if (pointer >= startOfBlock && pointer < startOfBlock + blockLength)
     doNotCollect();


 
 How compute startOfBlock ? GC keep startOfBlock for each pointer
 (pointer consits of actual pointer and pointer to startOfBlock)?
 or search for pointer such Block that pointer betwen
 startOfBlock..startOfBlock + blockLength ?


You might find this blog posts interesting, they explain in relative
detail how the D's GC works:
http://www.llucax.com.ar/blog/blog/tag/understanding%20the%20current%20gc
(you probably want to read it in reverse order :)

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
Qué sabía Galileo de astronomía, Mendieta! Lo que pasa es que en este
país habla cualquiera.
	-- Inodoro Pereyra
Aug 12 2010
prev sibling next sibling parent BCS <none anon.com> writes:
Hello Borneq,


 Użytkownik "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> napisał
 w wiadomości news:i40dhi$55q$1 digitalmars.com...
 

 Since the GC keeps track of the length of the memory block, it can
 also
 tell whether the pointer is inside the memory block.
 if (pointer >= startOfBlock && pointer < startOfBlock + blockLength)
 doNotCollect();


 How compute startOfBlock ? GC keep startOfBlock for each pointer
 (pointer
 consits of actual pointer and pointer to startOfBlock)?
 or search for pointer such Block that pointer betwen
 startOfBlock..startOfBlock + blockLength ?


The GC keeps a some sort of table of what it has allocated. IT can then just 
look up all the startOfBlock/blockLength values.

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Na.C3.AFve_mark-and-sweep

-- 
... <IXOYE><
Aug 12 2010
prev sibling parent Rory Mcguire <rjmcguire gm_no_ail.com> writes:
Borneq wrote:


 Użytkownik "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> napisał w
 wiadomości news:i40dhi$55q$1 digitalmars.com...

 Since the GC keeps track of the length of the memory block, it can also
 tell whether the pointer is inside the memory block.
  if (pointer >= startOfBlock && pointer < startOfBlock + blockLength)
      doNotCollect();


 
 How compute startOfBlock ? GC keep startOfBlock for each pointer (pointer
 consits of actual pointer and pointer to startOfBlock)?
 or search for pointer such Block that pointer betwen
 startOfBlock..startOfBlock + blockLength ?


GC doesn't keep track of pointer, it only keeps track of the start of 
allocated memory and the length of that allocated block.

it then has to scan to see if there are any pointers into that allocated 
block. This is why if you slice a subsection of an array the memory doesn't 
just get freed.

-Rory
Aug 12 2010
prev sibling parent Leandro Lucarella <luca llucax.com.ar> writes:
Nick Sabalausky, el 12 de agosto a las 01:00 me escribiste:

 "Borneq" <borneq antyspam.hidden.pl> wrote in message 
 news:i3vt2q$285d$1 digitalmars.com...

 Unlike Java, in D there are pointers and structs. Did not prevent it from 
 operation of Garbage Collector? Where is described garbage collection 
 algorithm ?


 
 Most things that are frequently believed to require a sandboxed VM langauge 
 like the JVM are misconceptions. There's nothing about pointers that 
 prevents garbage collection. The pointers do cause some complication, 
 though. For instance, D's GC is a conservative one, and therefore is prone 
 to false pointers occasionally preventing an object from being collected.


Conservativeness have nothing to do with pointers, and actually *all* GC
deal with pointers, is all the GC does, follow pointers to see what
chunks of memory are alive :)

There is a patch[1] to make D support semi-precise GC (only the heap
have type information).

[1] http://d.puremagic.com/issues/show_bug.cgi?id=3463

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
PROTESTA EN PLAZA DE MAYO: MUSICO SE COSIO LA BOCA
	-- Crónica TV
Aug 12 2010
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Borneq wrote:

 Unlike Java, in D there are pointers and structs. Did not prevent it 
 from operation of Garbage Collector? Where is described garbage 
 collection algorithm ?


The technical term for D's current gc algorithm is a conservative mark-sweep 
garbage collection algorithm. If you google on that, you'll find a lot of 
information.
Aug 11 2010