Better compaction heuristic

[damiendoligez]

Compaction is triggered when the current memory overhead becomes too large. This can happen in two cases:

• when fragmentation makes a lot of memory unallocatable
• when the live data has shrunk a lot
  In both cases, compacting the heap is a good idea.

Currently, we trigger the compaction based on an indirect computation of the overhead. In practice, this computation is noisy and the estimate is often way off. In this case, the compact_heap_maybe function will force a nonincremental major GC (a necessary first step for compaction) then get the actual overhead (easy to measure because the heap is now clean) and notice that the actual overhead is much lower than the estimate, and will give up on the compaction.

A better estimate of the overhead leads to fewer of these spurious major collections.

In this PR, our better estimate is simply a precise measurement of the overhead at the end of the previous cycle.

How much better is it? That depends on your program, of course. Here are the results from a few entries of the sandmark suite. On the left the old estimate: a plot of the actual overhead (y-axis) against the estimate (x-axis); on the right the new estimate: a plot of the current overhead (y-axis) against the previous cycle's overhead (x-axis). The closer to the diagonal, the better.

Note that this is comparing the two estimates, but the program is still using the old one.

We start with well-behaved programs:

• coq
  
  Note the outliers on the x=5000 line: they are actually at 1 million and were clipped to make the graph readable. In these cases, the estimated value is infinite.
• cubicle
  
  In this case, compaction is never triggered. Nevertheless, the new estimate looks much better.

We also have some programs with a less-standard use of memory:

• levinson-durbin
  
  This is numerical computation. The allocation pattern is quite different from coq or cubicle. The old estimate is always wrong: lots of points are estimated at 0 when the actual overhead is more than 1000 and would justify a compaction, while some estimates are at 1000000 (again, clipped at 5000) while the actual overhead is low. The new estimate is not perfect but still much better than the old.
• pidigits5
  
  This is mostly out-of-heap data (zarith) and nothing in the heap. This program has unusual behavior: it alternates between major GC and compaction, which explains the strange shape of the graph on the right. The new estimate looks better, but doesn't necessarily behave much better.

[gasche]

You have nice visualization for the accuracy of the heuristic, but no data on the impact on performance. Are you planning to report on this later/separately?

[gasche]

Below you have:

      previous_overhead =
        100.0 * (heap_wsz_at_cycle_start - marked_words) / marked_words;

I believe that both are correct, but it would be nice to make the two definitions easier to compare with simple refactorings.

{
  free_words = caml_fl_cur_wsz;
  live_words = Caml_state->stat_heap_wsz - caml_fl_cur_wsz;
  current_overhead = 100 * free_words / live_words;
}

{
  free_words = heap_wsz_at_cycle_start - marked_words;
  live_words = marked_words;
  current_overhead = 100 * free_words / live_words;
}

[gasche]

