x86-64 machine code (Linux system calls), 29B * 4.7GB/6.6GB = ~20.6 on tmpfs on Skylake
(Or even 28 bytes, but I haven't benchmarked Noah's suggestion of using the low 16 bits of the address as the count for rep stosd
. Asm source for it on Godbolt.)
At about 6.6 GiB/s, this runs faster than GNU yes
on tmpfs, the widely-used Linux ramdisk-like filesystem backed by the pagecache. I made sure to align my buffer to at least a cache-line boundary (and in fact a 4k page boundary) so the kernel's copy_from_user
memcpy-like function using rep movsb
would be most efficient.
I don't expect this will outperform yes
writing to an SSD on a fast Ryzen CPU which isn't the bottleneck; posted score is tentative. However, writing 2 or 4 bytes at a time is unusably slow so we need a buffer to avoid a huge score penalty (like a factor of 2000 on tmpfs!). But probably this will score about 29 running at the same speed as GNU yes
if they both fill the page-cache to max capacity with dirty pages and max out I/O bandwidth during the 1s window.
It's break-even for code size to use a buffer in the BSS instead of reserving stack space, in a Linux position-dependent executable where a static address can be put in a register with 5-byte mov r32, imm32
. Using more space in the BSS doesn't increase the size of an executable that already has a BSS section/segment. But in this case it does make the executable larger so I'm not totally sure it's justified to not count anything for executable metadata for the BSS. But as usual, I'm counting only the size of the .text
section. (And there's no initialized static data; all the constants are immediate.)
Without aligning the stack by 64 or 4k, sub esp, edx
; mov edi, esp
would be only 4 bytes, and safe in a Linux x32 executable: 32-bit pointers in 64-bit mode. (For efficient syscall
instead of slow int 0x80
or cumbersome sysenter
in 32-bit mode). Otherwise break-even for sub rsp, rdx
. So if not counting the BSS bothers you, save a byte and use the stack for buffers up to almost 8MiB (with default ulimit -s
).
We fill a buffer that's 4x larger than we actually pass to write; rep stosd
needs a repeat count of dword chunks and it's convenient to use the same number as a byte count for the system call.
Try it online! (NASM source which assembles to this answer's machine code.) It works on TIO; it doesn't depend on the output being a regular file or anything. Below is a NASM listing of machine code hexdump & source.
6 global _start
7 _start:
8 ;; All regs zeroed at the top of a Linux static executable (except RSP)
9
10 SIZEPOW equ 17
13 00000000 0FBAE911 bts ecx, SIZEPOW ; 1<<SIZEPOW x 4 bytes to fill.
14 00000004 89CA mov edx, ecx ; size arg for sys_write in bytes; 1/4 of the actual buffer size
15
16 00000006 B8790A790A mov eax, `y\ny\n`
25 0000000B BF[00000000] mov edi, buf ; mov r32, imm32 static address; 00... is before linking
26 00000010 89FE mov esi, edi ; syscall arg
27
28 ;shr ecx, 2 ; just fill 4x as much memory as needed
29 00000012 F3AB rep stosd ; wmemset(rdi, eax, rcx) 4*rcx bytes
30
31 00000014 8D7901 lea edi, [rcx + 1] ; mov edi, 1
32 .loop:
33 00000017 89F8 mov eax, edi ; __NR_write = stdout fileno
34 00000019 0F05 syscall
36 0000001B EBFA jmp .loop
47 section .bss
48 align 4096
49 00000000 <res 00080000> buf: resd 1<<SIZEPOW
0x1b + 2 bytes for last instruction is 29 bytes total.
mov cx, imm16
would also be 4 bytes, same as BTS, but is limited to 0..65535. vs. BTS r32, imm8 creating any power of 2. (Both depend on a zeroed RCX to start with, to produce a result zero-extended into RCX for rep stos
)
mov ax, `y\n`
would be 4 bytes, 1 fewer than mov eax, imm32
, but then we'd need rep stosw
which costs an extra operand-size prefix. This would have kept the ratio of filled buffer to used buffer at 2:1 instead of 4:1, so I should have done that to save a few pagefaults at startup, but not redoing the benchmarking now. (rep stosw
is still fast on Skylake I think; not sure if Zen+ might suffer; but more than a factor of 2 in fill bandwidth + page fault cost is unlikely.)
A static buffer makes alignment to a cache line (or even the page size) not cost instructions; having the stack only 16-byte aligned was a slowdown. I recorded times in comments on my original code that aligned the stack pointer by 64kiB or not after reserving space for a buffer. Alignment to 64k instead of 16B made a ~3% difference in overall speed for writing a 1GiB file (to tmpfs, exiting on ENOSPC) with SIZEPOW=16, and led to a reduction in instructions retired as well. (Measured with perf stat ./yes > testd/yesout
)
;;;; instead of mov edi, buf
sub rsp, rdx
; and rsp, -65536 ; With: 631.4M cycles 357.6M insns. Without: 651.3M cycles 359.4M instructions. (times are somewhat noisy but there's a real difference)
;; mov rdi, rsp ; 3 bytes
push rsp
pop rdi ; copy a 64-bit reg in 2 bytes
push rsp
pop rsi
For other benchmarking purposes (with a smaller 1GiB tmpfs), it was convenient to use a loop that exited when write()
failed (with -ENOSPC
) instead of looping until killed. I used this as the bottom of the loop
35 %if 0
36 0000001B EBFA jmp .loop
37 %else
38 test eax,eax ;;;;;;;;;;; For benchmarking purposes: abort on write fail
39 jge .loop
40
41 mov eax, 231 ; not golfed
42 xor edi, edi
43 syscall ; sys_exit_group(0)
44 %endif
45
Testing
I tested using tmpfs because I don't want to wear out my SSD repeatedly testing this. And because keeping up with a consumer-grade SSD is trivial with any reasonable buffer size. More interesting (to me) is to find the CPU/memory-bound sweet spot between system call overhead from making too many small write
system calls vs. L2 cache misses from re-reading too large a buffer every time. And also minimize time spent on filling a buffer before even starting to make system calls. (Although note that with write-behind I/O buffering for filesystems backed by real disk, there's no advantage to using a smaller buffer to get disk-write started sooner. I/O write-back to actual physical media wouldn't start until dirty pages hit the Linux kernel's high water mark. The default dirty timeout is 500 centisecs, and powertop suggests raising that to 1500 (15 seconds), so that's not going to come into play, just the high water mark. So what really matters is getting to the high water mark ASAP for a physical disk, and potentially pushing as many dirty pages into the pagecache as possible within the 1 second window, to finish writeback after yes
dies. So this 1-second test probably depends on how much RAM your machine has (and even how much free RAM), if you're using a physical disk instead of tmpfs.)
write
inside the kernel is basically a memcpy
from the provided buffer into the pagecache; specifically Linux's copy_from_user
function which uses rep movsb
on systems with ERMSB (Intel since IvB) or rep movsq
when it's fast (PPro and later, including non-Intel vendors.)
According to perf record
/ perf report
output, with a 128k buffer size, 45% of the counts for hardware "cycles" were in clear_page_erms
(on rep stosb
) and then 18.4% in copy_user_enhanced_fast_string
on rep movsb
. (Makes some sense: clearing is touching a cold page, copy is copying over a just-cleared buffer, presumably hitting in L2 cache for src and destination. Or L1d for dst if it clears 4k at a time. Or only L3 cache if it's clearing whole hugepages :/) Next highest was iov_iter_fault_in_readable
at 3.8%. But anyway, only ~63% of total CPU time was spent on the "real work" of actually copying into the pagecache. And that happens inefficiently, zeroing before copying.
I tried with tmpfs
with huge=never
(which is the default) and only got 4.8GiB for 1s with the 128kiB buffer version that gets 6.6GiB on hugepages. So clearly hugepages are worth it overall. perf record counts for cycles
were: 14%: clear_page_erms
and 10% copy_user_enhanced_fast_string
, with many other kernel functions taking low single digits percentages, like try_charge
at 4%, __pagevec_lru_add_fn
, get_mem_cgroup_from_mm
, __this_cpu_preempt_check
, and _raw_spin_lock_irq
at 3 to 2%. Managing memory in 4kiB chunks obviously costs a lot more than in 2MiB chunks.
Test setup
i7-6700k @ 3.9GHz with 0xd6 microcode update (Nov 2019). (quad core Skylake-client microarchitecture, per-core caches: L1d 32k, L2 256k. Shared L3 = 8MiB) vs. Ryzen having 512kiB L2 caches.
During this test: /sys/devices/system/cpu/cpufreq/policy0/energy_performance_preference
= balance_performance, not full performance
EPP setting. So this is closer to the normal bootup machine state of balance_power). I ran a warm-up run right before the main test to make sure the CPU speed was at full before the timed 1-second started: timeout 1s ./yes > testd/yesout; perf stat -d timeout 1s yes > testd/yesout
.
With EPP at performance
(max turbo = 4.2GHz, near-instant ramp-up), in practice it runs at 4.1GHz average for the test. I get up to 6.9GiB written instead of 6.6, for the 128k buffer version. (And up to 7.3GiB with the writev
version.)
16 GiB of DDR4-2666 (2x8GB DIMMs, dual channel)
OS = Arch GNU/Linux, kernel = Linux 5.4.13-arch1-1
Filesystem = tmpfs using transparent hugepages:
sudo mount -t tmpfs -o size=10G,huge=always tmpfs /tmp/test
. Much of the file is using transparent hugepages: from /proc/meminfo after writing a 6.4G file: ShmemHugePages: 6723584 kB
(6566MB), and goes down to 83968 kB
(82MB) after deleting it. It's using x86-64 2MiB hugepages instead of 4k normal pages to reduce TLB misses.
System idle except for Chromium using about 3% of one core at idle clock speed.
free memory was sufficient for tmpfs not to actually page anything out to swapspace during the test:
$ free -m # show numbers in megabytes. Test output deleted; tmpfs nearly empty
total used free shared buff/cache available
Mem: 15820 2790 12164 236 864 12497
Swap: 2047 930 1117
$ cat /proc/sys/vm/swappiness
6
Spectre / Meltdown mitigations (big overhead per system call, above the ~100 cycles each for syscall
/ sysret
to get in/out of the kernel):
$ grep . /sys/devices/system/cpu/vulnerabilities/*
/sys/devices/system/cpu/vulnerabilities/itlb_multihit:KVM: Vulnerable
/sys/devices/system/cpu/vulnerabilities/l1tf:Mitigation: PTE Inversion
/sys/devices/system/cpu/vulnerabilities/mds:Mitigation: Clear CPU buffers; SMT vulnerable
/sys/devices/system/cpu/vulnerabilities/meltdown:Mitigation: PTI
/sys/devices/system/cpu/vulnerabilities/spec_store_bypass:Mitigation: Speculative Store Bypass disabled via prctl and seccomp
/sys/devices/system/cpu/vulnerabilities/spectre_v1:Mitigation: usercopy/swapgs barriers and __user pointer sanitization
/sys/devices/system/cpu/vulnerabilities/spectre_v2:Mitigation: Full generic retpoline, IBPB: conditional, IBRS_FW, STIBP: conditional, RSB filling
/sys/devices/system/cpu/vulnerabilities/tsx_async_abort:Mitigation: Clear CPU buffers; SMT vulnerable
Results writing to tmpfs for 1 second: best case 6.6GiB
Timed with this as a shell one-liner
asm-link -nd yes.asm && # assemble with NASM + link
taskset -c 3 timeout 1s ./yes > testd/yesout; # warm-up run
time taskset -c 3 timeout 1s ./yes > testd/yesout;
ls -lh testd/yesout && rm testd/yesout
Up-arrow recall that string of commands a few times, take the best case. (Assume that lower values didn't ramp up the CPU speed right away; spent some time allocating hugepages, or had other spurious interference.)
I intentionally limited myself to only looking at 2 significant figures of file size (letting ls round to x.y GiB
) because I know there's going to be noise, so perhaps keeping the data simpler might be good.
Results for various buffer sizes writing to tmpfs: 6.6GiB
(I did see 6.7G in some early testing with SIZEPOW=16 or 17, and I think even 6.8 or 9, but couldn't reproduce it once things settled down. Maybe some lucky early arrangement of hugepages that didn't last into a stable state?)
SIZEPOW=1, buffer size: 2 (just 'y\n'
), best-case size: 2.9MiB
real 0m1.002s, user 0m0.431s, sys 0m0.570s
SIZEPOW=2, buffer size: 4, best-case size: 5.8MiB
real 0m1.002s, user 0m0.381s, sys 0m0.620s
...
SIZEPOW=11, buffer size: 1024, best-case size: 1.3GiB
real 0m1.005s, user 0m0.343s, sys 0m0.661s
SIZEPOW=11, buffer size: 2048, best-case size: 2.3GiB
real 0m1.008s, user 0m0.270s, sys 0m0.737s. (Smaller than 1x 4k page = bad)
SIZEPOW=12, buffer size: 4096, best-case size: 3.6GiB
real 0m1.012s, user 0m0.237s, sys 0m0.772s
SIZEPOW=13, buffer size: 8192 (same as GNU yes
), best-case size: 4.8GiB
real 0m1.016s, user 0m0.180s, sys 0m0.834s
SIZEPOW=14, buffer size: 16384, best-case size: 5.6GiB
real 0m1.018s, user 0m0.090s, sys 0m0.926s
SIZEPOW=15, buffer size: 32768, best-case size: 6.2GiB
real 0m1.019s, user 0m0.057s, sys 0m0.959s
SIZEPOW=16, buffer size: 64kiB, best-case size: 6.5GiB
real 0m1.021s, user 0m0.023s, sys 0m0.993s
SIZEPOW=17, buffer size: 128kiB (1/2 L2 cache size), best-case size: 6.6GiB
real 0m1.021s, user 0m0.017s, sys 0m1.002s
SIZEPOW=18, buffer size: 256kiB (= L2 cache size), best-case size: 6.6GiB
real 0m1.020s, user 0m0.013s, sys 0m1.005s
SIZEPOW=19, buffer size: 512kiB (2x L2 cache size), best-case size: 6.4GiB
real 0m1.021s, user 0m0.000s, sys 0m1.019s (User time getting meaningless / too small for Linux to measure accurately.)
SIZEPOW=20, buffer size: 1024kiB, best-case size: 6.2GiB
SIZEPOW=21, buffer size: 2MiB, best-case size: 5.7GiB
SIZEPOW=22, buffer size: 4MiB (1/2 L3 size), best-case size: 5.0GiB
SIZEPOW=23, buffer size: 8MiB (L3 cache size), best-case size: 4.9GiB
SIZEPOW=24, buffer size: 16MiB (2x L3 cache size), best-case size: 4.9GiB
SIZEPOW=25, buffer size: 32MiB, best-case size: 4.8GiB
...
SIZEPOW=28, buffer size: 256MiB, best-case size: 4.4GiB
GNU coreutils 8.31 yes
: buffer size 8192, best case size: 4.7GiB
(vs. 4.8GiB for my 8k buffer version. Perhaps because of lower startup overhead. My statically linked executable makes literally no system calls before write
, just a BSS pagefault or two, vs. GNU yes
being dynamically has more overhead before it gets going. And not quite as tight a loop around syscall
, probably involving indirect-call/ret into libc's write wrapper, so at least two different pages of code in user-space are touched between system calls. Two chances for iTLB or i-cache misses. (Making a system call tends to invalidate a lot, especially with Spectre / Meltdown / MDS mitigations enabled, but even without that if a lot of kernel code runs)
GNU yes
's buffer is 64-byte aligned (cache line) but not 4k-page aligned. IDK if that makes any difference or leads to more dTLB misses (from spanning 3 pages instead of 2). Being an odd multiple of 64 bytes (address ending in 0x440
) is not ideal for the L2 spatial prefetcher (which tries to complete 128B-aligned pairs of lines) but that's probably insignificant; 8kiB is small enough that we get lots of L1d hits and very few L2 misses overall, including both user and kernel space. (perf stat -d
)
The fall-off at the high end of size is I think due to cache and TLB misses. You can run perf stat -d
instead of time
to see LLC-misses. (And LLC-loads is an indication of L2 load misses. Indeed, small buffers get mostly L2 hits, larger buffers get some misses.)
Note that the time
real/user/system times are for the timeout
process itself, not for just the yes
workload. And that Linux's time accounting is somewhat granular, I think. perf stat
gives more details, but I didn't want even the tiny overhead of the occasional HW performance-counter event interrupt.
Further speedup ideas:
Spawning multiple threads (all writing with O_APPEND
) might be a minor win, depending on how much they serialize each other when appending. (I'm hoping they just reserve space and then copy, so a 2nd call can reserve more space while an earlier one is still copying. Otherwise we might need vmsplice
+ splice(2)
or something to do the page-dirtying in user-space and give pages to the kernel without further copying (SPLICE_F_GIFT
+ SPLICE_F_MOVE
)). But making a clone
system call would probably take significantly more code.
Intel desktop CPUs can nearly saturate their memory bandwidth with a single core, unlike many-core Xeons with higher memory / uncore latency; ironically/paradoxically worse single-core memory bandwidth despite more memory controller channels for higher aggregate bandwidth than dual/quad-core client chips. With significant time spent in the kernel not bottlenecked on DRAM bandwidth, multiple threads could still help.
Using writev(2)
to pass the same buffer multiple times with one system call could give the best of both worlds: small buffer for L1 / L2 hits while copying to the pagecache, but lots of work done per syscall. Maybe a few % speedup; (Tried it; got a 7.0G output with 20 io vecs for an 8kiB buffer, up from 6.6G. Kernel CPU time is now 49.5% clear_page_erms
, 13.2% copy_user_enhanced_fast_string
. So yes, less time spent copying, more time spent just clearing. 37 bytes, up from 29, score 26.3.
Source on Try it online!).
As expected it doesn't come close to paying for itself in user-space code size to create the array of ptr,length pairs, although it was possible with a loop
around 2 push
instructions (4 bytes), but extra instructions outside the loop to get the args into place were necessary. Also, the call number __NR_writev
is 20 so I used an array of 20 iovs, allowing the same trick as with fd
= __NR_write
to save a byte vs. lea
.
There's still overhead per iovec (200x 2k buffer is slower than 20x 8k buffer). The sweet spot is around 4k or 8k buffers, with very minor gains for using a big vector (20x 8k seems enough). IOV_MAX is "only" 1024, and isn't slower but is barely faster. (Try it online! - flexible iov size version for perf experiments also needs only a couple changes to flip back to plain write instead of writev.
write
system calls on a large-enough buffer to amortize overhead but not create too many L3 cache misses in the kernel'scopy_from_user
(basically memcpy into the pagecache or pipe buffer). \$\endgroup\$yes
is killed. Also, be careful when benchmarking: amount of free RAM could affect your measured result! Limit Linux background flush (dirty pages) has some benchmarks of dd of /dev/zero to a file. \$\endgroup\$