nelson@ohlone.UUCP (Bron Nelson) (10/16/87)
There has been considerable discussion (mostly in comp.arch) about
"Big Programs Hurt Performance" and the relative merits of a single
program with lots of options, vs. communicating small programs,
in particular the use of pipes in the Unix world. The canonical
example used is the Unix "ls" command producing single-column and
multi-column output, as opposed to piping single column output
through "pr." The software engineer in me insists that "many small
routines, each doing one job well" is the correct thing to do, but
my practical side recognizes the high cost of Unix pipes. I think
the answer is not to give up on "small is beautiful;" rather it
seems that the answer is to invent a cheaper method of combining
small pieces together. I ask for your comments, proposals, and
examples of existing systems that do a good job.
The rest of this note is a proposal for one method of combining
programs together that seems like it should be possible to do as an
"add on" in an existing system. Comments and criticisms are welcome
(as well as cries of "but OS/xyz already does that!").
I'll use the simple pipeline "ls | pr -4" as my example. Execution
of this requires several forks/execs, read/write system calls, etc.
Instead, let's invent a program something like a compiler/linker that
can take the binaries of ls and pr, and directly compose them into a
single process. I'll call this mythical beast the "Pipeline Composer,"
and the individual pieces "ls" and "pr -4" will be "Pipeline Fragments."
Instead of a pipe, we just allocate a 4K buffer directly in the composed
program's address space, and calls to "write" by ls, and "read" by
pr would fill and empty this local buffer, rather than an external one.
The tricky part that needs to be written is the driver routine for the
composed program, and new interfaces to the read/write routines that
will be used by the composed program.
When a call to read (write) finds the buffer empty (full), you do not
block and trap to the system (as you would with a pipe), instead you
trap to the driver. The driver looks for a pipeline fragment that is
not blocked (or has become unblocked), and (re)starts that fragment.
Now, this is tricky business in that the driver has to keep track of
what amounts to multiple process contexts and multiple call stacks,
but it all seems do-able (not easy). No doubt some restrictions will
have to be placed on pipeline fragments to ensure they can be composed
(various system calls would be off limits), but I could live with that.
Under this scheme, the composed program has significantly less interaction
with the system than the pipeline would. The composed program is of
course somewhat bigger and slower than a custom built utility would be,
but it should be smaller and faster than the pipeline. The individual
pieces can be small and simple; not encumbered by vast numbers of rarely
used options. Only the people wanting the additional functionality need
pay for it, and their cost is modest (I hope).
-----------------------
Bron Nelson {ihnp4, lll-lcc}!ohlone!nelson
Not the opinions of Cray Researchmsf@amelia (Michael S. Fischbein) (10/16/87)
In article <385@ohlone.UUCP> nelson@ohlone.UUCP (Bron Nelson) writes: >There has been considerable discussion (mostly in comp.arch) about >"Big Programs Hurt Performance" and the relative merits of a single >program with lots of options, vs. communicating small programs, >in particular the use of pipes in the Unix world. The canonical >example used is the Unix "ls" command producing single-column and >multi-column output, as opposed to piping single column output >through "pr." > I think the answer is not to give up on "small is beautiful;" > I ask for your comments, proposals, and >examples of existing systems that do a good job. > >I'll use the simple pipeline "ls | pr -4" as my example. OK, so will I. > I'll call this mythical beast the "Pipeline Composer," Goes on to describe a way of implementing the Pipeline Composer. Bron works for Cray and probably has their machines in mind when he conceptualizes a program; his technique is intended to minimize the number of (high overhead) fork/execs, among other things. But on most machines, a fork/exec does not impose the huge overhead it does on a Cray (well, I don't know abou XMPs or 1's, but the overhead on the 2 is awfully big compared to other UNIX boxes). One major complaint about typing ls | pr -4 -t instead of ls -C (the -C is needed in UNICOS) is the extra typing involved and the additional requirements it places on the (perhaps naive) user. One major complaint about the list of options approach is the size and complexity of each utility. A reasonable compromise (and one that I think is taken by many of the utilities) is to use the "system" or "popen" system calls available. Ls doesn't have to develop and debug a column routine; a system call to pr will work. That doesn't involve creating a new Pipeline Composer, either. mike Michael Fischbein msf@prandtl.nas.nasa.gov ...!seismo!decuac!csmunix!icase!msf These are my opinions and not necessarily official views of any organization.
finegan@uccba.UUCP (Mike Finegan) (10/21/87)
In article <385@ohlone.UUCP>, nelson@ohlone.UUCP (Bron Nelson) writes: > The software engineer in me insists that "many small > routines, each doing one job well" is the correct thing to do, but > my practical side recognizes the high cost of Unix pipes. I think > the answer is not to give up on "small is beautiful;" rather it > seems that the answer is to invent a cheaper method of combining > small pieces together. > Under this scheme, the composed program has significantly less interaction > with the system than the pipeline would. The composed program is of > course somewhat bigger and slower than a custom built utility would be, > but it should be smaller and faster than the pipeline. The individual > pieces can be small and simple; not encumbered by vast numbers of rarely > used options. Only the people wanting the additional functionality need > pay for it, and their cost is modest (I hope). The ideal use of pipes is quick and convenient prototyping of new programs, or new system-like routines. Once done correctly, combine it together efficiently, right? Sure, you don't always have source and maybe the ideal operating system should do all this just as fast ... My question(s) is: do system level pipes have the same resource allocation and/or expense as the function pipe() ? How do they compare to output of each stage to a temp file, and then execution of the next stage with the previous temp file ? Even with temp `files' in memory ? Should there be an adjustable buffer size for pipes ? Lastly, should you provide subroutine libraries (object) with all your system routines, and write simple programs to connect only those elements you desired? Or provide entry points to one object file? Lots of disk space, right? Is the idea to create fixes for the present flavors of Unix, or to create improved versions? Always lost in thought (or something similar), Mike Finegan ...!{hal,decuac,mit-eddie,pyramid,...}!uccba[!ucece1]!finegan
dg@wrs.UUCP (David Goodenough) (10/27/87)
I seem to remember hearing somewhere that BSD4.2/3 do pipes with sockets. I am not that much of a UNIX guru, but I have been lead to believe that sockets largely keep their stuff in memory - hence reads and writes are mainly going to be memory - memory copies. IF this is true it strikes me that piping under BSD4.2 is not as expensive as all that; and with the use of vfork the fork/execl cost is not too high. I tend to favour the "lots of small programs piped together" approach (ever since I used unix utilities and the /usr/man/cat* text to create a dictionary out of thin air one afternoon), although I agree that to novices it does create a bit of a learning curve. -- dg@wrs.UUCP - David Goodenough ..... !rtech!--\ >--!wrs!dg ..... !sun!--/ +---+ | +-+-+ +-+-+ | +---+
dick@ccb.ucsf.edu (Dick Karpinski) (11/03/87)
In article <385@ohlone.UUCP> nelson@ohlone.UUCP (Bron Nelson) writes: >... discussion ... >"Big Programs Hurt Performance" and the relative merits of a single >program with lots of options, vs. communicating small programs, >in particular the use of pipes in the Unix world. >... The software engineer in me insists that "many small >routines, each doing one job well" is the correct thing to do, but >my practical side recognizes the high cost of Unix pipes. >... the answer is to invent a cheaper method of combining .... In Principles of Program Design, Michael Jackson shows exactly how to do that by flattening the control structure of each piece. In Modula-2, Niklaus Wirth (with "light weight" processes) shows how to do it in general (except for passing the arguments). James O. Baker, in a private communication to me, explains how to do the argument passing. This reduces the cost of pipes to (roughly) the cost of calling a subroutine. The general notion is called "co-routines" in the computer science literature. My cut at it is to enhance the linker/loader to be able to compose alternative implementations of modules in a "streams"-like fashion. In my version, the interface into any module (such as the collection which supports standard output) is an appropriate place to install a programatic filter. I call it the extender-board-module notion. It inserts a (conceptual) extender board with a prototyping area between an existing client and its support module. A pipe then is simply an output acceptor for the left routine and an input provider to the right routine. There are other places where a well modularized program can profitably be split apart for one purpose or another. The term programatic filter is probably ill chosen since all Unix filters are programs, but is intended to distinguish it from the simple byte stream filter, since most modules are more complex. I, too, welcome comments about where these ideas have already been implemented or demonstrated. Dick Dick Karpinski Manager of Minicomputer Services, UCSF Computer Center UUCP: ...!ucbvax!ucsfcgl!cca.ucsf!dick (415) 476-4529 (11-7) BITNET: dick@ucsfcca or dick@ucsfvm Compuserve: 70215,1277 USPS: U-76 UCSF, San Francisco, CA 94143-0704 Telemail: RKarpinski Domain: dick@cca.ucsf.edu Home (415) 658-6803 Ans 658-3797