Fil-C · glibc · string/memcmp.c · commit a5d5dbc (+ test 4eef902) on mbrock/fil-c glibc-memcmp-noalloc, based on pizlonator/fil-c deluge 9d1ed206

memcmp without the eight heap allocations

glibc's generic memcmp finds its answer by taking the addresses of two local words and walking their bytes. Under Fil-C an address-taken local lives on the GC heap — so every memcmp and bcmp call allocated eight objects before comparing a single byte. In PHP serving WordPress that was a third of all allocation. The fix finds the same byte with one ctz.

The culprit: three lines of perfectly normal C

glibc's generic string/memcmp.c compares word at a time. When two words differ, a small helper has to say which byte differs first, and by how much — that difference is memcmp's return value. The helper re-reads the two words it was just handed, through pointers to its own parameters:

static int
memcmp_bytes (op_t a, op_t b)
{
  long int srcp1 = (long int) &a;
  long int srcp2 = (long int) &b;
  op_t a0, b0;

  do
    {
      a0 = ((byte *) srcp1)[0];
      b0 = ((byte *) srcp2)[0];
      srcp1 += 1;
      srcp2 += 1;
    }
  while (a0 == b0);
  return a0 - b0;
}

In ordinary C this costs nothing: a and b sit in registers or a stack slot, and the loop runs at most eight times. Nothing about it is wrong. It is only expensive once you know what Fil-C does with &a.

Why &a is expensive under Fil-C

address-taken local

A local variable whose address escapes, even just to (byte *)&a. Fil-C cannot keep it on the native stack: anything a pointer can reach must be a GC-managed object with bounds and shadow capabilities.

escape to the heap

The compiler moves such a local into a fresh heap allocation, made when the function is entered — before the first branch decides whether the local is ever used.

op_t

glibc's word type for the string functions: unsigned long on both Fil-C targets, x86-64 and aarch64.

memcmp_bytes is static and small, so it is inlined into memcmp — four times, once per call site in the unrolled comparison loops. Each inlined copy brings its own a and b. Four copies × two address-taken parameters = eight escaped locals, and the compiler hoists all eight allocations into memcmp's prologue. Every call pays for all of them, including calls that return on the first word and never reach any copy of memcmp_bytes at all. The same function backs bcmp, so it pays too.

What that costs in practice

memcmp is not a rare function. In PHP 8.5 it sits under hash lookups, ===, string comparison, str_starts_with and str_replace. Serving WordPress, one pass over the benchmark's requests made about 21 million of these prologue allocations — 678 MB allocated, roughly a third of everything the process allocated — for locals that almost never get read. They also set the pace of garbage collection: allocation volume is what asks FUGC for cycles, so a third of the GC pressure came from a three-line helper's addressing mode.

The fix: the words are already in registers

memcmp_bytes is handed both words by value. It never needed their addresses — it needed their bytes, in memory order. On a little-endian machine, memory order is lowest-byte-first, so the first differing byte is the lowest-order byte in which the words differ. That is what ctz(a ^ b) — count trailing zeros — finds: XOR marks every differing bit, and the lowest set bit sits in the first differing byte.

-  long int srcp1 = (long int) &a;
-  long int srcp2 = (long int) &b;
-  op_t a0, b0;
-
-  do
-    {
-      a0 = ((byte *) srcp1)[0];
-      b0 = ((byte *) srcp2)[0];
-      srcp1 += 1;
-      srcp2 += 1;
-    }
-  while (a0 == b0);
-  return a0 - b0;
+  /* Fil-C: taking the addresses of A and B made the compiler move them to
+     the heap, and since this function is inlined into memcmp, every memcmp
+     call made eight heap allocations. On little-endian machines the first
+     differing byte in memory is the lowest-order differing byte, so find it
+     by arithmetic. Callers only pass words that differ.  */
+  unsigned int shift = __builtin_ctzl (a ^ b) & ~7u;
+  return (int) ((a >> shift) & 0xff) - (int) ((b >> shift) & 0xff);

Seven lines in, thirteen out, in one function. No address is taken, nothing escapes, and memcmp goes back to allocating nothing at all.

Why the arithmetic version is exact

• ctz(0) never happens. __builtin_ctzl(0) is undefined, but every caller of memcmp_bytes in memcmp.c reaches it only after establishing that the two words differ — that is what the word-at-a-time loops test. So a ^ b ≠ 0 on entry, always.
• Little-endian is given. The identity “first byte in memory = lowest-order byte” is exactly little-endianness. Both Fil-C targets, x86-64 and aarch64, are little-endian, and this file already lives behind the generic implementation's byte-order handling. On a big-endian target the same idea would use clz; there is no such Fil-C target.
• The result is the same integer. The old loop returned a0 - b0 for the first differing byte pair; the new code extracts that same pair by shifting. Sign and magnitude are unchanged, not just the sign.
• Reads are unchanged. memcmp reads exactly the same words at the same addresses as before. The helper now computes on values already loaded instead of re-reading them through pointers — so if anything it reads less. There is no new out-of-bounds exposure; the test below deliberately ends ranges flush with object bounds.
• Timing. Generic memcmp was never constant-time (it exits at the first difference), and this change preserves that shape. Callers that need constant time already use their own, e.g. OpenSSL's CRYPTO_memcmp.

Test

filc/tests/memcmpnoalloc checks both halves of the claim — same answers and no allocation:

• Same answers: memcmp and bcmp are checked against a byte-loop reference at every source/destination alignment pair (8×8), lengths 0–72 and every mismatch position, on heap buffers of sizes 80–88 and on globals — with ranges ending exactly at the object's upper bound, so any over-read would trap instead of silently passing.
• No allocation: after a full collection, two million calls (varied offsets, lengths, plus full 4 KB bcmps) must request zero GC cycles, measured with zgc_requested_cycle().

Effect

On PHP 8.5 with the fixed memcmp/bcmp preloaded, on a quiet machine (per request pass over each fixture):

Filnix's staging toolchain has carried this since 22 October: the PHP 8.5 world built and tested with it, 1,222 PHP tests, 0 failures.

Two commits for pizlonator/fil-c deluge: a5d5dbc changes only projects/user-glibc-2.44/string/memcmp.c (+7/−13); 4eef902 adds filc/tests/memcmpnoalloc. This page was written for review and is not part of the patch.