Reading long lines either via stdin or file input is painfully slow. This is because the algorithm we use to extract individual characters from a shell string is quadratic in length of the line. This problem wasn't apparent when bootstrapping pnut, but it becomes an obstacle when writing utilities such as cat.
While we can't workaround the limitations of the shell and escape the quadratic complexity of our algorithm, we can extract more characters at once to reduce the constant C in O(C*n^2). We use smaller buffers of length 32, 64 and 128 to reduce the number of operations taking linear time over long strings.
Benchmarks
Results from ./shell-benchmarks/bench-cat.sh which reads a file and output it to stdout, like cat:
Context
Reading long lines either via stdin or file input is painfully slow. This is because the algorithm we use to extract individual characters from a shell string is quadratic in length of the line. This problem wasn't apparent when bootstrapping pnut, but it becomes an obstacle when writing utilities such as
cat.While we can't workaround the limitations of the shell and escape the quadratic complexity of our algorithm, we can extract more characters at once to reduce the constant
CinO(C*n^2). We use smaller buffers of length 32, 64 and 128 to reduce the number of operations taking linear time over long strings.Benchmarks
Results from
./shell-benchmarks/bench-cat.shwhich reads a file and output it to stdout, likecat: