particle_pool_benchmark.c

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

// -----------------------------------------------------------------------------
// Cross platform high resolution timer
// From https://gist.github.com/ForeverZer0/0a4f80fc02b96e19380ebb7a3debbee5

#include <stdint.h>
#include <stdbool.h>
#if defined(__linux)
	#define HAVE_POSIX_TIMER
	#include <time.h>
	#ifdef CLOCK_MONOTONIC
		#define CLOCKID CLOCK_MONOTONIC
	#else
		#define CLOCKID CLOCK_REALTIME
	#endif
#elif defined(__APPLE__)
	#define HAVE_MACH_TIMER
	#include <mach/mach_time.h>
#elif defined(_WIN32)
	#define WIN32_LEAN_AND_MEAN
	#include <windows.h>
#endif

static uint64_t ns() {
	static uint64_t is_init = 0;
#if defined(__APPLE__)
		static mach_timebase_info_data_t info;
		if (0 == is_init) {
			mach_timebase_info(&info);
			is_init = 1;
		}
		uint64_t now;
		now = mach_absolute_time();
		now *= info.numer;
		now /= info.denom;
		return now;
#elif defined(__linux)
		static struct timespec linux_rate;
		if (0 == is_init) {
			clock_getres(CLOCKID, &linux_rate);
			is_init = 1;
		}
		uint64_t now;
		struct timespec spec;
		clock_gettime(CLOCKID, &spec);
		now = spec.tv_sec * 1.0e9 + spec.tv_nsec;
		return now;
#elif defined(_WIN32)
		static LARGE_INTEGER win_frequency;
		if (0 == is_init) {
			QueryPerformanceFrequency(&win_frequency);
			is_init = 1;
		}
		LARGE_INTEGER now;
		QueryPerformanceCounter(&now);
		return (uint64_t) ((1e9 * now.QuadPart)	/ win_frequency.QuadPart);
#endif
}


typedef struct {
	float x, y, z;
} vec3_t;

#define vec3(X, Y, Z) ((vec3_t){.x = X, .y = Y, .z = Z})

vec3_t vec3_add(vec3_t a, vec3_t b) {
	return vec3(
		a.x + b.x,
		a.y + b.y,
		a.z + b.z
	);
}

vec3_t vec3_sub(vec3_t a, vec3_t b) {
	return vec3(
		a.x - b.x,
		a.y - b.y,
		a.z - b.z
	);
}

vec3_t vec3_mulf(vec3_t a, float f) {
	return vec3(
		a.x * f,
		a.y * f,
		a.z * f
	);
}

typedef struct {
	vec3_t position;
	vec3_t velocity;
	float time;
	bool active;
} particle_t;

#define PARTICLES_MAX 32768
particle_t particles[PARTICLES_MAX];

float rand_float(float min, float max) {
	return ((float)rand() / (float)RAND_MAX) * (max - min) + min;
}

void particle_init(particle_t *p) {
	p->position = vec3(0, 0, 0);
	p->velocity = vec3(rand_float(-1000, 1000), rand_float(0, 1000), rand_float(-1000, 1000));
	p->time = rand_float(0.5, 5.0);
}

void particle_update(particle_t *p) {
	float tick = 1.0/60.0;
	p->velocity.y += 8.0;
	p->velocity = vec3_sub(p->velocity, vec3_mulf(p->velocity, tick * 0.5)); // drag
	p->position = vec3_add(p->position, vec3_mulf(p->velocity, tick));
	p->time -= tick;
	if (p->time < 0) {
		p->active = false;
	}
}


// -----------------------------------------------------------------------------
// Implementation with two ptr arrays
particle_t *particles_2pa_free[PARTICLES_MAX];
particle_t *particles_2pa_active[PARTICLES_MAX];
int particles_2pa_free_len;
int particles_2pa_active_len;

void particles_2pa_init() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		particles_2pa_free[i] = &particles[PARTICLES_MAX - i -1];
	}
	particles_2pa_free_len = PARTICLES_MAX;
	particles_2pa_active_len = 0;
}

particle_t *particles_2pa_new() {
	if (particles_2pa_free_len == 0) {
		return NULL;
	}

	particle_t *p = particles_2pa_free[--particles_2pa_free_len];
	particles_2pa_active[particles_2pa_active_len++] = p;
	p->active = true;
	return p;
}

void particles_2pa_update() {
	for (int i = 0; i < particles_2pa_active_len; i++) {
		particle_t *p = particles_2pa_active[i];

		particle_update(p);

		if (p->active == false) {
			particles_2pa_active[i] = particles_2pa_active[--particles_2pa_active_len];
			particles_2pa_free[particles_2pa_free_len++] = p;
			i--;
		}
	}
}

// -----------------------------------------------------------------------------
// Implementation with one ptr array

int particles_pa_active_len;
particle_t *particles_pa[PARTICLES_MAX];

void particles_pa_init() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		particles_pa[i] = &particles[i];
	}
	particles_pa_active_len = 0;
}

particle_t *particles_pa_new() {
	if (particles_pa_active_len == PARTICLES_MAX) {
		return NULL;
	}

	particle_t *p = particles_pa[particles_pa_active_len++];
	p->active = true;
	return p;
}

void particles_pa_update() {
	for (int i = 0; i < particles_pa_active_len; i++) {
		particle_t *p = particles_pa[i];

		particle_update(p);

		if (p->active == false) {
			// Swap last and current
			particles_pa_active_len--;
			particles_pa[i] = particles_pa[particles_pa_active_len];
			particles_pa[particles_pa_active_len] = p;
			i--;
		}
	}
}

// -----------------------------------------------------------------------------
// Implementation with one index array

int particles_ia_active_len;
uint16_t particles_ia[PARTICLES_MAX];

void particles_ia_init() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		particles_ia[i] = i;
	}
	particles_ia_active_len = 0;
}

particle_t *particles_ia_new() {
	if (particles_ia_active_len == PARTICLES_MAX) {
		return NULL;
	}

	particle_t *p = &particles[particles_ia[particles_ia_active_len++]];
	p->active = true;
	return p;
}

void particles_ia_update() {
	for (int i = 0; i < particles_ia_active_len; i++) {
		uint16_t index = particles_ia[i];
		particle_t *p = &particles[index];

		particle_update(p);

		if (p->active == false) {
			// Swap last and current
			particles_ia_active_len--;
			particles_ia[i] = particles_ia[particles_ia_active_len];
			particles_ia[particles_ia_active_len] = index;
			i--;
		}
	}
}


// -----------------------------------------------------------------------------
// Implementation just with storage array, in-place move

int particles_move_active_len;

void particles_move_init() {
	particles_move_active_len = 0;
}

particle_t *particles_move_new() {
	if (particles_move_active_len == PARTICLES_MAX) {
		return NULL;
	}

	particle_t *p = &particles[particles_move_active_len++];
	p->active = true;
	return p;
}

void particles_move_update() {
	for (int i = 0; i < particles_move_active_len; i++) {
		particle_t *p = &particles[i];

		particle_update(p);

		if (p->active == false) {
			particles[i] = particles[--particles_move_active_len]; // invokes memcpy
			i--;
		}
	}
}


// -----------------------------------------------------------------------------
// Implementation just with storage array, linear scan

void particles_linear_init() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		particles[i].active = false;
	}
}

particle_t *particles_linear_new() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		if (particles[i].active == false) {
			particles[i].active = true;
			return &particles[i];
		}
	}
	return NULL;
}

void particles_linear_update() {
	for (int i = 0; i < PARTICLES_MAX; i++) {
		if (particles[i].active) {
			particle_update(&particles[i]);
		}
	}
}


// Run __VA_ARGS__ a number of times and measure the time taken
#define BENCHMARK_FN(NAME, WARMUP_RUNS, RUNS, ...) \
	do { \
		for (int benchmark_i = 0; benchmark_i < WARMUP_RUNS; benchmark_i++) { \
			__VA_ARGS__ \
		} \
		uint64_t time_start = ns(); \
		for (int benchmark_i = 0; benchmark_i < RUNS; benchmark_i++) { \
			__VA_ARGS__ \
		} \
		uint64_t total_time = ns() - time_start; \
		printf(NAME ": %8.2f ms\n", (double)total_time/1000000.0); \
	} while (0)

// The whole particle system, using the provided INIT, NEW and UPDATE functions
#define BENCHMARK_PARTICLES(NAME, SPAWN_CHANCE, INIT_FUNC, NEW_FUNC, UPDATE_FUNC) \
	srand(0xC0FFE); \
	INIT_FUNC(); \
	\
	BENCHMARK_FN(NAME, 1000, 100000, { \
		int new_chance = rand() % SPAWN_CHANCE; \
		if (new_chance == 0) { \
			int new_count = rand() % 1000; \
			for (int i = 0; i < new_count; i++) { \
				particle_t *p = NEW_FUNC(); \
				if (p) { \
					particle_init(p); \
				} \
			} \
		} \
		UPDATE_FUNC(); \
	})

int main(int argc, char **argv) {

	BENCHMARK_PARTICLES("Two ptr arrays,  spawn chance 1/50", 50, particles_2pa_init, particles_2pa_new, particles_2pa_update);
	BENCHMARK_PARTICLES("Two ptr arrays,  spawn chance 1/10", 10, particles_2pa_init, particles_2pa_new, particles_2pa_update);

	BENCHMARK_PARTICLES("One ptr array,   spawn chance 1/50", 50, particles_pa_init, particles_pa_new, particles_pa_update);
	BENCHMARK_PARTICLES("One ptr array,   spawn chance 1/10", 10, particles_pa_init, particles_pa_new, particles_pa_update);

	BENCHMARK_PARTICLES("One index array, spawn chance 1/50", 50, particles_ia_init, particles_ia_new, particles_ia_update);
	BENCHMARK_PARTICLES("One index array, spawn chance 1/10", 10, particles_ia_init, particles_ia_new, particles_ia_update);

	BENCHMARK_PARTICLES("In-place move,   spawn chance 1/50", 50, particles_move_init, particles_move_new, particles_move_update);
	BENCHMARK_PARTICLES("In-place move,   spawn chance 1/10", 10, particles_move_init, particles_move_new, particles_move_update);

	BENCHMARK_PARTICLES("Linear scan,     spawn chance 1/50", 50, particles_linear_init, particles_linear_new, particles_linear_update);
	BENCHMARK_PARTICLES("Linear scan,     spawn chance 1/10", 10, particles_linear_init, particles_linear_new, particles_linear_update);


	return 0;
}