Re: [MLton] tuning up mlton gc

On Wed, Jul 23, 2014 at 10:03 AM, Matthew Fluet <[email protected]> wrote:
> ---------- Forwarded message ----------
> From: Bernard Berthomieu <[email protected]>
> Date: Mon, Jul 21, 2014 at 10:44 AM
> Subject: tuning up mlton gc
> To: Matthew Fluet <[email protected]>, Stephen Weeks <[email protected]>
>
> We are using mlton at our place to implement model-checking tools.
> We are quite happy with it, but the cost of garbage collection in our
> applications always bothered me. Our applications typically generate
> a lot of data, a large percentage of which is persistent (state spaces).
> I guess this is the kind of applications that would most benefit from
> generational garbage collection.

Agreed that generational garbage collection makes sense when there is
a large amount of data that is live over many garbage collections.
This is especially true for the copying collection, since the time for
a copying collection is proportional to the amount of live data.

> I observed that mlton does not start with generational gc, but rather
> with a simple two-space copying, possibly switching later to generational,
> upon some conditions. I could not find in the mlton sources a simple
> way to force generational garbage collection from the start, but I've
> found that some gc constants could be tuned by the user (though these
> options are not documented).
> After some experiments, I found that setting live-ratio to 4.0,
> rather than the default 8.0, consistently resulted in a significant
> speedup of my applications.

After each garbage collection, the decision about whether or not to
use a minor collection (i.e., to use generational garbage collection)
for the next garbage collection is computed by:
  https://github.com/MLton/mlton/blob/on-20130715-release/runtime/gc/gc_state.c#L71-L99

>From this, you can observe that the runtime system options that
directly control whether or not to use generational collection are:
 * nursery-ratio  (default: 10.0)
 * copy-generational-ratio  (default: 4.0)
 * mark-compact-generational-ratio  (default: 8.0)

Setting live-ratio to 4.0 indirectly forces generational garbage
collection because it tends to make the following true:
  (float)h->size / (float)s->lastMajorStatistics.bytesLive <=
s->controls.ratios.copyGenerational
This is because live-ratio controls the desired size of the heap
relative to the live data after a major garbage collection; that is,
after each major garbage collection, the heap is resized so as to
satisfy:
  h->size == bytesLive * s->controls.ratios.live
(subject to other constraints such as minimum, maximum, and/or fixed
heap size, RAM size, etc. and skipping resizing if the current size is
close enough).

So, you may find it equally effective to set copy-generational-ratio
to 8.0 (or higher).  This would have the benefit of using a larger
heap, while still forcing minor collections.

