Path: utzoo!attcan!uunet!lll-winken!ames!haven!cvl!mimsy!chris From: chris@mimsy.UUCP (Chris Torek) Newsgroups: comp.lang.c Subject: Re: Requests for nominations of Great C Code (Was Re: Texts ... Message-ID: <16955@mimsy.UUCP> Date: 16 Apr 89 05:11:19 GMT References: <354@cbnewsc.ATT.COM> <433@algor2.UUCP> <942@atanasoff.cs.iastate.edu> <1500@mcgill-vision.UUCP> Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 Lines: 174 In article <1500@mcgill-vision.UUCP> mouse@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 = c_n = n = k = + 1 - 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 = , padding = ?) c_n = (overhead = , 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@mimsy.umd.edu Path: uunet!mimsy!chris