Caching

4 Caching

Forget About It

This chapter’s hardware, company, and institutional examples describe the period in which Algorithms to Live By was written. In the practical use of our intellect, forgetting is as important a function as remembering. —WILLIAM JAMES

You have a problem. Your closet is overflowing, spilling shoes, shirts, and underwear onto the floor. You think, “It’s time to get organized.” Now you have two problems. Specifically, you first need to decide what to keep, and second, how to arrange it. Fortunately, there is a small industry of people who think about these twin problems for a living, and they are more than happy to offer their advice. On what to keep, Martha Stewart says to ask yourself a few questions: “How long have I had it? Does it still function? Is it a duplicate of something I already own? When was the last time I wore it or used it?”

On how to organize what you keep, she recommends “grouping like things together,” and her fellow experts agree. Francine Jay, in The Joy of Less, stipulates, “Hang all your skirts together, pants together, dresses together, and coats together.” Andrew Mellen, who bills himself as “The Most Organized Man in America,” dictates, “Items will be sorted by type—all slacks together, shirts together, coats, etc. Within each type, they’re further sorted by color and style—long-sleeved or short-sleeved, by neckline, etc.”

Other than the sorting problem this could entail, it looks like good advice; it certainly seems unanimous.

Except that there is another, larger industry of professionals who also think obsessively about storage—and they have their own ideas.

Your closet presents much the same challenge that a computer faces when managing its memory: space is limited, and the goal is to save both money and time.

For as long as there have been computers, computer scientists have grappled with the dual problems of what to keep and how to arrange it.

The results of these decades of effort reveal that in her four-sentence advice about what to toss, Martha Stewart actually makes several different, and not fully compatible, recommendations—one of which is much more critical than the others. The computer science of memory management also suggests useful ways to arrange your closet and office.

At first glance, computers appear to follow Martha Stewart’s maxim of “grouping like things together.” Operating systems encourage us to put our files into folders, like with like, forming hierarchies that branch as their contents become ever more specific. But just as the tidiness of a scholar’s desk may hide the messiness of their mind, so does the apparent tidiness of a computer’s file system obscure the highly engineered chaos of how data is actually being stored underneath the nested-folder veneer.

What’s really happening is called caching. Caching plays a critical role in the architecture of memory, and it underlies everything from the layout of processor chips at the millimeter scale to the geography of the global Internet. It offers a new perspective on all the various storage systems and memory banks of human life—not only our machines, but also our closets, our offices, our libraries. And our heads.

The Memory Hierarchy

A certain woman had a very sharp consciousness but almost no memory.… She remembered enough to work, and she worked hard. —LYDIA DAVIS

Starting roughly around 2008, anyone in the market for a new computer has encountered a particular conundrum when choosing their storage option. They must make a tradeoff between size and speed. During the period described here, the computer industry was shifting from hard disk drives to solid-state drives; at the same price point, a hard disk will offer dramatically greater capacity, but a solid-state drive will offer dramatically better performance—as consumers shopping then were discovering.

What casual consumers may not know is that this exact tradeoff is being made within the machine itself at a number of scales—to the point where it’s considered one of the fundamental principles of computing.

In 1946, Arthur Burks, Herman Goldstine, and John von Neumann, working at the Institute for Advanced Study in Princeton, laid out a design proposal for what they called an electrical “memory organ.” In an ideal world, they wrote, the machine would of course have limitless quantities of lightning-fast storage, but in practice this wasn’t possible. (It still isn’t.) Instead, the trio proposed what they believed to be the next best thing: “a hierarchy of memories, each of which has greater capacity than the preceding but which is less quickly accessible.”

By having effectively a pyramid of different forms of memory—a small, fast memory and a large, slow one—maybe we could somehow get the best of both.

The basic idea behind a memory hierarchy should be intuitive to anyone who has ever used a library. If you are researching a topic for a paper, let’s say, there are some books you might need to refer to on multiple occasions. Rather than go back to the library each time, you of course check out the relevant books and take them home to your desk, where you can access them more easily.

