Concurrent allocation does not scale: default (Boehm) GC serializes GC_malloc across threads

Open

enghitaloopened 4mo ago

Describe the bug (performance / scalability)

On a multi-core machine, allocation-heavy work does not scale across threads under V's default (Boehm) GC. N threads each doing a fixed number of small heap allocations take ~N× longer in wall time (i.e. they run serially), while identical pure-compute work scales perfectly across cores. This caps thread-per-core servers (a common V use case): request handling that allocates per request cannot use more than ~one core's worth of allocation throughput.

Reproduction Steps

import time
import os

fn compute_work(iters int) u64 {
	mut acc := u64(1)
	for i in 0 .. iters {
		acc = acc * 6364136223846793005 + u64(i)
		acc ^= acc >> 13
	}
	return acc
}

fn alloc_work(iters int) u64 {
	mut acc := u64(0)
	for i in 0 .. iters {
		mut b := []u8{len: 256} // one small heap allocation per iteration
		b[0] = u8(i)
		acc += u64(b[0])
	}
	return acc
}

fn main() {
	mode := if os.args.len > 1 { os.args[1] } else { 'alloc' }
	nthreads := if os.args.len > 2 { os.args[2].int() } else { 1 }
	per := 3_000_000
	sw := time.new_stopwatch()
	mut threads := []thread u64{}
	for _ in 0 .. nthreads {
		if mode == 'compute' {
			threads << spawn compute_work(per)
		} else {
			threads << spawn alloc_work(per)
		}
	}
	mut total := u64(0)
	for t in threads {
		total += t.wait()
	}
	println('${mode} threads=${nthreads} wall=${sw.elapsed().milliseconds()}ms')
}

v -prod -o gcs bug.v
./gcs compute 1 ; ./gcs compute 16    # control: pure compute, no allocation
./gcs alloc   1 ; ./gcs alloc   16    # one small heap alloc per iteration

Current Behavior (16-core AMD Ryzen 7 5800H, Ubuntu 24.04)

compute threads=1   wall=4ms
compute threads=16  wall=5ms       # 16x the work, ~same wall time → scales linearly
alloc   threads=1   wall=260ms
alloc   threads=16  wall=4226ms    # 16x the work, 16.3x wall time → fully serialized

Each thread does identical, independent work. The only difference between the two modes is the per-iteration []u8{len:256} allocation. Compute parallelizes across all cores; allocation does not.

strace -fc ./gcs alloc 16 shows the time is in stop-the-world coordination, not the allocation itself:

% time     calls    syscall
 45.21    192192    clock_nanosleep
 45.00    220599    rt_sigsuspend
  4.05     31467    futex
  2.49    912906    rt_sigprocmask
  ...      441198    rt_sigreturn / getpid / tgkill

i.e. concurrent GC_malloc serializes on Boehm's global allocation lock / stop-the-world.

Expected Behavior

Concurrent small-object allocation should scale with cores (much closer to the compute control), so multi-threaded / thread-per-core programs can allocate in parallel.

Possible Solution

