Coffee Space

yes

This is the baseline yes currently installed on the test machine. The version information is as follows:

0026 $ yes --version
0027 yes (GNU coreutils) 8.32
0028 Copyright (C) 2020 Free Software Foundation, Inc.
0029 Licence GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>.
0030 This is free software: you are free to change and redistribute it.
0031 There is NO WARRANTY, to the extent permitted by law.
0032 
0033 Written by David MacKenzie.

yes-orig

This is the original “iteration 4” from the Reddit post:

0034 /**
0035  * yes.c
0036  *
0037  * Source: https://old.reddit.com/r/unix/comments/6gxduc/how_is_gnu_yes_so_fast/
0038  **/
0039 
0040 #define LEN 2
0041 #define TOTAL 8192
0042 
0043 int main(){
0044   char yes[LEN] = {'y', '\n'};
0045   char* buf = malloc(TOTAL);
0046   int bufused = 0;
0047   while(bufused < TOTAL){
0048     memcpy(buf + bufused, yes, LEN);
0049     bufused += LEN;
0050   }
0051   while(write(1, buf, TOTAL));
0052   return 1;
0053 }

This is ultimately the implementation we are trying to beat.

yes-prebuild_buffer

I wondered whether there would be any difference between dynamically allocating the buffer, or having the binary packed with the buffer already setup. My thinking was that it may be loaded into the same memory, therefore use a single page of cache.

0054 /**
0055  * yes-prebuild_buffer.c
0056  *
0057  * The idea for this modification is to pre-build the buffer used.
0058  **/
0059 
0060 #define LEN 2
0061 #define TOTAL 8192
0062 
0063 char buf[TOTAL] = {
0064   'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n',
0065   /* [..] Many duplicates here! [..] */
0066   'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n', 'y', '\n',
0067 };
0068 
0069 /**
0070  * main()
0071  *
0072  * The main entry function.
0073  *
0074  * @return The exit status.
0075  **/
0076 int main(){
0077   while(write(1, buf, TOTAL));
0078   return 1;
0079 }

The variable buf of course was filled with TOTAL number of y and \n values. This had the affect of increasing the binary size.

yes-setbuf

With this implementation, I was wondering whether the kernel was buffering the output to stdout (as it sometimes does with networks and disk I/O). The idea here was to override this with setvbuf and set the output as unbuffered _IOFBF:

0080 /**
0081  * yes-setbuf.c
0082  *
0083  * The idea for this modification is to set the program as unbuffered.
0084  **/
0085 
0086 #include <stdio.h>
0087 
0088 #define LEN 2
0089 #define TOTAL 8192
0090 
0091 /**
0092  * main()
0093  *
0094  * The main entry function.
0095  *
0096  * @return The exit status.
0097  **/
0098 int main(){
0099   char yes[LEN] = {'y', '\n'};
0100   char* buf = malloc(TOTAL);
0101   int bufused = 0;
0102   while(bufused < TOTAL){
0103     memcpy(buf + bufused, yes, LEN);
0104     bufused += LEN;
0105   }
0106   setvbuf(stdout, buf, _IOFBF, TOTAL);
0107   while(write(1, buf, TOTAL));
0108   return 1;
0109 }

yes-reduce_branch

An additional line of enquiry was whether we were paying any cost for the while loop, specifically in branching:

0110 /**
0111  * yes-reduce_branch.c
0112  *
0113  * The idea for this modification is to reduce the branching caused by the main
0114  * loop.
0115  **/
0116 
0117 #define LEN 2
0118 #define TOTAL 8192
0119 
0120 /**
0121  * main()
0122  *
0123  * The main entry function.
0124  *
0125  * @return The exit status.
0126  **/
0127 int main(){
0128   char yes[LEN] = {'y', '\n'};
0129   char* buf = malloc(TOTAL);
0130   int bufused = 0;
0131   while(bufused < TOTAL){
0132     memcpy(buf + bufused, yes, LEN);
0133     bufused += LEN;
0134   }
0135   while(1){
0136     write(1, buf, TOTAL);
0137     write(1, buf, TOTAL);
0138     write(1, buf, TOTAL);
0139     write(1, buf, TOTAL);
0140     write(1, buf, TOTAL);
0141     write(1, buf, TOTAL);
0142     write(1, buf, TOTAL);
0143     write(1, buf, TOTAL);
0144   }
0145   return 1;
0146 }

Of course the massive assumption here is that there isn’t tonnes of branching already in write() or any calls it makes - which you can be sure there is.

yes-aligned

One thing it’s possible we are paying for is unaligned memory - i.e. our data sits in two pages instead of just one. We can therefore allocate a memory aligned buffer and test this:

0147 /**
0148  * yes-aligned.c
0149  *
0150  * The idea for this modification is to force memory alignment.
0151  **/
0152 
0153 #define LEN 2
0154 #define TOTAL 8192
0155 
0156 /**
0157  * main()
0158  *
0159  * The main entry function.
0160  *
0161  * @return The exit status.
0162  **/
0163 int main(){
0164   char yes[LEN] = {'y', '\n'};
0165   char* buf = aligned_alloc(4096, TOTAL);
0166   int bufused = 0;
0167   while(bufused < TOTAL){
0168     memcpy(buf + bufused, yes, LEN);
0169     bufused += LEN;
0170   }
0171   while(write(1, buf, TOTAL));
0172   return 1;
0173 }

yes-vmsplice

This was a recommendation from the Reddit thread that was completely off of my radar - and hence made this exercise very much worth it. It turns out that vmsplice` is specifically designed for mapping data into a pipe.

0174 /**
0175  * yes-vmsplice.c
0176  *
0177  * The idea for this modification is to force vmsplicing.
0178  **/
0179 
0180 #define _GNU_SOURCE
0181 #define __need_IOV_MAX
0182 
0183 #include <stdlib.h>
0184 #include <stdio.h>
0185 #include <string.h>
0186 #include <fcntl.h>
0187 #include <limits.h>
0188 
0189 #define LEN 2
0190 #define TOTAL (1 * 1024 * 1024)
0191 #define IOVECS IOV_MAX
0192 
0193 /**
0194  * main()
0195  *
0196  * The main entry function.
0197  *
0198  * @return The exit status.
0199  **/
0200 int main(){
0201   char yes[LEN] = {'y', '\n'};
0202   char* buf = malloc(TOTAL);
0203   int bufused = 0;
0204   int i;
0205   struct iovec iov[IOVECS];
0206   while(bufused < TOTAL){
0207     memcpy(buf + bufused, yes, LEN);
0208     bufused += LEN;
0209   }
0210   for(i = 0; i < IOVECS; i++){
0211     iov[i].iov_base = buf;
0212     iov[i].iov_len = TOTAL;
0213   }
0214   fcntl(1, F_SETPIPE_SZ, TOTAL);
0215   while(vmsplice(1, iov, IOVECS, 0));
0216   return 1;
0217 }

Spoiler: It’s fast. And there is even hints that it could be even faster!

yes-single_char

One final idea was whether putc performs less checks that write(), therefore less branching and therefore faster:

0218 /**
0219  * yes-single_char.c
0220  *
0221  * The idea for this modification is to keep everything in cache.
0222  **/
0223 
0224 #include <stdio.h>
0225 #include <fcntl.h>
0226 
0227 /**
0228  * main()
0229  *
0230  * The main entry function.
0231  *
0232  * @return The exit status.
0233  **/
0234 int main(){
0235   while(1){
0236     putc('y', stdout);
0237     putc('\n', stdout);
0238   }
0239   return 1;
0240 }