In computing, this idea of a “memory hierarchy” remained just a theory until the development in 1962 of a supercomputer in Manchester, England, called Atlas. Its principal memory consisted of a large drum that could be rotated to read and write information, not unlike a wax phonograph cylinder. But Atlas also had a smaller, faster “working” memory built from polarized magnets. Data could be read from the drum to the magnets, manipulated there with ease, and the results then written back to the drum. This automatic management of small, fast memory was a pioneering “one-level storage system” that made the hierarchy truly practical.

Shortly after the development of Atlas, Cambridge mathematician Maurice Wilkes realized that this smaller and faster memory wasn’t just a convenient place to work with data before saving it off again. It could also be used to deliberately hold on to pieces of information likely to be needed later, anticipating similar future requests—and dramatically speeding up the operation of the machine. If what you needed was still in the working memory, you wouldn’t have to load it from the drum at all. As Wilkes put it, the smaller memory “automatically accumulates to itself words that come from a slower main memory, and keeps them available for subsequent use without it being necessary for the penalty of main memory access to be incurred again.”

The key, of course, would be managing that small, fast, precious memory so it had what you were looking for as often as possible.

To continue the library analogy, if you’re able to make just one trip to the stacks to get all the books you need, and then spend the rest of the week working at home, that’s almost as good as if every book in the library had already been available at your desk. The more trips back to the library you make, the slower things go, and the less your desk is really doing for you.

Wilkes’s proposal was implemented in the IBM 360/85 supercomputer later in the 1960s, where it acquired the name of the “cache.” Since then, caches have appeared everywhere in computer science. The idea of keeping around pieces of information that you refer to frequently is so powerful that it is used in every aspect of computation. Processors have caches. Hard drives have caches. Operating systems have caches. Web browsers have caches. And the servers that deliver content to those browsers also have caches, making it possible to instantly show you the same video of a cat riding a vacuum cleaner that millions of … But we’re getting ahead of ourselves a bit.

The story of the computer over the past fifty-plus years has been painted as one of exponential growth year after year—referencing, in part, the famously accurate “Moore’s Law” prediction, made by Intel’s Gordon Moore in 1975, that the number of transistors in CPUs would double every two years. What hasn’t improved at that rate is the performance of memory, which means that relative to processing time, the cost of accessing memory is also increasing exponentially. The faster you can write your papers, for instance, the greater the loss of productivity from each trip to the library. Likewise, a factory that doubles its manufacturing speed each year—but has the same number of parts shipped to it from overseas at the same sluggish pace—will mean little more than a factory that’s twice as idle. For a while it seemed that Moore’s Law was yielding little except processors that twiddled their thumbs ever faster and ever more of the time. In the 1990s this began to be known as the “memory wall.” Computer science’s best defense against hitting that wall has been an ever more elaborate hierarchy: caches for caches for caches, all the way down. Modern consumer laptops, tablets, and smartphones have on the order of a six-layer memory hierarchy, and managing memory smartly has never been as important to computer science as it is today.

Eviction and Clairvoyance

Depend upon it there comes a time when for every addition of knowledge you forget something that you knew before. It is of the highest importance, therefore, not to have useless facts elbowing out the useful ones. —SHERLOCK HOLMES

When a cache fills up, you are obviously going to need to make room if you want to store anything else, and in computer science this making of room is called “cache replacement” or “cache eviction.” As Wilkes wrote, “Since the [cache] can only be a fraction of the size of the main memory, words cannot be preserved in it indefinitely, and there must be wired into the system an algorithm by which they are progressively overwritten.” These algorithms are known as “replacement policies” or “eviction policies,” or simply as caching algorithms.

IBM, as we’ve seen, played an early role in the deployment of caching systems in the 1960s. Unsurprisingly, it was also the home of seminal early research on caching algorithms—none, perhaps, as important as that of László “Les” Bélády. Bélády was born in 1928 in Hungary, where he studied as a mechanical engineer before fleeing to Germany during the 1956 Hungarian Revolution with nothing but a satchel containing “one change of underwear and my graduation paper.” From Germany he went to France, and in 1961 immigrated to the United States, bringing his wife, “an infant son and $1,000 in my pocket, and that’s it.” It seems he had acquired a finely tuned sense of what to keep and what to leave behind by the time he found himself at IBM, working on cache eviction.

Bélády’s 1966 paper, “A Study of Replacement Algorithms for a Virtual-Storage Computer,” would become the most cited piece of computer science research for fifteen years. As it explains, the goal of cache management is to minimize the number of times you can’t find what you’re looking for in the cache and must go to the slower main memory to find it; these are known as “page faults” or “cache misses.”

The optimal cache eviction policy—essentially by definition, Bélády wrote—is, when the cache is full, to evict whichever item we’ll need again the longest from now.

Of course, knowing exactly when you’ll need something again is easier said than done. The hypothetical all-knowing, prescient algorithm that would look ahead and execute the optimal policy is known today in tribute as Bélády’s Algorithm.

Bélády’s Algorithm is an instance of what computer scientists call a “clairvoyant” algorithm: one informed by data from the future. It’s not necessarily as crazy as it sounds—there are cases where a system might know what to expect—but in general clairvoyance is hard to come by, and software engineers joke about encountering “implementation difficulties” when they try to deploy Bélády’s Algorithm in practice.

So the challenge is to find an algorithm that comes as close to clairvoyance as we can get, for all those times when we’re stuck firmly in the present and can only guess at what lies ahead. We could just try Random Eviction, adding new data to the cache and overwriting old data 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, even a simple cache can help when requests repeat, although its benefit depends on the workload and the costs of maintaining 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, such as LRU-K, 2Q, and LRFU, and those that adapt dynamically, like ARC.

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. Here’s why: if temporal locality holds, then the rough-sorting shelves contain the most important books in the whole building. These are the books that were most recently used, so they are the ones that patrons are most likely to be looking for. It seems a crime that arguably the juiciest and most browseworthy shelf of the libraries’ miles of stacks is both hidden away and constantly eroded by earnest library staff just doing their jobs.

Meanwhile, the lobby of the Moffitt Undergraduate Library—the location of the most prominent and accessible shelves—showcases the library’s most recently acquired books. This is instantiating a kind of FIFO cache, privileging the items that were last added to the library, not last read.

The dominant performance of the LRU algorithm in most tests that computer scientists have thrown at it leads to a simple suggestion: turn the library inside out. Put acquisitions in the back, for those who want to find them. And put the most recently returned items in the lobby, where they are ripe for the browsing.

Humans are social creatures, and presumably the undergraduate body would find it interesting to peruse its own reading habits. It would nudge the campus toward a more organic and free-form version of what colleges strive for when they assign “common books”: the facilitation of intellectual common points of reference. Here, the books being read on campus, whatever they happened to be, would become the books most likely to be serendipitously encountered by other students. A kind of grassroots, bottom-up analogue of the common book program.

But a system like this wouldn’t only be more socially positive. Since the items most recently returned are the ones most likely to be next checked out, it would also be more efficient.

It’s true that students might be puzzled by the fact that popular books will sometimes be found in the stacks and sometimes in the lobby. However, recently returned books that await reshelving are missing from the stacks either way. It’s just that currently they are off-limits during this brief limbo.

Allowing the returned books to adorn the lobby instead would give students a chance to short-circuit the shelving process entirely. No employees would have to venture into the stacks to deposit the volumes, and no students would have to venture into the stacks to get them back out. That’s exactly how caching is meant to work.

The Cloud at the End of the Street

“We actually made a map of the country, on the scale of a mile to the mile!” “Have you used it much?” I enquired. “It has never been spread out, yet,” said Mein Herr: “the farmers objected: they said it would cover the whole country, and shut out the sunlight! So we now use the country itself, as its own map, and I assure you it does nearly as well.” —LEWIS CARROLL

We often think of the Internet as a flat, independent, and loosely connected network. In fact, it’s none of those things. In the period described here, a quarter of all Internet traffic was reportedly handled by a single corporation, one that manages to stay almost entirely out of the headlines. This Massachusetts-based company is called Akamai, and they’re in the caching business.

