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 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 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
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();

(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 next 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
prev sibling 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 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