Custom ECS - pointer safety

These blocks, let's refer to them as a page, and this whole allocator... We'll call that a Book. So now we have a book that can contain pages!

When we declare a book we'll supply a type and a page size through templates that set the size and type of the array in the pages.

This allows us to store a data type T in a Book by looking if there's any free pages. If not, we make a new one and add it in the book pages. If we have a free page, we grab the most full one. After acquiring a page by one of these two means we add our T to a free array slot on the page.

But why did we place it in the most full page? And how do we find a free slot in the selected page?

Well, we put it in the fullest page because that means that any newly added T will tend to clump together in the same pages as all the others, meaning iteration speed will be better.

And how do we find a free slot in a page? By having the page array not store T directly and instead wrapping it in a Node and effectively placing a linked list inside the array. We then make all the empty/inactive nodes link together in a line and ensure that the line is linear through memory so that we don't get a cache-miss by iterating over the chain. As long as the nodes are stored in sequence in this array it shouldn't exhibit any of the performance problems normal linked lists are known for. By doing a similar chain with all the active nodes in the array as well we now have the means of following the inactive chain to locate a free slot. And we can iterate over the active chain to jump over the inactive nodes with a theoretically minimal impact on the CPU cache.

So, to iterate the entire book we can simply iterate each page, and to iterate each page we simply jump though the active chain and do whatever we need to on the data in each node we pass.

To insert into the book we simply grab the best page as described above and insert the data at the inactive head of that page and advance the head.

With this Book structure defined we can now store the components in a Spare-dense set where the dense set is one of these books.

Even though it's a complex algorithm and complete homebrew I think It's got a good chance at it being performant seeing how even though it's a little finicky to add and remove items it should be great for iterating over the active items at great speed given I set myself the constraint of not moving the data.

Even if it turns out to be terrible in practice I still think it's a great learning opportunity to even just try building something like it. Even if just to know what not to do. Plus, you never know, maybe it's a great idea.