ITS Emacs (the original TECO verision) using the SUPDUP display protocol supported "line saving", so it could tell your terminal to stash a line in memory before overwriting it, so later it could almost instantly redisplay that line when you scrolled back to it. That was really great at 300 baud. 1200 baud too, of course. But modems used to cost about a dollar a baud.

https://github.com/PDP-10/supdup/blob/master/supdup.mss#L635

I posted this earlier about the Gosling Emacs screen redisplay algorithm. That was the code that RMS rewrote.

https://news.ycombinator.com/item?id=26114104

To be fair, RMS a right to fuss and complain, because UniPress did kind of pull the rug out from under him. The display update optimization code that Gosling wrote was pretty ugly but amazingly brilliant dynamic programming stuff, and it had a skull-and-crossbones warning in the comments.

RMS originally used the display update code from Gosling Emacs, but then rewrote it all from scratch for later versions of Gnu Emacs, after UniPress threatened him not to use it. As modems and networks became faster, and people started using window systems instead of terminals, having an "Ultra-hot screen management package" became less important. But it's a really cool algorithm, a great example of dynamic programming, and Gosling even published a paper about it!

https://news.ycombinator.com/item?id=22849522

James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).
https://en.wikipedia.org/wiki/Gosling_Emacs

>Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not.

https://donhopkins.com/home/archive/emacs/skull-and-crossbon...

Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted.

https://donhopkins.com/home/archive/emacs/mw/display.c

/* 1 2 3 4 .... Each Mij represents the minumum cost of
+---+---+---+---+----- rearranging the first i lines to map onto
1 | | | | | the first j lines (the j direction
+---+---+---+---+----- represents the desired contents of a line,
2 | | \| ^ | | i the current contents). The algorithm
+---+---\-|-+---+----- used is a dynamic programming one, where
3 | | <-+Mij| | M[i,j] = min( M[i-1,j],
+---+---+---+---+----- M[i,j-1]+redraw cost for j,2
4 | | | | | M[i-1,j-1]+the cost of
+---+---+---+---+----- converting line i to line j);
. | | | | | Line i can be converted to line j by either
. just drawing j, or if they match, by moving
. line i to line j (with insert/delete line)
*/

https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...

https://dl.acm.org/doi/10.1145/1159890.806463

A redisplay algorithm, by James Gosling.

Abstract

This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques.

[...]

6. Conclusion

The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke).

Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach.

More info:

https://news.ycombinator.com/item?id=22850973