# Vector Skip List?

This topic is 4674 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.

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632996
• Total Posts
3009776
• ### Who's Online (See full list)

There are no registered users currently online

×