Ive heard from some sources that linked lists are slow to tarverse and use and that they are too slow to use in 3D. Is this true?? Because Ive seen some source code which uses linked lists extensively. Anyway, ARE linked lists slow or not?
well, it depends on how efficient your linked list implementation is. this would be a fast(ish) link list traversal:
typedef struct _list_ } struct _list_ *next; void *datastuffandthingshere; } LinkedList; void traverseLinkedList(LinkedList *this) { if(this) { dostuffwithdata(this->datastuffandthinsghere); traverseLinkedList(this->next); } }
and this would be a horribly inefficient version:
typedef struct _list_ } struct _list_ *next; void *datastuffandthingshere; } LinkedList; void traverseLinkedList(LinkedList *this) { sleep(1000); if(this) { dostuffwithdata(this->datastuffandthinsghere); traverseLinkedList(this->next); } }
in all seriousness, a properly coded (??!) linked list won’t be slow. The only thing that i could think of that’d make traversing it slower than, say, accessing an array is that an array has spatial continuity and a linked list doesn’t. You also have to look up the next pointer in a list for EACH item, and you only need to do that once and then ptr arithmetic to access array items. BUt, really, I wouldn’t worry too much.
Ha, welcome, Mr Stack Overflow!
Try this:
typedef struct _list_ } struct _list_ *next; void *datastuffandthingshere; } LinkedList; void traverseLinkedList(LinkedList *this) { while(this) { dostuffwithdata(this->datastuffandthinsghere); this=this->next; } }
Oh, and yes, linked lists are slow. Never use them for vertices.
Eh,
recursion is adequate for linked traversals. its easy enough to understand, no?
and linked lists are NOT slow. they are slower than SOME things, and not applicable to SOME things, but if you consider that a BSP tree is essentially a linked list, then… well… i’d like to see you code your BSP tree without them
Originally posted by john:
[b]Eh,
recursion is adequate for linked traversals. its easy enough to understand, no?
and linked lists are NOT slow. they are slower than SOME things, and not applicable to SOME things, but if you consider that a BSP tree is essentially a linked list, then… well… i’d like to see you code your BSP tree without them
[/b]
Well, maybe that statement of mine was too absolute. It’s more like what you said. They’re slower for some things. Especially if you have a whole lot of small things . Like vertices and faces. These shouldn’t be kept in a linked list.
As for the BSP tree, yes, you’re right again. Trees can make good use of recursion. But if you don’t need recursion (ie the true linked list case, not a tree), it can be a boost to do it without recursion as you save potentially huge amounts of stack traffic, depending on the size of the list.
I agree with zeckensack. Don’t use a function to traverse if you don’t have to. That leads to stack traffic, function call overhead, etc on top of the regular pointer arithmetic. Either way it’s acceptably fast, and you’d have a hard time using sorting structures without it.
Bottom line. Arrays are fastest, next pointers, but pointers are far more flexible.
Linked lists, arrays, and trees each have valuable and appropriate uses in 3D.
Cool, thats exactly what i needed to know. Coz so far I have avoided linked lists in my programming because most of the examples ive seen dont use them… only some do. So i thought maybe they werent such as good idea… Anyhow, are linked lists good for traversing polygon structures and lightmap structures?
The only thing that i could think of that’d make traversing it slower than, say, accessing an array is that an array has spatial continuity and a linked list doesn’t.
John, the way I do freelists, is allocate an array of all the entries in the freelist, rather than each element seperately, that way I get nice freelist architecture, plus spatial continutity, so it’s easy on the cache!
Freelists rule tho! Much better than traversing a big array each time for elements that are needed. I’d say they are excellent for graphics systems.
Nutty
I use linked lists alot, for various reasons, but remember that mem allocation happens for each node, and malloc esque calls are retty slow. Dpeneds how you use your lists as to whether this is a problem.
But then again if speed is that important for the current application of linked lists you can write a simple pool allocator which will malloc say 256 nodes at a time instead of 1 so you get very low alloc overhead plus less heap fragmentation.Other than that you can’t really say whether linked lists are good or bad.They hav linear(O(n)) search time so it gets worse as the number of nodes increases.Therefore, as zeckenzack allready said, they shouldn’t be used in performance-critical situations with large node counts.Actually I don’t remember using them in any performance-critical situation(i.e inside an inner loop),other structures(like heaps,hash tables,etc.)are usually more suitbale.They are usefull for bookkepping though like the freelists Nutty mentioned.
while on this subject can someone tell me if the way i handle this is optimal… or would link lists of some kind (free lists… what are these?) improve performance.
typedef struct {
bool alive;
float pos[3];
}t_entity;
t_entity test[100];
// set test objects randomly to alive true or false
for (int j = 0; j < 100, j++){
int result = rnd(0,1)
switch result
{
case 0:
test[j].alive = true
break;
default:
test[j].alive = false;
break;
}
}
// UPDATE objects cycle through all objects and perform action if alive optimise this
loop:
for (int k = 0; k < 100; k++){
if (test[k].alive == true){
// do something
}
}
goto loop:
Im handling most my objects like this… im hoping there is a faster way ?!? some stages there may only be 1 object left alive so im still doing up too 100 loops to find this object… case gets even worse if there are 1000, 10000, and so on objects…
That’s C not OpenGL, so you really need another forum. But anyway 
, the fastest thing to do is split the array into two, one for live objects and one for dead objects. If you can’t do this keep a track of the number of live objects. If an object dies swap it with the last live object. This assumes that an object does not die each loop.
i.e
typedef struct {
bool alive;
float pos[3];
}t_entity;
t_entity test[100];
int NumLiveObjects;
// set random number of test objects to alive = true. Set rest to false
NumLiveObjects = rnd(0,100);
for (int j = 0; j < NumLiveObjects, j++){
test[j].alive = true;
}
for (int j = NumLiveObjects; j < 100, j++){
test[j].alive = false;
}
}
// Following code no longer needed.
/* int result = rnd(0,1)
switch result
{
case 0:
test[j].alive = true
++NumLiveObjects
break;
default:
test[j].alive = false;
break;
}
*/
// Add following code for killing objects.
void KillObject(int Index) { // Swaps killed object with last live object to keep array optimised.
struct t_entity Temp = test[Index]; // Copy killed object to temp. Unnecessary if you don't track dead objects.
test[Index] = test[--NumLiveObjects]; // Decrement number of live object (becomes index o last live object). Copy to location of killed object.
test[NumLiveObjects] = Temp; // Copy killed object to where last live object was. Unnecessary if you don't track dead objects.
test[NumLiveObjects].alive = false; // Mark object as killed.
}
loop:
for (int k = 0; k < NumLiveObjects; k++){ // Change from k<100 to k < NumLiveObjects.
/* if (test[k].alive == true){ */ // No longer necessary.
// do something
/* } */ // No longer necessary.
}
goto loop:
PS. If I remember right nested if statements up to 8 work faster than the corresponding switch statement, so avoid using switch for 2 cases.
PSS: Do people still use goto?
[This message has been edited by Furrage (edited 03-21-2002).]
Swapping object structures??? you must have clock cycles that I do not have.
swap indexes instead.
Take two arrays one with elements of int and another with your object structure. to access the live object use
for (int i=0; i < numLiveobjects; i++){
do_whatever_with_object(objects[indexes[i]]);
}
or the other way which would be two link lists one for active and inactive objects and swap the pointers, but do not swap the physical data part of each node. a pointer is only 4 or 8 bytes… The data part of each object could have three floats for position, right there you have 12 bytes in your data part of each node. I am sure that you would like other information in each node than just position.
True. I was only thinking about the data structure he posted and not a larger one that might represent a Kligon warrior. But then I wasn’t thinking about indices… Hmm, I wonder how the time to derefence indices compares to pointers.
Don’t answer that we’ve devoted enough time to something off topic.