Why Frequently Used Data Lives in Faster, Smaller Memory

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.8 Free with a free account

Why Frequently Used Data Lives in Faster, Smaller Memory

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.8 · lesson 85 of 878 min · free with a free account

← How Java Allocates, Tracks, and Reclaims MemoryNext lesson: Navigating Massive Disk Datasets with Multi-Level Index Trees →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Memory hierarchies, locality, hit ratios, and building an LRU cache.

  • Explain the memory hierarchy and the two kinds of locality of reference
  • Compute average access time from a hit ratio
  • Compare FIFO, LRU, Random, and OPT replacement policies
  • Build an LRU cache from a hash map and a doubly linked list

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,082 words). Read along, or search it.

Opening Question

Same Work, Four Hundred Times Slower

Two loops each add up four million numbers. Both are order n, with the same number of steps. In one test, the first finished in under two milliseconds. The second took almost seven tenths of a second, about four hundred times longer. Same work, same big O. So where did the time go?

Memory Hierarchy

Caches, Main Memory, and Disk

Counting steps assumes every memory access costs the same. On a real computer it doesn't. No memory is large, fast, and cheap all at once. So computers stack layers: tiny, very fast caches next to the processor, then main memory, then disk. Each layer keeps copies of what it expects to be asked for next. In one test, chasing random positions through an array cost 1.5 nanoseconds per access, with 16 kilobytes of data. At 256 megabytes, it cost 182 nanoseconds: about 120 times more.

Locality

Temporal and Spatial Locality

A small cache works because programs aren't random. They show locality of reference, of two kinds. Temporal locality: a value used now will probably be used again soon, like a loop counter, or a popular record. Spatial locality: after one address, its neighbors usually come next. Hardware moves data in cache lines, typically 64 bytes, so one read brings in its neighbors too. In one test, a 4,096 by 4,096 grid was summed row by row, in 11.9 milliseconds. Column by column, the same additions took 187.7: almost 16 times as long.

Hit Ratio

Average Time per Request

When the cache holds what's asked for, that's a hit. Otherwise it's a miss: the data comes from the slower layer, and a copy is kept for next time. The fraction of requests that hit is the hit ratio, h. The average time per request is h times the hit time, plus one minus h, times the miss time. Take a 2 nanosecond hit and a 100 nanosecond miss. Run it. Half hits cost 51 nanoseconds a request. Going from 90 to 99 percent hits drops the average from 11.8 to 3.0, almost four times faster.

Quick Check

Ninety-Five Percent Hits

Quick check. A different cache answers a hit in 1 nanosecond, and a miss in 50. It hits 95 percent of the time. What's the average time per request? Pause and predict. About 3.45. The hits contribute 0.95 nanoseconds. The misses contribute 5 percent of 50, which is 2.5. So even at 95 percent hits, the rare misses take most of the time. Every point of hit ratio matters.

Replacement Policies

FIFO, LRU, Random, and OPT

A cache is small, so it fills. On the next miss, something must go. The rule that picks the victim is the replacement policy. FIFO evicts the item that's been in longest. LRU evicts the one unused for longest. Random needs no bookkeeping at all. And OPT evicts the item needed farthest in the future. No real cache can know that, but it shows the best possible. In one test, 80 percent of the requests went to a hot set of 200 items. With room for 200, LRU got 57.7 percent hits, and FIFO and Random about 52.

Worst Pattern

A Loop One Item Bigger Than the Cache

But no policy wins on every pattern. Here, a program reads 101 items in order, again and again, through a cache with room for 100. Run it. LRU and FIFO get no hits at all. Each time, they throw out exactly the item that's needed next. Random replacement gets about 96 percent.

LRU Cache

A Hash Map Plus a Doubly Linked List

