Requests for nominations of Great C Code (Was Re: Texts ...

[Chris Torek]

In article <1500 at mcgill-vision.UUCP> mouse at mcgill-vision.UUCP (der Mouse)
writes:
[re jag's display.c skull-and-crossbones:]
>>All ye who enter here:  Most of the code in this module is twisted
>>beyond belief!  Tread carefully.  If you think you understand it,
>>			      You Don't,
>>			    So Look Again.

>He wasn't kidding, either.  I once tried to rewrite it preparatory to,
>I think, making the cost formulas conform more closely to reality for
>the Sun console (where, for example, insert and delete operations have
>high overhead and slightly *negative* per-count cost).  All I succeeded
>in doing was slowing it down by about a factor of four, and introducing
>some bugs to boot.

Part of the problem was that the description of the algorithm was
contained in a CACM article; display.c had only a few hints in comments
as to what was going on.  But it was not actually all that hard to
work out.  My version of his display.c does have separate overhead
and per-count costs; it turns out, though, that on the Sun console,
if you have direct access to the frame buffer, it is faster just to
rewrite.

If anyone is curious: what is going on with the `M' matrix is
surprisingly simple.  You fill the thing with a bunch of arrows
pointing either to the left, up, or backwards diagonally.  Each
arrow thus points at a neighbour arrow, except for those along the
left edge and top row.  To fill the matrix, set up the arrows along
the left edge to point up; set those along the top to point left.
Set the one at (0,0) to `done':

	* < < < <
	^ . . . .
	^ . . . .
	^ . . . .
	^ . . . .

(This represents a four-line screen.)  An up arrow represents a line
deletion; a left arrow is an insert; and a back arrow is a rewrite in
place.  The row index (called `i') represents the contents of the
current screen at line `i', and the column index (called `j')
represents the contents of the desired screen at line `j'.  Then fill
in each `.' with the arrow that gives the least cost for transforming
the screen according to an insert, delete, or rewrite given i and j.
If the filled-in matrix looks like this:

	*  <  <  <  <

	^  \  <  \  \

	^  ^  \  ^  \

	^  \  ^  ^  \

	^  ^  ^  \  \

then we would (start at the bottom right) move back, up, up, back,
left, left, and done, rewriting line 4 in place, deleting line 3,
deleting line 2, writing line 1 in place, inserting (moving 1 down to
2), writing 1 in place again, inserting again (moving 1 and 2 to 2 and
3), and finally writing line 1 in place again.  All those other unused
arrows are there only because we did not know, before we finished,
whether they would be used.  The inserts and deletes we gather
together along the way, since some terminals can do multi-line
operations, so we really get `rewrite 4, goto 2, 2*delete, goto 1,
rewrite, goto 2, 2*insert, rewrite 2, goto 3, rewrite 3, done'.
(This is actually a stupid sequence and would never occur in
practise.)

What makes it hard is getting the right arrows into the cells.  Each
cell also has a cost (in terms of `characters sent to the terminal')
attached to it.  The cost for a delete is simply the cost of that
delete: if an ESC-M deletes a line, the cost for delete is 2.  (This
ignores padding, which complicates matters; more on that later.)  The
cost for an insert is the cost of that insert (2 for, e.g., ESC-L) plus
the cost for drawing line j (the one you want to show on the screen).
The cost for moving straight back (diagonally upward) is just the cost
for rewriting line i into line j.  If the text on line i matches that
on line j, this is free; otherwise it should be the number of
characters required, but as an optimisation, the code just uses the
number of characters on line j (otherwise it might have to compare n^2
lines; as it is, the comparison is `if the hashes match, the lines are
the same and the rewrite is free').

As an optimisation, instead of having each `up' or `left' arrow point
to its neighbour cell, if that cell is also an up, or is also a left,
we have it point to where its neighbour points (leapfrogging over all
the same sort of arrows, so to speak).  This gives a nice way to see
how many inserts or deletes are to be used.

On some terminals (ANS X3.64), insert or delete operations have a fixed
overhead no matter how many lines are inserted or deleted, but have a
variable additional factor.  For instance, ESC [ 4 L might insert four
lines, with essentially the same cost as ESC [ 1 L (inserts 1 line),
except for padding.  The padding cost depends on how far above the
bottom of the screen the cursor is at the time of the operation: to
insert four lines, the terminal must move (rows-4) lines downward, and
then must clear the four new lines.  On a 30-line screen, this affects
at least eight lines (23,24,25,26 move down to 27,28,29,30; then clear
23,24,25,26) and at most 30 (1,2,3,...,26 move to 5,6,7,...,30; then
clear 1,2,3,4).  The same rule applies to padding for deletion.  On
some stupidly-coded terminals (H19 in ANSI mode), padding is remarkably
significant: the H19 inserts 6 lines by inserting 1 line 6 times!
This can take quite a while and must be accounted for.  It is simplest
to define a fixed cost, a variable (per n lines) cost, with each
split into `overhead' and `padding due to being above the bottom of
the screen':

	let
		c_f = <fixed cost>
		c_n = <per-operation cost>
		n = <number of lines to insert or delete>
		k = <rows on screen> + 1 - <position of operation>

	then
		cost = n * (c_n.overhead + k * c_n.padding) +
			    c_f.overhead + k * c_f.padding

der Mouse's Sun costs are then

		c_f = (overhead = <large>, padding = ?)
		c_n = (overhead = <slightly negative>, padding = 0)

while those on a fast terminal that uses ESC-L and ESC-M for each
insert and delete are

		c_f = (overhead = 0, padding = 0)
		c_n = (overhead = 2, padding = 0)

Within Emacs, the padding cost represents actual NULs sent to the terminal
to keep it from sending ^S/^Q flow control; but even if flow control
is available, the pad costs should still be counted, as they represent
time taken by the terminal to do the operation.

So: a comment in my display.c:

   The algorithm used is a dynamic programming one, where
      M[i,j] = min (M[i-1,j]+dcost,		# UP,   implies delete
		    M[i,j-1]+icost+redraw cost,	# LEFT, implies ins+redraw
		    M[i-1,j-1]+rewrite cost)	# BACK, implies rewrite
  
   (It is not necessary to count a redraw cost for UPs as they force an
    equivalent number of LEFTs at some point.)
  
   The rewrite cost for a line is its redraw cost, unless line i matches
   line j, where it is free.  The UP and LEFT cases must also add the
   cost for doing an insert or delete.  This is actually rather tricky:
   the cost for an ID varies with the position above the bottom of the
   screen, and sometimes with the number of line IDs.  As it turns out
   we can just look at the UP'th or LEFT'th cell to see whether this is
   the first of a sequence.
  
   After we have finished putting UPs, LEFTs, and BACKs in the matrix,
   we start at the lower right corner and work backward, following the
   arrows up, left, or back, eventually reaching the top left.  Going
   up implies a deletion; going left implies insertion and rewrite; and
   every back implies a rewrite of old line i to new line j.  There is
   an exception:  UPs along the right edge of the matrix, and LEFTs
   along the bottom, are merely establishing a starting position and
   do not cause I/D operations (doing I/D there would be pointless
   anyway).  (LEFTs do still cause redraws.)
  
   Note that the elements along the left edge (j=0) are constant, and
   that the elements along the top (i=0) are constants plus the redraw
   sum for all lines <= j.

As it happens, we can precompute a great deal of these factors.  The
code to fill in the M cost matrix is order n^2, so getting the constant
factor down helps (n is typically between 24 and 60).  A new algorithm
would help more, but this one is provably optimal if the cost factors
are correct (which, alas, they are not).
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris