GUILE GC -- Write barrier for vectors

[hanwen]

Hi y'all,

I've recently benchmarked LilyPond for large scores, and to my
astonishment, I found that a large proportion of the time that Lily
runs, it spends doing GC. It might very well be that LilyPond is not
handling memory efficiently. Tips on improving this are welcome: in
large runs, lilypond allocates 30 to 300k smob objects, which probably
require a 20 to 50 cells each; most of these cells rarely change --
they are data representation, not runtime (i.e. often changing) data,
at least that is what I think: this particular run has cells-marked =
44M, cells-swept = 60M, meaning that 75% of the cells are not garbage,
right?

Linked against 1.7.0 without-threads, lily uses approximately 20% of
its time in GC on a 400 mhz PII/SDRAM. In another instance, the same
compile with lilypond linked against 1.5.6 on a 1Ghz PIII/DDR RDRAM,
uses approximately 50% of the total running time (!) for GC'ing.

Can anyone comment on the difference in running times?  I didn't see
much in the changelog that could explain this difference.  Could it be
that there is some anomaly that causes the timings to be skewed on the
fast machine? The total speed increase going from the 400mhz machine
to the 1ghz is consistent with the clock freqs.

Can anyone comment on how to improve the performance?

In any case, it seems that there is room for improvement on the GUILE
side, and one of these would be generational GC.

My plan was to have a generation counter for each CARD, and increase
that counter when no garbage was found during a sweep. When a card is
older than a certain threshold, all data in it is assumed to be live
and marked already.  Mutators (SETCDR, SET_VECTOR_ELT, etc.) reset the
generation counter of a card to 0.

Also, smobs and maybe some other types (which ones? structs?), are
always assumed to have been changed, since they are outside of GC's
control. It would probably be best to allocate them from a different
pool so that they won't poison the normal generations, but that would
require a slight extension of the GUILE API.

Of course: I don't know much about GC, but this is only a crude
try. My hope is that --when CARDS are small enough-- they will fill up
with "static" data that doesn't change all the time.

As a prelude, I tried to add a "soft" write barrier to the vector
code, by returning a const* in SCM_VELTS, and fixing where it goes
wrong. The cell codes already have this type of write barrier. I then
tried to fix up the remaining parts of the code. This is required by
any gen GC code, IIRC.

The patch is on
http://www.cs.uu.nl/~hanwen/public/software/guile-vector-wb, it is
against 1.7 CVS, checked out friday night.

* Print_state uses some kind of stack. This is a highly mutable thing,
right?

* Which other object types require a write barrier? eg. the subroutine
table, ports, structs?

* I introduced the SCM_VECTOR_SET macro, ie

        SCM_VECTOR_SET(vec,idx,value);

must be used for assignment.

* Direct write access to a vector must be done through the macro
SCM_WRITABLE_VELTS.

* I ran a GC test just to verify that it was working, but I would
really like to run the test-suite; I think that the following is a
disgrace:

        blauw:~/usr/src/guile/guile-core$ make -C test-suite/ test
        make: Entering directory 
`/home/hanwen/usr/src/guile/guile-core/test-suite'
        make: *** No rule to make target `test'.  Stop.
        make: Leaving directory 
`/home/hanwen/usr/src/guile/guile-core/test-suite'
        blauw:~/usr/src/guile/guile-core$ grep -i test-suite HACKING README  
BUGS 
        blauw:~/usr/src/guile/guile-core$ make test
        make: *** No rule to make target `test'.  Stop.

after some twiddling, the following command does something. It remains unsure 
whether this is
good or a bad result:

        blauw:~/usr/src/guile/guile-core$ libguile/.libs/lt-guile -e main -s 
test-suite/guile-test 
        ERROR: In procedure lstat:
        ERROR: No such file or directory: "/home/hanwen/bogus-path/test-suite"
        blauw:~/usr/src/guile/guile-core$ echo $?
        2

* Will this patch be integrated into CVS?  The FSF already has
  disclaimers for me.

* Et ceteram censeo GUILE 1.6 releasem esse


-- 

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