GC improvements

GC improvements

[Ludovic Courtès]

Hi,

I did some profiling with the workload I described earlier[0].

When using the three patches I sent recently[*], around 35% of the
execution time is spent in memory management:

   %   cumulative   self              self     total           
  time   seconds   seconds    calls   s/call   s/call  name    
  28.10     16.63    16.63    41385     0.00     0.00  ceval
  18.02     27.29    10.66    32399     0.00     0.00  scm_i_sweep_card
   8.54     32.34     5.06  4729114     0.00     0.00  scm_cell
   5.11     35.37     3.03  2737955     0.00     0.00  scm_ilookup
   3.23     37.28     1.91     7086     0.00     0.00  scm_i_init_card_freelist
   2.96     39.03     1.75   383266     0.00     0.00  scm_gc_mark_dependencies
   2.64     40.59     1.56      657     0.00     0.01  scm_i_mark_weak_vector_non_weak

Commenting out explicit calls to `scm_gc ()' and `scm_i_gc ()' doesn't
make a big difference.

The workload I used is quite similar to what happens at startup time:
new objects are created, new symbols are defined, and that's it.  The
symbols created (and even the numbers created) are expected to stay
alive until the end of the program.  Thus, intuitively, one might say
that there is nothing to collect in this program, so no need to
mark/sweep all the time.

Therefore, my question is: how can we improve on this?

As I understand it, generational GC could help solve this.  However,
being unfamiliar with this, I fail to see how this could be integrated,
and how much work is required.

Thanks,
Ludovic.

[0] http://lists.gnu.org/archive/html/guile-devel/2005-12/msg00093.html

[*] Improved `scm_from_locale_symbol ()' + `guile-reader', fixed
    FREE_COUNT in `scm_i_sweep_card ()', fixed CELLS_COLLECTED in
    `scm_i_sweep_some_cards ()')


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

Re: GC improvements

[Han-Wen Nienhuys]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1722 bytes --]

In article <87slsnk9u0.fsf@laas.fr>,
Ludovic Courtès <ludovic.courtes@laas.fr> wrote:
>The workload I used is quite similar to what happens at startup time:
>new objects are created, new symbols are defined, and that's it.  The
>symbols created (and even the numbers created) are expected to stay
>alive until the end of the program.  Thus, intuitively, one might say
>that there is nothing to collect in this program, so no need to
>mark/sweep all the time.

I think that GUILE creates garbage as a side effect of evaluating
code. If think that nothing needs to be swept, try disabling GC during
startup, and see how well it performs memory-wise.

>Therefore, my question is: how can we improve on this?
>
>As I understand it, generational GC could help solve this.  However,
>being unfamiliar with this, I fail to see how this could be integrated,
>and how much work is required.

For startup time, I think the best (as in: quickest) would be undump a
previous run, instead of recalculating all the initialization on every
run. Not only does this save on GC time, it also bypasses all evaluation.
Isn't this what Emacs also does?

Personally, I think it is much more interesting to optimize for
efficiency on longer projects.

BTW, I propose that the GC yields are changed a bit. I've heard other
people comment that GUILE is dead slow compared to PLT Scheme. I've
investigated with one Boehm's GC benchmarks, and for this case it
turns out that increasing GC minimum yields sped GUILE up by a factor
1.5 or so.


Han-Wen


P.S. what's keeping back the GUILE 1.8 release?




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

1.8 [was: GC improvements]

[Andy Wingo]

Hi Han-Wen,

On Fri, 2005-12-23 at 11:29 +0000, Han-Wen Nienhuys wrote:
> P.S. what's keeping back the GUILE 1.8 release?

My guess:

1) Marius' time being eaten by work ;-)
2) Lingering GC bugs
3) Lack of a threadsafety audit (although it's tough to say how this
would affect API; e.g. it shouldn't hold back the release)

BTW, I just compiled guile-gnome against 1.7. Seems to run OK, but I get
a segfault in one of the test suites, deep in GC. And of course as I
noted it doesn't even build on x86-64. Will do some bisection when I'm
back from holidays.

Regards,
-- 
Andy Wingo
http://wingolog.org/



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

Re: 1.8

[Kevin Ryde]

Andy Wingo <wingo@pobox.com> writes:
>
> My guess:

4) Under debug-cell-accesses, goops.test is throwing

	Non-pair accessed with SCM_C[AD]R: `#<<class> <foo> b7baf270>'

but I don't know if that's benign in practice.


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

Re: GC improvements

[Ludovic Courtès]

hanwen@byrd.xs4all.nl (Han-Wen Nienhuys) writes:

> I think that GUILE creates garbage as a side effect of evaluating
> code. If think that nothing needs to be swept, try disabling GC during
> startup, and see how well it performs memory-wise.

I did try commenting out all calls to `scm_i_gc ()' and running my
workload again.  Actually, it doesn't make a big difference: a lot of
time is still spent in `scm_i_sweep_card ()', called from
`scm_i_sweep_some_cards ()' and friends.

> For startup time, I think the best (as in: quickest) would be undump a
> previous run, instead of recalculating all the initialization on every
> run. Not only does this save on GC time, it also bypasses all evaluation.
> Isn't this what Emacs also does?

Don't know, we'd have to investigate further.  Still, that wouldn't fix
our greedy-GC problem.

Thanks,
Ludovic.


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

Re: GC improvements

[Han-Wen Nienhuys]

