1 of 51

Lecture 24: Memory and Locality

CSE 373: Data Structures and Algorithms

1

2 of 51

Warm Up

CSE 373 21 SP – CHAMPION

2

Worst case runtime?

Best case runtime?

In-practice runtime?

Stable?

In-place?

No

Yes

Worst case runtime?

Best case runtime?

In-practice runtime?

Stable?

In-place?

No

Worst case runtime?

Best case runtime?

In-practice runtime?

Stable?

In-place?

Yes

No

Merge Sort

Quick Sort

first element as pivot

Quick Sort

in-place

median of values as pivot

3 of 51

Announcements

Things are tough all over the world right now

Everyone gets +2 late days (thanks TAs!)
Extending the late turn in from 3 days after due date to 5 days after due date

P4 Spec Quiz Due today!

For extra credit
No late submissions accepted
P4 due Wednesday June 2^nd

Office Hours slight change

Tas have been instructed to help with ONE step of debugging: identify bug, reproduce bug or resolve bug
Goal is to move through OH queue faster so you have more questions answered in smaller chunks
OH Form will be added to OH page and bot

Tech Career Resources

No BS CS Career Talk recording: https://courses.cs.washington.edu/courses/cse142/21sp/explore.html
Section 9 Thursday 5/27 Interview Prep

CSE 373 21 SP – CHAMPION

3

4 of 51

Quick Sort (v1)

quickSort(list) {

if (list.length == 1):

return list

else:

pivot = choosePivot(list)

smallerHalf = quickSort(getSmaller(pivot, list))

largerHalf = quickSort(getBigger(pivot, list))

return smallerHalf + pivot + largerHalf

}

Worst case runtime?

Best case runtime?

In-practice runtime?

Stable?

In-place?

No

Can be done!

0	1	2	3
2	1	7	6

0	1
7	6

0
1

0
2

PIVOT

0
6

0
7

0	1	2	3
1	2	6	7

0	1
6	7

Worst case: Pivot only chops off one value

Best case: Pivot divides each array in half

5 of 51

Can we do better?

How to avoid hitting the worst case?

It all comes down to the pivot. If the pivot divides each array in half, we get better behavior

Here are four options for finding a pivot. What are the tradeoffs?

Just take the first element
Take the median of the full array
Take the median of the first, last, and middle element
Pick a random element

6 of 51

Strategies for Choosing a Pivot

Most commonly used

7 of 51

Quick Sort (v2: In-Place)

0	1	2	3	4	5	6	7	8	9
8	1	4	9	0	3	5	2	7	6

0	1	2	3	4	5	6	7	8	9
6	1	4	9	0	3	5	2	7	8

Low

X < 6

High

X >= 6

0	1	2	3	4	5	6	7	8	9
6	1	4	2	0	3	5	9	7	8

Low

X < 6

High

X >= 6

0	1	2	3	4	5	6	7	8	9
5	1	4	2	0	3	6	9	7	8

PIVOT?

PIVOT!

Select a pivot

Move pivot out of the way

Bring low and high pointers together, swapping elements if needed

Meeting point is where pivot belongs; swap in. Now recurse on smaller portions of same array!

Divide

8 of 51

Quick Sort (v2: In-Place)

quickSort(list) {

if (list.length == 1):

return list

else:

pivot = choosePivot(list)

smallerPart, largerPart = partition(pivot, list)

smallerPart = quickSort(smallerPart)

largerPart = quickSort(largerPart)

return smallerPart + pivot + largerPart

}

Worst case runtime?

Best case runtime?

In-practice runtime?

Stable?

In-place?

No

Yes

0	1	2	3	4	5
0	3	6	9	7	8

choosePivot:

- Use one of the pivot selection strategies

partition:

For in-place Quick Sort, series of swaps to build both partitions at once
Tricky part: moving pivot out of the way and moving it back!
Similar to Merge Sort divide step: two pointers, only move smaller one

9 of 51

Can we do better?

We’d really like to avoid hitting the worst case.

Key to getting a good running time, is always cutting the array (about) in half.

