Lecture 24: Memory and Locality

CSE 373: Data Structures and Algorithms

1

Announcements

UW IT Course Evaluations - 5 EC points for everyone if at least 90% fill out

• currently at 70%
• open until Friday EOD…

P4 due today

• last day for office hours
• no credit for unused late days

Final Exam

• Open online, open note
• 5 extra credit points available
• will release Today at 2PM
• will be due Saturday at noon (NOT MIDNIGHT)
• NO LATE ASSIGNMENTS ACCEPTED

Friday’s lecture

• meme review
• TA Q&A panel
• come ask course staff your questions about courses, career, tech and beyond!

CSE 373 22 SP – CHAMPION

2

Review: Binary, Bits and Bytes

• binary
• A base-2 system of representing numbers using only 1s and 0s
• - vs decimal, base 10, which has 9 symbols
• bit
• The smallest unit of computer memory represented as a single binary value either 0 or 1

​

CSE 373 SP 18 - KASEY CHAMPION

3

• byte
• The most commonly referred to unit of memory, a grouping of 8 bits
• Can represent 265 different numbers (28)
• 1 Kilobyte = 1 thousand bytes (kb)
• 1 Megabyte = 1 million bytes (mb)
• 1 Gigabyte = 1 billion bytes (gb)

​

Thought experiment

• public int sum1(int n, int m, int[][] table) {
• int output = 0;
• for (int i = 0; i < n; i++) {
• for (int j = 0; j < m; j++) {
• output += table[i][j];
• }
• }
• return output;
• }

CSE 373 SP 18 - KASEY CHAMPION

4

• public int sum2(int n, int m, int[][] table) {
• int output = 0;
• for (int i = 0; i < n; i++) {
• for (int j = 0; j < m; j++) {
• output += table[j][i];
• }
• }
• return output;
• }

What do these two methods do?

What is the big-Θ

Θ(n*m)

​

Check in question: tinyurl.com/Summer373L24

Incorrect Assumptions

• Accessing memory is a quick and constant-time operation

​

• Sometimes accessing memory is cheaper and easier than at other times
• Sometimes accessing memory is very slow

​

​

CSE 373 SP 18 - KASEY CHAMPION

5

Lies!

RAM (Random-Access Memory)

• - RAM is where data gets stored for the programs you run. Think of it as the main memory storage location for your programs.

​

- RAM goes by a ton of different names: memory, main memory, RAM are all names for this same thing.

CSE 373 SP 19 - KASEY CHAMPION

6

RAM can be represented as a huge array

CSE 373 SP 19 - KASEY CHAMPION

7

=

This is a main takeaway

If you’re interested in deeper than this : https://www.youtube.com/watch?v=fpnE6UAfbtU or take some EE classes?

RAM:

• addresses, storing stuff at specific locations
• random access

Arrays

• indices, storing stuff at specific locations
• random access

A rough view of arrays and linked lists

CSE 373 SP 19 - KASEY CHAMPION

8

int[] array = new int[3];

array[0] = 3;

array[1] = 7;

array[2] = 3;

Node front = new Node(3);

front.next = new Node(7);

front.next.next = new Node(3);

3

7

3

3

7

3

(drawing singly linked list instead of doubly because drawings are hard / the two are similar)

Memory Architecture

CSE 373 SP 18 - KASEY CHAMPION

9

CPU Register

L1 Cache

L2 Cache

RAM

Disk

Memory Architecture

• Takeaways:
• - the more memory a layer can store, the slower it is (generally)

- accessing the disk is very slow

​

Computer Design Decisions

• Physics
• Speed of light
• Physical closeness to CPU
• Cost
• “good enough” to achieve speed
• Balance between speed and space

CSE 373 SP 18 - KASEY CHAMPION

10

Locality

• How does the OS minimize disk accesses?

​

• Spatial Locality
• Computers try to partition memory you are likely to use close by
• - Arrays
• - Fields

​

• Temporal Locality
• Computers assume the memory you have just accessed you will likely access again in the near future

CSE 373 SP 18 - KASEY CHAMPION

11

Leveraging Spatial Locality

• When looking up address in “slow layer”
• - bring in more than you need based on what’s near by
• - cost of bringing 1 byte vs several bytes is the same
• - Data Carpool!

CSE 373 SP 18 - KASEY CHAMPION

12

How memory is used and moves around

CSE 373 SP 19 - KASEY CHAMPION

13

CSE 373 SP 19 - KASEY CHAMPION

14

CSE 373 SP 19 - KASEY CHAMPION

15

CSE 373 SP 19 - KASEY CHAMPION

16

CSE 373 SP 19 - KASEY CHAMPION

17

CSE 373 SP 19 - KASEY CHAMPION

18

CSE 373 SP 19 - KASEY CHAMPION

19

CSE 373 SP 19 - KASEY CHAMPION

20

CSE 373 SP 19 - KASEY CHAMPION

21

CSE 373 SP 19 - KASEY CHAMPION

22

Solution to Mercy’s traveling problem

​

​

• If we know Mercy is going to keep eating tuna . . . Why not buy a bunch during a single trip and save them all somewhere closer than the store?

​

• Let’s get Mercy a refrigerator!

CSE 373 SP 19 - KASEY CHAMPION

23

CSE 373 SP 19 - KASEY CHAMPION

