Locality Principle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// Example 1: Loop variables exhibit extreme temporal locality
// The variable 'i' is accessed on every iteration
void loop_temporal_locality() {
    int sum = 0;        // Accessed 1001 times (initialization + all iterations)
    for (int i = 0; i < 1000; i++) {  // 'i' accessed ~3000 times
        sum += i;       // sum accessed every iteration
    }
    // During execution:
    // - Instruction at 'for' statement: accessed 1000+ times
    // - 'i' variable: accessed ~3000 times (init, compare, increment)
    // - 'sum' variable: accessed ~1001 times
    // This creates EXTREME temporal locality for these locations
}
 
// Example 2: Function calls create temporal locality in instruction space
void frequently_called_function(int x) {
    // These instructions are accessed every time function is called
    static int call_count = 0;  // Strong temporal locality
    call_count++;
    // Function code exhibits temporal locality through repeated calls
}
 
void caller() {
    for (int i = 0; i < 10000; i++) {
        frequently_called_function(i);  // Code of this function accessed 10000 times
    }
}
 
// Example 3: Working with a small active set of variables
void matrix_multiply(int n, double *A, double *B, double *C) {
    // 'n' is accessed in every loop iteration (temporal locality)
    // Loop indices i, j, k have extreme temporal locality
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double sum = 0.0;  // sum accessed n times for each (i,j) pair
            for (int k = 0; k < n; k++) {
                sum += A[i*n + k] * B[k*n + j];
            }
            C[i*n + j] = sum;
        }
    }
    // Variables n, i, j, k, sum have MUCH stronger temporal locality
    // than the matrix elements themselves
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// Example 1: Excellent spatial locality - sequential access
void sum_array_good(int *arr, int n) {
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];  // Accesses arr[0], arr[1], arr[2], ...
    }                   // Each access is 4 bytes from the previous
    // Result: Each cache line (64 bytes) serves 16 consecutive accesses
    // Page (4KB) serves 1024 consecutive accesses
}
 
// Example 2: Terrible spatial locality - strided access
void sum_array_bad(int *arr, int n, int stride) {
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i * stride];  // Accesses arr[0], arr[stride], arr[2*stride], ...
    }
    // If stride = 1024, each access is 4KB apart
    // Each access potentially hits a different cache line AND different page
    // Result: Catastrophic cache and TLB miss rates
}
 
// Example 3: Matrix traversal - row vs column order
#define N 1000
double matrix[N][N];  // Row-major storage in C
 
// GOOD: Row-major access matches storage layout
double sum_row_major() {
    double sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += matrix[i][j];  // Consecutive memory access
        }
    }
    return sum;  // ~1 million accesses, ~1000 page accesses if 4KB pages
}
 
// BAD: Column-major access fights storage layout
double sum_column_major() {
    double sum = 0;
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            sum += matrix[i][j];  // Stride of N elements = 8000 bytes
        }
    }
    return sum;  // ~1 million accesses, potentially 1 million page accesses!
}
 
// Example 4: Structure layout affects spatial locality
struct BadLayout {
    char flags;           // 1 byte
    double values[1000];  // 8000 bytes
    char more_flags;      // 1 byte
};
// If you iterate over array of BadLayouts accessing only flags,
// you jump 8002 bytes between each access - terrible spatial locality
 
struct GoodLayout {
    char flags;
    char more_flags;
    // padding to alignment
    double values[1000];
};
// If struct array designed for access pattern, spatial locality improves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

# Conceptual implementation of locality metrics
 
