Prefetching optimisations for sweeping

[stedolan]

This PR contains two patches that optimise sweep_slice: a small refactoring that moves some globals to locals, and a use of prefetching. The goal is to reduce cache misses during GC.

Sweeping is a linear traversal of memory, which should already be fast. However, it is not a normal linear traversal: the next pointer is known only once you've loaded the length from the current one, making the algorithm more like a linked list traversal. This defeats some hardware prefetching mechanisms: the address dependencies mean that the next load is not exposed until the current one returns data (meaning out-of-order execution doesn't help), and the stride is irregular since not all objects are the same size. Stream prefetching does help somewhat by noticing sequential accesses, but (on Intel) doesn't cross 4k page boundaries and doesn't always prefetch data all the way to L1. See the intel optimisation manual for more details on hardware prefetching. (Currently, this code hasn't been benchmarked on AMD processors, and is a no-op on non-x86 architectures)

The prefetching in this patch is very straightforward: it prefetches 4k ahead of the sweep pointer.

On a small benchmark, this speeds up sweeping by around 25%. (Sweeping is about a quarter of the runtime of this benchmark, leading to a more modest overall improvement of a few percent).

This is a prelude to a more complicated patch that adds prefetching to marking, where it causes a more dramatic improvement.

(joint work with Will Hasenplaugh)

[dra27]

I think - but I have not experimented - that the MSVC equivalent is #include <winnt.h> and PreFetchCacheLine((p), PF_NON_TEMPORAL_LEVEL_ALL) (I'm not sure about the constant)

[xavierleroy]

Just curious: why only on x86? __builtin_prefetch exists on all GCC-supported platforms, even though it can be a no-op. And I'm sure ARM and others would benefit too.

[xavierleroy]

Also, I would document a bit:

#define caml_prefetch(p) __builtin_prefetch((p), 1, 3)
/* 1 = intent to write; 3 = all cache levels */

[stedolan]

Just curious: why only on x86? __builtin_prefetch exists on all GCC-supported platforms, even though it can be a no-op. And I'm sure ARM and others would benefit too.

I left others out because I don't really know anything about non-x86 memory hierarchies. We can turn it on for ARM if you like, but I can't judge how much / whether it'll help, and I don't have the expertise / time to do any serious benchmarking.

(I'll add the comments)

[stedolan]

Incidentally, when writing this I noticed another possible place for optimisation / cleanup, but haven't attempted it:

The caml_fl_merge_block function does a certain amount of work to determine whether the most recently found free block is mergeable with the current one (i.e. is it still free, and is it adjacent to the current block?). This information is known to the sweeper, as it processes blocks in order. We could possibly shave some more time off sweeping by changing the interface, and having the sweeper pass the previous block or NULL to caml_fl_merge_block, rather than the latter redetecting it. (This interface is somewhat subtle and difficult to debug, though, so this could be a delicate change)

[xavierleroy]

Sounds interesting. Thanks for looking into this.

[xavierleroy]

Just curious: why only on x86? __builtin_prefetch exists on all GCC-supported platforms, even though it can be a no-op. And I'm sure ARM and others would benefit too.

[xavierleroy]

Also, I would document a bit:

#define caml_prefetch(p) __builtin_prefetch((p), 1, 3)
/* 1 = intent to write; 3 = all cache levels */

[shubhamkumar13]

The 2 graphs represent the normalized running time of benchmarks on sandmark when #9934 is run with trunk as a baseline.

The first one is on an Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GHz.

The following table refers to trunk's raw running time result on the same Intel system.

	name	time_secs	gc.major_collections	gc.major_words
0	lu-decomposition.	1.32719	11	7775014
1	levinson-durbin.	2.74204	1894	250063925
2	menhir.sql-parser	6.98978	23	59727559
3	fft.	4.37065	41	140412857
4	setrip.-enc_-rseed_1067894368	1.52092	9	13301
5	yojson_ydump.sample.json	0.76486	17	2979936
6	revcomp2.	2.9139	25	49759392
7	test_decompress.64_524_288	4.1468	555	105774397
8	LU_decomposition.1024	4.00685	4	4194470
9	game_of_life.256	11.927	2	2101398
10	regexredux2.	18.9592	32	240256398
11	grammatrix.	93.5887	26	68529245
12	evolutionary_algorithm.10000_10000	70.5337	32	1300975436
13	floyd_warshall.512	4.47551	22	6396941
14	quicksort.4000000	2.91457	0	4000146
15	mandelbrot6.16_000	40.6443	0	0
16	matrix_multiplication.1024	9.70372	6	3152023
17	fasta6.25_000_000	5.81388	1	25417192
18	qr-decomposition.	2.38781	63	2696897
19	cubicle.szymanski_at.cub	495.709	1532	6372966728
20	lexifi-g2pp.	17.1283	8	183647
21	durand-kerner-aberth.	0.1383	92	237481
22	nbody.50_000_000	7.47168	0	0
23	fannkuchredux2.12	94.0485	0	0
24	fannkuchredux.12	83.9848	0	0
25	knucleotide3.	43.9427	7	34073208
26	cpdf.blacktext	4.31274	14	27976325
27	bdd.26	5.3187	12	2471440
28	kb_no_exc.	2.5074	227	23320680
29	menhir.ocamly	235.341	35	1147662209
30	cpdf.scale	13.7828	33	94564877
31	zarith_pi.5000	1.47259	642	392716558
32	spectralnorm2.5_500	7.50886	5	121482
33	binarytrees5.21	11.8288	63	270360189
34	cubicle.german_pfs.cub	224.007	377	3254161011
35	cpdf.squeeze	16.3786	37	140393871
36	minilight.roomfront	22.2329	68	10639641
37	kb.	3.97839	329	24449437
38	pidigits5.10_000	6.02947	2691	1664137387
39	naive-multilayer.	4.17674	242	1293140
40	menhir.sysver	86.3455	63	467046511
41	sequence_cps.10000	1.58179	779	219311
42	knucleotide.	43.8687	13	50878638
43	fasta3.25_000_000	7.48009	0	551

The second graph is on an AMD EPYC 7702 64-Core Processor

Similarly, trunk's running time on the Amd machine

	name	time_secs	gc.major_collections	gc.major_words
0	menhir.sql-parser	4.95038	23	59727559
1	spectralnorm2.5_500	5.02338	5	121482
2	test_decompress.64_524_288	2.55676	555	105774397
3	minilight.roomfront	13.6939	68	10648042
4	sequence_cps.10000	1.25108	777	219410
5	lexifi-g2pp.	7.1579	8	183441
6	durand-kerner-aberth.	0.0961349	92	237481
7	cpdf.blacktext	3.01654	14	27976325
8	cpdf.squeeze	11.6939	37	140393871
9	knucleotide3.	27.4065	7	34073208
10	LU_decomposition.1024	2.77154	4	4194470
11	grammatrix.	50.1481	26	68529245
12	menhir.ocamly	173.388	35	1147662209
13	lu-decomposition.	0.850682	11	7775014
14	levinson-durbin.	1.57413	1894	250063925
15	kb.	2.58478	329	24449437
16	zarith_pi.5000	0.787027	642	392716558
17	setrip.-enc_-rseed_1067894368	0.771906	9	13307
18	binarytrees5.21	7.58026	63	270360189
19	matrix_multiplication.1024	4.2848	6	3152023
20	fannkuchredux.12	50.0576	0	0
21	fannkuchredux2.12	47.999	0	0
22	qr-decomposition.	1.27351	63	2696897
23	kb_no_exc.	1.63776	227	23320680
24	knucleotide.	27.7144	13	50878638
25	pidigits5.10_000	3.21054	2691	1664137387
26	nbody.50_000_000	4.87069	0	0
27	evolutionary_algorithm.10000_10000	44.0215	33	1300975511
28	yojson_ydump.sample.json	0.530261	17	2979936
29	revcomp2.	1.88539	25	49759392
30	menhir.sysver	58.3835	63	466977775
31	mandelbrot6.16_000	21.3379	0	0
32	quicksort.4000000	1.64895	0	4000146
33	cubicle.german_pfs.cub	183.453	376	3249735172
34	bdd.26	2.99953	12	2471440
35	naive-multilayer.	2.78721	239	1285722
36	floyd_warshall.512	2.68485	22	6396941
37	cubicle.szymanski_at.cub	317.303	1535	6373523793
38	regexredux2.	11.9367	32	240256398
39	fasta3.25_000_000	5.02575	0	551
40	game_of_life.256	9.40374	2	2101398
41	fft.	2.57991	41	140412857
42	fasta6.25_000_000	3.76762	1	25417192
43	cpdf.scale	9.81784	32	95330715

[xavierleroy]

Thank you for the benchmarking work and the nice graphics! But I don't know what to conclude from these. A 10% speedup on some tests is very nice indeed, but a 6% slowdown on some other tests is a concern.

Also, I'm surprised that the effect on performance can be that strong: typically, GC takes 30% of execution times, and sweeping takes less time than marking, so the whole sweeping phase should be 10% or so of total execution time, and improving the sweeping phase can hardly improve the total running time by 10%.

[lpw25]

@damiendoligez

[damiendoligez]

This all looks good to me.

[damiendoligez]

IIUC this will prefetch the cache line at sweep_hp + 4k. Isn't this likely to conflict with the cache line that contains sweep_hp itself? I know caches are associative, but the associativity is rather low, so what is the probability of evicting sweep_hp itself when we still need it? Would it be hard to benchmark some variation of this number (for example 4032)?

[stedolan]

Excellent point, I'll try that.

[damiendoligez]

The caml_fl_merge_block function does a certain amount of work to determine whether the most recently found free block is mergeable with the current one (i.e. is it still free, and is it adjacent to the current block?). This information is known to the sweeper, as it processes blocks in order. We could possibly shave some more time off sweeping by changing the interface, and having the sweeper pass the previous block or NULL to caml_fl_merge_block, rather than the latter redetecting it. (This interface is somewhat subtle and difficult to debug, though, so this could be a delicate change)

You have to be careful because caml_fl_merge (the "most recently found free block") is also modified by the allocation functions. If you find a more efficient API for this function, I'll gladly review the PR.

[stedolan]

You have to be careful because caml_fl_merge (the "most recently found free block") is also modified by the allocation functions. If you find a more efficient API for this function, I'll gladly review the PR.

Yeah, that's the tricky subtlety I was referring to. An observation that might help is that allocation cannot occur during sweep_slice, so the synchronisation with the allocator only needs to happen at the start and end of that function, not in the inner loop of sweeping.

[gasche]

What's the status of this PR? The CI failure is a missing Changes entry (and indeed this probably deserves one). Could we move ahead and eventually merge?

[xavierleroy]

Performance evaluation is inconclusive, to me at least. This is supposed to make programs run faster, and it's unclear it does.

[gasche]

Ah, indeed, Damien's approval should probably be interpreted as "approval for correctness".

I looked at the graphs again. Several of the speedup results are found (in varying proportions) of both machines, but the most striking slowdown, bdd, is only found on the Intel machine. To me this suggests that the numbers may be partially noisy due to processor-specific code-cache effects. (Here the changes are in the runtime so we probably cannot use the random-nop-padding approach used in another PR to avoid those.)

Looking at the change, it is of course possible that the addition of one prefetching instruction would result in wide variation, but there is a more invasive refactoring in sweep_slice that reorders computations around to compute what to prefetch; this invasive change is more likely to be the cause of processor-specific variation, if there is some indeed. This suggests that one could:

• write a PR with the same reordering changes but without the prefetching instructions, and compare that one with this one (so only the prefetching instructions differ), and that one with trunk (so we see if there is a cost to the reordering)
• consider benchmarking the change that adds prefetching to freelist.c by itself, as it requires no refactoring. This may be more stable, but my understanding is that Stephen expects less of an improvement for that one change, sweeping was the motivation for this PR.

[dra27]

@stedolan says it's a prelude to another PR - is it also a prerequisite?

[lpw25]

I would like to raise a concern I have with using the sandmark benchmark suite for assessing the performance of changes to the GC: Why do we think this is a good and representative set of benchmarks for these kinds of changes? I've seen lots of great work from OCamlLabs on how to get reliable numbers out of these benchmarks, but I have yet to see any assessment of the quality of this particular set of benchmarks.

For example, most of these benchmarks seem to do very few major cycles and allocate very few major words. That does not resemble most of the real programs that I deal with.

It would also be good to see some analysis of the noise in these benchmarks, both between runs and between changes to code layout.

[gasche]

Parroting the usual answer from Landmark maintainers, and I think they have a point: if you think that a particular workflow is missing from their benchmark suite, you should probably contribute a benchmark to the suite.

[lpw25]

if you think that a particular workflow is missing from their benchmark suite, you should probably contribute a benchmark to the suite.

That doesn't help with assessing the quality of the benchmarks that are already in there. If the Sandmark maintainers are going to add benchmark results to other people's PRs then they need to provide some context as to why they think the numbers are relevant.

[xavierleroy]

The Sandmark numbers are better than nothing. (Many performance-oriented PRs came with no benchmarking whatsoever until recently.) But the numbers need to be interpreted! As I wrote earlier, the sweep phase is at most 10% of the total running time of the program, so variations of -10% / +6% in total running time don't just come from the sweep phase.

[kayceesrk]

I agree that it may not have been the best idea to run Sandmark on a PR not submitted by Multicore OCaml folks, especially when it remains difficult for the wider community to easily run the benchmarks on their end. But I am hoping that the process gets easier. We will refrain from running Sandmark on PRs not related to multicore.

That said, I wanted to bring the performance questions to a conclusion. I suspect that the original numbers were run on this PR and trunk and that point in time, which may have had unrelated commits. So I reran Sandmark on this PR (commit b419956) and the commit that this PR is based on (7d9e60d). The commit history is here: https://github.com/stedolan/ocaml/commits/sweep-optimisation. The normalized running time graph is here:

The baseline is 7d9360d. The graph shows the performance impact of this PR against the baseline. Lower is better. The numbers in the parenthesis is the running time in seconds for the baseline version. Overall, there is positive improvement.

I analysed the outliers in detail.

bdd

bdd is 2.6% slower in this PR according to the Sandmark run. bdd does not spend significant amount of time in the GC. The function sweep_slice takes 0.15% of the running time as reported by perf. Here is the perf stat output:

$ perf stat ./_build/4.12.0+7d9e60d_1/benchmarks/bdd/bdd.exe 26 # BASELINE

 Performance counter stats for './_build/4.12.0+7d9e60d_1/benchmarks/bdd/bdd.exe 26':

       5169.389420      task-clock (msec)         #    1.000 CPUs utilized
                 9      context-switches          #    0.002 K/sec
                 0      cpu-migrations            #    0.000 K/sec
             4,728      page-faults               #    0.915 K/sec
   11,34,59,02,093      cycles                    #    2.195 GHz
   22,49,12,29,020      instructions              #    1.98  insn per cycle
    4,95,24,82,879      branches                  #  958.040 M/sec
       5,87,93,810      branch-misses             #    1.19% of all branches

       5.169854280 seconds time elapsed

$ perf stat ./_build/4.12.0+b419956_1/benchmarks/bdd/bdd.exe 26 # THIS PR 

 Performance counter stats for './_build/4.12.0+b419956_1/benchmarks/bdd/bdd.exe 26':

       5470.182940      task-clock (msec)         #    1.000 CPUs utilized          
                10      context-switches          #    0.002 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
             4,727      page-faults               #    0.864 K/sec                  
   12,00,60,98,103      cycles                    #    2.195 GHz                    
   22,48,76,42,055      instructions              #    1.87  insn per cycle         
    4,95,23,07,655      branches                  #  905.328 M/sec                  
       7,80,00,231      branch-misses             #    1.58% of all branches        

       5.470739910 seconds time elapsed

There are more branch misses in the PR. However, the slowdown cannot just be explained with the changes introduced.

revcomp2

On the other side, we see a 6.8% improvement on revcomp2. This improvement is real. On the baseline, the program spends, ~10% of its time sweeping:

  47.64%  revcomp2.exe  revcomp2.exe      [.] camlDune__exe__Revcomp2__wr_238
  10.05%  revcomp2.exe  revcomp2.exe      [.] sweep_slice
   7.33%  revcomp2.exe  revcomp2.exe      [.] mark_slice
   6.71%  revcomp2.exe  revcomp2.exe      [.] caml_input_scan_line
   3.08%  revcomp2.exe  revcomp2.exe      [.] caml_page_table_lookup
   2.79%  revcomp2.exe  revcomp2.exe      [.] caml_oldify_one
   1.73%  revcomp2.exe  revcomp2.exe      [.] caml_alloc_string
   1.55%  revcomp2.exe  revcomp2.exe      [.] caml_alloc_shr_for_minor_gc

with this PR, sweeping takes 5.3% of the total time:

  52.14%  revcomp2.exe  revcomp2.exe      [.] camlDune__exe__Revcomp2__wr_238
   8.13%  revcomp2.exe  revcomp2.exe      [.] mark_slice
   6.85%  revcomp2.exe  revcomp2.exe      [.] caml_input_scan_line
   5.30%  revcomp2.exe  revcomp2.exe      [.] sweep_slice
   3.28%  revcomp2.exe  revcomp2.exe      [.] caml_page_table_lookup
   2.47%  revcomp2.exe  revcomp2.exe      [.] caml_oldify_one
   1.93%  revcomp2.exe  revcomp2.exe      [.] caml_alloc_shr_for_minor_gc

Conclusions

I'm doing an experiment to quantify the noise in Sandmark. This is especially fiddly to quantify accurately due to the microarchitectural optimisations on modern processors. See the work in #10039.

Given the overall improvement, I am for accepting this PR.

[lpw25]

Thank you very much for the analysis KC. That makes things much clearer.

I agree that it may not have been the best idea to run Sandmark on a PR not submitted by Multicore OCaml folks, especially when it remains difficult for the wider community to easily run the benchmarks on their end. But I am hoping that the process gets easier. We will refrain from running Sandmark on PRs not related to multicore.

I don't want to dissuade you too much from adding benchmark results to PRs.

I think my concern is mostly that dropping a benchmark results graph in a comment, without the much more involved work needed to investigate the results and provide context for people who are not familiar with the nature of the particular benchmarks, is as likely to do harm as it is to do good.

When that additional work is done -- as you have very helpfully done in your previous comment -- then the results start to become very useful and greatly appreciated.

[kayceesrk]

Thanks Leo. We'll make sure we provide an interpretation of the numbers and not just the raw results.

[stedolan]

I am unable to reproduce the bdd slowdown: on several Intel machines with different build settings, PIE vs. non-PIE, etc, I can detect no difference in the performance of bdd before and after this patch.

I suspect the observed slowdown may possibly be caused by Intel's workaround for their JCC bug. Many recent Intel processors have a serious bug in their decoded instruction cache. Intel's workaround, distributed in a microcode update, is to disable the decoded instruction cache around jump instructions crossing a 32-byte boundary. This has a performance cost, which is usually low but has been observed to cause +/- 20% performance swings, particularly in microbenchmarks.

By configuring OCaml as follows, padding bytes can be inserted to ensure that no jumps cross 32-byte boundaries and the workaround never triggers:

./configure CC='gcc -Wa,-mbranches-within-32B' AS='as -mbranches-within-32B'

It might be worth building OCaml like this in future Sandmark runs on Intel processors.

@damiendoligez I played around with the offset number a bit and didn't notice any of the cache aliasing you mentioned. I've left it at 4000 just in case. The performance is not strongly affected by this parameter: it needs to be big enough that the prefetch has time to complete before the data is needed, and small enough that the data hasn't already fallen out of cache by the time sweeping gets there. I saw good results anywhere from 1k to 100k, and I left the parameter close to the bottom end of the range (very large values cause additional cache pollution, by prefetching many kilobytes beyond the end of the region being swept).

[stedolan]

@damiendoligez Does your "approved" still stand? (There was discussion since, but as far as I'm concerned this is ready to merge)

[damiendoligez]

Sure. Merging now. I'll make a note to do some benchmarking on other architectures.