4 ms·

From my experience from more than a dozen years ago: To avoid allocation churn, one can use a big array of objects and for each index a flag whether the array

From my experience from more than a dozen years ago: To avoid allocation churn, one can use a big array of objects and for each index a flag whether the array element contains an object or not. Today I would say I used an arena. Combined with the fly-weight pattern in some use cases you don't need to reach for unsafe at all. For me it was about a visual simulation of chemical reactions. In each frame iteration an array was held and even this long time ago it was fast enough to allow smooth animation with tens of thousands of possibly colliding particles. I respect research out of curiousity. This way we learn what works and what doesn't work. So keep up this work but I just wanted to tell about the boring alternative.

Someone 3y ago
> a big array of objects for each index a flag whether the array element contains an object or not. Typically, you never need to iterate through all used objects. Also, all unused objects are interchangeable from the program’s view. Each just is a chunk of memory that you can use to write a Foo to. That leads to the standard way to do this for objects that are at least as large as a pointer: make the array an array of union{Foo, Foo*}, and, at allocation, create a linked list through all the unused entries. Getting memory for a new Foo then is just a matter of removing the head of the list, freeing a Foo a matter of appending it to the head of the list. That means you don’t need n flags (one for each entry, but only a single Foo* pointing to the head of the free list. That’s a big gain if n is large. (Doing that in Java is left as an exercise. It may not be possible)
bitwize 3y ago
I wrote an ECS in (Android's version of) Java that does just this for game entity components. Each component type has a big array associated with it; plus there's a big bit array of used/free flags for entities. The EID (entity ID) serves as an index into the arrays of its various components.

Someone 3y ago

> a big array of objects for each index a flag whether the array element contains an object or not. Typically, you never need to iterate through all used objects. Also, all unused objects are interchangeable from the program’s view. Each just is a chunk of memory that you can use to write a Foo to. That leads to the standard way to do this for objects that are at least as large as a pointer: make the array an array of union{Foo, Foo*}, and, at allocation, create a linked list through all the unused entries. Getting memory for a new Foo then is just a matter of removing the head of the list, freeing a Foo a matter of appending it to the head of the list. That means you don’t need n flags (one for each entry, but only a single Foo* pointing to the head of the free list. That’s a big gain if n is large. (Doing that in Java is left as an exercise. It may not be possible)

bitwize 3y ago

I wrote an ECS in (Android's version of) Java that does just this for game entity components. Each component type has a big array associated with it; plus there's a big bit array of used/free flags for entities. The EID (entity ID) serves as an index into the arrays of its various components.