Maybe a silly question: in the version below you defend against division-by-zero but not here. Is there a reason for the difference? (Division-by-zero occurs when no words are live anymore, I don't know how it could happen in practice.)

[damiendoligez]

Marking this as WIP because @lpw25 pointed out to me that I should be able to avoid the extra instruction in the inner loop of mark_slice and @stedolan thinks it could make a noticeable difference because of register pressure. New commit coming soon.

[damiendoligez]

@gasche: here's the performance impact. I've used 4.11.1 with best-fit as the baseline, and a subset of sandmark (eliminating the benchmarks that don't do any compaction).

Time (lower is better):

I re-ran the benchmark to get an idea of the noise level:

I'd say everything is noise except the improvement for pidigits and zarith.

Maximum heap size (Iower is better):

Note that spectralnorm has a tiny heap (only one chunk in the baseline) and what happens is a kind of quantization error: the compaction reduces the size of the heap, which then needs to increase and gets larger than the baseline.

Two things I find a bit surprising:

• most benchmarks do fewer compactions, but the two that benefit most (pidigits and zarith) get better results by doing a lot more compactions.
• the levinson-durbin benchmark manages to do 2000 major GCs and 700 compactions in less than 3 seconds. Of course its heap is small, but still.

Raw data:

name	time (base)	time (new)	major coll (base)	major coll (new)	compactions (base)	compactions (new)
chameneos_redux_lwt.600000	1.71	1.71	204	201	2	2
cpdf.scale	10.86	11.50	27	28	1	0
cpdf.squeeze	13.64	13.20	32	32	1	0
durand-kerner-aberth.	0.11	0.12	85	83	2	2
kb.	3.02	2.98	276	252	27	2
kb_no_exc.	1.81	1.79	206	195	13	1
levinson-durbin.	2.57	2.58	2125	1906	708	635
naive-multilayer.	3.15	3.24	123	141	2	2
pidigits5.10_000	5.02	3.14	3137	2996	1045	1354
revcomp2.	2.32	2.38	19	17	1	0
sequence_cps.10000	1.27	1.28	667	761	2	2
setrip.-enc_-rseed_1067894368	1.14	1.14	7	9	2	2
spectralnorm2.5_500	6.11	6.28	5	7	0	2
test_decompress.64_524_288	3.09	3.12	587	489	96	64
yojson_ydump.sample.json	0.59	0.58	19	16	6	5
zarith_pi.5000	1.23	0.89	749	750	250	375

[gasche]

Interesting! Interpreting the data you give is hard because the plots that you had before are measuring both metrics on the old implementation, while the benchmarks you give compare the old to the new implementation, which does its compactions and GCs at different time. Ideally we would see a plot of the memory usage over the program lifetime, with either the old and the new implementations, to be able to understand what is going on.

One remark:

This is mostly out-of-heap data (zarith) and nothing in the heap.

Is this true? My understanding is that Zarith implements bignums by allocating Custom or Abstract blocks that hold the gmp bigint inside the OCaml block, see caml_z.c : ml_z_alloc.

The program that is being measured is zarith_pi.ml, which computes the decimals of pi by building a rational approximation with larger and larger (relative) numerators and denominators. I think that what is happening is that larger and larger abstract/custom blocks are allocated inside the heap, most of them short-lived, but that the blocks that were freed recently were slightly smaller, creating fragmentation issues indeed.

[gasche]

Here is a made-up story of what might happen in the zarith-pi benchmark:

General context:

• As said earlier: the program allocates short-lived blocks that are larger and larger over time.
• Wild guess: during most of the program life, these blocks go directly to the major heap.
• When an incremental GC slice occurs, many of the blocks freed are smaller than the "current size" of the blocks.
  This increases fragmentation, as these free spaces cannot be used to fit new allocations.
• When a non-incremental GC occurs, almost all the blocks are freed.
• Therefore, if a compaction triggers shortly after a full major GC, then the actual overhead is very small, but if we wait a long time to compact we observe a much larger overhead. On the "actual overhead" plots, we observe a lot of samples with an actual overhead around 2000x (note: the plot values are percentages, right?), this corresponds to the overhead of the maximal delay between a major GC and the following compaction.

Note: what is the major allocator used in these measurements? I would expect best-fit to do better than other allocators here, by being more effective at coalescing slightly-too-small blocks into large-enough blocks.

Narrative for the performance difference:

• The previous, broken estimation for this program was 0 most of the time, until it suddenly became infinite. This program had 750 major-GC cycles and 250 compactions, this suggests that we had, regularly, 1 compaction for 3 full GC cycles.
• The new estimate uses the overhead at the end of the previous GC cycle, so it increases gradually over time. With the new implementation, this program has 375 compactions, which suggests that the gradual increase crosses the threshold quicker, leading to a compaction every 2 major cycles.
• Non-incremental major GCs are excellent for this program, which allocates a lot of short-lived blocks on the major heap. They result in a completely-free heap, making future allocations much faster. Having non-incremental cycles more often results in a large performance improvement.

[gasche]

Remark:

In this PR, our better estimate is simply a precise measurement of the overhead at the end of the previous cycle.

I'm not familiar with how the incremental major GC works, but is the overhead computed at the end of a GC cycle really "precise"? If I understand correctly, it is precise if we assume that an incremental GC cycle behaves like a non-incremental GC, but it may be imprecise if there was a lot of allocations and deaths in major heap in the middle of the cycle (because in this case the number of marked words may be much lower than the number of dead words). If this is correct, then what you call actual[0] is really "ground truth", but what you call actual[-1] is not, it is also a sort of estimate.

[lpw25]

I think that counting everything that is marked during a cycle gives you a precise measure of everything that was live at the start of the cycle. It sounds like maybe you are picturing the behaviour of an incremental update collector rather than a snapshot at the beginning collector.

[gasche]

Ah, so you are saying that the incremental major GC guarantees that all the memory that was live at the start of the cycle will have been traversed at the end of the cycle (and only that memory?), so the overhead measurement at the end of a GC cycle corresponds to the ground truth about the memory not at this point, but at the beginning of the cycle. Fair enough. (This means that there is more than one-major-cycle of distance between the measurement and its use, but we really are talking about two ground truths.)

[damiendoligez]

My understanding is that Zarith implements bignums by allocating Custom or Abstract blocks

Oh yes that's right. And your explanation of the fragmentation is correct. This is similar to the framgentation you get when you append repeatedly to a large string.

[damiendoligez]

Wild guess: during most of the program life, these blocks go directly to the major heap.

I'm pretty sure they are simply too large for the minor heap.

Therefore, if a compaction triggers shortly after a full major GC, then the actual overhead is very small, but if we wait a long time to compact we observe a much larger overhead.

I don't think so. The overhead is the ratio of (everything else)/(live data). A full major GC doesn't change it. Also, the full major GC only turns floating garbage (which is expected to be about the same size as the free list) into free-list blocks so its effect on fragmentation is probably limited.

On the "actual overhead" plots, we observe a lot of samples with an actual overhead around 2000x (note: the plot values are percentages, right?)

Right.

[damiendoligez]

Note: what is the major allocator used in these measurements?

I must confess I don't remember.

I would expect best-fit to do better than other allocators here, by being more effective at coalescing slightly-too-small blocks into large-enough blocks.

Why? Coalescing is mostly independent of the allocation policy. And next-fit has the property of getting stuck in the largest heap block, so it should leave more time for small blocks to be coalesced, if anything.

[stedolan]

There is a very slight inaccuracy here: caml_darken_all_roots_slice counts 1 unit of work for each root, regardless of whether or not it was actually marked. (This probably doesn't make any difference in practice, though)

[damiendoligez]

Well it's inaccurate anyway because the roots are not taken into account in the slice size computation, so this is, in a sense, extra work.

[stedolan]

This line should be two lines earlier: currently, it ignores the contribution to marked_words made by caml_darken_all_roots_start

[stedolan]

Thanks, this is looking good, and is a big improvement over trunk's heuristics.

I dug into the weird behaviour of levinson-durbin. This is an unusual program, with a large proportion of its allocation consisting of short-lived but large allocations (temporary arrays).

On bytecode, the current behaviour is bad (claiming 18000% overhead). This turns out to be due to the ordering issue in start_cycle (see comment) causing roots to be ignored by the heuristic, which has a particularly strong effect on this program because most of the allocations are large roots. Fixing this brings the estimated overhead from 18000% to ~400% and compactions from ~4000 (all aborted) to 4.

On native code, this fix is not enough. The native-code behaviour is different, having vastly fewer minor allocations (I think this is because ocamlopt removes many temporary boxed floats). The overhead grows large, because:

• A single major slice can mark or sweep at most 30% of the heap.
• The rate of major slices is tied to minor allocation: one major GC slice per minor heap's worth of allocation.
• This program has an unusually high ratio of major to minor allocation, because many allocations are too big for the minor heap.

The program continually has a large work backlog because major slices are not happening frequently enough to keep up with allocation. I think we should consider changing or removing the p = 0.3 cap, and/or triggering extra major slices when there are a very large number of direct-to-major-heap allocations. (Not as part of this PR, though!)

So, this program naturally GCs too slowly, which causes the overhead to grow and compaction to trigger very regularly. On one hand this makes sense, as compaction is indeed triggering when the overhead is large. On the other hand it doesn't, as compaction is now working around a bug in GC scheduling, rather than dealing with a too-large freelist.

As an alternative, I experimented a little with a different heuristic:

      uintnat live = marked_words + allocated_words_during_cycle;
      previous_overhead =
        100.0 * (Caml_state->stat_heap_wsz - live) / live;

The idea here is that we compute the ideal heap size after the cycle, as the sum of what was live at the beginning and what was allocated during, and compare to the actual heap size. This will avoid triggering compactions in programs with a small amount of live data but a high rate of allocation of garbage. This worked somewhat better on levinson-durbin (no compations, 22% faster, but 7% more memory used), but that is again a weird program. However, I haven't done any serious benchmarking on this, and you have on the current proposal, so I'm leaning towards keeping what's proposed in this patch.

---

tl;dr:

• I'd be happy to merge this with the current heuristic, once the start_cycle issue is fixed.
• Did you consider anything along the lines of the above heuristic? Do you have opinions / measurements about it?
• At some point I'd like to revisit the p=0.3 cap. I don't really understand what it's for, and it seems harmful sometimes.

[lpw25]

I don't quite understand your description of levinson-durbin in native code. caml_alloc_shr will request a major slice when caml_allocated_words > Caml_state->minor_heap_wsz and caml_alloc calls caml_check_urgent_gc. So I would still expect us to be doing enough major slices to keep up with allocations.

[stedolan]

I don't quite understand your description of levinson-durbin in native code. caml_alloc_shr will request a major slice when caml_allocated_words > Caml_state->minor_heap_wsz and caml_alloc calls caml_check_urgent_gc. So I would still expect us to be doing enough major slices to keep up with allocations.

That does look like the right mechanism, but I don't think the condition is right. The major GC will hit the p=0.3 cap, at default space_overhead settings, when:

caml_allocated_words / Caml_state->stat_heap_wsz > 0.109

This is independent of the current condition caml_allocated_words > Caml_state->minor_heap_wsz. I don't think it's correct for this condition to have anything to do with the minor heap size: using a very large minor heap and doing a lot of major allocations should not cause the major GC to just stop.

Concretely, levinson-durbin major GC slices often happen when caml_allocated_words is about 25% of the minor heap size (so not enough to trigger the condition), but about 18% of the major heap size (well above the 10% limit that triggers a maximal slice). (However, a program with a larger minor than major heap is a weird program to begin with)

[gasche]

What I hear from @stedolan's comments is that looking at the benchmarks that have abnormally-high overhead reveals implementation bugs or conceptual issues with the current GC decisions. It may be worth fixing (some of) those issues first, and revisiting the specific question of compaction heuristics second, instead of making decisions based on corner cases for which the measurements/deductions may be obscured or rendered invalid by those other issues.

[gasche]

My wording above is a bit too strong; rather than saying we should wait with this specific change, I think that at least we shouldn't take the outliers too seriously for decision-making. Omitting the outliers still suggests that the PR is an improvement over the current state.

[stedolan]

I wouldn't phrase it exactly like that. I think analysing the behaviour of edge cases is an excellent way to understand a system, because issues that cause hard-to-diagnose small-but-significant performance changes in real code can cause huge obvious swings in outliers.

In this case, analysing the levinson-durbin outlier revealed a bug in this patch (two lines in start_cycle are in the wrong order) which should be fixed before this PR is merged.

(It also revealed a bunch of other weird unrelated stuff, some of which I'd like to look at more closely later, but which shouldn't block this PR from being merged).

[damiendoligez]

@stedolan

This will avoid triggering compactions in programs with a small amount of live data but a high rate of allocation of garbage.

But what is "a high rate of allocation of garbage"? The GC is self-pacing, so the allocation rate is supposed to be the same for all programs. When it isn't true, that means we have a bug in GC scheduling, so you are also trying to work around it...

[stedolan]

But what is "a high rate of allocation of garbage"? The GC is self-pacing, so the allocation rate is supposed to be the same for all programs. When it isn't true, that means we have a bug in GC scheduling, so you are also trying to work around it...

You're right of course, that comment of mine is nonsense. I think I had a bad understanding of why the p=0.3 cap was being hit. (I now think that it's actually because of how small the major heap is here, and how infrequent major slices are. I think the heuristic for forcing a major slice is slightly off, but in a way that can only affect really weird programs, so I don't think it needs fixing here)