We also think of the Internet as abstract, dematerial, post-geographic. We’re told our data is “in the cloud,” which is meant to suggest a diffuse, distant place. Again, none of these are true. The reality is that the Internet is all about bundles of physical wires and racks of metal. And it’s much more closely tied to geography than you might expect. Engineers think about geography on a tiny scale when they design computer hardware: faster memory is usually placed closer to the processor, minimizing the length of the wires that information has to travel along. Today’s processor cycles are measured in gigahertz, which is to say they are performing operations in fractions of nanoseconds.

For reference, that’s the time it takes light to travel a few inches—so the physical layout of a computer’s internals is very much a concern.

And applying the same principle at a dramatically larger scale, actual geography turns out to be critical for the functioning of the web, where the wires span not inches but potentially thousands of miles. If you can create a cache of webpage content that is physically, geographically closer to the people who want it, you can serve those pages faster.

Much of the traffic on the Internet is now handled by “content distribution networks” (CDNs), which have computers around the world that maintain copies of popular websites. This allows users requesting those pages to get their data from a computer that’s nearby, without having to make the long haul across continents to the original server. Akamai, a major CDN provider in this account, manages such a network: content providers pay for their websites to be “Akamaized” for better performance. An Australian who streams video from the BBC, for instance, is probably hitting local Akamai servers in Sydney; the request never makes it to London at all. It doesn’t have to. Says Akamai’s chief architect, Stephen Ludin, “It’s our belief—and we build the company around the fact—that distance matters.”

In our earlier discussion, we noted that certain types of computer memory have faster performance but cost more per unit of storage, leading to a “memory hierarchy” that tries to get the best of both. But it’s not actually necessary to have memory made of different materials for caching to make sense. Caching is just as useful when it’s proximity, rather than performance, that’s the scarce resource.

This fundamental insight—that in-demand files should be stored near the location where they are used—also translates into purely physical environments. For example, Amazon’s enormous fulfillment centers generally eschew any type of human-comprehensible organization, of the kind you’d find in a library or a department store. Instead, employees are told to place incoming items wherever they can find space in the warehouse—batteries cheek by jowl with pencil sharpeners, diapers, barbecue grills, and learn-the-dobro DVDs—and tag the location of each item in a central database using bar codes. This deliberately disorganized-looking storage system, sometimes called “chaotic storage,” still has one visible exception: high-demand items are placed in a different area, more quickly accessible than the rest. That area is Amazon’s cache.

Amazon had been granted a patent for an innovation that pushes this principle one step further. The patent talks about “anticipatory package shipping,” which the press seized upon as though Amazon could somehow mail you something before you bought it. Amazon, like any technology company, would love to have that kind of Bélády-like clairvoyance—but for the next best thing, it turns to caching. Their patent is actually for shipping items that have been recently popular in a given region to a staging warehouse in that region—like having their own CDN for physical goods.

Then, when somebody places an order, the item is just down the street.

Anticipating the purchases of individuals is challenging, but when predicting the purchases of a few thousand people, the law of large numbers kicks in. Somebody in Berkeley is going to order, say, recycled toilet paper in a given day, and when they do it’s already most of the way there.

When the things popular in an area are also from that area, an even more interesting geography of the cloud emerges. In 2011, film critic Micah Mertes created a map of the United States using each state’s “Local Favorites” from Netflix—highlighting the movies uncommonly popular in each of those states. Overwhelmingly, it turned out, people love watching movies set where they live. Washingtonians favor Singles, set in Seattle; Louisianans watch The Big Easy, set in New Orleans; Angelinos unsurprisingly enjoy L.A. Story; Alaskans love Braving Alaska; and Montanans, Montana Sky.

And because nothing benefits quite so much from local caching as the enormous files that comprise full-length HD video, regional demand would give Netflix a reason to cache a film such as L.A. Story near Los Angeles. The map alone does not establish where Netflix actually stored those files.

Caching on the Home Front

While caching began as a scheme for organizing digital information inside computers, it’s clear that it is just as applicable to organizing physical objects in human environments. When we spoke to John Hennessy—then president of Stanford University, and a pioneering computer architect who helped develop modern caching systems—he immediately saw the link:

