Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: "Nils M Holm" Newsgroups: comp.compilers Subject: Re: how to find gc roots in stack machine? Date: Mon, 1 Jul 2013 17:33:33 +0200 Organization: Compilers Central Lines: 25 Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <13-07-003@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: leila.iecc.com 1372905623 43602 64.57.183.58 (4 Jul 2013 02:40:23 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Thu, 4 Jul 2013 02:40:23 +0000 (UTC) Keywords: GC, code Posted-Date: 03 Jul 2013 22:40:23 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com X-Received-Bytes: 2166 Xref: csiph.com comp.compilers:934 n.oje.bar@gmail.com: > I am writing a simple compiler for a simple stack machine. Now I want > to add a garbage collector. To do this I need a way to be able to find > all roots in the stack at any given time (or at least at some special > points in time). Basically any value on the stack is a potential root. The real problem is to distinguish values that point to addresses in the address space of the virtual machine from literal values (which do not point to any address or to an address outside of the scope of the GC). A common approach is to check whether a value on the stack is in the (collectable part of the) address space of the VM. If so, treat it as a root. This approach is simple and does not require any meta information. The drawback is, of course, that it may mark objects that are not longer used. This is called the "conservative" approach to GC. The other variant, the "precise" approach, usually sacrifices one bit of information per stack element. This bit is then used to indicate whether or not that value points to an address. The book "Garbage Collection" by Jones & Lins is still a valuable resource on that topic. -- Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org