some side comments about absolute line gotos

[barmar@Think.COM (Barry Margolin)]

There are some good software engineering reasons for having a command
that does a goto-line# operation, even if its implementation would be no
better than the key sequence the user would type.  The details of the
editor's implementation should not govern the user interface.

Also, even with Zwei's linked list buffer design there are opportunities
for optimization of goto-line#.  Multics Emacs maintained the number of
lines in the buffer (the primitives for inserting and deleting lines in
the linked list increment and decrement it); goto-line# can then decide
whether the line is closer to the end or beginning of the buffer, so it
never has to traverse more than half the buffer.  Zwei, with its
hierarchical node structure, could improve on this by maintaining
starting and ending line numbers for each node (these could be updated
on an as-needed basis, or by a background process).

In fact, the line number could be stored in the LINE-PLIST for each
line, along with a tick indicating when the line number was last known
to be valid; the if the line number tick is newer than the buffer's
modification tick then the line number is valid, and relative motion
from a line with a valid line number would update the target's line
number if necessary (most buffer motion is relative, so this is a fairly
easy way to keep this stuff up to date).  Goto-line# could then look at
the current line's line number, and determine whether it would be faster
to use relative motion from a buffer end or the current location.

One question, of course, is whether it's worthwhile optimizing
goto-line#.  Except for paging, FORWARD-LINE can traverse 23K lines per
second on my 3640.  Unfortunately, paging is likely to be a factor
(Multics Emacs's implementation of buffer lines as an indirect pointer
to the string is better in this respect, because you can fit more line
objects on a page if the contents aren't interspersed); I can take about
35 page faults per second, so if I assume an average of 60 characters
per line that's 10 lines per memory page (a mostly unmodified buffer is
likely to have adjacent lines sequential in memory -- hooray for areas)
this brings it down to 350 lines per second if the buffer is completely
paged out.  If goto-line# is expected to be a common operation then
optimization might be worth it (the relative motion described in the
previous paragraph should have reasonably low paging so it should
average several thousand lines per second).

                                                barmar