Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

paulcoz

Comparison: Linked Lists, Arrays, Dyn. Mem Alloc and other stuff

This topic is 6403 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've been doing some research on dynamic memory allocation and what the different ways are of storing objects, the object's related polys, and the poly's related vertices. I would like people to post here some different methods of storing data in linked lists, arrays etc. , and also allocating memory for these. I will include here what I think are the pros and cons of the different methods: Arrays - Pros ------------- Easy to implement Each segment in the array is sequential in memory Arrays - Cons ------------- Cannot easily extend the size of the array, and keep things sequential in memory Using invalid indices cause GPF's Dynamic Memory Allocation - Pros --------------------------- More setup required, but not much harder to implement than arrays Can easily extend the size of the arrays Dynamic Memory Allocation - Cons -------------------------------- It is hard to keep things sequential in memory, resulting in cache misses If you forget to release a structure, the memory is lost It seems to me you can use Linked Lists with either arrays or dyn. mem. alloc. but it would make more sense in dyn. mem. alloc. because the objects are spread out over memory and thus harder to keep track of. Perhaps there are other good systems as well because there are some problems with linked lists. One good idea would be to have an object with pointers to all of the objects polys (a sequential array of pointers, as opposed to including the next poly address within each poly). Then if you delete a poly you know exactly where the space was in memory without having to do a sequential search through all the other polys till you find the one you are after. Please provide your own thoughts - maybe this can be the definitive discussion on the topic. Paulcoz. Edited by - paulcoz on 11/29/00 10:25:07 PM

Share this post


Link to post
Share on other sites
Advertisement
I think, you really must allocate your memory dynamically, considering your project from your last posting. Hope you read my reply there. You''ll be amazed how easy it is to keep track of your memory, using classes with dynamic lists. Constructors and destructors will help you.
You just can''t allocate the memory for your whole world with its absolute maximums statically.

HTH Wunibald

Share this post


Link to post
Share on other sites
Nothing wrong with abusing C++ a little =P.
  
template <class D> class node {
public:
D data;
node <D> *child;
node <D> *parent;
node(void) {
child = parent = NULL;
}
};

template <class T> class llist {
public:
T *head;
T *addnode(void) {
T *newnode = new T;
if(head!=NULL) {
head->parent = newnode;
newnode->child = head;
}
head = newnode;
return newnode;
}
void deletenode(T *delnode) {
if(delnode!=NULL) {
delnode->parent->child = delnode->child;
delnode->child->parent = delnode->parent;
delete delnode;
}
}
llist(void) {
head = NULL;
}
~llist(void) {
T *current = head;
T *temp;
while(current!=NULL) {
temp = current->child;
delete current;
current = temp;
}
}
};




http://www.gdarchive.net/druidgames/

Share this post


Link to post
Share on other sites
Well, for relatively small chunks of data, I prefer to use dynamic arrays. They''re built into Delphi, and in C++ I have a template for them that uses realloc() for the resizing. The problem is that resizing an array can take ages. It might have to move the memory block if it can''t be resized in place. Furthermore, if you try to resize an array, and there''s no room for a single contiguous memory block of that size, you''re boned

Your suggestion to store an array of pointers to data is also very useful. I do this all the time in my 3D engine, to store pointers to polygons, pointers to sectors, pointers to textures, ...

I only resort to trees, lists or other dynamic structures like that if a) they better fit a particular algorithm I''m implementing (e.g. BSP) or b) if I need to store so much data that it''s not usually possible to find a single contiguous memory block to put it in.

The only thing I never do is use arrays with a hard-coded maximum size.

If you''re really paranoid about memory leaks, you could write your classes so that they keep a reference counter, and have objects delete themself when the count reaches zero. Another thing that I do is to give all my objects a unique ID number, and to store the objects in a binary tree (using the ID as the search key). I mainly use this to quickly locate trigger targets and the likes, but having pointers to everything in a central location can also help to avoid clashes when you''re trying to delete objects.

- Tom

Share this post


Link to post
Share on other sites
I am thinking of doing away with the linked list, and creating an array of pointers to all objects like this:

object *objects[MAX_OBJECTS_IN_MAP];
objects[0] = address of first object
objects[1] = address of second object

then, when you create a new object (other than the first) you can say:

object *newobject = new object;
objects[(current object count)] = newobject;
newobject->data = add data here
current object count++;

Also, when you delete an object from memory you can do this:

object *address;
address = objects[112]; // object to delete
address = delete object;

for (count = (deleted object no); count < (current object count -1); count++)
{
objects[count] = objects[count + 1];
}
objects[(current object count)] = NULL;
current object count--;

Do you think having an array of pointers to objects will work o.k.?

Delphi3d - I did see your point - "The only thing I never do is use arrays with a hard-coded maximum size.". That's the main problem I can see with this way - you have to allocate an array of pointers for each list (whether it contain objects or polys) you have, regardless of whether all of them are used. This is however an improvement on my old static non-dynamic method. (hey Wunibald?) At least you are only allocating memory to pointers that are not being used, instead of allocating memory to whole objects, polys that aren't used but take up lots of precious RAM.

I know it's not properly "dynamic memory allocation" because of the limitation being placed on the total number of objects, but there seem to be huge advantages when you have an index, especially if you consider deleting objects from a linked list, where you have to make sure you update all of the parent and child nodes.

Any last-minute thoughts/warnings - "don't do it paulcoz!!"?

Paulcoz.

Edited by - paulcoz on December 9, 2000 6:41:20 AM

Share this post


Link to post
Share on other sites
Linked lists have been great for me, I had to scrap one of my first engines entirely because I used a dynamic array system, I ended up regretting it.

It is your choice though, if even map has about the same amount of objects (or something along those lines), then it probably wouldn''t be such a bad idea, it all depends on the situation.



http://www.gdarchive.net/druidgames/

Share this post


Link to post
Share on other sites
The most common alternative to either is a tree. You can also combine the two for what I call a segmented array. That is a linked list of arrays. It is a good alternative when you need ability to insert randomly as well as search randomly.

Share this post


Link to post
Share on other sites

  • 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!