# Vector Skip List?

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

## 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 on other sites
What's wrong with just using a linked list?

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

##### Share on other sites
Quote:
 Original post by SneftelWhat'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 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 on other sites
Quote:
 Original post by SneftelYou 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 on other sites
A heap sounds like a pretty good idea to me.

##### 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 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 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 on other sites
Quote:
 Original post by hplus0603Lists and heaps are all horrible ideas -- they will thrash the cache badly.

Agreed.
Quote:
 Original post by hplus0603I 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.

That was my first idea, although I figured that skipping over dead particles instead of checking their flag would be faster. Not sure if the complexity of managing the skip list would counter that though.
Quote:
 Original post by SiCraneI'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.

That sounds even better, very simple and efficient. I think I'll use that solution.

The memory pool allocator was some complex stuff. I looked through the boost library and found that "boost::shmem::node_allocator" seemed to be the closest to what I wanted except it looks complex and requires a call to the deallocate function manually after use. It seems like it could use a few wrappers at the least.

Eitherway, custom allocators are interesting but I'll need quite a bit more research before I use a custom memory pooling allocator.

##### Share on other sites
Using boost::pool for a pooled allocator is fairly easy.
#include <list>#include <boost/pool/pool_alloc.hpp>std::list<int, boost::pool_allocator<int> > int_list;

##### Share on other sites
Oh, I was looking for an example of that but I could not find it. Although reading about the Shemm Node Allocator showed me that there are many ways to implement that concept. The mention of mutexes has me wondering if boost pool locks threads which can be a slower operation than just allocating another block of memory (according to my research on the Shemm Node Allocator).

*edit* I just found where you copied your example, I look through all of the boost pool documentation now.

*edit again*
Quote:
 // Exiting the function does NOT free the system memory allocated by the pool allocator // You must call // boost::singleton_pool::release_memory() // in order to force that

Seems like its complex too, it creates a singelton pool which must be made thread safe with a locking mutex. Also, seems like I have to manually destroy it.

[Edited by - T1Oracle on January 4, 2006 9:05:36 PM]

##### Share on other sites
You could just have a vector divided into two parts, with the first part consisting of active particles and the second dead particles. When you need a new particle simple activate the first dead one and increment the iterator to the dead section. When one dies swap it with the last live particle and decrement the iterator to the dead particle. You'll have excellent cache performance, but the speed will depend on how quickly you can swap 2 particles. Note that you don't have to completely swap all the data between two particles, so you can optimize this depending on your particle system.