Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!mailrus!ames!uhccux!virtue!comp.vuw.ac.nz!munnari.oz.au!metro!cluster!andrewt
From: andrewt@cs.su.oz (Andrew Taylor)
Newsgroups: comp.lang.prolog
Subject: Re: GC triggering and stack limit checking by MMU hardware
Keywords: GC, stack, heap, MMU
Message-ID: <1113@cluster.cs.su.oz>
Date: 25 Jul 90 02:08:28 GMT
References: <1990Jul19.151524.22544@diku.dk> <3260@swi.swi.psy.uva.nl> <11079@alice.UUCP>
Sender: news@cluster.cs.su.oz
Reply-To: andrewt@cluster.cs.su.oz (Andrew Taylor)
Organization: Basser Dept of Computer Science, University of Sydney, Australia
Lines: 55

In article <11079@alice.UUCP> pereira@alice.UUCP () writes:
>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.

I've been working on native code compilation for the MIPS architectures.
Even if you can afford to keep the a register for each stack limit,
The saving in execution time from moving checking to hardware can be at
least 20%. How you assess such a gain is dependant on your aims. My aim
is high performance and I'll go to great lengths for a 20% gain.

A demand for high performance may be rare yet in the Prolog world but
it isn't elsewhere, to quote John Mashey (from MIPS) -
"we've got customers who will commit vile acts for another ten percent"

Returning from a segmentation violation isn't a problem on the MIPS
nor on most RISCs I expect. I don't fully understand remark (3) but
I can't see how having 5 address regions instead of 3 will cause poor
VM performance. I'm more worried about multiple stacks causing poor cache
performance because of conflicts.

Invoking the garbage collector is a problem with hardware limit checking
because the stacks are likely not to be in a consistent state when an
exception occurs. One possibility, which I believe the ECRC's Sepia system
uses?, is for the exception routine to set a global flag which is checked
at CALL ports and the garbage collector invoked if it is set. This brings back
some of the costs which we were trying to avoid.

Its possible if all stack data words are tagged that a robust garbage collector
could operate with inconsistant stacks. If this can be made to work
and having all stack data tagged is not too onerous then this is the go.

Alternatively on the MIPS the exception could invoke the garbage collector
which simulates instruction execution until an instruction is reached where
the stacks are known to be consistant (e.g a call instruction). This will
definitely involve getting your hands dirty but I believe its feasible.

Andrew