This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
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"))