Simplified compaction without page table by damiendoligez · Pull Request #9728 · ocaml/ocaml

damiendoligez · 2020-06-30T19:36:27Z

This is an alternative to #9704. Here we take advantage of the self-describing closure representation to greatly simplify the compactor, which frees one bit in each pointer, that we use to get rid of the page table. The only drawback is that we now have to encode/decode pointers with some bit-twiddling on each access.

The new compactor gets rid of one pass (out of four) and the performance seems to be slightly better than the alternatives on @xavierleroy's synthetic benchmark.

List length	#runs	# heap chunks	time w/ page table (s)	time w/ binary search (s)	time w/ simplified compactor (s)
10_000_000	80	42	0.54 / 0.58 / 0.87	0.55 / 0.58 / 0.89	0.51 / 0.53 / 0.80
50_000_000	16	53	2.31 / 2.40 / 2.88	2.35 / 2.39 / 2.67	2.14 / 2.24 / 2.49
100_000_000	8	58	4.79 / 4.82 / 4.87	4.87 / 5.23 / 6.77	4.45 / 4.48 / 4.52
200_000_000	4	63	9.80 / 9.85 / 9.92	10.02 / 10.05 / 10.07	9.11 / 9.20 / 9.26
400_000_000	2	68	20.47 / 20.55 / 20.64	20.84 / 20.92 / 21.00	19.48 / 19.48 / 19.48

I ran the benchmark on our big server and the results looked noisy, so I ran them each several times and report min/avg/max for each.

xavierleroy

What a pleasure to see the fabled page-less compactor!

I still don't understand the algorithm, but was not expecting to. Below are stylistic suggestions and one question.

xavierleroy · 2020-07-01T13:14:47Z

runtime/compact.c