The bundled Boehm GC appears not to use thread-local allocation. Building libgc with -DTHREAD_LOCAL_ALLOC (Boehm's per-thread free lists, used by GC_malloc for small objects) lets concurrent small allocations proceed without taking the global lock on the fast path, and should restore most of the scaling. If that is impractical, documenting the limitation plus the -gc none + arena/manual-memory path for hot multi-threaded code would help server authors.

V version: V 0.5.1 498584c Environment: Ubuntu 24.04 LTS, Linux 6.8.0-41-generic, x86_64

NOTE

You can use the 👍 reaction to increase the issue's priority for developers.

Please note that only the 👍 reaction to the issue itself counts as a vote. Other reactions and those to comments will not be taken into account.

Activity

enghitalo4mo ago

Regression / acceptance test (machine-independent)

A pass/fail test for a scaling property can't use an absolute time threshold (flaky across core counts / VMs / CI). This version instead measures a pure-compute control on the same machine to learn its real parallelism, then requires that concurrent allocation scales at least ~40% as well as compute. It skips (no false failure) when the machine can't parallelize compute at all (<4 cores, contended VM).

FAILS today (Boehm serializes GC_malloc on a global lock: allocation ~1×, often <1×).
PASSES once small-object allocation has a lock-free fast path (e.g. libgc built with THREAD_LOCAL_ALLOC).

import time
import runtime

fn alloc_work(iters int) u64 {
	mut acc := u64(0)
	for i in 0 .. iters {
		mut b := []u8{len: 256} // one small heap allocation per iteration
		b[0] = u8(i)
		acc += u64(b[0])
	}
	return acc
}

fn compute_work(iters int) u64 {
	mut acc := u64(1)
	for i in 0 .. iters {
		acc = acc * 6364136223846793005 + u64(i)
		acc ^= acc >> 13
	}
	return acc
}

fn par_alloc(nt int, per int) i64 {
	sw := time.new_stopwatch()
	mut ts := []thread u64{}
	for _ in 0 .. nt {
		ts << spawn alloc_work(per)
	}
	mut a := u64(0)
	for t in ts {
		a += t.wait()
	}
	assert a > 0
	return sw.elapsed().milliseconds()
}

fn par_compute(nt int, per int) i64 {
	sw := time.new_stopwatch()
	mut ts := []thread u64{}
	for _ in 0 .. nt {
		ts << spawn compute_work(per)
	}
	mut a := u64(0)
	for t in ts {
		a += t.wait()
	}
	assert a > 0
	return sw.elapsed().milliseconds()
}

fn test_concurrent_allocation_scales() {
	cores := runtime.nr_cpus()
	if cores < 4 {
		eprintln('SKIP: needs >= 4 cores (got ${cores})')
		return
	}
	nt := if cores > 8 { 8 } else { cores }
	alloc_work(200_000) // warm up
	compute_work(200_000)

	// Compute control: same shape, no allocation — learns this machine's parallelism.
	c_serial := par_compute(1, nt * 40_000_000)
	c_par := par_compute(nt, 40_000_000)
	c_speedup := f64(c_serial) / f64(c_par)
	if c_speedup < f64(nt) * 0.5 {
		eprintln('SKIP: machine did not parallelize compute (${c_speedup:.1f}x on ${nt} threads; contended/VM?)')
		return
	}

	// Allocation: same shape, one small heap alloc per iteration.
	a_serial := par_alloc(1, nt * 2_000_000)
	a_par := par_alloc(nt, 2_000_000)
	a_speedup := f64(a_serial) / f64(a_par)

	println('scaling on ${cores} cores (${nt} threads): compute=${c_speedup:.1f}x  alloc=${a_speedup:.1f}x')
	assert a_speedup > c_speedup * 0.4, 'concurrent allocation scaled only ${a_speedup:.1f}x vs compute ${c_speedup:.1f}x (${nt} threads) — GC_malloc serializes on a global lock (vlang/v#27486)'
}

Current output (FAILS) — V 0.5.1 498584c, 16-core Ryzen 7 5800H

scaling on 16 cores (8 threads): compute=6.4x  alloc=0.8x
   > assert a_speedup > c_speedup * f64(0.4), ...
        Message: concurrent allocation scaled only 0.8x vs compute 6.4x (8 threads) — GC_malloc serializes on a global lock (vlang/v#27486)
FAIL

Pure compute scales 6.4× across 8 threads on this box; allocation scales 0.8× (i.e. 8 threads doing the same total work are slower than 1 thread — global-lock contention on top of serialization). The bar is compute × 0.4, so it adapts to the host and only fires where real parallelism exists. Caveat: it is still a timing measurement, so it belongs with benchmarks rather than the fast unit suite; the compute-normalization + skip-gate are what make it dependable as a reproducer/guard.