CS264: Beyond Worst-Case Analysis Lecture #1: Three Motivating Examples∗

We begin in Sections 2–4 with three examples that clearly justify the need for a course like this, and for alternatives to the traditional worst-case analysis of algorithms. Our discussion is brief and informal, to provide motivation and context. Later lectures treat these examples, and many others, in depth. 2 Caching: LRU vs. FIFO Our first example demonstrates how the worst-case analysis of algorithms can fail to differ-entiate between empirically “better ” and “worse ” solutions. The setup should be familiar from your system courses, if not your algorithms courses. There is a small fast memory (the “cache”) and a big slow memory. For example, the former could be an on-chip cache and the latter main memory; or the former could be main memory and the latter a disk. There is a program that periodically issues read and write requests to data stored on “pages ” in the big slow memory. In the happy event that the requested page is also in the cache, then it can be accessed directly. If not — on a “page fault ” a.k.a. “cache miss ” — the requested page needs to be brought into the cache, and this requires evicting an incumbent page. The key algorithmic question is then: which page should be evicted? For example, consider a cache that has room for four pages (Figure 1). Suppose the first four page requests are for a, b, c, and d; these are brought into the (initially empty) cache in succession. Perhaps the next two requests are for d and a — these are already in the cache so no further actions are required. The party ends when the next request is for page e — now one of the four pages a, b, c, d needs to be evicted to make room for it. Even worse, perhaps the subsequent request is for page f, requiring yet another eviction. ∗ c©2014, Tim Roughgarden