class LocalityAnalyzer:
    """Analyze memory access trace for locality characteristics."""
    
    def __init__(self, page_size=4096):
        self.page_size = page_size
        self.trace = []  # List of (timestamp, address)
        
    def record_access(self, timestamp, address):
        """Record a memory access."""
        self.trace.append((timestamp, address))
    
    def compute_working_set(self, window_size):
        """
        Compute working set size over time with given window.
        Returns list of (time, working_set_size) pairs.
        
        This directly implements Denning's working set definition:
        W(t, Δ) = {pages accessed in interval [t-Δ, t]}
        """
        results = []
        for i, (t, addr) in enumerate(self.trace):
            # Find all accesses in window [t - window_size, t]
            window_start = t - window_size
            pages_in_window = set()
            
            for j in range(i, -1, -1):
                access_time, access_addr = self.trace[j]
                if access_time < window_start:
                    break
                page = access_addr // self.page_size
                pages_in_window.add(page)
            
            results.append((t, len(pages_in_window)))
        
        return results
    
    def compute_reuse_distance(self):
        """
        Compute reuse distance distribution.
        Reuse distance = number of distinct addresses accessed since last use.
        
        Lower reuse distances indicate stronger temporal locality.
        """
        last_access = {}  # address -> trace position
        distinct_since = {}  # address -> set of addresses since last access
        reuse_distances = []
        
        access_stack = []  # Stack to track unique accesses
        
        for i, (t, addr) in enumerate(self.trace):
            page = addr // self.page_size
            
            if page in last_access:
                # Find how many distinct pages accessed since last use
                # This is the reuse distance (LRU stack depth)
                if page in access_stack:
                    distance = access_stack.index(page)
                    reuse_distances.append(distance)
                    access_stack.remove(page)
            else:
                reuse_distances.append(float('inf'))  # First access
            
            access_stack.insert(0, page)  # Move to top of stack
            last_access[page] = i
        
        return reuse_distances
    
    def compute_stride_distribution(self):
        """
        Compute distribution of strides (distances between consecutive accesses).
        
        Concentration near zero indicates strong spatial locality.
        """
        strides = []
        for i in range(1, len(self.trace)):
            prev_addr = self.trace[i-1][1]
            curr_addr = self.trace[i][1]
            stride = abs(curr_addr - prev_addr)
            strides.append(stride)
        
        return strides
    
    def summarize_locality(self):
        """Generate locality summary statistics."""
        strides = self.compute_stride_distribution()
        reuse = self.compute_reuse_distance()
        
        # Spatial locality: fraction of strides within one cache line
        cache_line = 64
        spatial_score = sum(1 for s in strides if s < cache_line) / len(strides)
        
        # Temporal locality: fraction of reuses within small distance
        finite_reuse = [r for r in reuse if r != float('inf')]
        if finite_reuse:
            temporal_score = sum(1 for r in finite_reuse if r < 100) / len(finite_reuse)
        else:
            temporal_score = 0
        
        return {
            'spatial_locality_score': spatial_score,  # 0-1, higher = better
            'temporal_locality_score': temporal_score,  # 0-1, higher = better
            'average_stride': sum(strides) / len(strides),
            'median_reuse_distance': sorted(finite_reuse)[len(finite_reuse)//2] if finite_reuse else None,
            'unique_pages': len(set(addr // self.page_size for _, addr in self.trace))
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

# Demonstration: Locality strength determines working set effectiveness
 
import random
from collections import defaultdict
 
class WorkingSetSimulator:
    """
    Simulate working set model effectiveness under different locality conditions.
    """
    
    def __init__(self, num_pages, memory_frames, window_delta):
        self.num_pages = num_pages
        self.memory_frames = memory_frames
        self.window_delta = window_delta
        self.access_history = []  # Circular buffer of recent page accesses
        self.resident_pages = set()
        self.page_faults = 0
        self.total_accesses = 0
        
    def generate_high_locality_trace(self, length, hot_pages=10):
        """
        Generate trace with strong temporal locality.
        Most accesses go to a small set of 'hot' pages.
        """
        hot_set = list(range(hot_pages))
        trace = []
        for _ in range(length):
            if random.random() < 0.9:  # 90% accesses to hot pages
                trace.append(random.choice(hot_set))
            else:  # 10% accesses to random pages
                trace.append(random.randint(0, self.num_pages - 1))
        return trace
    
    def generate_low_locality_trace(self, length):
        """
        Generate trace with poor temporal locality.
        Accesses uniformly distributed across all pages.
        """
        return [random.randint(0, self.num_pages - 1) for _ in range(length)]
    
    def compute_working_set(self, current_time):
        """Compute working set from recent history."""
        working_set = set()
        window_start = max(0, current_time - self.window_delta)
        
        for t in range(window_start, current_time + 1):
            if t < len(self.access_history):
                working_set.add(self.access_history[t])
        
        return working_set
    
    def access_page(self, page, current_time):
        """Process a page access using working set policy."""
        self.total_accesses += 1
        self.access_history.append(page)
        
        # Check if page is resident
        if page not in self.resident_pages:
            self.page_faults += 1
            
            # Compute current working set
            ws = self.compute_working_set(current_time)
            
            # Make room if needed
            if len(self.resident_pages) >= self.memory_frames:
                # Evict pages not in working set
                pages_to_evict = self.resident_pages - ws
                if pages_to_evict:
                    # Remove one page not in working set
                    self.resident_pages.remove(pages_to_evict.pop())
                else:
                    # All pages are in working set - need more memory or evict LRU
                    # (In true working set model, this indicates insufficient memory)
                    oldest = min(self.resident_pages, 
                                key=lambda p: self.access_history[::-1].index(p) 
                                if p in self.access_history else float('inf'))
                    self.resident_pages.remove(oldest)
            
            self.resident_pages.add(page)
    
    def simulate(self, trace):
        """Run simulation on given trace."""
        for t, page in enumerate(trace):
            self.access_page(page, t)
        
        return {
            'page_faults': self.page_faults,
            'total_accesses': self.total_accesses,
            'fault_rate': self.page_faults / self.total_accesses,
            'final_working_set_size': len(self.compute_working_set(len(trace) - 1))
        }
 
# Compare high vs low locality workloads
def compare_locality_impact():
    """
    Demonstrate that working set model works well BECAUSE of locality.
    """
    print("Comparing Working Set Effectiveness vs Locality Strength")
    print("=" * 60)
    print(f"Pages: 1000, Memory Frames: 50, Window: 100 accesses")
    print(f"Trace length: 10000 accesses")
    print()
    
    # High locality workload
    sim_high = WorkingSetSimulator(num_pages=1000, memory_frames=50, window_delta=100)
    trace_high = sim_high.generate_high_locality_trace(10000, hot_pages=20)
    result_high = sim_high.simulate(trace_high)
    
    # Low locality workload
    sim_low = WorkingSetSimulator(num_pages=1000, memory_frames=50, window_delta=100)
    trace_low = sim_low.generate_low_locality_trace(10000)
    result_low = sim_low.simulate(trace_low)
    
    print("HIGH LOCALITY (90% to 20 hot pages):")
    print(f"  Page faults: {result_high['page_faults']}")
    print(f"  Fault rate: {result_high['fault_rate']:.4f}")
    print()
    
    print("LOW LOCALITY (uniform random):")
    print(f"  Page faults: {result_low['page_faults']}")
    print(f"  Fault rate: {result_low['fault_rate']:.4f}")
    print()
    
    print("CONCLUSION:")
    print(f"  High locality fault rate is {result_low['fault_rate']/result_high['fault_rate']:.1f}x better")
    print(f"  Working set model effectiveness DEPENDS on locality presence!")
 
# Output example:
# HIGH LOCALITY: Fault rate ~0.02 (2%)
# LOW LOCALITY: Fault rate ~0.95 (95%)  
# Working set works because locality exists!