I'm writing a toy lispish compiler (with a vague idea of common lisp
or scheme's semantics) and I was wondering at what times it's ok to
run a GC:
(defun blah (x)
; 1
)
(let ((foo (cons 0 0)))
(blah foo)
(bar bar)
(baz baz))
; 2
Would people be surprised if (cons 0 0) was reclaimed at point 1 (or
even earlier) or do they expect it to be done at some point after 2
(i.e. when foo leaves lexical scope)?
I know this toy example doesn't really make a difference but imagine
one where users can actually detect the difference (say pedantic
examples involving finalizers, weak-refs, continuations, and/or
exceptions).
In article <························@j27g2000cwj.googlegroups.com>,
"Me" <···················@yahoo.com> wrote:
> I'm writing a toy lispish compiler (with a vague idea of common lisp
> or scheme's semantics) and I was wondering at what times it's ok to
> run a GC:
>
> (defun blah (x)
> ; 1
> )
>
> (let ((foo (cons 0 0)))
> (blah foo)
> (bar bar)
> (baz baz))
> ; 2
>
> Would people be surprised if (cons 0 0) was reclaimed at point 1 (or
> even earlier) or do they expect it to be done at some point after 2
> (i.e. when foo leaves lexical scope)?
>
> I know this toy example doesn't really make a difference but imagine
> one where users can actually detect the difference (say pedantic
> examples involving finalizers, weak-refs, continuations, and/or
> exceptions).
No programming construct can tell the difference. The GC may only
reclaim an object when it's impossible for the program to access it in
any way. None of the things you mention change that -- the compiler can
always tell all the constructs that have access to a lexical variable
(this is one of the main reasons why lexical scoping is generally
preferable over dynamic scoping).
If FOO is referenced in any of the kinds of things you mention, this
will usually preclude it being GCed. For instance,
(let ((foo (cons 0 0)))
(bar (lambda () foo)))
While compiling this, there's no way to know what BAR does with the
closure -- it could save it in a global variable. So it is not safe to
reclaim the cons.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Me wrote:
> I'm writing a toy lispish compiler (with a vague idea of common lisp
> or scheme's semantics) and I was wondering at what times it's ok to
> run a GC:
>
> (defun blah (x)
> ; 1
> )
>
> (let ((foo (cons 0 0)))
> (blah foo)
> (bar bar)
> (baz baz))
> ; 2
>
> Would people be surprised if (cons 0 0) was reclaimed at point 1 (or
> even earlier) or do they expect it to be done at some point after 2
> (i.e. when foo leaves lexical scope)?
A clever compiler could indeed detect that the variable foo is not used
after the invocation of blah anymore and allow the garbage collector to
free it earlier.
> I know this toy example doesn't really make a difference but imagine
> one where users can actually detect the difference (say pedantic
> examples involving finalizers, weak-refs, continuations, and/or
> exceptions).
You should never design your code based on the assumption that the
garbage collector collects any of your objects. It might never collect
them at all, not even when the program exits. Garbage collection is an
optimization for space, and like all optimizations it is optional.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
(message (Hello 'Me)
(you :wrote :on '(14 Feb 2007 16:10:20 -0800))
(
M> Would people be surprised if (cons 0 0) was reclaimed at point 1 (or
M> even earlier) or do they expect it to be done at some point after 2
M> (i.e. when foo leaves lexical scope)?
it's safe to reclaim it as soon as it's possible to prove that there is no
way to reach it.
however, i suspect most implementations will not bother to detect that that
early.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"?? ???? ??????? ?????")
On Feb 15, 4:13 am, "Alex Mizrahi" <········@users.sourceforge.net>
wrote:
> (message (Hello 'Me)
> (you :wrote :on '(14 Feb 2007 16:10:20 -0800))
> (
>
> M> Would people be surprised if (cons 0 0) was reclaimed at point 1 (or
> M> even earlier) or do they expect it to be done at some point after 2
> M> (i.e. when foo leaves lexical scope)?
>
> it's safe to reclaim it as soon as it's possible to prove that there is no
> way to reach it.
> however, i suspect most implementations will not bother to detect that that
> early.
If GC is run in a thread that can be activated at any time, then you
have no such assurance. If the last reference to an object is in a
machine register, and the thread overwrites it, then if GC is run
right after that machine instruction, the object is gone.
(message (Hello 'Kaz)
(you :wrote :on '(16 Feb 2007 12:34:14 -0800))
(
??>> it's safe to reclaim it as soon as it's possible to prove that there
??>> is no way to reach it. however, i suspect most implementations will
??>> not bother to detect that that early.
KK> If GC is run in a thread that can be activated at any time, then you
KK> have no such assurance. If the last reference to an object is in a
KK> machine register, and the thread overwrites it, then if GC is run
KK> right after that machine instruction, the object is gone.
i mean typically bindings are allocated on stack (which keeps it
referenced), aren't they?
also i think typically GC is not running in separate thread but is activated
by thread itself exactly in point of allocation. i.e. it tries to allocate
next object, sees it's low on stack and launches GC.
moreover, if you allow CPU registers to reference objects, if GC will be
running in a separate thread, it will _have_ to cooperate with other threads
running -- because it cannot read register contents of other threads itself,
and even if it can, if it's not conservative GC, it will not know semantics
of registers (is it int or ptr). thus, in this case it will be easier to
duplicate references in stack frames.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"?? ???? ??????? ?????")
On Feb 14, 4:10 pm, "Me" <···················@yahoo.com> wrote:
> I know this toy example doesn't really make a difference but imagine
> one where users can actually detect the difference (say pedantic
> examples involving finalizers, weak-refs, continuations, and/or
> exceptions).
Users who want good compilers have no right to be surprised by object
lifetime calculations that are based on actual variable liveness
rather than the abstract lifetime as related to the static scope. :)