compiler_rt memset is not optimal #32091

Zig Version

0.16.0

Steps to Reproduce and Observed Behavior

$ git clone https://codeberg.org/kiesel-js/kiesel
$ zig build -Doptimize=ReleaseFast -Dtarget=x86_64-linux-musl -Denable-intl=false -Denable-temporal=false
$ objdump --no-addresses --no-show-raw-insn --disassemble='compiler_rt.memset' ./zig-out/bin/kiesel
./zig-out/bin/kiesel: file format elf64-x86-64
Disassembly of section .text:
<compiler_rt.memset>:
 mov %rdi,%rax
 test %rdx,%rdx
 je <compiler_rt.memset+0x81>
 mov %rdx,%r8
 mov %rdx,%rdi
 mov %rax,%rcx
 and 0ドルx7,%r8
 je <compiler_rt.memset+0x36>
 xor %ecx,%ecx
 nopl 0x0(%rax)
 mov %sil,(%rax,%rcx,1)
 add 0ドルx1,%rcx
 cmp %rcx,%r8
 jne <compiler_rt.memset+0x20>
 mov %rdx,%rdi
 sub %rcx,%rdi
 add %rax,%rcx
 cmp 0ドルx8,%rdx
 jb <compiler_rt.memset+0x81>
 push %rbp
 mov %rsp,%rbp
 xor %edx,%edx
 cs nopw 0x0(%rax,%rax,1)
 nopl 0x0(%rax)
 mov %sil,(%rcx,%rdx,1)
 mov %sil,0x1(%rcx,%rdx,1)
 mov %sil,0x2(%rcx,%rdx,1)
 mov %sil,0x3(%rcx,%rdx,1)
 mov %sil,0x4(%rcx,%rdx,1)
 mov %sil,0x5(%rcx,%rdx,1)
 mov %sil,0x6(%rcx,%rdx,1)
 mov %sil,0x7(%rcx,%rdx,1)
 add 0ドルx8,%rdx
 cmp %rdx,%rdi
 jne <compiler_rt.memset+0x50>
 pop %rbp
 ret

Compare to 0.15 which used musl's memset:

.global memset
.type memset,@function
memset:
	movzbq %sil,%rax
	mov 0ドルx101010101010101,%r8
	imul %r8,%rax
	cmp 126,ドル%rdx
	ja 2f
	test %edx,%edx
	jz 1f
	mov %sil,(%rdi)
	mov %sil,-1(%rdi,%rdx)
	cmp 2,ドル%edx
	jbe 1f
	mov %ax,1(%rdi)
	mov %ax,(-1-2)(%rdi,%rdx)
	cmp 6,ドル%edx
	jbe 1f
	mov %eax,(1+2)(%rdi)
	mov %eax,(-1-2-4)(%rdi,%rdx)
	cmp 14,ドル%edx
	jbe 1f
	mov %rax,(1+2+4)(%rdi)
	mov %rax,(-1-2-4-8)(%rdi,%rdx)
	cmp 30,ドル%edx
	jbe 1f
	mov %rax,(1+2+4+8)(%rdi)
	mov %rax,(1+2+4+8+8)(%rdi)
	mov %rax,(-1-2-4-8-16)(%rdi,%rdx)
	mov %rax,(-1-2-4-8-8)(%rdi,%rdx)
	cmp 62,ドル%edx
	jbe 1f
	mov %rax,(1+2+4+8+16)(%rdi)
	mov %rax,(1+2+4+8+16+8)(%rdi)
	mov %rax,(1+2+4+8+16+16)(%rdi)
	mov %rax,(1+2+4+8+16+24)(%rdi)
	mov %rax,(-1-2-4-8-16-32)(%rdi,%rdx)
	mov %rax,(-1-2-4-8-16-24)(%rdi,%rdx)
	mov %rax,(-1-2-4-8-16-16)(%rdi,%rdx)
	mov %rax,(-1-2-4-8-16-8)(%rdi,%rdx)
1:	mov %rdi,%rax
	ret
2:	test 15,ドル%edi
	mov %rdi,%r8
	mov %rax,-8(%rdi,%rdx)
	mov %rdx,%rcx
	jnz 2f
1:	shr 3,ドル%rcx
	rep
	stosq
	mov %r8,%rax
	ret
2:	xor %edx,%edx
	sub %edi,%edx
	and 15,ドル%edx
	mov %rax,(%rdi)
	mov %rax,8(%rdi)
	sub %rdx,%rcx
	add %rdx,%rdi
	jmp 1b