Now build an LRU cache. It must find an entry by key quickly, and keep entries in order of recent use. No single structure does both. A hash map finds a key in constant time, but has no order. A doubly linked list keeps the order, most recent at the front. It can unlink an entry in constant time, if it's handed the entry. So the hash map stores each key's position in the list. A get moves the entry to the front. A put on a full cache first evicts the entry at the back, from both structures. Here the list lives in two integer arrays, prev and next. Slot zero marks the head, and slot one the tail. Run it. With room for three: put one, two, three, get one, then put four. Key 2 was least recent, so it's gone, and key 3 is still there. And on 300,000 random requests, it agreed with Java's own access-ordered LinkedHashMap every time.

Quick Check

Which Key LRU Evicts

Quick check. The same cache, with room for three. Put one, two, and three. Get two, then get one. Then put four. Which key is gone? Pause and predict. Three. The gets moved two, then one, to the front, so three slid to the back: the least recently used. It was put most recently of the original three, but LRU counts uses, not arrivals. FIFO would have evicted key one.

Measurement

Why Combine Two Structures

Why combine two structures? A list alone works, but finding a key means scanning it. In one test, a list-only cache slowed in step with its size: 339 nanoseconds a request at 100 entries, and 12,953 at 10,000. The combined cache stayed between 33 and 48. At a million entries, even the combined cache slowed to about 199 nanoseconds. The cache itself no longer fit in the processor's cache.

Locality in Practice

Arrays Versus Scattered Linked Nodes

Back to the two loops. Both sum four million numbers. The fast one walks an int array, whose elements sit side by side, so each cache line carries sixteen of them. The slow one follows a linked list whose nodes lie scattered through memory. Nearly every hop is a cache miss. In one test: the int array, 1.70 milliseconds. An ArrayList of Integers, 9.18. A LinkedList built in order, 31.61. And the shuffled nodes, 692.66. All four are order n. Locality is the difference.

Trade-Offs

Where Linked Lists Still Win

Linked lists still win in one place: inserting where they already hold the position. In one test of 100,000 inserts, adding at the front took 4.7 milliseconds with a LinkedList, against 396.5 for an ArrayList. But inserting in the middle took the LinkedList 9,389.7. Reaching the middle means thousands of hops, each a likely miss. So start with an array-based structure. Choose a linked one when something hands you the node directly, as the hash map does in the LRU cache.

Key Takeaways

Caching and Locality in Brief

To sum up. Memory comes in layers, and the small fast ones work because of temporal and spatial locality. The average time is h times the hit time, plus one minus h, times the miss time. LRU usually beats FIFO, but a loop one item bigger than the cache defeats it. An LRU cache pairs a hash map with a doubly linked list. And arrays beat linked lists through locality.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Why Frequently Used Data Lives in Faster, Smaller Memory

What is locality of reference?
Locality of reference is the tendency of programs to reuse recent data and nearby addresses. Temporal locality means a value used now will probably be used again soon, like a loop counter. Spatial locality means an address's neighbors usually come next; hardware moves data in cache lines, typically 64 bytes, so one read brings its neighbors too. That is why summing a large grid row by row beats column by column.
How do you calculate average memory access time from a hit ratio?
Average time per request equals h times the hit time plus (1 - h) times the miss time, where h is the hit ratio. With a 2-nanosecond hit and a 100-nanosecond miss, a 90 percent hit ratio averages 11.8 nanoseconds, while 99 percent averages about 3.0. Because misses are so much slower, even a small share of misses can take most of the total time.
How do you implement an LRU cache?
An LRU cache pairs a hash map with a doubly linked list. The map finds each key's list entry in constant time, and the list keeps entries in order of recent use, most recent at the front. A get moves its entry to the front, and a put on a full cache first evicts the entry at the back from both structures. In Java, an access-ordered LinkedHashMap can provide the same behavior.
Why is a linked list slower than an array when both are O(n)?
A linked list is usually slower because its nodes are scattered through memory, so nearly every hop can be a cache miss, while an array's elements sit side by side and each cache line carries several of them. In one test summing four million numbers, an int array took 1.70 milliseconds and a linked list with shuffled nodes took 692.66. Big O counts steps, not the cost of each memory access.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →