compare.c: avoid inner pointers on the compare stack

To compare same-size blocks containing values, do_compare_val recursively
compares the first argument of each block, and pushes "the rest of the
arguments' on both sides to the compare stack. The compare stack thus
contains pairs of sequences of arguments to be compared.

Before this PR, pairs of sequences of arguments are represented by:

- two inner pointers (into the parent blocks) to the first arguments
  to be compared on each side
- a "count" field remembering the number of arguments still to compare

The use of inner pointers that are not valid OCaml values makes some
things delicate, for example we could not ask the GC to scan the
compare stack (as is being considered in the context of # 12039).

After this PR, pairs of sequences of arguments are represented by:

- pointers to the parent containing blocks on each side
  (that is, valid OCaml values)
- an "offset" field remembering the offset of the next argument to
  compare, stored as a tagged OCaml integer
- a "size" field remembering the size of the two blocks,
  store as a tagged OCaml integer

At this point, the compare stack contains only valid OCaml values and
could be registered as a single block of local GC roots.

Note: storing the size is superfluous as the size can also be computed
from the blocks themselves (bit-shifting on the header value). In our
tests, storing the size and comparing directly against it noticeably
improves performance on some architectures (a 10-20% different on
compare microbenchmarks). The cost is to use 4 words per element
instead of 3.

1 files changed, 9 insertions, 7 deletions

diff --git a/runtime/compare.c b/runtime/compare.c
index 8348f99dda..f96d0c14d9 100644
--- a/runtime/compare.c
+++ b/runtime/compare.c
@@ -25,7 +25,7 @@
 
 /* Structural comparison on trees. */
 
-struct compare_item { volatile value * v1, * v2; mlsize_t count; };
+struct compare_item { value v1, v2, offset, size; };
 
 #define COMPARE_STACK_INIT_SIZE 8
 #define COMPARE_STACK_MIN_ALLOC_SIZE 32
@@ -280,9 +280,10 @@ static intnat do_compare_val(struct compare_stack* stk,
       if (sz1 > 1) {
         sp++;
         if (sp >= stk->limit) sp = compare_resize_stack(stk, sp);
-        sp->v1 = &Field(v1, 1);
-        sp->v2 = &Field(v2, 1);
-        sp->count = sz1 - 1;
+        sp->v1 = v1;
+        sp->v2 = v2;
+        sp->offset = Val_long(1);
+        sp->size = Val_long(sz1);
       }
       /* Continue comparison with first field */
       v1 = Field(v1, 0);
@@ -293,9 +294,10 @@ static intnat do_compare_val(struct compare_stack* stk,
   next_item:
     /* Pop one more item to compare, if any */
     if (sp == stk->stack) return EQUAL; /* we're done */
-    v1 = *((sp->v1)++);
-    v2 = *((sp->v2)++);
-    if (--(sp->count) == 0) sp--;
+    v1 = Field(sp->v1, Long_val(sp->offset));
+    v2 = Field(sp->v2, Long_val(sp->offset));
+    sp->offset += 2;/* Long_val(sp->offset) += 1 */
+    if (sp->offset == sp->size) sp--;
   }
 }