From 8add1663d9a02db2bc65224cdceb480733a81379 Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Tue, 13 Dec 2016 07:51:23 -0800 Subject: sparkler: introduce a particle system A while ago I made this particle system on SDL, and had the beginnings of an octree implemented within it, but never finished actually using the octree to accelerate the proximity searches. This now has the octree completed and of course more particle interactions now that neighbors could be found more quickly. The simulation somewhat resembles a fireworks display. Every particle is drawn as a single pixel. The visual effect is dominated by spontaneously spawned rockets which explode into thousands of particles accompanied by bursts that thrust particles away from the explosion radially in an expanding sphere resembling a shock wave. When the shock wave happens to strike another rocket, it explodes, resulting in another shock wave. This can produce spectacular chain reactions, so it's worth running for some time and seeing what transpires. --- modules/sparkler/chunker.c | 225 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 modules/sparkler/chunker.c (limited to 'modules/sparkler/chunker.c') diff --git a/modules/sparkler/chunker.c b/modules/sparkler/chunker.c new file mode 100644 index 0000000..ca072eb --- /dev/null +++ b/modules/sparkler/chunker.c @@ -0,0 +1,225 @@ +#include +#include +#include +#include +#include + +#include "chunker.h" +#include "container.h" +#include "list.h" + +/* Everything associated with the particles tends to be short-lived. + * + * They come and go frequently in large numbers. This implements a very basic + * chunked allocator which prioritizes efficient allocation and freeing over + * low waste of memory. We malloc chunks at a time, doling out elements from + * the chunk sequentially as requested until the chunk is cannot fulfill an + * allocation, then we just retire the chunk, add a new chunk and continue. + * + * When allocations are freed, we simply decrement the refcount for its chunk, + * leaving the chunk pinned with holes accumulating until its refcount reaches + * zero, at which point the chunk is made available for allocations again. + * + * This requires a reference to the chunk be returned with every allocation. + * It may be possible to reduce the footprint of this by using a relative + * offset to the chunk start instead, but that would probably be more harmful + * to the alignment. + * + * This has some similarities to a slab allocator... + */ + +#define CHUNK_ALIGNMENT 8192 /* XXX: this may be unnecessary, callers should be able to ideally size their chunkers */ +#define ALLOC_ALIGNMENT 8 /* allocations within the chunk need to be aligned since their size affects subsequent allocation offsets */ +#define ALIGN(_size, _alignment) (((_size) + _alignment - 1) & ~(_alignment - 1)) + +typedef struct chunk_t { + chunker_t *chunker; /* chunker chunk belongs to */ + list_head_t chunks; /* node on free/pinned list */ + uint32_t n_refs; /* number of references (allocations) to this chunk */ + unsigned next_offset; /* next available offset for allocation */ + uint8_t mem[]; /* usable memory from this chunk */ +} chunk_t; + +typedef struct allocation_t { + chunk_t *chunk; /* chunk this allocation came from */ + uint8_t mem[]; /* usable memory from this allocation */ +} allocation_t; + +struct chunker_t { + chunk_t *chunk; /* current chunk allocations come from */ + unsigned chunk_size; /* size chunks are allocated in */ + list_head_t free_chunks; /* list of completely free chunks */ + list_head_t pinned_chunks; /* list of chunks pinned because they have an outstanding allocation */ +}; + + +/* Add a reference to a chunk. */ +static inline void chunk_ref(chunk_t *chunk) +{ + assert(chunk); + assert(chunk->chunker); + + chunk->n_refs++; + + assert(chunk->n_refs != 0); +} + + +/* Remove reference from a chunk, move to free list when no references remain. */ +static inline void chunk_unref(chunk_t *chunk) +{ + assert(chunk); + assert(chunk->chunker); + assert(chunk->n_refs > 0); + + chunk->n_refs--; + if (chunk->n_refs == 0) { + list_move(&chunk->chunks, &chunk->chunker->free_chunks); + } +} + + +/* Return allocated size of the chunk */ +static inline unsigned chunk_alloc_size(chunker_t *chunker) +{ + assert(chunker); + + return (sizeof(chunk_t) + chunker->chunk_size); +} + + +/* Get a new working chunk, retiring and replacing chunker->chunk. */ +static void chunker_new_chunk(chunker_t *chunker) +{ + chunk_t *chunk; + + assert(chunker); + + if (chunker->chunk) { + chunk_unref(chunker->chunk); + chunker->chunk = NULL; + } + + if (!list_empty(&chunker->free_chunks)) { + chunk = list_entry(chunker->free_chunks.next, chunk_t, chunks); + list_del(&chunk->chunks); + } else { + /* No free chunks, must ask libc for memory */ + chunk = malloc(chunk_alloc_size(chunker)); + } + + /* Note a chunk is pinned from the moment it's created, and a reference + * is added to represent chunker->chunk, even though no allocations + * occurred yet. + */ + chunk->n_refs = 1; + chunk->next_offset = 0; + chunk->chunker = chunker; + chunker->chunk = chunk; + list_add(&chunk->chunks, &chunker->pinned_chunks); +} + + +/* Create a new chunker. */ +chunker_t * chunker_new(unsigned chunk_size) +{ + chunker_t *chunker; + + chunker = calloc(1, sizeof(chunker_t)); + if (!chunker) { + return NULL; + } + + INIT_LIST_HEAD(&chunker->free_chunks); + INIT_LIST_HEAD(&chunker->pinned_chunks); + + /* XXX: chunker->chunk_size does not include the size of the chunk_t container */ + chunker->chunk_size = ALIGN(chunk_size, CHUNK_ALIGNMENT); + + return chunker; +} + + +/* Allocate non-zeroed memory from a chunker. */ +void * chunker_alloc(chunker_t *chunker, unsigned size) +{ + allocation_t *allocation; + + assert(chunker); + assert(size <= chunker->chunk_size); + + size = ALIGN(sizeof(allocation_t) + size, ALLOC_ALIGNMENT); + + if (!chunker->chunk || size + chunker->chunk->next_offset > chunker->chunk_size) { + /* Retire this chunk, time for a new one */ + chunker_new_chunk(chunker); + } + + if (!chunker->chunk) { + return NULL; + } + + chunk_ref(chunker->chunk); + allocation = (allocation_t *)&chunker->chunk->mem[chunker->chunk->next_offset]; + chunker->chunk->next_offset += size; + allocation->chunk = chunker->chunk; + + assert(chunker->chunk->next_offset <= chunker->chunk_size); + + return allocation->mem; +} + + +/* Free memory allocated from a chunker. */ +void chunker_free(void *ptr) +{ + allocation_t *allocation = container_of(ptr, allocation_t, mem); + + assert(ptr); + + chunk_unref(allocation->chunk); +} + + +/* Free a chunker and it's associated allocations. */ +void chunker_free_chunker(chunker_t *chunker) +{ + chunk_t *chunk, *_chunk; + + assert(chunker); + + if (chunker->chunk) { + chunk_unref(chunker->chunk); + } + + assert(list_empty(&chunker->pinned_chunks)); + + list_for_each_entry_safe(chunk, _chunk, &chunker->free_chunks, chunks) { + free(chunk); + } + + free(chunker); +} + +/* TODO: add pinned chunk iterator interface for cache-friendly iterating across + * chunk contents. + * The idea is that at times when the performance is really important, the + * chunks will be full of active particles, because it's the large numbers + * which slows us down. At those times, it's beneficial to not walk linked + * lists of structs to process them, instead we just process all the elements + * of the chunk as an array and assume everything is active. The type of + * processing being done in this fashion is benign to perform on an unused + * element, as long as there's no dangling pointers being dereferenced. If + * there's references, a status field could be maintained in the entry to say + * if it's active, then simply skip processing of the inactive elements. This + * tends to be more cache-friendly than chasing pointers. A linked list + * heirarchy of particles is still maintained for the parent:child + * relationships under the assumption that some particles will make use of the + * tracked descendants, though nothing has been done with it yet. + * + * The current implementation of the _particle_t is variable length, which precludes + * this optimization. However, breaking out the particle_props_t into a separate + * chunker would allow running particles_age() across the props alone directly + * within the pinned chunks. The other passes are still done heirarchically, + * and require the full particle context. + */ -- cgit v1.2.1