Jump to content
  • Advertisement
Sign in to follow this  
T1Oracle

Vector Skip List?

This topic is 4522 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have thought of a problem in which doubly linked lists (ala STL) and dynamic arrays (vector) can solve but would do so with wasteful memory deallocations and reallocations. Problem: Say that you have a particle system that generates particles which decay in a random order. Is it better to avoid the cost of creating and then destroying particle objects that will only be recreated later? If so (and I do assume that it is so), then how can one best do this? I have thought up a solution that would employ a vector (STL) with a skip list (I believe that is the term for a linked list that can point to elements further ahead then the next sequential item). Step 1) populate vector with particles Step 2) cycle through particles and update each particle until one has decayed Step 3) for every decayed particle set the previous particle (within the vector) to point to the next undecayed particle within the system (finding this will be as easy as deleting 1 item from a singly linked list, the vector is cycled through via the list pointers). Step 4) newly generated particles overwrite the spaces of decayed particles which are then reinserted into the list (so that they become part of the update cycle). Finding these spaces will be as simple as checking for when the next list pointer (should be an iterator from the containing vector class) points to something other than the next vector element. When there are no spaces left no new particles are generated effectively limiting the particle count within the particle system. I am not certain how to best implement such a system, however my approach would be to try to mimic some of the features of the STL in a custom container that followed the methods of the STL. I have never tried that before however, and if there already is a better solution available then I'd rather use that. Of course it is nice to learn. I imagine that this concept can be applied to problems outside of my particle system idea.

Share this post


Link to post
Share on other sites
Advertisement
Or a heap where you push in the particle by its decay time from the current time?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
What's wrong with just using a linked list?

Because when you remove an item from the linked list the memory space once occupied by the element is deallocated. When you insert into a linked list a new memory space is allocated. Memory allocations and deallocations are expensive operations.

I am not sure if the STL implementation of lists has a way around this, but every example of linked lists that I see do exactly that. There is no way to guarantee that memory is not being allocated when it could have otherwise been reclaimed directly from a dead particle, thus saving that CPU time.

Share this post


Link to post
Share on other sites
You can use a fixed-size small object pool allocator for the linked list if you're worried about allocation/deallocation overhead.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
You can use a fixed-size small object pool allocator for the linked list if you're worried about allocation/deallocation overhead.

Interesting, I was looking at some memory pool stuff in the boost library though haven't tried any of it yet. That probably is the best answer, I'll research it.

Share this post


Link to post
Share on other sites
Just use two lists. One active list, and one free list.
* If a particle dies, you remove it from the active list and push it onto the free list.
* If you want to create a particle, pop an item off the free list and use that, unless the free list is empty, in which case you'll have to allocate a particle.

Share this post


Link to post
Share on other sites
Lists and heaps are all horrible ideas -- they will thrash the cache badly.

I would create a fixed array, the size of the largest amount of particles that you want to allow; each item is the particle state record (NOT a pointer!). Rip through this array (linearly) and process each particle. Then have a "particle is dead" flag within the record for each particle, and if a particle is dead, don't process that particle any more. When you rip through the list, you can also generate the output particle vertex buffer at the same time, or you can do that in a second pass (trusting the fact that the particle data will all be in L2 cache after you've processed it).

Honestly, this is not only simpler than any complicated management method; it's also faster at runtime.

Share this post


Link to post
Share on other sites
I'm not seeing the problem with using just a vector here either. It doesn't sound like order is important in this case so removing an item from the vector can be done cheaply by copying the last element on top of the current element and then calling pop_back(). Or if your element type has a cheaper swap than assignment operator, calling swap instead.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!