24

CSE 373 SP 19 - KASEY CHAMPION

25

CSE 373 SP 19 - KASEY CHAMPION

26

CSE 373 SP 19 - KASEY CHAMPION

27

RAM

CPU

CPU – kind of like the home / brain of your computer. Pretty much all computation is done here and data needs to move here to do anything significant with it (math, if checks, normal statement execution).

Data travels between RAM and the CPU, but it’s slow

Before

CSE 373 SP 19 - KASEY CHAMPION

28

RAM

CPU

Cache!

Bring a bunch of data back when you go all the way to RAM

Bring a bunch of food back when you go all the way to the store

After

Cache

• Rough definition: a place to store some memory that’s smaller and closer to the CPU compared to RAM. Because caches are closer to the CPU (where your data generally needs to go to be computed / modified / acted on) getting data from cache to CPU is a lot quicker than from RAM to CPU. This means we love when the data we want to access is conveniently in the cache.

​

• Generally we always store some data here in hopes that it will be used in the future and that we save ourselves the distance / time it takes to go to RAM.

​

• Analogy from earlier: The refrigerator (a cache) in your house to store food closer to you than the store. Walking to your fridge is much quicker than walking to the store!

​

CSE 373 SP 19 - KASEY CHAMPION

29

CSE 373 SP 19 - KASEY CHAMPION

30

RAM

CPU

Cache!

Bring a bunch of data back when you go all the way to RAM

Bring a bunch of food back when you go all the way to the store

After

This is a big idea!

How is a bunch of memory taken from RAM?

CSE 373 SP 19 - KASEY CHAMPION

31

• Imagine you want to retrieve the 1 at index 4 in RAM
• Your computer is smart enough to know to grab some of the surrounding data because computer designers think that it’s reasonably likely you’ll want to access that data too.
• (You don’t have to do anything in your code for this to happen – it happens automatically every time you access data!)
• To answer the title question, technically the term / units of transfer is in terms of ‘blocks’.

This is a big idea (continued)!

How is a bunch of memory taken from RAM?�(continued)

CSE 373 SP 19 - KASEY CHAMPION

32

cache

original data (the 1) we wanted to look up gets passed back to the cpu

CPU

all the data from the block gets brought to the cache

How does this pattern of memory grabbing affect our programs?

• - This should have a major impact on programming with arrays. Say we access an index of an array that is stored in RAM. Because we grab a whole bunch of contiguous memory even when we just access one index in RAM, we’ll probably be grabbing other nearby parts of our array and storing that in our cache for quick access later.

​

Imagine that the below memory is just an entire array of length 13, with some data in it.

​

​

​

​

​

CSE 373 SP 19 - KASEY CHAMPION

33

Just by accessing one element we bring the nearby elements back with us to the cache. In this case, it’s almost all of the array!

Leveraging Temporal Locality

• When looking up address in “slow layer”
• Once we load something into RAM or cache, keep it around or a while
• - But these layers are smaller
• When do we “evict” memory to make room?

CSE 373 SP 18 - KASEY CHAMPION

34

Moving Memory

• Amount of memory moved from disk to RAM
• - Called a “block” or “page”
• ≈4kb
• Smallest unit of data on disk

​

• Amount of memory moved from RAM to Cache
• - called a “cache line”
• ≈64 bytes

​

• Operating System is the Memory Boss
• - controls page and cache line size
• - decides when to move data to cache or evict

CSE 373 SP 18 - KASEY CHAMPION

35

Thought Experiment

• public int sum1(int n, int m, int[][] table) {
• int output = 0;
• for (int i = 0; i < n; i++) {
• for (int j = 0; j < m; j++) {
• output += table[i][j];
• }
• }
• return output;
• }

CSE 373 SP 18 - KASEY CHAMPION

36

• public int sum2(int n, int m, int[][] table) {
• int output = 0;
• for (int i = 0; i < n; i++) {
• for (int j = 0; j < m; j++) {
• output += table[j][i];
• }
• }
• return output;
• }

Why does sum1 run so much faster than sum2?

sum1 takes advantage of spatial and temporal locality

Java and Memory

• What happens when you use the “new” keyword in Java?
• - Your program asks the Java Virtual Machine for more memory from the “heap”
• Pile of recently used memory
• - If necessary the JVM asks Operating System for more memory
• Hardware can only allocate in units of page
• If you want 100 bytes you get 4kb
• Each page is contiguous

​

CSE 373 SP 18 - KASEY CHAMPION

37

What happens when you create a new array?

• Program asks JVM for one long, contiguous chunk of memory

What happens when you create a new object?

• Program asks the JVM for any random place in memory

What happens when you read an array index?

• Program asks JVM for the address, JVM hands off to OS
• OS checks the L1 caches, the L2 caches then RAM then disk to find it
• If data is found, OS loads it into caches to speed up future lookups

What happens when we open and read data from a file?

• Files are always stored on disk, must make a disk access

Array v Linked List

• Is iterating over an ArrayList faster than iterating over a LinkedList?

​

• Answer:
• LinkedList nodes can be stored in memory, which means the don’t have spatial locality. The ArrayList is more likely to be stored in contiguous regions of memory, so it should be quicker to access based on how the OS will load the data into our different memory layers.

CSE 373 SP 18 - KASEY CHAMPION

38