Path: utzoo!utgpu!watserv1!watmath!att!dptg!ulysses!andante!alice!pereira
From: pereira@alice.UUCP (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: GC triggering and stack limit checking by MMU hardware
Keywords: GC, stack, heap, MMU
Message-ID: <11079@alice.UUCP>
Date: 21 Jul 90 04:26:35 GMT
References: <1990Jul19.151524.22544@diku.dk> <3260@swi.swi.psy.uva.nl>
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs
Lines: 42

In article <3260@swi.swi.psy.uva.nl> jan@swi.psy.uva.nl (Jan Wielemaker) writes:
>The proposed schema is very simple to implement.  It provides
>dynamically growing stacks (to some limit, but on most modern machines
>this limit can be high as the virtual address space is large).  Expanding
>the stacks is almost for free.  On conventional systems a stack shifter
>needs to be implemented.  This is tiresome and shifting the stacks is
>an expensive operation.

I disagree on several counts:

1. The amortized cost of stack shifting, if the stack expansion and garbage-collection
scheduling factors are computed right, is in my experience trivial (<1% or runtime).
I wrote the first Prolog stack shifter, for DEC-10 Prolog, and once I got the
expansion factors right, no one ever complained about stack shifting costs.
I was also involved in designing and implementing the Quintus stack shifter,
which again has very low amortized costs because of properly chosen expansion
factors.

2. As I pointed out in an earlier message, it is not in general safe to rely
on being able to return from a segmentation violation in Unix. Even if it works
in your tests, it might fail for a violation occuring in particular processor
state, particularly if other aspects of the state (eg. page maps) are affected
by the signal function. Nothing in the OS specification guarantees that
segmentation violations can be returned from. And then there are OS bugs...

3. Very large (even if sparse) address spaces are not free, because with them
one gets into multilevel page tables and other address translation overheads.
In my experience, VM implementations are optimized for relatively small
and compact address spaces on various common machines. Large address spans can bring
out the worst in paging algorithms.


A well-designed bounds check mechanism costs relatively little,
is portable, and does not depend on the vagaries of machine and OS implementation.
The idea of using VM for bounds check has come up over and over again (we
considered it for DEC-10 Prolog in 1978, for example!), but the payoff
always seems mediocre compared with its complication, lack of portability
and sensitivity to OS bugs.

Fernando Pereira
AT&T Bell Labs, Murray Hill, NJ 07974
pereira@research.att.com