Jump to content
  • Advertisement
Sign in to follow this  
taz0010

Fast link list container

This topic is 2995 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 want to create a link list class without the overhead of dynamically allocating each element. I believe this can be achieved by using a fixed capacity. The list is initialised with enough room allocated for the maximum number of elements. The elements can be stored in an array, without worrying about the previous/next pointers being invalidated, as the array never increases in size during the lifetime of the container.

Can I find an implementation of this or do I need to roll my own? What about using std::list with a custom allocator? I don't know how the custom allocator system works or whether I can expect the same performance I'd get doing it by hand.

Okay, now suppose I want to make another container which is the same as above, but supports dynamic resizing. So this second container is allowed to grow beyond it's original capacity. When the container needs to resize to accommodate new elements, new memory is allocated and the contents copied across. But now the previous/next pointers of each element are invalidated.
How can the pointers be adjusted so they point to the correct elements in the newly allocated memory? According to MSDN, pointer arithmetic is only safe if you're comparing pointers to the same array or block of memory. Does this mean it's not reliable to find the number of bytes between the new and old memory, and add the difference to each pointer?

So are there any existing Link List implementations that use array based allocation rather than per-element allocation?

Share this post


Link to post
Share on other sites
Advertisement
I'd try a std::list with a boost::pool_allocator and see if that's fast enough for your needs.

Share this post


Link to post
Share on other sites
typedef std::pair<int, X> Entry;
std::vector<Entry> list;


The int in Entry is the "pointer" to next node.

Quote:
How can the pointers be adjusted so they point to the correct elements in the newly allocated memory?
They don't, they are just indices.


If using single linked list, the above requires 2 head pointers. One for empty cells, other for actual linked list. Whenenver an entry is removed, it's appended to empty list, whenever a cell is added, it is put into first cell from empty list.

With double linked list, removal can be done directly, where the removed cell is replaced with last element in the array.


The more important thing about above design is that such linked list can be directly serialized, as well as moved around memory as needed. Underlying storage may also be resized as needed, since all references are just indices, not pointers.

Share this post


Link to post
Share on other sites
Not sure why you don't just use std::list. It is rather quick and the way your post is written, it seems you don't quite understand how a linked list works. A linked list doesn't need any relation to an array. The only overhead in creating a new linked list node would be the 2 pointers, and either another pointer to the object you are adding or the construction of your object type.

Linked list nodes are not sequential in memory, they hold pointers to the next and previous elements (previous if it is a doubly linked list) and either a pointer to your data, or an object of your data.

std::list<foo*> myPointerList;
should only create 3 pointers when you add a new node.
Although if you do:
myPointerList.push_back(new foo());
you will be creating the new object along with the 3 pointers.


std::list<foo> myObjectList;
should create 2 pointers and an object of type foo when you add a new node.

So typically a linked list class only holds 2 pointers itself, one to the front node, one to the end node.

Share this post


Link to post
Share on other sites
Quote:
Original post by JonConley
Not sure why you don't just use std::list. It is rather quick and the way your post is written, it seems you don't quite understand how a linked list works.


I thought he got that but I'm curious why he needs a linked list with a fixed size in the first place. The only advantages left are O(1) removal and sorting, in case copying the value_type takes significant time. But maybe there's another advantage I can't think of right now.

Share this post


Link to post
Share on other sites
Quote:
Not sure why you don't just use std::list. It is rather quick and the way your post is written, it seems you don't quite understand how a linked list works. A linked list doesn't need any relation to an array. The only overhead in creating a new linked list node would be the 2 pointers, and either another pointer to the object you are adding or the construction of your object type.


There's also the memory overhead of the dynamic allocation itself. The actual size of a std::list node containing a 4 byte integer is about 24 bytes. 38 bytes if you run from within the MSVC IDE.
My nodes are 8 bytes, so the custom list method will result in a 50% or 100% size increase, depending on whether I actually need it doubly linked. std::list on the other hand will incur a 250% increase. I'm guessing that cache misses will be the bottleneck.

