Data layout basics

Data layout refers to the memory representation of the variables that belong to a data structure or an object. It describes the way the variables are stored in memory.

For example, assume you are creating a 3D simulation program or a game where you want to model the movement of thousands of particles and you have the following data structures for the 3D objects:


            // Helper struct of a 3D vector with x, y, z, coordinates
typedef struct vec3 {
  float x, y, z;
} vec3_t;

// The object struct
typedef struct object {
  uint32_t id;
  float weight;
  vec3_t position;
  vec3_t velocity;
  void *model_data;
} object_t;

These are example data structures. Actual simulations have more information per object. Extra information may include additional identifiers, volume information, a pointer to a 3D model for display purposes, boundary information, or even representations of quantum wavefunctions. The details are beyond the scope of this Learning Path, but most software uses the same principle, regardless of whether it’s a game or a molecular dynamics simulation.

The core of the program is the main for loop, which changes the positions and velocities of the objects in tiny amounts and updates them multiple times per second, thereby giving the notion of movement.

In this Learning Path, you will compile and run loops and measure performance.

Use a text editor to copy the code below and save it in a file named simulation1.c


            #include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <sys/time.h>
#include <unistd.h>

// Helper struct of a 3D vector with x, y, z, coordinates
typedef struct vec3 {
  float x, y, z;
} vec3_t;

// The object struct
typedef struct object {
  uint32_t id;
  float weight;
  vec3_t position;
  vec3_t velocity;
  void *model_data;
} object_t;

// Helper function to return a random float number from 0.0f to a.
float randf(float a) {
  return ((float)rand()/(float)(RAND_MAX)) * a;

#define N           100000 // number of particles
#define SECONDS     100    // duration in seconds
#define STEPSPERSEC 1000   // steps per second or time resolution

void init_objects(object_t *objects) {
  // Give initial speeds and positions
  for (size_t i=0; i < N; i++) {
    objects[i].id = i;
    objects[i].weight = randf(2.0f);
    // initial positions in box [-10, 10], velocity in [-1, 1]
    objects[i].position.x = randf(20.0) - 10.0f;
    objects[i].position.y = randf(20.0) - 10.0f;
    objects[i].position.z = randf(20.0) - 10.0f;
    objects[i].velocity.x = randf(2.0) - 1.0f;
    objects[i].velocity.y = randf(2.0) - 1.0f;
    objects[i].velocity.z = randf(2.0) - 1.0f;


void simulate_objects(object_t *objects, float duration, float step) {

  float current_time = 0;
  while (current_time < duration) {
    // Move the object in steps
    for (size_t i=0; i < N; i++) {
      objects[i].position.x += objects[i].velocity.x * step;
      objects[i].position.y += objects[i].velocity.y * step;
      objects[i].position.z += objects[i].velocity.z * step;
    current_time += step;

int main() {
  object_t objects[N];


  const float duration = SECONDS;
  const float step = 1.0f/STEPSPERSEC;
  struct timeval th_time_start, th_time_end;

  gettimeofday(&th_time_start, NULL);
  simulate_objects(objects, duration, step);
  gettimeofday(&th_time_end, NULL);

  double elapsed;
  elapsed = (th_time_end.tv_sec - th_time_start.tv_sec); // sec
  elapsed += (th_time_end.tv_usec - th_time_start.tv_usec) / 1000000.0; // us to sec

  printf("elapsed time: %f\n", elapsed);

Compile the code with GCC:


            gcc -O3 simulation1.c -o simulation1

Unless stated, the examples are compiled with gcc version 12. Your results may vary based on your exact compiler version.

Run the program:



The elapsed time is printed. Depending on your hardware, the printed value may may be different.


        elapsed time: 14.605558


This is not a realistic simulation as there is no collision detection, no bounds checking, no gravity or other forces between the particles. But once you have finished reading it, you will be able to start learning how to change the data layout to help the compiler perform auto vectorization and increase the performance of a loop.

Refer to Learn about Autovectorization for a good introduction to autovectorization.

Use objdump to view the assembly code for the program, look for thesimulate_objects()


            objdump -S simulation1 | less

The disassembly for simulate_objects() is:


        0000000000000b54 <simulate_objects>:
 b54:   1e202018        fcmpe   s0, #0.0
 b58:   1e204006        fmov    s6, s0
 b5c:   1e204023        fmov    s3, s1
 b60:   0e040424        dup     v4.2s, v1.s[0]
 b64:   5400004c    b6c <simulate_objects+0x18>
 b68:   d65f03c0        ret
 b6c:   914f4001        add     x1, x0, #0x3d0, lsl #12
 b70:   0f000405        movi    v5.2s, #0x0
 b74:   91002002        add     x2, x0, #0x8
 b78:   91242021        add     x1, x1, #0x908
 b7c:   aa0203e0        mov     x0, x2
 b80:   bd401402        ldr     s2, [x0, #20]
 b84:   9100a000        add     x0, x0, #0x28
 b88:   bc5e0000        ldur    s0, [x0, #-32]
 b8c:   fc5d8001        ldur    d1, [x0, #-40]
 b90:   1f030040        fmadd   s0, s2, s3, s0
 b94:   fc5e4002        ldur    d2, [x0, #-28]
 b98:   0e22cc81        fmla    v1.2s, v4.2s, v2.2s
 b9c:   fc1d8001        stur    d1, [x0, #-40]
 ba0:   bc1e0000        stur    s0, [x0, #-32]
 ba4:   eb00003f        cmp     x1, x0
 ba8:   54fffec1    b80 <simulate_objects+0x2c>  // b.any
 bac:   1e2328a5        fadd    s5, s5, s3
 bb0:   1e2520d0        fcmpe   s6, s5
 bb4:   54fffe4c    b7c <simulate_objects+0x28>
 bb8:   d65f03c0        ret


You may have spotted a few SIMD instructions (especially fmla v1.2s, v4.2s, v2.2s). This is better than no SIMD instructions, but it looks like the performance is not optimal.

Continue to the next section to learn how to optimize the code.