at random. One of the startling early results in caching theory is that, while far from perfect, this approach is not half bad. As it happens, just having a cache at all makes a system more efficient, regardless of how you maintain it. Items you use often will end up back in the cache soon anyway. Another simple strategy is First-In, First-Out (FIFO), where you evict or overwrite whatever has been sitting in the cache the longest (as in Martha Stewart’s question “How long have I had it?”). A third approach is Least Recently Used (LRU): evicting the item that’s gone the longest untouched (Stewart’s “When was the last time I wore it or used it?”).
It turns out that not only do these two mantras of Stewart’s suggest very different policies, one of her suggestions clearly outperforms the other. Bélády compared Random Eviction, FIFO, and variants of LRU in a number of scenarios and found that LRU consistently performed the closest to clairvoyance. The LRU principle is effective because of something computer scientists call “temporal locality”: if a program has called for a particular piece of information once, it’s likely to do so again in the near future. Temporal locality results in part from the way computers solve problems (for example, executing a loop that makes a rapid series of related reads and writes), but it emerges in the way people solve problems, too. If you are working on your computer, you might be switching among your email, a web browser, and a word processor. The fact that you accessed one of these recently is a clue that you’re likely to do so again, and, all things being equal, the program that you haven’t been using for the longest time is also probably the one that won’t be used for some time to come.
In fact, this principle is even implicit in the interface that computers show to their users. The windows on your computer screen have what’s called a “Z-order,” a simulated depth that determines which programs are overlaid on top of which. The least recently used end up at the bottom. As former creative lead for Firefox, Aza Raskin, puts it, “Much of your time using a modern browser (computer) is spent in the digital equivalent of shuffling papers.” This “shuffling” is also mirrored exactly in the Windows and Mac OS task switching interfaces: when you press Alt + Tab or Command + Tab, you see your applications listed in order from the most recently to the least recently used.
The literature on eviction policies goes about as deep as one can imagine—including algorithms that account for frequency as well as recency of use, algorithms that track the time of the next-to-last access rather than the last one, and so on. But despite an abundance of innovative caching schemes, some of which can beat LRU under the right conditions, LRU itself—and minor tweaks thereof—is the overwhelming favorite of computer scientists, and is used in a wide variety of deployed applications at a variety of scales. LRU teaches us that the next thing we can expect to need is the last one we needed, while the thing we’ll need after that is probably the second-most-recent one. And the last thing we can expect to need is the one we’ve already gone longest without.
Unless we have good reason to think otherwise, it seems that our best guide to the future is a mirror image of the past. The nearest thing to clairvoyance is to assume that history repeats itself—backward.
Turning the Library Inside Out
Deep within the underground Gardner Stacks at the University of California, Berkeley, behind a locked door and a prominent “Staff Only” notice, totally off-limits to patrons, is one of the jewels of the UC library system. Cormac McCarthy, Thomas Pynchon, Elizabeth Bishop, and J. D. Salinger; Anaïs Nin, Susan Sontag, Junot Díaz, and Michael Chabon; Annie Proulx, Mark Strand, and Philip K. Dick; William Carlos Williams, Chuck Palahniuk, and Toni Morrison; Denis Johnson, Juliana Spahr, Jorie Graham, and David Sedaris; Sylvia Plath, David Mamet, David Foster Wallace, and Neil Gaiman … It isn’t the library’s rare book collection; it’s its cache.
As we have already discussed, libraries are a natural example of a memory hierarchy when used in concert with our own desk space. In fact, libraries in themselves, with their various sections and storage facilities, are a great example of a memory hierarchy with multiple levels. As a consequence, they face all sorts of caching problems. They have to decide which books to put in the limited display space at the front of the library, which to keep in their stacks, and which to consign to offsite storage. The policy for which books to shunt offsite varies from library to library, but almost all use a version of LRU. “For the Main Stacks, for example,” says Beth Dupuis, who oversees the process in the UC Berkeley libraries, “if an item hasn’t been used in twelve years, that’s the cutoff.”
At the other end of the spectrum from the books untouched in a dozen years is the library’s “rough sorting” area, which we visited in the previous chapter. This is where books go just after they are returned, before they’re fully sorted and shelved once again in the stacks. The irony is that the hardworking assistants putting them back on their shelves might, in some sense, be making them less ordered.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.