Caching is such an obvious thing because we do it all the time. I mean, the amount of information I get … certain things I have to keep track of right now, a bunch of things I have on my desk, and then other things are filed away, and then eventually filed away into the university archives system where it takes a whole day to get stuff out of it if I wanted. But we use that technique all the time to try to organize our lives.

The direct parallel between these problems means that there’s the potential to consciously apply the solutions from computer science to the home.

First, when you are deciding what to keep and what to throw away, LRU can be a useful starting point when recent use predicts future need. It can work better than FIFO, though age and recency are not the only reasons to keep an object. You shouldn’t necessarily toss that T-shirt from college if you still wear it every now and then. But the plaid pants you haven’t worn in ages? Those can be somebody else’s thrift-store bonanza.

Second, exploit geography. Make sure things are in whatever cache is closest to the place where they’re typically used. This isn’t a concrete recommendation in most home-organization books, but it consistently turns up in the schemes that actual people describe as working well for them. “I keep running and exercise gear in a crate on the floor of my front coat closet,” says one person quoted in Julie Morgenstern’s Organizing from the Inside Out, for instance. “I like having it close to the front door.” A slightly more extreme example appears in the book Keeping Found Things Found by William Jones:

A doctor told me about her approach to keeping things. “My kids think I’m whacky, but I put things where I think I’ll need them again later, even if it doesn’t make much sense.” As an example of her system, she told me that she keeps extra vacuum cleaner bags behind the couch in the living room. Behind the couch in the living room? Does that make any sense?… It turns out that when the vacuum cleaner is used, it is usually used for the carpet in the living room.… When a vacuum cleaner bag gets full and a new one is needed, it’s usually in the living room. And that’s just where the vacuum cleaner bags are.

A final insight, which hasn’t yet made it into guides on closet organization, is that of the multi-level memory hierarchy. Having a cache is efficient, but having multiple levels of caches—from smallest and fastest to largest and slowest—can be even better.

Where your belongings are concerned, your closet is one cache level, your basement another, and a self-storage locker a third. (These are in decreasing order of access speed, of course, so you should use the LRU principle as the basis for deciding what gets evicted from each level to the next.)

But you might also be able to speed things up by adding yet another level of caching: an even smaller, faster, closer one than your closet.

Tom’s otherwise extremely tolerant wife objects to a pile of clothes next to the bed, despite his insistence that it’s in fact a highly efficient caching scheme.

Fortunately, our conversations with computer scientists revealed a solution to this problem too.

Rik Belew of UC San Diego, who studies search engines from a cognitive perspective, recommended the use of a valet stand. Though you don’t see too many of them these days, a valet stand is essentially a one-outfit closet, a compound hanger for jacket, tie, and slacks—the perfect piece of hardware for your domestic caching needs. Which just goes to show that computer scientists won’t only save you time; they might also save your marriage.

Filing and Piling

After deciding what to keep and where it should go, the final challenge is knowing how to organize it. We’ve talked about what goes in the closet and where the closet should be, but how should things be arranged inside? One of the constants across all pieces of home-organization advice we’ve seen so far is the idea of grouping “like with like”—and perhaps no one so directly flies in the face of that advice as Yukio Noguchi. “I have to emphasize,” says Noguchi, “that a very fundamental principle in my method is not to group files according to content.”

Noguchi, described here as an economist at the University of Tokyo, is the author of a series of books that offer “super” tricks for sorting out your office and your life.

Their titles translate roughly to Super Persuasion Method, Super Work Method, Super Study Method—and, most relevantly for us, Super Organized Method.

Early in his career as an economist, Noguchi found himself constantly inundated with information—correspondence, data, manuscripts—and losing a significant portion of each day just trying to organize it all. So he looked for an alternative. He began by simply putting each document into a file labeled with the document’s title and date, and putting all the files into one big box. That saved time—he didn’t have to think about the right place to put each document—but it didn’t result in any form of organization.

Then, sometime in the early 1990s, he had a breakthrough: he started to insert the files exclusively at the left-hand side of the box. And thus the “super” filing system was born.

The left-side insertion rule, Noguchi specifies, has to be followed for old files as well as new ones: every time you pull out a file to use its contents, you must put it back as the leftmost file when you return it to the box. And when you search for a file, you always start from the left-hand side as well. The most recently accessed files are thus the fastest to find.