The code is currently fast enough using vectors only, but managing indices and iterators is quite complicated due to the large number of removal/move operations I'm doing. I realised that the problem I'm working on can be solved a lot easier using lists. And constant time complexity on remove operations is a plus too.

Share this post


Link to post
Share on other sites
Constant time removal won't happen if you use arrays. The only way to do that would be to have an array of nodes with your data, and the node has an index to the next item. Even then you'd have to keep a list of free nodes handy incase you deleted something in the middle.

something like this: array with empty spots O is filled X is empty.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| O | X | O | O | O | O | X | X | X | O |

now if that was a list implementation based on a vector the relationships are:
0->2, 2->3, 3->4, 4->5, 5->9.
[Side Note:] it wouldn't have to be in order, the relationships could be:
0->2, 2->4, 4->5, 5->3, 3->9.

You'd also have a list of empty nodes which would be: 1,6,7,8

Now to insert into 1 you'd have to change 0's relationship insert and remove it from the list (a priority queue would work best so you always use the lowest spot available which would gurantee that the previous element is the relationship you need to change, unless the empty spot is 0 then you change the front index).

Now this would allow constant deletions but would give a lot of over head in terms of the priority queue and insertion.


If you wanted to keep all nodes left aligned like:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| O | 0 | O | O | O | O | O | X | X | X |

The relationships would be easier since it is just the next and previous index into the array, pushing to the back would be easy (as long as you weren't full of course). Insertion into an already occupied space becomes a problem, and deletion (especially of a range) can become a problem.

Inserting something between 3 and 4 would require anything from 4 to the end to be copied 1 node to the right, and then 4 would have to be set to the node you are inserting.

Deleting the range from 1 to 4 would require you to move 5 and 6 to the left, copying them.

Even if you went with the left aligned with a node relationship (doesn't have to be in order, but each node stores the index to the node in front of it) you'd have some sort of problem with insertion and deletion and you'd have to cascade updates to the nodes whose "children" will be moving.

Share this post


Link to post
Share on other sites
I'm guessing (although feel free to correct me) that you don't need to preserve element order. If this is indeed this case, just use the swap-and-pop idiom (exchange the item to be removed with the tail item in the vector/array, then decrease the capacity of the container by 1). Bam - constant time removal, no per-item allocation overhead, contiguous storage for better cache locality, free random access iteration, and all the rest of the perks of a flat container.

Share this post


Link to post
Share on other sites
I don't know why I didn't think of it before but you mean removing an item by swapping the last index with the one being deleted?
Say the last index being used is 8, but you want to delete the node at 4, you'd swap 8 to 4, then set the end of the list to be 7 correct?

With this though you still have the range deletion problem, would have to move all elements from the last node being deleted down.

I just feel it'd be easier and more cpu efficient to stick with a regular linked list, less copying and swapping, although it does depend on the datatypes that will be used. An integer based arraylist swap could be just as quick(maybe a little quicker) then if you were to reassign the pointer in a regular linked list. When you get larger objects the linked list will be much quicker since all it will be is a delete and a pointer assignment.

Unless I am completely wrong (which may be the case) your method could save some memory overhead but it does seem like it'd take up (depending on the objects in the list) more overall cpu time to do certain operations on the list.

Quick edit:
How about a stack based retrieval system? Allocate n-1 nodes in the stack, create a front node, create and end node, and as you use and delete nodes, pull off the stack, then when you delete a node, just toss it back onto the stack? This will preallocate everything and only take copying data into the new nodes (and you won't even need to delete the data inside the nodes once you put them back on the stack). Copy incoming data to node that was pulled from the top of the stack, insert where it needs to be in linked list. Delete an element by changing the previous node's pointer, and toss the node to be deleted back on the stack.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!