CS 208 s21 — Learning Block #17

Table of Contents

1 Exercise

Which of the following are examples of spatial or temporal locality?1

  • the loop variable in a for loop
  • accessing elements of an array in order
  • printing how long a program took to run
  • reusing a temporary array
  • combining multiple related variables into an object or struct
  • passing function arguments as pointers

2 Practice

CSPP practice problem 6.8 (p. 609)2 

#define N 1000

typedef struct {
    int vel[3];
    int acc[3];
} point;

point p[N];

The three functions below perform the same operation with varying degrees of spatial locality. Rank the functions with respect to the spatial local enjoyed by each. Explain how you arrived at your ranking. 

void clear1(point *p, int n) {
    int i, j;

    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            p[i].vel[j] = 0;
        }
        for (j = 0; j < 3; j++) {
            p[i].acc[j] = 0;
        }
    }
}

void clear2(point *p, int n) {
    int i, j;

    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            p[i].vel[j] = 0;
            p[i].acc[j] = 0;
        }
    }
}

void clear3(point *p, int n) {
    int i, j;

    for (j = 0; j < 3; j++) {
        for (i = 0; i < n; i++) {
            p[i].vel[j] = 0;
        }
        for (i = 0; i < n; i++) {
            p[i].acc[j] = 0;
        }
    }
}

3 Work on Lab 3

Footnotes:

1
  • the loop variable in a for loop: TEMPORAL (accessing the same data each loop iteration)
  • accessing elements of an array in order: SPATIAL (accessing adjacent memory locations)
  • printing how long a program took to run: NEITHER (unrelated to data access)
  • reusing a temporary array: TEMPORAL (memory already in cache)
  • combining multiple related variables into an object or struct: SPATIAL (variables are made to be adjacent in memory)
  • passing function arguments as pointers: NEITHER (may avoid unnecessary copying of memory, but not directly related to locality)
2

The key to solving this problem is to visualize how the array is laid out in memory and then analyze the reference patterns. Function clear1 accesses the array using a stride-1 reference pattern and thus clearly has the best spatial locality. Function clear2 scans each of the N structs in order, which is good, but within each struct it hops around in a non-stride-1 pattern at the following offsets from the beginning of the struct: 0, 12, 4, 16, 8, 20. So clear2 has worse spatial locality than clear1. Function clear3 not only hops around within each struct, but also hops from struct to struct. So clear3 exhibits worse spatial locality than clear2 and clear1.