r/unix • u/kjensenxz • Jun 13 '17
How is GNU `yes` so fast?
How is GNU's yes so fast?
$ yes | pv > /dev/null
... [10.2GiB/s] ...Compared to other Unices, GNU is outrageously fast. NetBSD's is 139MiB/s, FreeBSD, OpenBSD, DragonFlyBSD have very similar code as NetBSD and are probably identical, illumos's is 141MiB/s without an argument, 100MiB/s with. OS X just uses an old NetBSD version similar to OpenBSD's, MINIX uses NetBSD's, BusyBox's is 107MiB/s, Ultrix's (3.1) is 139 MiB/s, COHERENT's is 141MiB/s.
Let's try to recreate its speed (I won't be including headers here):
/* yes.c - iteration 1 */
void main() {
while(puts("y"));
}
$ gcc yes.c -o yes
$ ./yes | pv > /dev/null
... [141 MiB/s] ...That's nowhere near 10.2 GiB/s, so let's just call write without the puts overhead.
/* yes.c - iteration 2 */
void main() {
while(write(1, "y\n", 2)); // 1 is stdout
}
$ gcc yes.c -o yes
$ ./yes | pv > /dev/null
... [6.21 MiB/s] ...Wait a second, that's slower than puts, how can that be? Clearly, there's some buffering going on before writing. We could dig through the source code of glibc, and figure it out, but let's see how yes does it first. Line 80 gives a hint:
/* Buffer data locally once, rather than having the
large overhead of stdio buffering each item. */The code below that simply copies argv[1:] or "y\n" to a buffer, and assuming that two or more copies could fit, copies it several times to a buffer of BUFSIZ. So, let's use a buffer:
/* yes.c - iteration 3 */
#define LEN 2
#define TOTAL LEN * 1000
int main() {
char yes[LEN] = {'y', '\n'};
char *buf = malloc(TOTAL);
int used = 0;
while (used < TOTAL) {
memcpy(buf+used, yes, LEN);
used += LEN;
}
while(write(1, buf, TOTAL));
return 1;
}
$ gcc yes.c -o yes
$ ./yes | pv > /dev/null
... [4.81GiB/s] ...That's a ton better, but why aren't we reaching the same speed as GNU's yes? We're doing the exact same thing, maybe it's something to do with this full_write function. Digging leads to this being a wrapper for a wrapper for a wrapper (approximately) just to write().
This is the only part of the while loop, so maybe there's something special about their BUFSIZ?
I dug around in yes.c's headers forever, thinking that maybe it's part of config.h which autotools generates. It turns out, BUFSIZ is a macro defined in stdio.h:
#define BUFSIZ _IO_BUFSIZWhat's _IO_BUFSIZ? libio.h:
#define _IO_BUFSIZ _G_BUFSIZAt least the comment gives a hint: _G_config.h:
#define _G_BUFSIZ 8192Now it all makes sense, BUFSIZ is page-aligned (memory pages are 4096 bytes, usually), so let's change the buffer to match:
/* yes.c - iteration 4 */
#define LEN 2
#define TOTAL 8192
int main() {
char yes[LEN] = {'y', '\n'};
char *buf = malloc(TOTAL);
int bufused = 0;
while (bufused < TOTAL) {
memcpy(buf+bufused, yes, LEN);
bufused += LEN;
}
while(write(1, buf, TOTAL));
return 1;
}And, since without using the same flags as the yes on my system does make it run slower (yes on my system was built with CFLAGS="-O2 -pipe -march=native -mtune=native"), let's build it differently, and refresh our benchmark:
$ gcc -O2 -pipe -march=native -mtune=native yes.c -o yes
$ ./yes | pv > /dev/null
... [10.2GiB/s] ...
$ yes | pv > /dev/null
... [10.2GiB/s] ...We didn't beat GNU's yes, and there probably is no way. Even with the function overheads and additional bounds checks of GNU's yes, the limit isn't the processor, it's how fast memory is. With DDR3-1600, it should be 11.97 GiB/s (12.8 GB/s), where is the missing 1.5? Can we get it back with assembly?
; yes.s - iteration 5, hacked together for demo
BITS 64
CPU X64
global _start
section .text
_start:
inc rdi ; stdout, will not change after syscall
mov rsi, y ; will not change after syscall
mov rdx, 8192 ; will not change after syscall
_loop:
mov rax, 1 ; sys_write
syscall
jmp _loop
y: times 4096 db "y", 0xA
$ nasm -f elf64 yes.s
$ ld yes.o -o yes
$ ./yes | pv > /dev/null
... [10.2GiB/s] ...It looks like we can't outdo C nor GNU in this case. Buffering is the secret, and all the overhead incurred by the kernel throttles our memory access, pipes, pv, and redirection is enough to negate 1.5 GiB/s.
What have we learned?
Buffer your I/O for faster throughput
Traverse source files for information
You can't out-optimize your hardware
Edit: _mrb managed to edit pv to reach over 123GiB/s on his system!
Edit: Special mention to agonnaz's contribution in various languages! Extra special mention to Nekit1234007's implementation completely doubling the speed using vmsplice!
