msm@SRC.DEC.COM (Mark S. Manasse) (05/09/89)
Several weeks ago, I got into a minor name-calling skirmish with
some other contributors to xpert about how to really do mouse-tracking
in X. Rather than continue to foam at the mouth, as is my usual
habit, I decided to treat this as an opportunity to indulge briefly
in the scientific method. And guess what -- we were all wrong.
I apologize for the delay in promulgating these findings, but, except
in electrochemistry, the findings of science come slower than flaming.
And, in the interests of science, I've included my program below,
so you can all try to reproduce my results. Deuterium not included.
Allow me to recap, for those of you who may be wondering what I'm
getting on about. One of the puzzling things about network window
systems has been how to get good performance for mouse-tracking without
consuming too much in the way of system resources.
There are three plausible ways to track the cursor in X11, say for
the purposes of rubber-banding a rectangle. The first is to poll
the cursor position rapidly, painting whenever you detect changes
in the position of the cursor. This gives you the lowest latency
of all possibilities in return for the maximum consumption of server,
client, and network resources.
You'll recall that a month or two ago I asked you to run some
experiments for me on cursor-tracking in X. Well, you did, and thank
you. I have some results now, and I'd like to let you know what they
are, although I'm not sure how much they mean. We'll refer to this
style of interaction as POLLING.
A second possibility is to ask the server to send you motion events
whenever the cursor moves. This decreases the amount of load, if
event delivery is faster than the sampling rate for the mouse, and
increases it otherwise. By doing event compression on the client
side, and adding a sync call after painting, we can arrange things
so that even in case of heavy load, the server and client never get
farther out of sync than is necessary. We'll refer to this style
as MOTION.
The final possibility is to use PointerMotionHint. In this mode,
the X server delivers a position only after a button or key event
or window crossing. Having delivered the position, it doesn't send
any more until you ask it to send you one the next time the mouse
moves. This uses very little bandwidth or resources on the server
and client, but it does require an extra round-trip for each reported
position when things are running fast, when compared to MOTION. We'll
call this HINTING.
Now that you're all up to speed on what the possibilities are, let
me remind you of the debate. It was offered to the net as fact that
only POLLING could provide anything resembling good performance.
I countered that in most situations, a synchronous, compressing version
of MOTION could work well, but that HINTING was the one true path to
enlightenment. I asserted that HINTING and POLLING would be
indistinguishable, except that HINTING would use fewer resources.
So what did I do? First, I implemented each of these strategies
as best I could. Then, I wrapped a program around this that creates
two windows, randomly choosing the interaction style for each window.
In each case, the user interface was fixed: you press the left mouse
button in a window, and hold it down. As you move the mouse, the
outline of a rectangle is displayed in the window. If you press
another button while the left button is down, or release the left
button, the rectangle vanishes. When you think that you've detected
a difference in the performance of the two windows, you middle-click
in the window you "like better", or at random if you're sure they're
different, but not sure which was better. If you're convinced that
they are, in fact, identical (which is one of the possibilities),
you right-click in either window.
To refute my hypothesis that HINTING and POLLING were indistinguishable, I
didn't need to put in the stuff about expressing a preference. But I
thought it might be interesting, and it didn't seem to compromise the
experiment much. I did put in this statement when I asked people to run
my program:
Don't feel that you have to choose between them if you feel they're
the same; part of the experiment includes sometimes making them
actually *be* the same, so that I can tell if the feeling that
they're different is real or not. In fact, I'm more interested
in whether you press the middle button or the right button than
I am in which window you liked better, unless it turns out that
there are very clear preferences on that score. What I'll be
doing is looking to see if the frequency with which people could
tell the difference between two styles of dragging is statistically
distinguishable from the frequency with which they perceived
differences between identical styles.
In order to enhance any perception of differences, the program prints
out what interaction style each window has as soon as the user presses
the middle or right button. I did ask subjects to hide any
load-average monitoring tools that they might have on their screen,
so that they would not observe that side-effect of polling. I felt
that telling the user what style of interaction each window had would
allow users with "golden eyes" to hone their skills at finding ways
to establish the kind of window they were dealing with, which might
help them in refuting my hypothesis of indistinguishability. It does
mean that the preference information is less valuable than it might
be, assuming that there are techniques for distinguishing, since users
who are good at distinguishing, and have a preference for some style
could feign a preference for that style. I considered this an
acceptable compromise in the design of the experiment, after removing
myself from the subject pool.
The implementations of the different styles were relative naive.
In particular, the polling loop always polls; a more sophisticated
implementation might choose to do something else after a few
round-trips with no detected motion. The motion loop synchronizes
after every painting request; a more sophisticated implementation
might try to synchronize only after every fifth or tenth request.
I don't think either of these affected the outcome much, but you should
feel free to rerun the experiment however you like.
I released the program, and captured results for six weeks. There
are three obvious conclusions from the data:
1) In our environment (fast workstations), this experiment was not
sensitive enough to exhibit a difference between the tracking
styles, when the program and the server ran on the same
workstation. That is, the hypothesis of indistinguishibility may
hold in the local-execution case.
2) When running over a local-area network, using a time-shared machine
to run the client, significance was achieved in determining whether
the two windows were identical or not.
3) No distinction was observed in preference for one style over another.
Again, due to the design of the experiment, this conclusion is at
best weakly supported by the evidence.
The data:
Local Remote
Perceived as: same different same different
Both POLLING or HINTING 8 4 17 14
One POLLING, one HINTING 7 3 6 15
Both POLLING or MOTION 9 4 11 6
One POLLING, one MOTION 2 2 15 15
Both HINTING or MOTION 7 4 10 8
One HINTING, one MOTION 9 4 10 23
The local case is client and server on the same workstation, remote
is client on a time-shared machine on the same local ethernet. A
limited number of experiments were run across gateways, and over
56 kilobaud serial lines, with similar results. In the remote case,
of the 30 trials where POLLING went head-to-head with another style,
and was detected as different, it was preferred 15 times. Of the
38 remote trials each where HINTING and MOTION went head-to-head
with another style, each was preferred 19 times. In the local case,
POLLING was favored in all five of the head-to-head trials in which
a distinction was found; HINTING was favored in 4 of 7 head-to-head
trials; MOTION was favored in 1 of 6 head-to-head trials. The
cumulative statistics in the local case show that in exactly 1/3
of all cases, whether a distinction exists or not, a distinction
was perceived. The remote case shows a strong bias toward detecting
differences; of the 84 trials in which the windows differed, the
difference was noticed 53 times (63%). Of the 32 times that the
windows were the same, a difference was perceived 14 times (44%).
Mark
#! /bin/sh
# This is a shell archive. If you save it in file 'foo', unpack it
# by typing 'sh foo'
echo Extracting Makefile
cat >Makefile <<'!End!of!file!'
#CFLAGS = -DMAILTO=user@host.domain
abx: abx.o
$(CC) -o abx abx.o -lX11
!End!of!file!
echo Extracting abx.c
cat >abx.c <<'!End!of!file!'
#include <sys/types.h>
#include <sys/timeb.h>
#include <stdio.h>
#include <X11/Xlib.h>
#include <X11/X.h>
#include <signal.h>
#include <pwd.h>
extern long random();
extern char *getlogin(), *getenv();
typedef struct {
int h_x;
int h_y;
int h_height;
int h_width;
int highlightOn;
} HighlightInfoRec, *HighlightInfo;
HighlightInfoRec nhi, ohi;
Display *dpy;
GC xorGC;
Window w0, w1;
int c0, c1;
char *testname[] ={"Poll", "Hint", "Motion"};
char *preference[] = {"chose window 0", "chose window 1", "didn't choose"};
int hist[3][3][3];
cleanup(sig, code, scp) int sig, code; struct sigcontext *scp; {
int i,j,k;
FILE *f;
char *unam, hostbuf[1000];
struct passwd *pwent;
#ifdef MAILTO
f = popen("mail MAILTO", "w");
unam = getlogin();
if (!unam || !*unam)
unam = getpwuid(getuid())->pw_name;
if (!unam)
unam = "Don't know who";
gethostname(hostbuf, 999);
hostbuf[999] = '\0';
fprintf(f, "%s on %s, talking to display %s\n", unam, hostbuf,
getenv("DISPLAY"));
for (i=0; i<3; i++)
for (j=0; j<3; j++)
for (k=0; k<3; k++)
fprintf(f, "%d%c", hist[i][j][k], k<2?' ':'\n');
pclose(f);
#endif
exit(0);
}
main(argc, argv) char *argv[]; {
int i,j,k,c2;
FILE *f;
XGCValues gcv;
time_t now = time((long *)0);
int white, black;
if(!(dpy = XOpenDisplay(NULL))) {
fprintf(stderr, "Can't open display!\n");
exit(1);
}
signal(SIGINT, cleanup);
for (i=0; i<3; i++)
for (j=0; j<3; j++)
for (k=0; k<3; k++)
hist[i][j][k] = 0;
white = WhitePixel(dpy, DefaultScreen(dpy));
black = BlackPixel(dpy, DefaultScreen(dpy));
gcv.function = GXinvert;
gcv.plane_mask = black ^ white;
xorGC = XCreateGC(dpy, DefaultRootWindow(dpy), GCFunction | GCPlaneMask,
&gcv);
srandom(getpid() + now);
printf("Left drag in windows to test dragging.\n");
printf("Middle click in a window to express a preference for that window,\n"
);
printf("if you can tell them apart; if you can tell them apart, but had no\n"
);
printf("preference, middle click at random.\n");
printf("Right click in either window if they are indistinguishable.\n");
printf("Type ^C to exit.\n");
w0 = XCreateSimpleWindow(dpy, DefaultRootWindow(dpy), 0, 0, 200, 200, 0,
black, white);
w1 = XCreateSimpleWindow(dpy, DefaultRootWindow(dpy), 200, 0, 200, 200, 0,
black, white);
XStoreName(dpy, w0, "Test of drag styles, window 0");
XStoreName(dpy, w1, "Test of drag styles, window 1");
XSetIconName(dpy, w0, "Drag test 0");
XSetIconName(dpy, w1, "Drag test 1");
XMapWindow(dpy, w0);
XMapWindow(dpy, w1);
for (;;) {
c0 = random() % 3;
c1 = random() % 3;
c2 = runtest();
printf("Window 0 was %s. Window 1 was %s. You %s.\n",
testname[c0], testname[c1], preference[c2]);
hist[c0][c1][c2]++;
fflush(stdout);
}
}
runtest() {
XEvent ev;
Window jroot, jchild;
int rx, ry, x, y, state, chorded;
nhi.highlightOn = False;
ohi = nhi;
switch(c0) {
case 0: XSelectInput(dpy, w0, ButtonPressMask | ButtonReleaseMask);
break;
case 1: XSelectInput(dpy, w0, ButtonPressMask | ButtonReleaseMask |
Button1MotionMask | PointerMotionHintMask);
break;
case 2: XSelectInput(dpy, w0, ButtonPressMask | ButtonReleaseMask |
Button1MotionMask);
}
switch(c1) {
case 0: XSelectInput(dpy, w1, ButtonPressMask | ButtonReleaseMask);
break;
case 1: XSelectInput(dpy, w1, ButtonPressMask | ButtonReleaseMask |
Button1MotionMask | PointerMotionHintMask);
break;
case 2: XSelectInput(dpy, w1, ButtonPressMask | ButtonReleaseMask |
Button1MotionMask);
}
for(;;) {
XNextEvent(dpy, &ev);
switch (ev.xany.type) {
case ButtonPress:
if (chorded = !!(ev.xbutton.state & ~LockMask)) {
nhi.highlightOn = False;
UndrawAndDrawOutline(ev.xbutton.window, &ohi, &nhi);
ohi = nhi;
break;
}
if (ev.xbutton.button != Button1) break;
nhi.highlightOn = True;
nhi.h_x = ev.xbutton.x;
nhi.h_y = ev.xbutton.y;
nhi.h_width = nhi.h_height = 0;
UndrawAndDrawOutline(ev.xbutton.window, &ohi, &nhi);
ohi = nhi;
if (ev.xbutton.window == w0 && c0 == 0 ||
ev.xbutton.window == w1 && c1 == 0)
while (! XEventsQueued(dpy, QueuedAfterReading)) {
XQueryPointer(dpy, ev.xbutton.window, &jroot, &jchild,
&rx, &ry, &x, &y, &state);
RedrawOutline(ev.xbutton.window, x, y);
}
break;
case ButtonRelease:
if (chorded) break;
switch(ev.xbutton.button) {
case Button1:
nhi.highlightOn = False;
UndrawAndDrawOutline(ev.xbutton.window, &ohi, &nhi);
ohi = nhi;
break;
case Button2:
return ev.xbutton.window == w1;
case Button3:
return 2;
}
break;
case MotionNotify:
if (ev.xmotion.window == w0 && c0 == 1 ||
ev.xmotion.window == w1 && c1 == 1) {
RedrawOutline(ev.xmotion.window, ev.xmotion.x, ev.xmotion.y);
XQueryPointer(dpy, ev.xmotion.window, &jroot, &jchild,
&rx, &ry, &x, &y, &state);
RedrawOutline(ev.xmotion.window, x, y);
} else {
XEvent peek;
while (XEventsQueued(dpy, QueuedAfterReading) &&
(XPeekEvent(dpy, &peek),
peek.xany.type == MotionNotify &&
peek.xmotion.window == ev.xmotion.window))
XNextEvent(dpy, &ev);
RedrawOutline(ev.xmotion.window, ev.xmotion.x, ev.xmotion.y);
XSync(dpy, False);
}
break;
}
}
}
RedrawOutline(w, x, y) Window w; int x,y; {
nhi.h_width = x - nhi.h_x;
nhi.h_height = y - nhi.h_y;
UndrawAndDrawOutline(w, &ohi, &nhi);
ohi = nhi;
}
static XSegment *
ComputeOutline(h, q)
HighlightInfo h; register XSegment *q;
{
if (!(h->highlightOn)) return q;
if (h->h_width < 0) { h->h_x += h->h_width; h->h_width = -h->h_width; }
if (h->h_height < 0) { h->h_y += h->h_height; h->h_height = -h->h_height; }
q->x1 = h->h_x;
q->y1 = h->h_y;
q->x2 = h->h_x + h->h_width - 1;
q++->y2 = h->h_y;
q->x1 = h->h_x + h->h_width - 1;
q->y1 = h->h_y + 1;
q->x2 = h->h_x + h->h_width - 1;
q++->y2 = h->h_y + h->h_height - 2;
q->x1 = h->h_x + h->h_width - 1;
q->y1 = h->h_y + h->h_height - 1;
q->x2 = h->h_x;
q++->y2 = h->h_y + h->h_height - 1;
q->x1 = h->h_x;
q->y1 = h->h_y + h->h_height - 2;
q->x2 = h->h_x;
q++->y2 = h->h_y + 1;
return q;
}
UndrawAndDrawOutline(w, ohi, nhi) Window w; HighlightInfo ohi, nhi;
{
XSegment outline[8], *r;
if (ohi->highlightOn == nhi->highlightOn && ohi->h_x == nhi->h_x
&& ohi->h_y == nhi->h_y && ohi->h_width == nhi->h_width
&& ohi->h_height == nhi->h_height)
return;
r = ComputeOutline(nhi, ComputeOutline(ohi, outline));
if (r != outline) XDrawSegments(dpy, w, xorGC, outline, r-outline);
}
!End!of!file!