Warzone 2100 Forums

Hmm, somehow everbody missed my point.

Indeed it doesn't matter if you implement a linked list in C or C++. My point was that the current implementation has a "current node" pointer and that is a very bad idea (i think everybody will agree on that point) - so it's currently not brilliant. Further, i don't blame anyone for that because i'm very sure it's there from the beginning and was done by Pumpkin Studios.

Actual that was all what i was trying to say...

i suppose i don't understand your meaning in regards to the "current node" type thing. as long as there's a pointer to the beginning of the list (for any kind of linked list), you won't lose track of the data, and when you're iterating through it, there's no possible way to do it *without* a "current node" pointer without a secondary loop, or an if/else chain using a "next node" pointer which has zero benefit aside from adding inefficient edge conditions. my guess is we're talking about two different concepts.

i do agree with you, though: since c++ uses the exact same pointer semantics as c, anything that can be achieved in one, can be done in the other with no difference in performance. i was simply remarking on the typical practice of c++ programmers, especially those who've learned exclusively from computer science teachers in the last 8 years, to "over-classify" (which does indeed slow things down in execs created on a typical c++ compiler, including g++).

He means warzone holds an iterator inside the structure itself, which is bizarre. You seem to keep talking about linked lists and outside iterators in general.

...and since linked lists are used by programmers in almost all cases for their performance benefits...

On a related note, they aren't. They're used by programmers because they're the best structure for holding ordered datasets while inserting and deleting from the middle of the chain. Compared to variable or constant-length arrays, they have terrible locality of reference, and call malloc/free much more often.

As a final note - *p=0 sets the data at p to zero. I think p=0 is what you were after. 

EDIT: However, that hash table implementation in lib/gamelib/hashtabl.[ch] is fairly non-standard... Things like memory leaks on failure, and the fact that it can't rehash, combined with the odd use of two keys, which store pointers in integers. That module just made my day. 

bremac wrote: He means warzone holds an iterator inside the structure itself, which is bizarre. You seem to keep talking about linked lists and outside iterators in general.

okay, i see what you mean.

bremac wrote: On a related note, they aren't. They're used by programmers because they're the best structure for holding ordered datasets while inserting and deleting from the middle of the chain. Compared to variable or constant-length arrays, they have terrible locality of reference, and call malloc/free much more often.

i accept your argument, but i consider "performance" to be a valid reason for using a linked list where a novice programmer might first choose an array, though i'll give to the idea that a seasoned c/c++ programmer would choose a linked list as "the right solution" to many problems.

bremac wrote: As a final note - *p=0 sets the data at p to zero. I think p=0 is what you were after. 

ah, yes. i was definitely wrong, and bremac said what i meant.

kage wrote: i accept your argument, but i consider "performance" to be a valid reason for using a linked list where a novice programmer might first choose an array, though i'll give to the idea that a seasoned c/c++ programmer would choose a linked list as "the right solution" to many problems.

yes linked list is blend of performance and code simplicity.Sometimes using class version of simple data structure implementation is an overkill.

edit:btw wz still runs as fast as it used to be(game logic wise,you can get absurd fps with relatively new cpu with all glvertex3* functions commented out),though the cpu has to wait every single opengl command(we have about 4000 glvertex3* and 2000 glenable/gldisable state changes in a normal scene) to finish every frame,which makes wz run poorly on any system(no matter how good your cpu/memory is) with a low-end gfx card or a broken gfx card driver...

kage wrote: an optimizing compiler might inline a function like getNext(), in which case, no, it wouldn't decrease performance. however, if it's not inlined, then you're looking at a lot of stack manipulation that is always implicit with any compiled-in function call, and since linked lists are used by programmers in almost all cases for their performance benefits, it seems shameful for a programmer to put it within a function, even if they knew it was going to get inlined when they compiled it. in general, using functions for that kind of linked-list manipulation is a signature computer-science type thing to do, where the student explored linked lists as an "interesting data structure" rather than the practical applications behind it.

Well in case of the C++ STL linked list algorithm you get inlining whether you want it or not. Simply because the entire STL (std::list in ) implementation is templated, so the overhead you get from that really is only compile time overhead. Plus comparing an std::vector to a linked list is rather inaccurate (vector had indexed access just like an array, which increases its overhead because memory will have to be maintained sequentially (i.e. a vector must make sure that all contained objects follow up on eachother in memory: std::vector a; (++&a[0]) == (&[1])).

Anyway most STL algorithms really only provide type safety and encapsulation above the C implementations. And because they're all template instantiations they will not imply any performance degradation (not with a good compiler that is, g++ is a good in in this respect).