Ludovic Courtès wrote:
> hanwen@byrd.xs4all.nl (Han-Wen Nienhuys) writes:
> 
> 
>>I think that GUILE creates garbage as a side effect of evaluating
>>code. If think that nothing needs to be swept, try disabling GC during
>>startup, and see how well it performs memory-wise.
> 
> 
> I did try commenting out all calls to `scm_i_gc ()' and running my
> workload again.  Actually, it doesn't make a big difference: a lot of
> time is still spent in `scm_i_sweep_card ()', called from
> `scm_i_sweep_some_cards ()' and friends.

the easiest way is to modify

   scm_gc_for_newcell()


so it directly passes to the

   scm_i_get_new_heap_segment (freelist, abort_on_error);

case

-- 
  Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen


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

Re: GC improvements

[Ludovic Courtès]

Hi Han-Wen,

Thanks for your input!

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

> the easiest way is to modify
>
>   scm_gc_for_newcell()
>
>
> so it directly passes to the
>
>   scm_i_get_new_heap_segment (freelist, abort_on_error);
>
> case

No, that won't have any impact because this very case is rarely
reached.

I checked this by adding two (static) counters to `scm_gc_for_newcell ()':
one that counts the number of calls, and one that counts the number of
non-EOL returns of the first `scm_i_sweep_some_segments ()' call.  The
ratio (still for the same workload) is _always_ very, very close to 1.

This is because `scm_i_sweep_some_segments ()' does not actually only
sweep segments: it sometimes (actually here, most of the time)
*initializes* them.  The reason is that it uses `scm_i_sweep_some_cards ()'
which in turn chooses whether to initialize or sweep depending on
whether the segment at hand is already initialized (SWEEPER is chosen
based on SEG->FIRST_TIME).

This interleaving of initialization and sweeping makes it pretty hard to
track exactly where fresh cells come from.  I guess one solution might
be to maintain a list of the uninitialized segments and pick cells
directly from there before actually sweeping.

To be continued...  Hopefully!  ;-)

Thanks,
Ludovic.


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

Re: GC improvements

[Ludovic Courtès]

Hi,

ludovic.courtes@laas.fr (Ludovic Courtès) writes:

> This interleaving of initialization and sweeping makes it pretty hard to
> track exactly where fresh cells come from.  I guess one solution might
> be to maintain a list of the uninitialized segments and pick cells
> directly from there before actually sweeping.

Thinking about it, this solution looks like the beginning of the
generational approach to GC: we'd define uninitialized segments (i.e.,
those whose FIRST_TIME field is true) as one generation, and the others
as another generation.

I think we could even have 3 segment generations:

1. The kids, i.e., the uninitialized segments;

2. The youngsters, i.e., segments recently initialized and where
   sweeping gave good results in the past;

3. The elderly, i.e., those for which sweeping has been unproductive for
   some time already.

Remarks:

* This is a very coarse approach to generational GC as it's done on a
  per-segment basis.  For this reason, it doesn't make sense to have
  more that 3 generations (due to fragmentation, each segment may
  include a variety of kids, youngsters, and elderly).  Even 3
  generations (instead of just 2) is a questionable approach.

  OTOH, even though there is fragmentation, I think it's reasonable to
  assume that some segments, those created and populated at startup
  time, will actually only contain elderly cells, whereas segments
  initialized during the life time of the program (especially for
  long-running or interactive applications) may be more fragmented and
  may be considered as "young".  Hence the intermediary generation.

  Additionally, I'm assuming that elderly segments cannot move back to
  the "youngsters" generation, which seems to be generally assumed in
  generational GC.

* This poor man's generational GC has the advantage of being quite easy
  to implement.  Basically, instead of having a single segment table as
  we have now, we'd have to maintain a set of three segment tables,
  which would not be too complicated it seems.

  In particular, it's much easier to implement than the per-cell
  generational GC, as proposed by Greg Harvey in
  http://home.thezone.net/~gharvey/guile/ggc-notes.txt .  It's also less
  intrusive: basically `scm_i_sweep_some_segments ()' is the only place
  where generations would be taken into account.  Of course, the outcome
  would certainly be better with a per-cell approach, but I'd expect the
  per-segment approach to yield a non-null benefit for a pretty low
  cost.


What do you think?  Are there flaws in this reasoning?  :-)

Thanks,
Ludovic.


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

Re: GC improvements

[Han-Wen Nienhuys]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1978 bytes --]

In article <87psn64tq5.fsf@laas.fr>,
Ludovic Courtès <ludovic.courtes@laas.fr> wrote:
>> This interleaving of initialization and sweeping makes it pretty hard to
>> track exactly where fresh cells come from.  I guess one solution might
>> be to maintain a list of the uninitialized segments and pick cells
>> directly from there before actually sweeping.

>* This poor man's generational GC has the advantage of being quite easy
>  to implement.  Basically, instead of having a single segment table as
>  we have now, we'd have to maintain a set of three segment tables,
>  which would not be too complicated it seems.
>
>  In particular, it's much easier to implement than the per-cell
>  generational GC, as proposed by Greg Harvey in
>  http://home.thezone.net/~gharvey/guile/ggc-notes.txt .  It's also less
>  intrusive: basically `scm_i_sweep_some_segments ()' is the only place
>  where generations would be taken into account.  Of course, the outcome
>  would certainly be better with a per-cell approach, but I'd expect the
>  per-segment approach to yield a non-null benefit for a pretty low
>  cost.

I don't get it. I thought the generational would save on the marking
phase. What's sweeping got to do with it?

>What do you think?  Are there flaws in this reasoning?  :-)

Yes; it's reasoning. In my experience, nice sounding theories and
approaches are usually meaningless. Programmers (including myself) are
notoriously bad at predicting performance characteristics. Why don't
you do some measurements before trying to design code?

I've tried "poor man's" optimizations before, and I always had to
conclude that optimizations introduced extra overhead, with a net loss
in performance.  that

If you want to have generational GC, I recommend to plug in Boehms GC
collector. MzScheme also does this with good results.



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