How do we choose a good pivot?

Here are four options for finding a pivot. What are the tradeoffs?

Just take the first element
Take the median of the first, last, and middle element
Take the median of the full array
Pick a random element as a pivot

CSE 373 19 SU - ROBBIE WEBER

9

10 of 51

Pivots

CSE 373 19 SU - ROBBIE WEBER

10

Median of three is a common choice in practice

11 of 51

Sorting: Summary

	Best-Case	Worst-Case	Space	Stable
Selection Sort	Θ(n²)	Θ(n²)	Θ(1)	No
Insertion Sort	Θ(n)	Θ(n²)	Θ(1)	Yes
Heap Sort	Θ(n)	Θ(nlogn)	Θ(n)	No
In-Place Heap Sort	Θ(n)	Θ(nlogn)	Θ(1)	No
Merge Sort	Θ(nlogn)	Θ(nlogn)	Θ(nlogn) Θ(n)* optimized	Yes
Quick Sort	Θ(nlogn)	Θ(n²)	Θ(n)	No
In-place Quick Sort	Θ(nlogn)	Θ(n²)	Θ(1)	No

What does Java do?

Actually uses a combination of 3 different sorts:

If objects: use Merge Sort* (stable!)
If primitives: use Dual Pivot Quick Sort
If “reasonably short” array of primitives: use Insertion Sort

Researchers say 48 elements

Key Takeaway: No single sorting algorithm is “the best”!

Different sorts have different properties in different situations
The “best sort” is one that is well-suited to your data

* They actually use Tim Sort, which is very similar to Merge Sort in theory, but has some minor details different

12 of 51

Insertion Sort

STRATEGY 1:

ITERATIVE IMPROVEMENT

STRATEGY 2:

IMPOSE STRUCTURE

STRATEGY 3:

DIVIDE AND CONQUER

Selection Sort

Heap Sort

Merge Sort

Quick Sort

WORST

BEST

STABLE

IN-PLACE

STABLE

WORST

BEST

WORST

BEST

WORST

BEST

WORST

BEST

Minimizes array writes, otherwise never preferred.

Simple, stable, low-overhead, great if already sorted.

Always good runtimes

Stable, very reliable! In-place variant is slower.

Fastest in practice (constant factors), bad worst case.

SPACE

13 of 51

Insertion Sort

STRATEGY 1:

ITERATIVE IMPROVEMENT

STRATEGY 2:

IMPOSE STRUCTURE

STRATEGY 3:

DIVIDE AND CONQUER

Selection Sort

Heap Sort

Merge Sort

Quick Sort

WORST

BEST

STABLE

IN-PLACE

STABLE

WORST

BEST

WORST

BEST

WORST

BEST

WORST

BEST

Minimizes array writes, otherwise never preferred.

Simple, stable, low-overhead, great if already sorted.

Always good runtimes

Stable, very reliable! In-place variant is slower.

Fastest in practice (constant factors), bad worst case.

SPACE

Can we do better than n log n?

For comparison sorts, NO. A proven lower bound!

Intuition: n elements to sort, no faster way to find “right place” than log n

However, niche sorts can do better in specific situations!

Many cool niche sorts beyond the scope of 373!

Radix Sort (Wikipedia, VisuAlgo) - Go digit-by-digit in integer data. Only 10 digits, so no need to compare!

Counting Sort (Wikipedia)

Bucket Sort (Wikipedia)

External Sorting Algorithms (Wikipedia) - For big data™

14 of 51

But Don’t Take it From Me…

Insertion Sort: https://www.youtube.com/watch?v=ROalU379l3U
Selection Sort: https://www.youtube.com/watch?v=Ns4TPTC8whw
Heap Sort: https://www.youtube.com/watch?v=Xw2D9aJRBY4
Merge Sort: https://www.youtube.com/watch?v=XaqR3G_NVoo
Quick Sort: https://www.youtube.com/watch?v=ywWBy6J5gz8

DANCE EDITION

Here are some excellent visualizations for the sorting algorithms we’ve talked about!

Comparing Sorting Algorithms

