lazy sweeping.

lazy sweeping.

[Han-Wen]

Here are some results of my lazy sweeping implementation:

Java tree benchmark 

 1.7.0:  
 time ~/usr/bin/guile -s  /tmp/GCBench.scheme.txt 

   user	2m20.350s
   sys	0m0.310s


 1.7.0 + newgc + lazy sweeping
 time ./libguile/.libs/lt-guile -s /tmp/GCBench.scheme.txt

   user	2m20.120s
   sys	0m0.240s

Nothing spectacular. But now checkout ... the startup time!
(this is the time for starting guile, and then pressing ^D)

	1.7.0:  
	time ~/usr/bin/guile

	user	0m0.170s
	sys	0m0.000s


	1.7.0 + newgc + lazy sweeping  
	user	0m0.090s
	sys	0m0.010s


The lazy sweeping approximately halves the startup time of GUILE. I
consider the old GC beat; when can we start integrating this? 

  http://www.cs.uu.nl/~hanwen/public/guile/lazy-sweeping.tar.gz

Implementation notes:

 * Lazy sweeping sounds like a feature, but it actually leads to
   simpler, more natural code than the old sweeping code.

 * Various debug functions (mainly those having to do with checking
   the freelist) become moot; I removed them.

 * I removed SCM_FREECELL_P(). It's meaning has become ambiguous.

 * Lazy sweeping naturally complements multi-threaded use: whenever a
   thread runs out of free cells, we can simply sweep a few (say 512)
   cells, and return that for private use by that thread. 

 * Et ceteram censeo GUILE 1.6 releasem esse.

-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl   |   http://www.cs.uu.nl/~hanwen 

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Michael Livshin]

Han-Wen <hanwen@cs.uu.nl> writes:

> Here are some results of my lazy sweeping implementation:
>
> [ snippo ]
>
>  * Lazy sweeping sounds like a feature, but it actually leads to
>    simpler, more natural code than the old sweeping code.

did you consider various finalizations?  like closing file descriptors
of dead ports, sort of fing.

if you just lazy-sweep naively, some external resources may never get
freed.

-- 
Every program is a part of some other program and rarely fits.
                -- Alan Perlis



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Tom Lord]

       Nothing spectacular. But now checkout ... the startup time!
       (this is the time for starting guile, and then pressing ^D)


This is not a very good measure of effective start-up time in
SCM-based (incremental graph translation) Schemes.  Odds are you have
a lot of untranslated code in that image, and when I add my
application code, you'll have even more untranslated code.  Substitute
anything useful for that ^D, and the real costs will start to become
more apparent, especially if your application involves long-running
processes.

