Chapter 29: The Final Optimized Undo

With a few simple considerations, we come up with a good way to reduce the storage requirements of our original Undo. However, as you ll read in the chapter that follows this one, first came some false starts. Here, we ll take a look at how well things turned out, and then we ll explore the dead ends.

Deciding to Begin Again

This chapter is out of chronological order. Following it is a dark chapter about the false starts I made trying to optimize Undo. This one is moved forward for three reasons: first, it will be easier to understand if placed in proximity to the initial Undo that you just read about in Chapter 28, Oh No! Undo! ”the one that snapshots everything. Second, with knowledge of how truly simple the optimization turns out to be, you ll benefit more from the false-start chapter that follows ”Chapter 30, The Long Dark Teatime of the Soul. Third, you may wish to skip over much of the false-start material. It s quite painful ”to me, at least, who made all the mistakes ”but I promised to show you most everything in this book.

We came up with three basic approaches to optimizing our initial Undo:

• First, do nothing. This could be a perfectly viable solution. We have a working Undo that happens to waste a lot of memory. However, it seems to cause no problems in actual use. Our main motivation for fixing it wasn t that it was hurting the program, but that the simple implementation almost seemed like cheating, so we wanted to show how to evolve it to something better.

• Second, compare the lines. There will be more discussion of this in Chapter 30, but here s the idea: Most changes affect only a line or two. If we compared all the lines from the beginning down until the first line that didn t match, and then we compared all the lines from the end until the first line that didn t match, we could limit our considerations to those in between. It seems that these would invariably be just exactly the lines that were changed, and that rarely, if ever, would there be anything extra in there. We would have to consider deletions carefully , to be sure we handled them correctly, but that should be no problem. One concern is that this might be quite costly, but it would be easy to write a test to decide that.

• Third, handle the most common case only. The most common case, by far, is the user typing one ordinary character into an existing line. Looking at this book as an example, there are typically around 500 characters in each paragraph ”and I write very short paragraphs. It seems likely that handling this one case ”insert a character into the current line ”would reduce the storage requirements by well over 99 percent.

I must reflect on these options and counsel with Chet to find out what I really think. And I ll have to gird my loins to delete all that code, although now that I m sure it really cannot work, it s a lot easier. Read on...