Re: tools to make non-conservative GC feasible.

[James Rauser <rausejme@ina.de>]

Mikael Djurfeldt wrote:
> 
> "Perry E. Metzger" <perry@piermont.com> writes:
> 
> > The reason we like "conservative collectors" is because we can be lazy
> > while programming and not worry about what does and doesn't have to be
> > visible to the collector.
> 
> Isn't there one more issue?  I'm not at all certain that a precise
> collector would be more efficient.  With conservative GC you have to
> scan the stack once per GC.  With precise GC, you have to do
> bookkeeping (both registering and off-registering) for every single
> SCM variable occuring on the stack between GC:s...
> 
> /mdj

I lurk on this list because I'm also interested in language
implementations, having spent the last six years building an
(as yet proprietary, but soon-to-be GPL'd) interpreter for OEL,
a C++-like language but with dynamic features of scheme.
OEL is implemented in C++, and the original system used a C++
smart-pointer class to register stack variables (a sketch below,
done from distant, bad memories...).

class ObjectVar : GCRoot {
	Object *p;
	ObjectVar *prev;
	static ObjectVar *stackroots;
public:
	ObjectVar( Object *_p = 0 ) {
		p = _p; prev = stackroots; stackroots = this;
	}
	~ObjectVar() {
		stackroots = prev;
	}
	operator Object *() { return p; }
	Object *operator ->() { return p; }
}

To use it, all programmers had to do was remember to declare stack
variables as "ObjectVar" instead of "Object *".  Sounds simple.

It worked okay, as long as the programmers writing C++ code for
kernel extensions and such were constantly aware of whether a pointer
had to be declared Object* or ObjectVar.  It was impossible to use
ObjectVar consistently for *all* local variables, because then
for example every procedure argument and temporary had to be
constructed and deconstructed, and return values don't have the
right semantics.  If you were careful *not* to use ObjectVar in
critical paths, e.g., allocating environment frames where you knew
that a stack variable was not the only link to an object,
performance overhead was acceptable but not insignificant.

But boy oh boy, if you ever forgot an ObjectVar were you *did*
need it, you had a bug that could lurk literally for *years*,
waiting for a GC to get triggered at exactly the right (or wrong)
moment.  Even if the bug did get triggered during testing, finding
it was often a exercise that lasted a day or two, and could often
only be done by someone (me!) with an intimate knowledge of the
GC system.  Mere mortals ;) wanting only to write simple C++
extensions didn't have a chance...

We switched to conservative stack scanning (precise everywhere
else) about 2 years ago and never looked back.  I've not yet had
a really bad experience in "real" code with bogus garbage getting
retained from the stack, but I do have one "obfuscated OEL" program
that gets bitten badly.  Depending on the C++ compiler and platform,
it needs either 1.5 MB or 20 MB to compute the first 500 prime
numbers using totally ridiculous, deeply recursive code.  The
real problem lies in temporary stack locations introduced by the
compiler in the byte-code switch.  Under Linux for example,
GCC 2.7.2.1 screws up badly, but egcs-1.1b doesn't.  Some compilers
(DEC cxx and IBM xlC in particular) allocate stack temporaries
like crazy, but aren't smart enough to determine that their
lifetimes are disjunct, resulting in stack frames of up to several
hundred words, littered with temporary results that in (non-tail)
recursive programs all get retained.  This kind of behavior worries
me, but not enough to try to go back to precise stack marking.

(A scheme version of the prime-number script is attached.  Guile 1.2
under SOLARIS does okay.  Don't laugh, its a translation from the
original python, into OEL, and then into scheme.  I'm not a scheme
programmer.)

Jim

-- 
===================================================================
James S. Rauser                                     rausejme@ina.de
INA Werk Schaeffler KG/Abt. KOS3                  +49 9132 82 32 43
Industriestrasse 1-3                  91074 Herzogenaurach, Germany


(debug-disable `debug)
(debug-disable `trace)
(debug-set! stack 20000)

(define reduce
  (lambda (f lst val)
    (if (null? lst)
	val
	(reduce f (cdr lst) (f val (car lst))))))

;;; call f until it returns #f, collect results
(define collect0
  (lambda (f)
    (reverse (let loop ((rslt `()) (val (f)))
               (if val
                   (loop (cons val rslt) (f))
                   rslt)))))

;;; append lst to itself n times
(define list-mul
  (lambda (lst n)
	(let loop ((rslt `()) (remain n))
	  (if (<= remain 0)
		  rslt
		  (loop (append lst rslt) (- remain 1))))))

;;; Return a function that produce integers from "start" to "stop"
;;; by step, then returns Nil.
(define range
  (lambda (start stop step)
    (let ((val (- start step)))
      (if (< step 0)
          (lambda ()
            (if (<= val stop)
                #f
                (begin (set! val (+ val step)) val)))
          (lambda ()
            (if (>= val stop)
                #f
		(begin (set! val (+ val step)) val)))))))

;;; Goofy not-equal predicate, which returns either #f or the right operand.
(define !=
  (lambda (x y)
    (if (not (eqv? x y))
      y
      #f)))

;;; here's where the obfuscated stuff starts, original Python code:
;;;
;;; p=lambda n,s=2,np=lambda s,f:reduce(lambda x,y:x and y,map(lambda
;;;   x,y:x%y,[s+1]*(s/2),range(2,s/2+2)))and s+1or f(s+1,f
;;;   ):n>0and[s]+p(n-1,np(s,np))or[]

(define np
  (lambda (s f)
    (if (reduce (lambda (x y) (and x y))
;;; Variant 1:
;;;	        (map (lambda (x y) (not (= 0 (remainder x y))))
;;;                  (list-mul (list (+ s 1)) (quotient s 2))
;;;		     (collect0 (range 2 (+ 1 (quotient s 2)) 1)))
;;; Variant 2:
		(map (let ((r (range 2 (+ 1 (quotient s 2)) 1)))
                       (lambda (x) (not (= 0 (remainder x (r))))))
                     (list-mul (list (+ s 1)) (quotient s 2)))
;;; 
                #t)
        (!= 0 (+ s 1))
        (!= 0 (f (+ s 1) f)))))

(define p
  (lambda (n s np)
    (if (> n 0)
        (cons s (p (- n 1)
                   (np s np)
                   np))
	'())))


(let ((t0 (get-internal-run-time))
      (rslt (p 500 2 np))
      (t1 (get-internal-run-time)))
  (display rslt)
  (display "\n")
  (for-each (lambda (x) (display x) (display "\n")) (gc-stats))
  (display "\nUser time: ")
  (display (/ (- t1 t0) internal-time-units-per-second))
  (display "\n"))