+    case Caml_white:
+      CAMLassert (Is_in_heap (q));
+      if (Tag_hd (h) == Infix_tag){
+        if (Is_black_val ((value) q - Infix_offset_val (q))) break;


If q is an infix pointer in the major heap, the enclosing closure block is in the major heap too, so how can the enclosing block be black?

On the other hand, if you suspect q may point within a closure allocated outside the heap, the test is OK but the assertion on line 74 will be false.

Indeed, I'll update the assertion on line 74. The idea is that it's easy to check the real header. The alternative would be to mandate that every infix header outside the heap be black, but that would be more work for things like ancient or even flambda.

In any case, white-colored infix headers out of the heap should be forbidden, because this will produce out-of-heap pointers to non-black values, which is breaking other pieces of code (e.g., weak.c).

The conclusion of #9735 seems to be that the compactor would be the only one to rely on this invariant, so I'd rather take the less-demanding option.

runtime/compact.c

xavierleroy

A couple of weird types.

runtime/compact.c

jhjourdan

The approach looks good to me, and the code is indeed simpler.

I left a few remarks: perhaps the most important is that the new compactor should not rely on the no-naked-pointer mode and should therefore read the page table when necessary in naked pointers mode.

runtime/compact.c

jhjourdan · 2020-07-02T16:25:55Z

runtime/compact.c

+    case Caml_white:
+      CAMLassert (Is_in_heap (q));
+      if (Tag_hd (h) == Infix_tag){
+        if (Is_black_val ((value) q - Infix_offset_val (q))) break;


In any case, white-colored infix headers out of the heap should be forbidden, because this will produce out-of-heap pointers to non-black values, which is breaking other pieces of code (e.g., weak.c).

jhjourdan · 2020-07-02T16:59:15Z

runtime/compact.c

+    case Caml_white:
+      CAMLassert (Is_in_heap (q));
+      if (Tag_hd (h) == Infix_tag){
+        if (Is_black_val ((value) q - Infix_offset_val (q))) break;


runtime/compact.c

jhjourdan · 2020-07-04T17:57:13Z

runtime/compact.c

-     Link infix headers in each block in an inverted list of inverted lists.
-     Don't forget roots and weak pointers. */
+     Don't forget roots and weak pointers.
+     This is a mark-like pass. */


What do you mean by this?

To me, since this is a pass where we traverse each object in order from the first to the last in the heap, this seems very much sweep-like.

I mean it enumerates every pointer to every block, including the roots.

jhjourdan · 2020-07-05T03:23:54Z

runtime/compact.c


 void caml_invert_root (value v, value *p)
 {
+  CAMLassert (Is_long (*p) || Is_in_heap (*p) || Is_black_val (*p));


This assertion is wrong in naked pointers mode. In no-naked-pointers mode, it is useless since it uses Is_in_heap, which will be defined to 1.

That said, note that this assertion is failing in CI currently. This indicates that even in no-naked-pointers mode, some root contains a naked pointer (or is inverted several times?), or something else fishy.

Suggested change

CAMLassert (Is_long (*p) || Is_in_heap (*p) || Is_black_val (*p));

CAMLassert (Is_long (*p) || Is_in_heap (*p) || Is_black_val (*p) ||

Tag_val(*p) == Infix_tag);

Actually, these assertion failures are simply related to white infix headers (see #9735). The change above fixes the issue.

I dislike those complicated assertions. You're trying to check that *p is an OK OCaml value, but if it isn't the GC would have bombed already.

These complicated assertions are usually the by-product of debugging sessions.

runtime/roots_byt.c

jhjourdan · 2020-07-05T03:37:43Z

runtime/compact.c

+          *p = q;
+
+          if (t == Closure_tag){
+            /* Revert the infix pointers. */


Suggested change

/* Revert the infix pointers. */

/* Revert the pointers to infix blocks. */

There is no such thing as an infix block... There are infix pointers inside blocks, though.

jhjourdan · 2020-07-05T03:58:03Z

Another TODO: finally get rid of the page table in no-noaked-pointers mode, since we don't use it any more.

But I guess you want to do that in a separate PR.

xavierleroy

This is starting to look very good, but please make sure that the code works in naked-pointers mode as well as in no-naked-pointers mode. We have to support both modes until OCaml 5.00 at least. And the new code should still be more efficient than the old code even in naked-pointers mode, since it has 3 passes instead of 4.

runtime/compact.c

xavierleroy · 2020-07-05T17:30:14Z

runtime/compact.c


 void caml_invert_root (value v, value *p)
 {
+  CAMLassert (Is_long (*p) || Is_in_heap (*p) || Is_black_val (*p));


I dislike those complicated assertions. You're trying to check that *p is an OK OCaml value, but if it isn't the GC would have bombed already.

xavierleroy · 2020-07-05T17:31:37Z

runtime/compact.c

+          *p = q;
+
+          if (t == Closure_tag){
+            /* Revert the infix pointers. */


There is no such thing as an infix block... There are infix pointers inside blocks, though.

runtime/roots_byt.c

xavierleroy · 2020-07-05T17:35:44Z

Another TODO: finally get rid of the page table in no-noaked-pointers mode, since we don't use it any more. But I guess you want to do that in a separate PR.

Yes, that would be a separate PR. Also, remember that we still need the page table in debug mode because of all these Is_in_heap assertions that litter the runtime system.

jhjourdan · 2020-07-05T18:27:33Z

Also, remember that we still need the page table in debug mode because of all these Is_in_heap assertions that litter the runtime system.

Ah, I did not understand that you wanted to keep the page table for the debug mode. Then perhaps we also want to assert in debug mode that it is used rightfully in Is_in_value_area.

…mpaction algorithm and remove the use of the page table

Co-authored-by: Jacques-Henri Jourdan <jourgun@gmail.com>

xavierleroy

The code looks very good to me. However, the Travis CI is still failing hard. For the record: it tests naked-pointers mode exclusively; we still need to add no-naked-pointers mode to the Travis configurations.

jhjourdan

The code looks good to me. The CI failures are due to the assertion in caml_invert_root, which should either be completely removed or guarded by an #ifdef NO_NAKED_POINTERS.

jhjourdan · 2020-07-07T09:35:52Z

runtime/compact.c

+  CAMLassert (Is_long (*p) || Is_in_heap (*p) || Is_black_val (*p)
+              || Tag_val (*p) == Infix_tag);


This assertion is wrong in naked pointers mode when *p is a naked pointer (e.g., a code pointer in bytecode mode, which explain the CI failure).

xavierleroy · 2020-07-13T08:57:54Z

I take good note that the weird assertion is to be removed sooner rather than later. The code is fine, let's squash and merge!

xavierleroy reviewed Jul 1, 2020

View reviewed changes

runtime/compact.c Outdated Show resolved Hide resolved

runtime/compact.c Outdated Show resolved Hide resolved

jhjourdan mentioned this pull request Jul 2, 2020

Make sure closures which are statically allocated by the compiler use black infix headers. #9735

Closed

damiendoligez force-pushed the nnp-compact branch from e70b6c5 to 7cab019 Compare July 3, 2020 10:13

jhjourdan requested changes Jul 5, 2020

View reviewed changes

xavierleroy reviewed Jul 5, 2020

View reviewed changes

damiendoligez added 3 commits July 6, 2020 13:53

taking advantage of the new closure representation to simplify the co…

31ad147

…mpaction algorithm and remove the use of the page table

Add Changes entry and take Xavier's remarks into account

cec78ec

fix wrong assertion

7f1f2da

damiendoligez force-pushed the nnp-compact branch from ee57ca2 to 7f1f2da Compare July 6, 2020 11:54

damiendoligez and others added 3 commits July 6, 2020 13:58

fix word format in comment

98875b8

Co-authored-by: Jacques-Henri Jourdan <jourgun@gmail.com>

micro-optimize switch statement

48fd27c

Co-authored-by: Jacques-Henri Jourdan <jourgun@gmail.com>

changes suggested by @jhjourdan and @xavierleroy

14913e6

xavierleroy reviewed Jul 6, 2020

View reviewed changes

xavierleroy added the multicore-prerequisite label Jul 6, 2020

jhjourdan approved these changes Jul 7, 2020

View reviewed changes

fix assertion that is true only in NNP mode

3329bb8

xavierleroy merged commit 601819f into ocaml:trunk Jul 13, 2020

xavierleroy mentioned this pull request Jul 13, 2020

Compacting the heap without the page table #9704

Closed

sadiqj mentioned this pull request Jul 14, 2020

Garbage collector colours change #9756

Merged

damiendoligez deleted the nnp-compact branch July 15, 2020 09:35

	CAMLassert (Is_long (p) \|\| Is_in_heap (p) \|\| Is_black_val (*p));
	CAMLassert (Is_long (p) \|\| Is_in_heap (p) \|\| Is_black_val (*p) \|\|
	Tag_val(*p) == Infix_tag);

	/* Revert the infix pointers. */
	/* Revert the pointers to infix blocks. */

		CAMLassert (Is_long (p) \|\| Is_in_heap (p) \|\| Is_black_val (*p)
		\|\| Tag_val (*p) == Infix_tag);

Conversation

damiendoligez commented Jun 30, 2020

Uh oh!

xavierleroy left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

xavierleroy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

jhjourdan left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jhjourdan Jul 5, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jhjourdan Jul 5, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jhjourdan commented Jul 5, 2020

Uh oh!

xavierleroy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

xavierleroy commented Jul 5, 2020

Uh oh!

jhjourdan commented Jul 5, 2020

Uh oh!

xavierleroy left a comment

Choose a reason for hiding this comment

Uh oh!

jhjourdan left a comment

Choose a reason for hiding this comment

jhjourdan Jul 5, 2020 •

edited

Loading

jhjourdan Jul 5, 2020 •

edited

Loading