next »

[metamorphosis]

Hi all,
I'm aware a lot of people on here probably use X/Y/Z game engine rather than coding directly, so this question is more for those who're using languages like C/C++/etc. I'm basically doing some research on behalf of the C++ standards committee to gather evidence for use of a specific type of technology in industry, so that we can justify standardizing it.

So, without further ado:

1. Are you using the following type of data container in your game systems: sequential element storage, either in multiple memory blocks or one singular memory block, elements are marked by a boolean/bit/token when erased and these marked elements are subsequently skipped over during iteration (enables erasure without invalidating pointers to elements).

2. If so, is the container multiple-memory-block or singular?

3. If not, do you use another type of container when you need stable iterators/pointers to elements and/or fast erasures?

4. Do you think that there are benefits to this style of container being standardized?

5. Any additional comments or questions?

Thanks,
M

[michaelplzno]

Is this what's called an object pool?

I use this sort of design pattern when I'm making particle systems and don't want to have to constantly shrink and grow a container because of paranoia about creating garbage in c#. Its possible using c#'s list collection would do this work for me, and I could just remove and add particles at will with list.remove and list.add without worrying about allocations, but I never really trust the structures that are part of the language. To some extent, for me, its faster to just write my own code rather than read all the fine print associated with a language feature.

The way I do it is to have a particle object and a flag or other data member that determines if the particle is alive so that new particles can be created by iterating the array without destroying or creating memory. Since I never have more than a few thousand particles on screen its pretty simple to deal with. I'm not really taking advantage of the stable pointer situation though, it seems like c# automatically keeps pointers to objects stable even if I were using a list there because the list would just be a list of pointers rather than actually keeping the memory in a block.

I'm not really a c++ guy anymore, so I can't say you should make such a thing part of STL or whatever, but its not too difficult to roll your own, and someone who knows why they would need such a structure is likely not going to need an implementation as part of STL for them.

[metamorphosis]

Is this what's called an object pool?

I use this sort of design pattern when I'm making particle systems and don't want to have to constantly shrink and grow a container because of paranoia about creating garbage in c#. Its possible using c#'s list collection would do this work for me, and I could just remove and add particles at will with list.remove and list.add without worrying about allocations, but I never really trust the structures that are part of the language. To some extent, for me, its faster to just write my own code rather than read all the fine print associated with a language feature.

The way I do it is to have a particle object and a flag or other data member that determines if the particle is alive so that new particles can be created by iterating the array without destroying or creating memory. Since I never have more than a few thousand particles on screen its pretty simple to deal with. I'm not really taking advantage of the stable pointer situation though, it seems like c# automatically keeps pointers to objects stable even if I were using a list there because the list would just be a list of pointers rather than actually keeping the memory in a block.

I'm not really a c++ guy anymore, so I can't say you should make such a thing part of STL or whatever, but its not too difficult to roll your own, and someone who knows why they would need such a structure is likely not going to need an implementation as part of STL for them.

Thanks for your response and apologies for my late reply.
Yes some people call this an object pool - or a bucket array - or many other names.
It's uncomplicated to roll your own using the system you described, but implementing it well is tricky - particularly if you intend to adhere to C++ standard guidelines (constant-time iterator operators).
Using your system there are branching checks for every object, whether it's alive or not, which makes iterator operators ++ and -- linear in the number of dead elements between the alive ones.
Using my system it's constant time to iterate between 2 alive elements, because the jump-counting skipfield pattern keeps a record of the number of 'dead' elements which are contiguous.
It's also non-branching, which has a significant impact on some processor types.

But my main reason for reaching out is just to establish whether/not the pattern is common - luckily, it is - not to promote my personal implementation (plf::colony). So thanks for your feedback, it is helpful.
Cheers-
M