up vote 2 down vote favorite

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.

share|improve this question
    
What exactly do you mean with "use implement the array as a sorted list"? I don't think I've come across that before. – congusbongus May 23 '16 at 2:15
    
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. – Andreas May 23 '16 at 11:36
up vote 2 down vote accepted

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.

share|improve this answer
    
That does help, and no im doing an assignment for one of my classes and we have to justify all of our algorithm choices. – Zac Shepherd May 23 '16 at 2:46
    
@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. – Alexandre Vaillancourt May 23 '16 at 2:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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