SCM performs pretty damn well if what you want is a fast
edit-rerun-debug cycle for CAE and symbolic math tasks, especially
with the special GC for environments.  It's also great if you have an
`eval'-intensive application.

Unexec helps, though I've noted substantial qualitative differences
between unexec _before_ running through most execution paths
vs. _after_: incremental translation in action.

Heck, you want _really_ fast start up time?  Read the first line of
input to Guile before doing _anything_ else, doing a short-circuit 
exit if the first line is just EOF.  That'll be really fast ;-)


-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen Nienhuys]

guile@cmm.kakpryg.net writes:
> > [ snippo ]
> >
> >  * Lazy sweeping sounds like a feature, but it actually leads to
> >    simpler, more natural code than the old sweeping code.
> 
> did you consider various finalizations?  like closing file descriptors
> of dead ports, sort of fing.
> 
> if you just lazy-sweep naively, some external resources may never get
> freed.

Ah, good idea. You mean when exiting GUILE completely? I'll add that.

-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl    | http://www.cs.uu.nl/~hanwen/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Michael Livshin]

Han-Wen Nienhuys <hanwen@cs.uu.nl> writes:

> guile@cmm.kakpryg.net writes:
>> 
>> did you consider various finalizations?  like closing file descriptors
>> of dead ports, sort of fing.
>> 
>> if you just lazy-sweep naively, some external resources may never get
>> freed.
>
> Ah, good idea. You mean when exiting GUILE completely? I'll add
> that.

er.  perhaps I was confused.

if I remember correctly, Guile has some logic to cope with suddenly
running out of file descriptors: it calls GC in the hope that some
port objects are unreachable.

I guess now you don't have to nesessarily do a full GC right away,
instead you may want to finish the sweep first and see if that helps,
and only do a new GC if finishing the sweep haven't helped.  hmm.  so
that's not as fiddly as I thought, and probably works as it is.

ditto for malloced memory, I guess.

sorry.

-- 
Paranoid schizophrenics outnumber their enemies at least two to one.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen Nienhuys]

guile@cmm.kakpryg.net writes:
> if I remember correctly, Guile has some logic to cope with suddenly
> running out of file descriptors: it calls GC in the hope that some
> port objects are unreachable.
> 
> I guess now you don't have to nesessarily do a full GC right away,
> instead you may want to finish the sweep first and see if that helps,
> and only do a new GC if finishing the sweep haven't helped.  hmm.  so
> that's not as fiddly as I thought, and probably works as it is.
> 
> ditto for malloced memory, I guess.

Hrm. I'll have to add some more logic then -- we want to be able to
completely clean the heap, but not advance the "free mem starts here"
pointer. What would be the right behavior: doing a full sweep, or a
mark + full sweep? Or maybe just both (first the full sweep, if it
doesn't yield enough: the full mark.) 

Do you know where that function is?   I can't seem to find how a new
port is added. Oh wait. This goes through scm_must_malloc. Ok.

-- 
Han-Wen Nienhuys   |   hanwen@cs.uu.nl    | http://www.cs.uu.nl/~hanwen/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Michael Livshin]

Han-Wen Nienhuys <hanwen@cs.uu.nl> writes:

> guile@cmm.kakpryg.net writes:
>> if I remember correctly, Guile has some logic to cope with suddenly
>> running out of file descriptors: it calls GC in the hope that some
>> port objects are unreachable.
>> 
>> I guess now you don't have to nesessarily do a full GC right away,
>> instead you may want to finish the sweep first and see if that helps,
>> and only do a new GC if finishing the sweep haven't helped.  hmm.  so
>> that's not as fiddly as I thought, and probably works as it is.
>> 
>> ditto for malloced memory, I guess.
>
> Hrm. I'll have to add some more logic then -- we want to be able to
> completely clean the heap, but not advance the "free mem starts here"
> pointer. What would be the right behavior: doing a full sweep, or a
> mark + full sweep? Or maybe just both (first the full sweep, if it
> doesn't yield enough: the full mark.)

that's what I've meant, yes.  however, it's just as optimization, and
the occurences where it might theoretically matter (system heap
exhaustion or running out of file descriptors) could probably be
considered to be rare enough.

as long as you take care to finish the last sweep before marking, you
should be fine, correctness-wise.

-- 
REALITY is an illusion that stays put.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen Nienhuys]

guile@cmm.kakpryg.net writes:
> >> ditto for malloced memory, I guess.
> >
> > Hrm. I'll have to add some more logic then -- we want to be able to
> > completely clean the heap, but not advance the "free mem starts here"
> > pointer. What would be the right behavior: doing a full sweep, or a
> > mark + full sweep? Or maybe just both (first the full sweep, if it
> > doesn't yield enough: the full mark.)
> 
> that's what I've meant, yes.  however, it's just as optimization, and
> the occurences where it might theoretically matter (system heap
> exhaustion or running out of file descriptors) could probably be
> considered to be rare enough.
> 
> as long as you take care to finish the last sweep before marking, you
> should be fine, correctness-wise.

at first I didn't, and it barfed all over the place. That is neat
about working with the GC itself. Any error will blow up grotesquely:
that makes debugging a lot easier.

by-the-by: anyone for a quick hint how to setup a C catch handler from C?  

-- 
Han-Wen Nienhuys   |   hanwen@cs.uu.nl    | http://www.cs.uu.nl/~hanwen/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Mikael Djurfeldt]

Han-Wen wrote:

>Here are some results of my lazy sweeping implementation:
>
>[...]
>
>The lazy sweeping approximately halves the startup time of GUILE. I
>consider the old GC beat; when can we start integrating this? 
>
Nice! However, be careful about benchmarking information. When hacking
the evaluator, I've noticed performance changes up to 30% just by changing
the textual order of functions within a compilation unit...

> * Lazy sweeping naturally complements multi-threaded use: whenever a
>   thread runs out of free cells, we can simply sweep a few (say 512)
>   cells, and return that for private use by that thread.
>
[Without having studied your code:] Is it enough to lock one mutex for the
joint apparatus of sweeping and marking before doing the lazy sweep
in order to avoid interference between threads?  (One would not want to
stop all threads before sweeping 512 cells...)

Best,
M




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen Nienhuys]

djurfeldt@nada.kth.se writes:
> > * Lazy sweeping naturally complements multi-threaded use: whenever a
> >   thread runs out of free cells, we can simply sweep a few (say 512)
> >   cells, and return that for private use by that thread.
> >
> [Without having studied your code:] Is it enough to lock one mutex for the
> joint apparatus of sweeping and marking before doing the lazy sweep
> in order to avoid interference between threads?  (One would not want to
> stop all threads before sweeping 512 cells...)

I think that the only the allocation has to be locked, i.e. if two
threads run out of space at the same time, only one can collect new
cells. For marking, all threads should be stopped.

-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl    | http://www.cs.uu.nl/~hanwen/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen Nienhuys]

lord@regexps.com writes:
> 
> 
>        Nothing spectacular. But now checkout ... the startup time!
>        (this is the time for starting guile, and then pressing ^D)
> 
> 
> This is not a very good measure of effective start-up time in
> SCM-based (incremental graph translation) Schemes.  Odds are you have
> a lot of untranslated code in that image, and when I add my

My intent was not measuring the performance of eval() and friends,
simply the act of reading in code into GUILE. If the new GC can be
attributed for the improvement, then it seems that reading in the
files generates a lot of garbage. The cost of that collecting that is
now smeared out over future allocations.


-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl    | http://www.cs.uu.nl/~hanwen/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Han-Wen]

guile@cmm.kakpryg.net writes:
> >  * Lazy sweeping sounds like a feature, but it actually leads to
> >    simpler, more natural code than the old sweeping code.
> 
> did you consider various finalizations?  like closing file descriptors
> of dead ports, sort of fing.
> 
> if you just lazy-sweep naively, some external resources may never get
> freed.

oh, btw, I noticed that only ports are flushed on exit of GUILE (gc.c
- onexit ()). The manual talks about "freeing resources" for the smob
free function. I believe that is inaccurate: free is only for freeing
memory. Stuff like closing files should happen in an explicitly called
function, for the free() might never get called at then end.

-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl   |   http://www.cs.uu.nl/~hanwen 

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: lazy sweeping.

[Michael Livshin]

Han-Wen <hanwen@cs.uu.nl> writes:

> oh, btw, I noticed that only ports are flushed on exit of GUILE (gc.c
> - onexit ()). The manual talks about "freeing resources" for the smob
> free function. I believe that is inaccurate: free is only for freeing
> memory. Stuff like closing files should happen in an explicitly called
> function, for the free() might never get called at then end.

why not free resources in smob free() too?  think of it as of a safety
net.

but of course freeing external resources explicitly is preferable.

-- 
A CONS is an object which cares.
                -- Bernie Greenberg.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel