Robert@soma.UUCP (12/16/86)
[This was forwarded from xpert@athena.mit.edu. Masscomp intends on supporting
X, but Sun has NeWS. Some think Sun will make another "standard" like NFS
with NeWS. This is a discussion of some of the differences. It might be a bit
biased... -- sob, moderator]
NeWS Brakes
Robert W. Scheifler
MIT Laboratory for Computer Science
October 30, 1986
Since Sun's announcement of NeWS, many people have asked me "Who will win?"
(X versus NeWS). I cannot, of course, pretend to know the answer to this
question. However, from the relative safety of my ivory tower at MIT, I
can pretend that the more interesting question is "Who is right?"[*]. The
following note attempts to answer this question; these are my personal
opinions, and should not be construed as the opinions of my employers or of
anyone else. My understanding of NeWS comes from [1] and [2]. For the
most part, I will confine myself to relatively high-level issues, since [1]
contains very few details. I assume the reader has read [1], and is
reasonably familiar with X. In the following, I refer to X Version 10
simply as "V10", and X Version 11 as "V11".
Downloading: Panacea or False Hope?
An interesting feature of NeWS is the ability to download code
(specifically PostScript) into the server. Sun claims this is a solution
to latency problems otherwise incurred with IPC round-trips, for example,
when animating objects on the screen in response to mouse motion. They are
fairly careful in not giving menu highlighting and window outline rubber
banding as examples of this. On a uni- or multi-processor with IPC based
on shared memory, latency (and bandwidth) is unlikely to be an issue. V10
has shown quite clearly that even the relatively long network latencies
under current Unix implementations is not a problem for simple forms of
tracking[**], and it is clear (from systems like the Stanford V kernel and
the Xerox Cedar system) that a 5x to 10x reduction in latency is to be had
even on existing hardware. Solving the problem at the network level
reduces complexity not only in window systems, but in many other
distributed systems as well. Also, we have seen many V10 applications that
are actually faster when client and server are placed on separate machines,
simply because more CPU cycles are available.
If downloading is not particularly important for simple tracking, perhaps
it is useful for more complex tracking. So, let's consider an example of
complex tracking, based on (but not identical to) the Symbolics Genera
window system [3]. This is but one example, there are plenty of others
(even in current V10 applications).
We have a large collection of objects displayed in the window. Each object
is responsible for displaying its contents, but the application at a higher
level keeps track of the visual extents of the objects. Each object also
defines what operations can be performed on it, and what accelerators
(key/button combinations) can be used to execute some of those operations.
As the mouse is moved over an object, the object is asked to highlight
itself, and to produce a string documenting the possible accelerators
(based on the current key states); the string is displayed at the bottom of
the screen. In addition, objects may be used as arguments to commands
typed from the keyboard. For example, when typing the command "Show
Directory", only objects (such as file pathnames) capable of supplying a
directory name are active (i.e., highlight when the mouse is over them),
and all other objects become inactive. This is accomplished by querying
the objects dynamically as the mouse moves, to see if they are both willing
and capable of producing a given type of value.
It should be clear from this example that there is no reasonable functional
separation that would allow a front end to be downloaded into a server in
such a way as to avoid round-trip communication. The tracking is
intimately bound to the semantics of objects. In general, a front end
performing complex tracking will require access to much the same data
structures and knowledge representations used by the back end for the
"real" work. Separating out the information will be painful at best, and
even if the relevant information could be isolated or even duplicated in
the server, the communication costs have merely been moved (the information
has to be kept up to date somehow), not eliminated.
Even if one could download a front end into the server, would one really
want to? PostScript may be Turing complete, but if my front end is at all
large or complex, I certainly do not want to write it in PostScript. I
presumably already have a wonderful language and environment for writing my
applications (e.g., Flavors, CommonLoops, C++); should I really believe
industry/academia is going to start providing compilers to PostScript?
Noticeably absent from [1] is any discussion of debugging; the print/dump
operators that are mentioned indicate a giant step backward in debugging.
In addition, one must be wary of assuming that the processing power of the
server is at least as great as the power of the client. Although this is a
reasonable assumption for graphics output specifically, exactly the
opposite will almost always be true for general computation, given both
typical hardware (do you really think my "terminal" is going to have a
faster CPU and more physical memory than whatever machine I use to run my
"real" programs?) and compiled (in the client) versus interpreted (in the
server) execution. (It would be interesting to know how much of the
interpreter and graphics substrate in NeWS is written in PostScript.)
Sharing and malleability of "common" user interface components is cited by
Sun as being significant considerations; menus are given as a specific
example. To allow sharing and wholesale replacement of components,
interfaces must be defined precisely and agreed upon universally. At this
level of programming, agreement in the real world seems highly unlikely;
one needs only to look at the menu interfaces of existing window systems to
realize that, although they have much in common, they differ quite a bit in
detail. Furthermore, commercial interests tend to prize "tamper-proof"
packaging highly, to minimize service and maintenance headaches.
The Imaging Model
Sun apparently believes they can provide X emulation on top of NeWS. This
is simply not possible for color displays, given the PostScript imaging
model. What is true is that PostScript emulation on top of V11 is
straightforward, either done entirely on the client side, or in combination
with an upward compatible extension to the V11 core protocol.
Although NeWS allows the setting of a "current RasterOp function"
explicitly for "backward compatibility", the ability to restrict the
operation to a subset of the hardware planes appears to be absent.
Further, NeWS has no concept of colormaps, and hence no concept of
arranging for pixel values to have particular relationships, and no concept
of diddling the colormap to change colors dynamically without repainting
the image. These mechanisms are of vital importance not only to
sophisticated imaging and CAD applications, but to "everyday" applications
(like xterm) as well.
For example, the ability (by clever arrangement of pixel values and by
restricting graphics to particular planes) to highlight and un-highlight
regions without redrawing, or to draw and erase foreground text without
affecting background images, is crucial for high performance. This trick
is used in many V10 applications, and the V11 colormap allocation
primitives allow such games to be played in a reasonably device-independent
fashion. NeWS has an "overlay" mechanism which attempts to provide
equivalent functionality. However, the overlay semantics appear to be so
ill-defined (e.g., no guarantees about color or performance) as to be
nearly useless. One of the important lessons we learned from V10 was that
attempting to define something so vaguely that it can be always be
implemented in some fashion simply results in a mechanism so unpredictable
that no one dares use it. V11 has explicitly steered clear of attempting
to "standardize" overlay semantics, yet provides a window class mechanism
by which overlays can be added in an upward compatible fashion.
Although Sun claims that NeWS, by virtue of its abstraction, will provide a
better match than X with future graphics hardware, the opposite actually
seems to be true. V11 has been designed explicitly with future hardware in
mind. Next generation hardware will allow (within limits) a separate
colormap per window, with colormaps of various types (e.g., both
pseudo-color and direct-color). V11 provides direct support for this
hardware. Since a PostScript client provides no "up front" indications of
color usage, heuristics on the part of a NeWS server are unlikely to
perform as well as specific engineering in V11. Future hardware (such as
the Cambridge Rainbow [4]), supporting variable depth windows with the
hierarchy implemented in silicon, has also been accounted for in the V11
design; both windows and off-screen images of varying depths can be
supported. Again, lacking up front resource requirements from clients, a
NeWS server cannot hope to match the minimum memory allocation that is
possible in V11.
Sun apparently believes that, by hiding the true size of the colormap, they
can do a better job of keeping all windows at "true" color than a V11
server can. Once clients have already displayed in "too many" colors,
which server can do a better job of picking the "best" colors to display?
The answer is that a V11 server has the same information as a NeWS server,
and so can make the same decision. However, a V11 server also has
additional information, in the form of what logical colormaps are "most
desirable" to display, so perhaps a V11 server can actually do better than
a NeWS server. One might think that a NeWS server could do better by
limiting colors as they are used by clients, by using various color
approximations. However, to do this effectively requires prior knowledge
of how many colors clients will use, and which of those colors are most
important. PostScript provides no such declarative mechanism. (Achieving
the effect by forcing clients to redraw their windows would of course be
quite unacceptable.) The same problems exist for playing anti-aliasing
tricks; there is no mechanism in PostScript to indicate where anti-aliasing
will be most helpful. The cause of these problems, of course, is that
PostScript was designed for printers, and printers simply do not have the
same kinds of palette restrictions that displays have.
PostScript (at least according to [2]), does not allow full color images to
be transferred; one must choose between 1, 2, 4, and 8 bit images with a
mapping from N-bit value to color. V11, on the other hand, allows full
color images to be transferred. PostScript also mandates a single image
format, in terms of bit order and byte padding. One of the lessons we
learned from V10 was that this was a bad idea if you wanted good
performance across a variety of hardware. Requiring clients to handle
several different formats is a bit awkward, but substantial performance
improvements are possible as a result.
The coordinate transformation mechanism of PostScript is certainly
powerful, but power can be a double-edged sword. If the display hardware
happens to provide a matching mechanism, then pushing the transformations
into the server can increase performance. However, if the display hardware
cannot do transformations, it is quite likely that the client machine can
perform the transformations at least as fast as the server; delaying the
transformations may actually slow things down (particularly when floating
point is involved). In addition, PostScript transformations are purely
2-D, making the addition of 3-D transformations a bit problematical.
"Convenience" transformations are just as easily performed on the client
side as in the server. Convenience transformations also have their
problems. Although being "off by half of a dot" is not really a problem at
current and future printing densities, screen resolutions now and for quite
a while are not so accommodating (it seems quite unlikely that even
monochrome [much less color] displays with Megascan-like densities will be
on everyone's desktop anytime soon). Precision is vital; "off by one" is
not good enough. Of course, not all transformations are a simple matter of
convenience; true scaling and rotation of a source image are possible in
PostScript. If true scaling and rotation turn out to be important
considerations, the V11 protocol can easily be extended in an upward
compatible fashion to support it. The fact that V11 uses a state-based
protocol (as does PostScript) makes this straightforward.
System Design
The use of lightweight processes and non-preemptive scheduling in NeWS are
not new. Indeed, that is a fundamental problem: the technology is already
dated. Decent operating systems supporting multi-processors, lightweight
processes, shared memory, preemptive scheduling, and efficient
synchronization exist today, and even Unix implementations with such
support are fast becoming a reality. Equally important, next generation
display hardware is quite likely to contain the necessary support for true
multi-threaded use. A true multi-threaded V11 server will be able to take
advantage of all this technology (for example, a true multi-threaded V10
server has already been implemented), but getting a NeWS server to do the
same will be extremely difficult. The decision to use non-preemptive
scheduling is the key here. Certainly this makes life much easier in the
short term, but once you commit to it there is no changing your mind. I
spent the last few years designing and implementing a multi-process
environment for a fairly sophisticated distributed systems language [5]. I
used lightweight processes with semi-preemptive scheduling (preemption
could only occur at certain procedure calls). This certainly simplified
synchronization issues enormously, but the code as it now stands would
require substantial modifications to run in a preemptive or multi-processor
environment.
Event handling in NeWS is another area of concern. Given the "wonderful"
capabilities of PostScript, why are clients restricted to using primitive
component matching to express interest in events? Allowing clients to use
true functions to express interest would provide significantly more
flexibility. Is there some concern here that executing functions will not
be fast enough? One hopes not, or faith in the whole PostScript concept
begins to crumble. Another problem with the NeWS event mechanism is too
much synchronization. In particular, there is no notion of which events
require synchronization. Instead, NeWS guarantees that when an event is
dispatched, the destined processes are guaranteed to run before another
event will be dispatched. This will only serve to slow the server down in
a true multi-process environment. And even in the intended NeWS
environment, what happens if the destined process is busy performing some
other prolonged task (like reading from the network)? In contrast, V11
only requires synchronization at explicit event grabs, which are expected
to be infrequent.
Stability
Both NeWS and V11 claim commitment to stability. The V11 design is based
on concrete experience and feedback from V10. The V11 design has been
reviewed by people in many universities and companies, with very positive
results. This gives me confidence that V11 stability can be a reality. As
discussed above, a number of fundamental design decisions in NeWS leave me
uneasy; if Sun chooses to change them, stability will be lost, but if Sun
chooses not to change them, significant performance will be lost.
[*] This is a perfect example of "language design by implementation". The
two questions are obviously semantically equivalent, but the implementors
have inexplicably chosen to make them different. :-)
[**] People who have only used X on a Sun tend not to believe this. The
implementation on the Sun uses an inferior mechanism for getting input
events from the kernel to the server (select/read on a file descriptor
instead of shared memory), and this significantly affects performance.
[1] NeWS Preliminary Technical Overview. Sun Microsystems, Inc. October 1986.
[2] Adobe Systems, Inc. PostScript Language Reference Manual. Addison-Wesley,
1985.
[3] Programming the User Interface. Symbolics, Inc. 1986.
[4] Wilkes, A. J. et al. The Rainbow Workstation. The Computer Journal 27,2.
May 1984.
[5] Liskov, B., and Scheifler, R.
Guardians and Actions: Linguistic Support for Robust, Distributed Programs.
ACM Transactions on Programming Languages and Systems 5,3. July 1983.