The other condition that depends upon runtime options is:
  (((float)(h->size - s->lastMajorStatistics.bytesLive) /
(float)nurserySize) <= s->controls.ratios.nursery
The left-hand-side of the comparison is computing the ratio of the
nurserySize after the last major garbage collection to the current
nurserySize (presumably after a minor collection).  The default
setting of nursery-ratio to 10.0 says to switch back to a major
garbage collection after the nursery has been reduced to one-tenth of
its original size.  So, setting nursery-ratio to a higher value would
stay with minor collections longer.

Given the analysis above, it would seem that with the default values
of live-ratio 8.0 and copy-generational-ratio 4.0, the runtime system
would tend not to switch over to generational garbage collection when
there is plenty of available RAM, because (float)h->size /
(float)s->lastMajorStatistics.bytesLive would be approximately 8.0
(the live-ratio value) and therefore not <= 4.0 (the
copy-generational-ratio).  The runtime system would switch over to
generational garbage collection when the desired heap size does not
fit in RAM and (float)h->size /
(float)s->lastMajorStatistics.bytesLive falls below the live-ratio
value.

I will note that these conditions don't seem to be capturing your
scenario, where there is a large proportion of data that is preserved
across multiple major garbage collections.  I think that the intuition
(at the time the generational gc was implemented and the default
ratios set) was that a program would likely be running short on RAM if
it were performing many garbage collections.  Of course, RAM has
gotten cheaper and I think that it is less often that the runtime
system cannot satisfy the desired heap size.

In any case, the collection of runtime controls and their effects are
fairly complicated.  It would be very nice to review, rationalize, and
refactor the various controls.

> My understanding is that decreasing live-ratio prompts generational
> garbage collection to occur earlier, which greatly cuts gc cost here.
> The attached files show gc-summary for the two values of this option
> on a typical run (in 32 bit).

It certainly forces the generational garbage collection to occur
earlier, but that isn't necessarily always effective:

[mtf@fenrir tmp]$ ./DLXSimulator @MLton gc-summary -- 100 > /dev/null
GC type time ms number  bytes      bytes/sec
------------- ------- ------- --------------- ---------------
copying  3,783  1,837  3,531,238,728    933,449,287
mark-compact      0      0              0              -
minor      0      0              0              -
total time: 16,867 ms
total GC time: 3,826 ms (22.7%)
max pause time: 8 ms
total bytes allocated: 42,872,283,376 bytes
max bytes live: 3,174,432 bytes
max heap size: 25,485,312 bytes
max stack size: 1,408 bytes
num cards marked: 0
bytes scanned: 0 bytes
bytes hash consed: 0 bytes
[mtf@fenrir tmp]$ ./DLXSimulator @MLton gc-summary live-ratio 4.0 --
100 > /dev/null
GC type time ms number  bytes      bytes/sec
------------- ------- ------- --------------- ---------------
copying 12,194  6,780 10,864,430,656    890,965,319
mark-compact      0      0              0              -
minor  3,142  4,082  1,990,329,704    633,459,493
total time: 31,822 ms
total GC time: 16,805 ms (52.8%)
max pause time: 9 ms
total bytes allocated: 42,879,154,136 bytes
max bytes live: 3,174,504 bytes
max heap size: 12,738,560 bytes
max stack size: 1,408 bytes
num cards marked: 4,568
bytes scanned: 6,393,040 bytes
bytes hash consed: 0 bytes
[mtf@fenrir tmp]$ ./DLXSimulator @MLton gc-summary
copy-generational-ratio 8.0 -- 100 > /dev/null
GC type time ms number  bytes      bytes/sec
------------- ------- ------- --------------- ---------------
copying  3,892  1,829  3,519,827,208    904,374,922
mark-compact      0      0              0              -
minor     32     27     20,218,520    631,828,750
total time: 17,219 ms
total GC time: 3,979 ms (23.1%)
max pause time: 8 ms
total bytes allocated: 42,872,270,344 bytes
max bytes live: 3,174,504 bytes
max heap size: 25,485,312 bytes
max stack size: 1,408 bytes
num cards marked: 29
bytes scanned: 42,024 bytes
bytes hash consed: 0 bytes
[mtf@fenrir tmp]$ ./DLXSimulator @MLton gc-summary
copy-generational-ratio 16.0 -- 100 > /dev/null
GC type time ms number  bytes      bytes/sec
------------- ------- ------- --------------- ---------------
copying  1,454    471  1,294,143,408    890,057,331
mark-compact      0      0              0              -
minor 14,896  7,232  9,906,411,512    665,038,367
total time: 29,547 ms
total GC time: 16,460 ms (55.7%)
max pause time: 8 ms
total bytes allocated: 42,870,305,408 bytes
max bytes live: 3,174,936 bytes
max heap size: 25,485,312 bytes
max stack size: 1,408 bytes
num cards marked: 7,702
bytes scanned: 11,444,640 bytes
bytes hash consed: 0 bytes


> 1. Do you agree with this analysis of the improvement ?

Yes.

> 2. Are there some way other than playing with ratios (which could
> have some undesired effects as well) to have mlton always use
> generational gc ? I don't mind having to recompile mlton or the runtime.
>
> 3. Would there be any drawbacks to do so ?

You could recompile the runtime with FORCE_GENERATIONAL set to TRUE
(in runtime/gc/debug.h), but that would effect all programs linked to
that recompiled runtime.  I think that adjusting
copy-generational-ratio is the simplest and safest solution.

------------------------------------------------------------------------------
Want fast and easy access to all the code in your enterprise? Index and
search up to 200,000 lines of code with a free copy of Black Duck
Code Sight - the same software that powers the world's largest code
search on Ohloh, the Black Duck Open Hub! Try it now.
http://p.sf.net/sfu/bds