please help about the implementation of GC.

please help about the implementation of GC.

[Alin Soare]

[-- Attachment #1: Type: text/plain, Size: 524 bytes --]

Hi,

I wish to read the algorithm of gc, and I cannot.

I understand that I have to have read about black-red trees, but what other
former requirement is necessary to understand the implementation ?

Can somebody help me step-by-step in order to understand it ? Or what
requirement is necessary to understand it ? I have already read about the
algorithm of "conservative stack scanning", but this is not enough. I still
do not understand almost anything from the gc of emacs... Please help.

Thanks a lot in advance,

Alin.

[-- Attachment #2: Type: text/html, Size: 592 bytes --]

Re: please help about the implementation of GC.

[Andreas Schwab]

Alin Soare <as1789@gmail.com> writes:

> I wish to read the algorithm of gc, and I cannot.

The Emacs gc is a simple mark and sweep collector.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: please help about the implementation of GC.

[Eli Zaretskii]

> From: Andreas Schwab <schwab@linux-m68k.org>
> Date: Sun, 30 Oct 2011 17:56:15 +0100
> Cc: Emacs Dev <emacs-devel@gnu.org>
> 
> Alin Soare <as1789@gmail.com> writes:
> 
> > I wish to read the algorithm of gc, and I cannot.
> 
> The Emacs gc is a simple mark and sweep collector.

Right.

Alin, you can start by reading the node "Garbage Collection" in the
ELisp manual, and then proceed reading alloc.c, where you will see
many functions named mark_SOMETHING and then gc_sweep that does the
sweep stage.  If you want more background before reading the ELisp
manual, try googling "mark and sweep garbage collection".

Re: please help about the implementation of GC.

[Alin Soare]

[-- Attachment #1: Type: text/plain, Size: 1012 bytes --]

> > > I wish to read the algorithm of gc, and I cannot.
> >
> > The Emacs gc is a simple mark and sweep collector.
>
> Right.
>
> Alin, you can start by reading the node "Garbage Collection" in the
> ELisp manual, and then proceed reading alloc.c, where you will see
> many functions named mark_SOMETHING and then gc_sweep that does the
> sweep stage.  If you want more background before reading the ELisp
> manual, try googling "mark and sweep garbage collection".
>

I have read the mark-sweep algorithm; I know it. However, I do not manage
making the connection with alloc.c.

For example, I cannot understand what kind of objects are kept in every
node of the red-black tree  (in books I never saw gc implemented with
red-black trees). I know that the objects are kept in obarrays. What link
is there between obarrays and red-black tree of gc ?

What happens to a Lisp_Object defined in C code? Is it freed if it is found
by conservative stack algorithm ? What is the link between GCPRO? macros
and the gc ?

[-- Attachment #2: Type: text/html, Size: 1324 bytes --]

Re: please help about the implementation of GC.

[Andreas Schwab]

Alin Soare <as1789@gmail.com> writes:

> What happens to a Lisp_Object defined in C code?

They always form a GC root, see staticpro.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: please help about the implementation of GC.

[Stefan Monnier]

> For example, I cannot understand what kind of objects are kept in every
> node of the red-black tree  (in books I never saw gc implemented with
> red-black trees). I know that the objects are kept in obarrays. What link
> is there between obarrays and red-black tree of gc ?

Start by ignoring the conservative stack scanning (which is the one
that uses the red-black tree).  Also the fact that we use a red-black
tree is not important: it's just a map from addresses to information
about them (whether the address is allocated to Elisp data and if so to
which kind of data).


        Stefan