This practice began, Noguchi explains, because returning every file to the left side was just easier than trying to reinsert it at the same spot it came from.

Only gradually did he realize that this procedure was not only simple but also startlingly efficient.

The Noguchi Filing System clearly saves time when you’re replacing something after you’re done using it. There’s still the question, however, of whether it’s a good way to find the files you need in the first place. After all, it certainly goes against the recommendations of other efficiency gurus, who tell us that we should put similar things together. Indeed, even the etymology of the word “organized” evokes a body composed of organs—which are nothing if not cells grouped “like with like,” marshalled together by similar form and function.

But computer science gives us something that most efficiency gurus don’t: guarantees.

Though Noguchi didn’t know it at the time, his filing system represents an extension of the LRU principle. LRU tells us that when a full cache must admit an item, we should discard the item least recently used—but it doesn’t tell us where we should put the new item.

The answer to that question comes from a line of research carried out by computer scientists in the 1970s and ’80s.

Their version of the problem is called “self-organizing lists,” and its setup almost exactly mimics Noguchi’s filing dilemma.

Imagine that you have a set of items in a sequence, and you must periodically search through them to find specific items.

The search itself is constrained to be linear—you must look through the items one by one, starting at the beginning—but once you find the item you’re looking for, you can put it back anywhere in the sequence. Where should you replace the items to make searching as efficient as possible?

The definitive paper on self-organizing lists, published by Daniel Sleator and Robert Tarjan in 1985, examined (in classic computer science fashion) the worst-case performance of various ways to organize the list given all possible sequences of requests.

Intuitively, since the search starts at the front, you want to arrange the sequence so that the items most likely to be searched for appear there. But which items will those be? We’re back to wishing for clairvoyance again. “If you know the sequence ahead of time,” says Tarjan, who splits his time between Princeton and Silicon Valley, “you can customize the data structure to minimize the total time for the entire sequence. That’s the optimum offline algorithm: God’s algorithm if you will, or the algorithm in the sky. Of course, nobody knows the future, so the question is, if you don’t know the future, how close can you come to this optimum algorithm in the sky?”

Sleator and Tarjan’s results showed that some “very simple self-adjusting schemes, amazingly, come within a constant factor” of clairvoyance. Namely, if you follow the LRU principle—where you simply always put an item back at the very front of the list—then, under the standard list-update cost model, its total cost is at most twice the offline optimum, with an additive allowance for the initial arrangement. This is a worst-case guarantee for the model, not a claim that no other algorithm can achieve the same bound.

Noguchi’s system uses the move-to-front rule. The theorem gives that rule a strong worst-case guarantee for sequential list searches; it does not make the filing system optimal for every office or every sequence of requests.

Sleator and Tarjan’s results also provide us with one further twist, and we get it by turning the Noguchi Filing System on its side. Quite simply, a box of files on its side becomes a pile.

And it’s the very nature of piles that you search them from top to bottom, and that each time you pull out a document it goes back not where you found it, but on top. In short, the mathematics of self-organizing lists suggests something radical: the big pile of papers on your desk, far from being a guilt-inducing fester of chaos, is actually one of the most well-designed and efficient structures available. What might appear to others to be an unorganized mess is, in fact, a self-organizing mess. Putting each used item back on top implements move-to-front, provided you search from the top and the list-update model fits the task.

In the previous chapter we examined cases where leaving something unsorted was more efficient than taking the time to sort everything; here, however, there’s a very different reason why you don’t need to organize it. You already have.

The Forgetting Curve

Of course, no discussion of memory could be complete without mention of the “memory organ” closest to home: the human brain. Over the past few decades, the influence of computer science has brought about something of a revolution in how psychologists think about memory.

The science of human memory is said to have begun in 1879, with a young psychologist at the University of Berlin named Hermann Ebbinghaus. Ebbinghaus wanted to get to the bottom of how human memory worked, and to show that it was possible to study the mind with all the mathematical rigor of the physical sciences.

So he began to experiment on himself. Each day, Ebbinghaus would sit down and memorize a list of nonsense syllables. Then he would test himself on lists from previous days.