Profiling shows compiler_rt memset is about 4x slower than musl:

image

image

Expected Behavior

Something as fundamental as memset should have decent performance before we drop the libc implementation.

Workaround: kiesel-js/kiesel@c31209a754

Note that while this issue is exacerbated by using zig's memset implementation for libc, the missed optimization has always been affecting Zig code. I disagree with the implication above; given the purpose of Zig project to replace C, it is just as important, if not more important, to have decent performance for @memset in zig as it is in libc. Making them use the same implementation is a good step forward towards this goal, in particular since it appears to have shown a spotlight on the problem.

Agreed - I did not mean to imply this is only relevant for C code, that just happens to be where most of the usage is in my profiled benchmark because it's (bdw)gc-heavy.

Understood. To be clear, I very much appreciate you bringing this up, and I agree with you it's an important issue. I just wanted to communicate to other contributors that performance parity does not block the zig libc subproject - even on memset and memcpy. That said I would of course like to see attempts to bring it up to speed, ideally without using inline asm. We can make changes to SIMD in the language as necessary.

Issue close criteria: when all Tier 1 and Tier 2 supported targets have equal or better machine code than at least these libcs, if not all known other implementations:

• musl
• glibc

Exceptions can be made if a "sweet spot" is found - if the same zig source code (not inline assembly) can output machine code within 5% of optimal.

Issue close criteria: when all Tier 1 and Tier 2 supported targets have equal or better machine code than at least these libcs, if not all known other implementations:

* musl
* glibc

I'd be happy to give this a go, but first I'd like to nail down what you mean by "equal or better codegen".
My first instinct would be equal or better performance in benchmarks in ReleaseFast, but perhaps we should also ensure small (& reasonably efficient) codegen in ReleaseSmall?

Me and maybe some others from this Ziggit thread are also trying to write a better memset. Probably it's best to benchmark each and use the fastest. For ReleaseSmall we can do something similar to what is done in memcpy: Use a small implementation (like the current one) for ReleaseSmall and a fast implementation for the other modes.

Yep, followed the thread. Your implementation looks quite good already

I've tried to improve on @rpkak's implementation. I've made some benchmarks that also compares them to glibc and musl. They are roughly match glibc's x86_64 assembly, and beat musl's x86_64 assembly (although there are some edge cases where this isn't the case). They also handily beat the memset builtin to Ubuntu's glibc by default.

I was unable to compile the aarch64 assembly for either musl or glibc, so the benchmark on that cpu is less informative, but the x86_64 output is promising.

"Write Length" is the len parameter of the memset calls.

Google Cloud C4D instance 2vCPU (AMD zen4)

result
result

Google Cloud C4A instance 2vCPU (Google axion aarch64)

result
result

Intel 8565u (laptop cpu)

result
result

Benchmark code: https://github.com/skk64/zig-memset-bench

If this is good enough, I'm happy to submit a PR.

If this is good enough

if it is an incremental improvement, it is good enough to be merged

edit: the perf in those graphs looks good enough to close this issue as well.

@samkk wrote in #32091 (comment):

Benchmark code: https://github.com/skk64/zig-memset-bench

How can I run your benchmark? Just running zig build with version 0.17.0-dev.813+2153f8143 results in compile errors.
Is your benchmark using std's Clock.now() or hyperfine? Your repo seems to include both.

@rpkak got it to compile with:

