Data locality

Data locality#

One of the questions in Activity 53 was about the trade-offs of different data structures, e.g., array vs struct.

How far data is placed from each other can affect performance.

Array of structs vs struct of arrays#

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1'000'000

// Array of Structs (AoS)
typedef struct {
  int x;
  int y;
  int z;
} PointAoS;

PointAoS points_aos[N];

// Struct of Arrays (SoA)
typedef struct {
  int x[N];
  int y[N];
  int z[N];
} PointSoA;

PointSoA points_soa;

void initAoS() {
  for (int i = 0; i < N; i++) {
    points_aos[i].x = rand();
    points_aos[i].y = rand();
    points_aos[i].z = rand();
  }
}
void initSoA() {
  for (int i = 0; i < N; i++) {
    points_soa.x[i] = rand();
    points_soa.y[i] = rand();
    points_soa.z[i] = rand();
  }
}

int sum_x_aos() {
  int sum = 0;
  for (int i = 0; i < N; i++) {
    sum += points_aos[i].x; // x's are more far from each other
  }
  return sum;
}

int sum_x_soa() {
  int sum = 0;
  for (int i = 0; i < N; i++) {
    sum += points_soa.x[i]; // x's are more nearby
  }
  return sum;
}

int main() {
  srand(time(NULL));

  initAoS();
  auto start = clock();
  int sum_aos = sum_x_aos();
  auto end = clock();
  printf("AoS sum: %d, time: %f ms\n", sum_aos,
         ((double)(end - start) / CLOCKS_PER_SEC) * 1000);

  initSoA();
  start = clock();
  int sumSoA = sum_x_soa();
  end = clock();
  printf("SoA sum: %d, time: %f ms\n", sumSoA,
         ((double)(end - start) / CLOCKS_PER_SEC) * 1000);
}

Output on my computer:

AoS sum: -893370230, time: 1.249000 ms
SoA sum: 863692085, time: 0.674000 ms

Output on the cloud server:

AoS sum: -386893557, time: 2.520000 ms
SoA sum: 1294359959, time: 2.459000 ms
https://upload.wikimedia.org/wikipedia/commons/e/e8/Shared_private.png

Fig. 24 When data is read, it is stored on many layers of cache, which become smaller in size towards the processor cores.
CC BY-SA 4.0. By Avadlam3. Source: Wikimedia Commons#

Struct of arrays achieve a better performance, because x’s are near each other.

Appendix#

This is related to how memory is organized in processors.

cache

a hardware of software component that stores data so that future requests for that data can be served faster

Contents