Different Types of Input Data: https://www.toptal.com/developers/sorting-algorithms
More Thorough Walkthrough: https://visualgo.net/en/sorting?slide=1

Comparing Sorting Algorithms

15 of 51

Memory & Locality!

CSE 373 20 SP – CHAMPION & CHUN

15

16 of 51

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

16

Decimal	Decimal Break Down	Binary	Binary Break Down
0		0
1		1
10		1010
12		1100
127		01111111

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)

17 of 51

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

17

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)

18 of 51

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

18

Lies!

19 of 51

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

19

20 of 51

RAM can be represented as a huge array

CSE 373 SP 19 - KASEY CHAMPION

20

=

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

It turns out that for computer scientists / programming, we don’t have to know about the circuits and electricity that makes this green blob computer chip works. Luckily for us RAM can be thought of as a very big array -- this is how we should thing about RAM in our programs for us to be able to take advantage of it / understand how our programs interact with it.

RAM can be thought of as an array for 2 reasons in particular

you think of RAM having spaces for you to store stuff, just like you would in an array … and it also has indices (but for memory its called addresses) that describe where in RAM / the array a particular piece of data is located

Also just because of this Random access thing – you might have heard this before but people sometimes describe arrays as random access because you can access any random index in an array equally to other indices / easily. It’s the same for RAM (the computer chip one) – all addresses are easily accessed as all the others

21 of 51

A rough view of arrays and linked lists

CSE 373 SP 19 - KASEY CHAMPION

21

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

7

3

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

22 of 51

Memory Architecture

CSE 373 SP 18 - KASEY CHAMPION

22

CPU Register

L1 Cache

L2 Cache

RAM

Disk

What is it?	Typical Size	Time
The brain of the computer!	32 bits	≈free
Extra memory to make accessing it faster	128KB	0.5 ns
Extra memory to make accessing it faster	2MB	7 ns
Working memory, what your programs need	8GB	100 ns
Large, longtime storage	1 TB	8,000,000 ns

23 of 51

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

23

24 of 51

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

24

25 of 51

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

25

26 of 51

How memory is used and moves around

CSE 373 SP 19 - KASEY CHAMPION

26

27 of 51

CSE 373 SP 19 - KASEY CHAMPION

27

28 of 51

CSE 373 SP 19 - KASEY CHAMPION

28

29 of 51

CSE 373 SP 19 - KASEY CHAMPION

29

30 of 51

CSE 373 SP 19 - KASEY CHAMPION

30

31 of 51

CSE 373 SP 19 - KASEY CHAMPION

31

32 of 51

CSE 373 SP 19 - KASEY CHAMPION

32

33 of 51

CSE 373 SP 19 - KASEY CHAMPION

33

34 of 51

CSE 373 SP 19 - KASEY CHAMPION

34

35 of 51

CSE 373 SP 19 - KASEY CHAMPION

35

36 of 51

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

36

37 of 51

CSE 373 SP 19 - KASEY CHAMPION

37

38 of 51

CSE 373 SP 19 - KASEY CHAMPION

38

39 of 51

CSE 373 SP 19 - KASEY CHAMPION

39

40 of 51

CSE 373 SP 19 - KASEY CHAMPION

40

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

41 of 51

CSE 373 SP 19 - KASEY CHAMPION

41

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

42 of 51

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

42

43 of 51

CSE 373 SP 19 - KASEY CHAMPION

43

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!

44 of 51

How is a bunch of memory taken from RAM?

CSE 373 SP 19 - KASEY CHAMPION

44

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)!

45 of 51

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

CSE 373 SP 19 - KASEY CHAMPION

45

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

46 of 51

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

46

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!

47 of 51

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

47

48 of 51

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

48

49 of 51

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

49

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

0	1	2	3	4

0	1	2
‘a’	‘b’	‘c’

0	1	2
‘d’	‘e’	‘f’

0	1	2
‘g’	‘h’	‘i’

0	1	2
‘j’	‘k’	‘l’

0	1	2
‘m’	‘n’	‘o’

50 of 51

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

50

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

51 of 51

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

51