--- a/src/main.zig
+++ b/src/main.zig
@@ -48,12 +48,12 @@ pub fn main(init: std.process.Init) !void {
 const args = try init.minimal.args.toSlice(arena);
 
 if (args.len < 4) {
- std.debug.print("Usage: {} [memset name] [total bytes written] [bytes written per memset call]\n", .{args[0]});
+ std.debug.print("Usage: {s} [memset name] [total bytes written] [bytes written per memset call]\n", .{args[0]});
 return error.NotEnoughArgs;
 }
 
- const memset = memset_fn(args[1]) catch (e) {
- std.debug.print("{} doesn't match any memset\n", .{args[1]});
+ const memset = memset_fn(args[1]) catch |e| {
+ std.debug.print("{s} doesn't match any memset\n", .{args[1]});
 // std.debug.print("\n", .{});
 return e;
 };

My bad - I was pretty slack with version control. Fixed now. I used the gen_results(...).sh scripts to generate the data, then plot it with the plot.py script. It requires hyperfine and the plotting uses pandas+matlotlib

I compared @samkk and my implementation with this code:

conststd=@import("std");constcount=100;constbytes=1<<26;conststep=1<<15;externfnrpkakMemset(dest:?[*]u8,c:u8,len:usize)callconv(.c)?[*]u8;externfnskk64Memset(dest:?[*]u8,c:u8,len:usize)callconv(.c)?[*]u8;pubfnmain()!void{constslice=trystd.heap.page_allocator.alloc(u8,bytes+1);for(0..count)|_|{varptr=slice.ptr+1;_=&ptr;for(0..bytes/step)|_|{_=rpkakMemset(ptr,'A',step);// _ = skk64Memset(ptr, 'A', step);ptr+=step;}}}

The + 1 after bytes and slice.ptr makes the input unaligned to the page and anything smaller (unaligned is with + 1, aligned is without + 1).

The ptr += step causes the implementation to use less used memory (uncached is with ptr += step;, cached is without ptr += step;).

$ for mode in {un,}aligned_{un,}cached; do poop -d 100000 ./rpkak_"$mode" ./skk64_"$mode"; done
Benchmark 1 (455 runs): ./rpkak_unaligned_uncached
 measurement mean ± σ min ... max outliers delta
 wall_time 220ms ± 874us 217ms ... 223ms 7 ( 2%) 0%
 peak_rss 68.7MB ± 82.8KB 68.5MB ... 68.8MB 1 ( 0%) 0%
 cpu_cycles 1.05G ± 6.14M 1.04G ... 1.07G 11 ( 2%) 0%
 instructions 170M ± 34.2 170M ... 170M 34 ( 7%) 0%
 cache_references 278M ± 599K 272M ... 279M 6 ( 1%) 0%
 cache_misses 183K ± 5.09K 174K ... 200K 8 ( 2%) 0%
 branch_misses 4.12K ± 132 3.77K ... 4.77K 5 ( 1%) 0%
Benchmark 2 (442 runs): ./skk64_unaligned_uncached
 measurement mean ± σ min ... max outliers delta
 wall_time 226ms ± 937us 224ms ... 230ms 4 ( 1%) 💩+ 2.9% ± 0.1%
 peak_rss 68.7MB ± 83.2KB 68.5MB ... 68.8MB 0 ( 0%) + 0.0% ± 0.0%
 cpu_cycles 1.08G ± 4.71M 1.07G ... 1.09G 1 ( 0%) 💩+ 2.8% ± 0.1%
 instructions 164M ± 42.0 164M ... 164M 19 ( 4%) ⚡- 3.5% ± 0.0%
 cache_references 305M ± 375K 302M ... 306M 8 ( 2%) 💩+ 9.8% ± 0.0%
 cache_misses 158K ± 1.86K 154K ... 181K 10 ( 2%) ⚡- 13.8% ± 0.3%
 branch_misses 4.28K ± 119 3.93K ... 5.12K 19 ( 4%) 💩+ 3.9% ± 0.4%
Benchmark 1 (2116 runs): ./rpkak_unaligned_cached
 measurement mean ± σ min ... max outliers delta
 wall_time 47.2ms ± 759us 45.9ms ... 50.9ms 51 ( 2%) 0%
 peak_rss 3.71MB ± 92.2KB 3.51MB ... 3.85MB 0 ( 0%) 0%
 cpu_cycles 222M ± 2.31M 220M ... 235M 446 (21%) 0%
 instructions 169M ± 4.78 169M ... 169M 31 ( 1%) 0%
 cache_references 5.98M ± 5.92M 1.08M ... 105M 771 (36%) 0%
 cache_misses 4.30K ± 328 3.88K ... 5.47K 298 (14%) 0%
 branch_misses 3.26K ± 49.5 3.13K ... 3.42K 11 ( 1%) 0%
Benchmark 2 (1664 runs): ./skk64_unaligned_cached
 measurement mean ± σ min ... max outliers delta
 wall_time 60.1ms ± 768us 57.5ms ... 63.4ms 341 (20%) 💩+ 27.3% ± 0.1%
 peak_rss 3.72MB ± 94.0KB 3.51MB ... 3.85MB 0 ( 0%) + 0.4% ± 0.2%
 cpu_cycles 287M ± 3.01M 277M ... 299M 244 (15%) 💩+ 29.2% ± 0.1%
 instructions 163M ± 4.45 163M ... 163M 18 ( 1%) ⚡- 3.5% ± 0.0%
 cache_references 6.71M ± 8.45M 1.18M ... 41.1M 473 (28%) 💩+ 12.2% ± 7.7%
 cache_misses 4.42K ± 393 3.94K ... 5.49K 0 ( 0%) 💩+ 2.8% ± 0.5%
 branch_misses 3.41K ± 45.8 3.23K ... 3.55K 92 ( 6%) 💩+ 4.3% ± 0.1%
Benchmark 1 (457 runs): ./rpkak_aligned_uncached
 measurement mean ± σ min ... max outliers delta
 wall_time 219ms ± 726us 218ms ... 222ms 3 ( 1%) 0%
 peak_rss 68.7MB ± 75.6KB 68.5MB ... 68.8MB 2 ( 0%) 0%
 cpu_cycles 1.05G ± 4.20M 1.04G ... 1.06G 0 ( 0%) 0%
 instructions 169M ± 2.90 169M ... 169M 14 ( 3%) 0%
 cache_references 274M ± 451K 272M ... 275M 4 ( 1%) 0%
 cache_misses 162K ± 2.82K 156K ... 174K 11 ( 2%) 0%
 branch_misses 5.00K ± 118 4.49K ... 5.23K 30 ( 7%) 0%
Benchmark 2 (456 runs): ./skk64_aligned_uncached
 measurement mean ± σ min ... max outliers delta
 wall_time 219ms ± 970us 218ms ... 229ms 5 ( 1%) + 0.1% ± 0.1%
 peak_rss 68.7MB ± 75.3KB 68.5MB ... 68.8MB 3 ( 1%) + 0.0% ± 0.0%
 cpu_cycles 1.04G ± 3.58M 1.04G ... 1.05G 0 ( 0%) - 0.1% ± 0.0%
 instructions 164M ± 3.89 164M ... 164M 20 ( 4%) ⚡- 3.0% ± 0.0%
 cache_references 274M ± 393K 273M ... 275M 4 ( 1%) - 0.0% ± 0.0%
 cache_misses 166K ± 3.41K 156K ... 177K 13 ( 3%) 💩+ 2.6% ± 0.3%
 branch_misses 4.40K ± 125 3.98K ... 4.67K 30 ( 7%) ⚡- 12.0% ± 0.3%
Benchmark 1 (2213 runs): ./rpkak_aligned_cached
 measurement mean ± σ min ... max outliers delta
 wall_time 45.1ms ± 724us 44.0ms ... 58.4ms 30 ( 1%) 0%
 peak_rss 3.68MB ± 86.9KB 3.50MB ... 3.83MB 0 ( 0%) 0%
 cpu_cycles 211M ± 839K 210M ... 216M 230 (10%) 0%
 instructions 168M ± 4.28 168M ... 168M 64 ( 3%) 0%
 cache_references 2.78M ± 529K 451K ... 3.61M 426 (19%) 0%
 cache_misses 4.30K ± 355 3.83K ... 5.48K 354 (16%) 0%
 branch_misses 3.48K ± 52.6 3.18K ... 3.69K 42 ( 2%) 0%
Benchmark 2 (2219 runs): ./skk64_aligned_cached
 measurement mean ± σ min ... max outliers delta
 wall_time 45.0ms ± 722us 43.9ms ... 54.6ms 11 ( 0%) - 0.2% ± 0.1%
 peak_rss 3.69MB ± 88.2KB 3.44MB ... 3.83MB 1 ( 0%) + 0.1% ± 0.1%
 cpu_cycles 211M ± 428K 211M ... 216M 241 (11%) - 0.0% ± 0.0%
 instructions 163M ± 3.95 163M ... 163M 36 ( 2%) ⚡- 3.0% ± 0.0%
 cache_references 2.81M ± 452K 453K ... 4.31M 413 (19%) + 1.1% ± 1.0%
 cache_misses 4.28K ± 344 3.88K ... 5.51K 353 (16%) - 0.5% ± 0.5%
 branch_misses 3.34K ± 46.5 3.19K ... 3.50K 34 ( 2%) ⚡- 4.2% ± 0.1%

@rpkak wrote in #32091 (comment):

wall_time 60.1ms ± 768us 57.5ms ... 63.4ms 341 (20%) 💩+ 27.3% ± 0.1%

Before I saw this, I was never convinced that aligning writes mattered for something like memset. But it looks like it does if all the memory is already in L1.