Does cat use lazy evaluation?

Question

When using pipes for example

sudo cat /dev/sda | strings | less

I can move around the lines of strings of my sda device. But are the contents of the sda device loaded fully and outputed to the output stream of cat? Or are the new lines evaluated whenever a program requests output from cat ? ( i.e. i press j on the less pager)

Answer 1

This has more to do with how less works than with how cat or strings work.

The cat command will only push data to its standard output, and it will block whenever the pipe buffer between it and strings is full and nobody is reading. cat does minimal buffering by itself, and the pipe buffer is typically small.

This is also true for strings. It will process the data from cat and will block when less is not reading the data that strings produces.

less will buffer its input to allow you to move back and forth in the data that it displays. When you scroll to the next page, less will read more data from strings into its buffer. While you are not scrolling forward, I believe less will only read a limited amount of data (and hence strings and cat will be blocked while you are not scrolling forward).

If you pipe a large amount of data to less, quite a lot of memory will be used for this buffering if you decide to read it all to the end with less.

There is an option, -B, that limits the amount of memory used for buffering to 64 kilobytes (or however much you specify with the -b option). Limiting the buffer size in this way will prevent you from scrolling back more than what can be stored in the specified buffer space, but will also allow you to read huge amounts of data with less without running out of memory.

See also man less on your system.

Answer 2

Pipes have limited buffer space, and if a pipe reader (such as less in your example) does not read more data from the pipe, the writer will be blocked after filling the buffer. This will affect the strings command, which in turn will block the cat command after its pipe is full.

Naturally, the cat command cannot read the whole sda device contents into main memory, so if blocks that haven't been read by it yet are being changed, cat will see the changed contents.

Answer 3

Both cat and strings, and most similar utilities¹, read a little bit of input at a time, process it, then read more input, and so on. So in your case, cat only reads what less displays, plus a little more that's in transit.

In more detail, the basic operation of cat is:

• Reserve a few kilobytes of memory for use as a buffer.
• While there's more input available:
  • Read up to N bytes of input into the buffer. (This overwrites data that was written out in a previous cycle.)
  • Write the buffer content to the output.

The write operation blocks until there's a place to copy the output. When the output of a pipe, the pipe itself consumes a little memory in the kernel, which is called the pipe buffer. Once that's full, if cat tries to write to the pipe, the write attempt blocks until there's room. There can be room in the pipe buffer when the process on the read end of the pipe reads some data.

The strings program works in the same way as cat, except that it doesn't copy its whole input, only selected parts.

The less program works a bit differently: it keeps everything that it's read in memory. It doesn't recycle its buffer, it keeps growing it as long as more input keeps coming in. The read part is similar, however, in that less only reads data when it needs it: it only reads up to the last line that it displays, plus a little more that it reads in anticipation if available.

So when you run sudo cat /dev/sda | strings | less, what's been read from /dev/sda consists of:

• Data that less has already displayed (or scrolled past).
• Up to a few kB of data that less has read but not yet displayed.
• Up to a few kB in the pipe buffer between strings and less.
• Up to a few kB in the memory of strings.
• Up to a few kB in the pipe buffer between cat and strings.
• Up to a few kB in the memory of cat.

You can watch when each program reads and writes data by tracing its system calls:

sudo strace -e read,write -o cat.strace cat /dev/sda | strace -e read,write -o cat.strace strings | strace -e read,write -o less.strace less

and watch the *.strace files. You can also check how much cat has read by checking the file offset, for example with lsof -p1234 or with head /proc/1234/fdinfo/0 where 1234 is the process ID of cat.

¹ _{Among the basic text processing utility, the main exception is sort, which can't emit any output until it's read the whole input: for all it knows, the first line of output may well be the last line of input that it reaches.}

Answer 4

On some systems (e.g. MS-Dos) the pipe is implemented by copying the output of the first command to a file, then running the 2nd command to read from this file. Unix does not do it that way.

On Unixes it is like a production line. Each stage works simultaneously, reading input and producing output. If process A produces faster than process B consumes, then there is a build up of stock between process A and B. When this is too much (½KiB to 4 KiB), process A is paused. When there is no stock for B to process, then B is paused. Processes are paused and un-paused, to keep stock levels low.

The code in these programs does not care about any of this. It just reads input and writes output. If it tries to read, before data is available, or tries to write before the next process is ready, then the operating system, will pause it, until ready.

When there is no more to read (and nothing more is on its way), the reader gets an end-of-file, and will exit. This in turn triggers an end-of-file in the next process.