2
\$\begingroup\$

So im looking at ways of handling large amounts of data in situations such as an entity manager or particle system.

So i have concluded to use an object pool, and there are two things that I could do to keep track of the free locations.

I can either have a free list through a linked list or use implement the array as a sorted list.

Both of these methods will work and i am sure there are more. My question is what is the difference and prefered usage cases for each of these methods, and if there is any difference at all.

If u have an questions please ask, and this is a real question and if u find a "duplicate" please check with me first in the comments. Ive had people mark my questions in the past as a duplicate when they were in fact unrelated.

\$\endgroup\$
  • 1
    \$\begingroup\$ What exactly do you mean with "use implement the array as a sorted list"? I don't think I've come across that before. \$\endgroup\$ – congusbongus May 23 '16 at 2:15
  • \$\begingroup\$ I have an object pool (c++ template) where the objects are in an array and free indices are on a stack. No need for sorting really as it sort of defragments itself over time. \$\endgroup\$ – Andreas May 23 '16 at 11:36
  • \$\begingroup\$ One important consideration: do you have items that need to hold references to particular entities in this collection? For something like particle systems, we usually don't - as long as the system can iterate over the whole batch of particles, nothing cares about holding a reference to any one particular particle between frames. Or something like an entity manager, we often do (say, one entity wants to reference its "target" or "parent" entity). The complexity of these relationships can affect your decision whether to re-arrange instances to pack them tight or keep them in place with some gaps \$\endgroup\$ – DMGregory Feb 3 '18 at 5:27
  • \$\begingroup\$ Also, don't worry too much about duplicate votes - it takes 5 different (non-mod) users to agree a question is a duplicate before it can be closed, and even if it comes to that, if the question is edited to clarify the difference, it can be re-opened quickly. \$\endgroup\$ – DMGregory Feb 3 '18 at 5:30
2
\$\begingroup\$

The theory will tell that you're likely to get less cache misses (so 'more efficiency' w.r.t. response time) if your objects are close one to another in memory.

This means that if you use an array, and your objects are contiguous, and you access each of them in a in-memory-sequential fashion, it will be more efficient than if you hop from here to there and here again with a linked list.

That's the theory.

Now, the questions that are left:

  • Can you get that efficiency?
  • Do you need that kind of efficiency?

You mentioned an array that you'd keep sorted. Will the time you save by avoiding cache misses be more important than the time it'll take to keep your array sorted?

Did you profile your application and realized that you have a bottleneck there? It's generally not worth doing premature optimization.

\$\endgroup\$
  • \$\begingroup\$ That does help, and no im doing an assignment for one of my classes and we have to justify all of our algorithm choices. \$\endgroup\$ – Zac Shepherd May 23 '16 at 2:46
  • \$\begingroup\$ @ZacShepherd Justifying algorithm is a good way to make you realize what you're doing. If you want to see what's faster, you'll have to implement both and test both approaches with similar data. Still, the profiler will be your friend. \$\endgroup\$ – Vaillancourt May 23 '16 at 2:53
0
\$\begingroup\$

My question is what is the difference and prefered usage cases for each of these methods, and if there is any difference at all.

Free list is a really good bet if you need stable indices (free list with one big contiguous buffer) or pointers (in which case you use a free list with linked buffers). You do not need to store a stack on the side to reclaim in constant-time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.