Pursuing this habit over the course of a year, he established many of the most basic results in human memory research. He confirmed, for instance, that practicing a list multiple times makes it persist longer in memory, and that the number of items one can accurately recall goes down as time passes.

His results mapped out a graph of how memory fades over time, known today by psychologists as “the forgetting curve.”

Ebbinghaus’s results established the credibility of a quantitative science of human memory, but they left open something of a mystery.

Why this particular curve? Does it suggest that human memory is good or bad? What’s the underlying story here? These questions have stimulated psychologists’ speculation and research for more than a hundred years.

In 1987, Carnegie Mellon psychologist and computer scientist John Anderson found himself reading about the information retrieval systems of university libraries.

Anderson’s goal—or so he thought—was to write about how the design of those systems could be informed by the study of human memory.

Instead, the opposite happened: he realized that information science could provide the missing piece in the study of the mind. “For a long time,” says Anderson, “I had felt that there was something missing in the existing theories of human memory, including my own. Basically, all of these theories characterize memory as an arbitrary and non-optimal configuration.… I had long felt that the basic memory processes were quite adaptive and perhaps even optimal; however, I had never been able to see a framework in which to make this point. In the computer science work on information retrieval, I saw that framework laid out before me.”

A natural way to think about forgetting is that our minds simply run out of space.

The key idea behind Anderson’s new account of human memory is that the problem might be not one of storage, but of organization.

According to his theory, the mind has essentially infinite capacity for memories, but we have only a finite amount of time in which to search for them.

Anderson made the analogy to a library with a single, arbitrarily long shelf—the Noguchi Filing System at Library of Congress scale.

You can fit as many items as you want on that shelf, but the closer something is to the front the faster it will be to find.

The key to a good human memory then becomes the same as the key to a good computer cache: predicting which items are most likely to be wanted in the future. Barring clairvoyance, the best approach to making such predictions in the human world requires understanding the world itself.

With his collaborator Lael Schooler, Anderson set out to perform Ebbinghaus-like studies not on human minds, but on human society.

The question was straightforward: what patterns characterize the way the world itself “forgets”—the way that events and references fade over time?

Anderson and Schooler analyzed three human environments: headlines from the New York Times, recordings of parents talking to their children, and Anderson’s own email inbox.

In all domains, they found that a word is most likely to appear again right after it had just been used, and that the likelihood of seeing it again falls off as time goes on.

In other words, reality itself has a statistical structure that mimics the Ebbinghaus curve.

This suggests something remarkable.

If the pattern by which things fade from our minds is the very pattern by which things fade from use around us, then there may be a very good explanation indeed for the Ebbinghaus forgetting curve—namely, that the pattern may reflect adaptation to the world, making likely-to-be-needed information easier to retrieve. The resemblance supports a model of memory; it does not establish perfect tuning.

Human memory and human environments. The left panel shows the percentage of nonsense syllables Ebbinghaus correctly recalled from a list, as a function of the number of hours he waited after first memorizing the list. The right panel shows the chance that a word appears in the headlines of the New York Times on a given day, as a function of the time since its previous appearance in print.

In putting the emphasis on time, caching shows us that memory involves unavoidable tradeoffs, and a certain zero-sumness. You can’t have every library book at your desk, every product on display at the front of the store, every headline above the fold, every paper at the top of the pile.

And in the same way, you can’t have every fact or face or name at the front of your mind. “Many people hold the bias that human memory is anything but optimal,” wrote Anderson and Schooler. “They point to the many frustrating failures of memory. However, these criticisms fail to appreciate the task before human memory, which is to try to manage a huge stockpile of memories. In any system responsible for managing a vast data base there must be failures of retrieval. It is just too expensive to maintain access to an unbounded number of items.”

This understanding has in turn led to a second revelation about human memory. If these tradeoffs really are unavoidable, and the brain appears to be optimally tuned to the world around it, then what we refer to as the inevitable “cognitive decline” that comes with age may in fact be something else.

The Tyranny of Experience

A big book is a big nuisance. —CALLIMACHUS, LIBRARIAN AT ALEXANDRIA

