Buffering

Computers have at least two flavors of memory storage. The registers are the “retail” storage, directly addressable by the processor. There is magnetic disk storage, which is “wholesale” and contains pages, with, say, 512 register-sized numbers per page. Each page must be loaded into 512 contiguous registers to be seen by the processer. To search a document, a program needs to bring these pages into memory, one at a time. By the way, the videos that Netflix stores are handled the same way. That’s why, if you rewind the video, there might be an irritating pause. The program is retrieving a previous page.

Getting back to our pattern: it’s possible, albeit unlikely, that the fifth character in the text is the last character on a page and the sixth is the first character of a new page, which we have just brought in from the disk, replacing the contents of the previous page, so backing up in the text requires getting the previous page back.

There are different ways to solve this problem, including keeping two 512 register buffers active, but I chose to make the search algorithm more complicated.