How do pipelines limit memory usage?

Question

Brian Kernighan explains in this video the early Bell Labs attraction to small languages/programs being based on memory limitations

A big machine would be 64 k-bytes--K, not M or G--and so that meant any individual program could not be very big, and so there was a natural tendency to write small programs, and then the pipe mechanism, basically input output redirection, made it possible to link one program to another.

But I don't understand how this could limit memory usage considering the fact that the data has to be stored in RAM to transmit between programs.

From Wikipedia:

In most Unix-like systems, all processes of a pipeline are started at the same time [emphasis mine], with their streams appropriately connected, and managed by the scheduler together with all other processes running on the machine. An important aspect of this, setting Unix pipes apart from other pipe implementations, is the concept of buffering: for example a sending program may produce 5000 bytes per second, and a receiving program may only be able to accept 100 bytes per second, but no data is lost. Instead, the output of the sending program is held in the buffer. When the receiving program is ready to read data, then next program in the pipeline reads from the buffer. In Linux, the size of the buffer is 65536 bytes (64KB). An open source third-party filter called bfr is available to provide larger buffers if required.

This confuses me even more, as this completely defeats the purpose of small programs (though they would be modular up to a certain scale).

The only thing I can think of as a solution to my first question (the memory limitations being problematic dependent upon the size data) would be that large data sets simply weren't computed back then and the real problem pipelines were meant to solve was the amount of memory required by the programs themselves. But given the bolded text in the Wikipedia quote, even this confuses me: as one program is not implemented at a time.

All this would make a great deal of sense if temp files were used, but it's my understanding that pipes do not write to disk (unless swap is used).

Example:

sed 'simplesubstitution' file | sort | uniq > file2

It's clear to me that sed is reading in the file and spitting it out on a line by line basis. But sort, as BK states in the linked video, is a full stop, so the all of the data has to be read into memory (or does it?), then it's passed on to uniq, which (to my mind) would be a one-line-at-a-time program. But between the first and second pipe, all the data has to be in memory, no?

Answer 1

The data doesn’t need to be stored in RAM. Pipes block their writers if the readers aren’t there or can’t keep up; under Linux (and most other implementations, I imagine) there’s some buffering but that’s not required. As mentioned by mtraceur and JdeBP (see the latter’s answer), early versions of Unix buffered pipes to disk, and this is how they helped limit memory usage: a processing pipeline could be split up into small programs, each of which would process some data, within the limits of the disk buffers. Small programs take less memory, and the use of pipes meant that processing could be serialised: the first program would run, fill its output buffer, be suspended, then the second program would be scheduled, process the buffer, etc. Modern systems are orders of magnitude larger than the early Unix systems, and can run many pipes in parallel; but for huge amounts of data you’d still see a similar effect (and variants of this kind of technique are used for “big data” processing).

In your example,

sed 'simplesubstitution' file | sort | uniq > file2

sed reads data from file as necessary, then writes it as long as sort is ready to read it; if sort isn’t ready, the write blocks. The data does indeed live in memory eventually, but that’s specific to sort, and sort is prepared to deal with any issues (it will use temporary files it the amount of data to sort is too large).

You can see the blocking behaviour by running

strace seq 1000000 -1 1 | (sleep 120; sort -n)

This produces a fair amount of data and pipes it to a process which isn’t ready to read anything for the first two minutes. You’ll see a number of write operations go through, but very quickly seq will stop and wait for the two minutes to elapse, blocked by the kernel (the write system call waits).

Answer 2

But I don't understand how this could limit memory usage considering the fact that the data has to be stored in RAM to transmit between programs.

This is your fundamental error. Early versions of Unix didn't hold pipe data in RAM. They stored them on disc. Pipes had i-nodes; on a disc device that was denoted the pipe device. The system administrator ran a program named /etc/config to specify (amongst other things) which volume on which disc was the pipe device, which volume was the root device, and which the dump device.

The amount of pending data was constrained by the fact that only the direct blocks of the i-node on disc were used for storage. This mechanism made the code simpler, because much the same algorithm was employed for reading from a pipe as was employed for reading for a regular file, with some tweaks caused by the fact that pipes are non-seekable and the buffer is circular.

This mechanism was replaced by others in the middle to late 1980s. SCO XENIX gained the "High Performance Pipe System", which replaced i-nodes with in-core buffers. 4BSD made unnamed pipes into socketpairs. AT&T reimplemented pipes using the STREAMS mechanism.

And of course the sort program performed a limited internal sort of 32KiB chunks of input (or whatever smaller amount of memory it could allocate if 32KiB was not available), writing the sorted results to intermediate stmX?? files in /usr/tmp/ which it then externally merge sorted to provide the final output.

Further reading

• Steve D. Pate (1996). "Inter-process communication". UNIX Internals: A Practical Approach. Addison-Wesley. ISBN 9780201877212.
• Maurice J. Bach (1987). "System Calls for the File System". The Design of The Unix Operating System. Prentice-Hall. ISBN 0132017571.
• Steven V. Earhart (1986). "config(1M)". Unix Programmer's Manual: 3. System Administration Facilities. Holt, Rinehart, and Winston. ISBN 0030093139. pp. 23–28.
• Abhijit Menon-Sen (2020-03-23). How are Unix pipes implemented?. toroid.org.

Answer 3

You are partially correct, but only by accident.

In your example, all data must indeed have been read "in between" the pipes, but it needs not be resident in memory (including virtual memory). Usual implementations of sort can sort datasets that won't fit in RAM by doing partials sorts to tempfiles, and merging. However, it is a given fact that you cannot possibly output a sorted sequence before having read each and every element. That's pretty obvious. So yes, sort can only start outputting to the second pipe after having read (and done whatever, possibly partially sorting tempfiles) everything from the first. But it doesn't necessarily have to keep it all in RAM.

However, this has nothing to do with how pipes work. Pipes can be named (traditionally they were all named) which means nothing more and nothing less than they have a location in the file system, like files. And that's just what pipes were once upon a time, files (with writes coalesced as much as physical memory availability would allow, as an optimization).

Nowadays, pipes are a small, finite-size kernel buffer to which data is copied, at least that's what conceptually happens. If the kernel can help it, copies are elided by playing VM tricks (for example, piping from a file usually just makes the same page available for the other process to read, so it's finally only a read operation, not two copies, and no additional memory than already used by the buffer cache anyway is needed. In some situations you may get 100% zero-copy, too. Or, something very close.

If pipes are small and finite-size, then how can this work for any unknown (possibly large) amount of data? That's simple: When nothing more fits, the write blocks until there's room again.

The philosophy of many simple programs was most useful once upon a time when memory was very scarce. Because, well, you could do work in small steps, one at a time. Nowadays, the advantages are, apart from some extra flexibility, I daresay, not that great any more.
However, pipes are implemented very efficiently (they had to be!), so there is no disadvantage either, and it's an established thing which is working fine and which people are used to, so there is no need to change the paradigm.