Why don’t they make the whole plane out of that black box stuff? —STEVEN WRIGHT

The need for a computer memory hierarchy, in the form of a cascade of caches, is in large part the result of our inability to afford making the entire memory out of the most expensive type of hardware. The fastest cache on current computers, for instance, is made with what’s called SRAM, which costs roughly a thousand times as much per byte as the flash memory in solid-state drives.

But the true motivation for caching goes deeper than that.

In fact, even if we could get a bespoke machine that used exclusively the fastest form of memory possible, we’d still need caches. As John Hennessy explains, size alone is enough to impair speed:

When you make something bigger, it’s inherently slower, right? If you make a city bigger, it takes longer to get from point A to point B. If you make a library bigger, it takes longer to find a book in the library. If you have a stack of papers on your desk that’s bigger, it takes longer to find the paper you’re looking for, right? Caches are actually a solution to that problem.… For example, right now, if you go to buy a processor, what you’ll get is a Level 1 cache and a Level 2 cache on the chip. The reason that there are—even just on the chip there are two caches!—is that in order to keep up with the cycle rate of the processor, the first-level cache is limited in size.

In these models, a larger store of information can make retrieval slower. The cost also depends on how the information is organized and accessed.

Brian and Tom, in their thirties, already find themselves more frequently stalling a conversation as, for instance, they wait for the name of someone “on the tip of the tongue” to come to mind.

Then again, Brian at age ten had two dozen schoolmates; twenty years later he has hundreds of contacts in his phone and thousands on Facebook, and has lived in four cities, each with its own community of friends, acquaintances, and colleagues.

Tom, by this point in his academic career, has worked with hundreds of collaborators and taught thousands of students. (In fact, this very book involved meeting with about a hundred people and citing a thousand.)

Such effects are by no means limited to social connections, of course: a typical two-year-old knows two hundred words; a typical adult knows thirty thousand.

And when it comes to episodic memory, well, every year adds a third of a million waking minutes to one’s total lived experience.

Considered this way, it’s a wonder that the two of us—or anyone—can mentally keep up at all. What’s surprising is not memory’s slowdown, but the fact that the mind can possibly stay afloat and responsive as so much data accumulates.

If the fundamental challenge of memory really is one of organization rather than storage, perhaps it should change how we think about the impact of aging on our mental abilities. Work discussed here by a team of psychologists and linguists led by Michael Ramscar at the University of Tübingen has suggested that what we call “cognitive decline”—lags and retrieval errors—may not be about the search process slowing or deteriorating, but (at least partly) an unavoidable consequence of the amount of information we have to navigate getting bigger and bigger. Regardless of whatever other challenges aging brings, a greater store of memories can create harder retrieval problems in this account of aging. The old can mock the young for their speed: “It’s because you don’t know anything yet!”

Ramscar’s group demonstrated the impact of extra information on human memory by focusing on the case of language.

Through a series of simulations, the researchers showed that simply knowing more makes things harder when it comes to recognizing words, names, and even letters. The simulations suggest that accumulated knowledge can explain some slower responses. That does not mean all age-related memory changes are consequences of learning, or that every search grows slower in the same way. The archive metaphor captures one proposed contribution to the problem.

An understanding of the unavoidable computational demands of memory, Ramscar says, should help people come to terms with the effects of aging on cognition. “I think the most important tangible thing seniors can do is to try to get a handle on the idea that their minds are natural information processing devices,” he writes. “Some things that might seem frustrating as we grow older (like remembering names!) are a function of the amount of stuff we have to sift through … and are not necessarily a sign of a failing mind.” As he puts it, “A lot of what is currently called decline is simply learning.”

Caching gives us the language to understand what’s happening. An occasional “brain fart” can resemble a “cache miss.” That gives us another way to think about retrieval delays. The disproportionate occasional lags in information retrieval are a reminder of just how much we benefit the rest of the time by having what we need at the front of our minds. So as you age, and begin to experience these sporadic latencies, take heart: the length of a delay is partly an indicator of the extent of your experience. Accumulated experience may explain part of that effort. The analogy helps explain ordinary retrieval delays; it cannot establish the cause of a particular person’s memory difficulties.