Jump to content

  • Log In with Google      Sign In   
  • Create Account


practica usability of linked lists


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
20 replies to this topic

#1 fir   Members   -  Reputation: -402

Like
0Likes
Like

Posted 13 September 2013 - 02:35 PM

I am writing programs a couple of years (in c) but I never ever

used a linked list - it is always arrays - arrays are sufficient and

more efficient than linked list (as many say but i do not measure the

thing) Are there a real practical cases where usage of linked list 

would be better from efficiency reason than arrays - are they realy

used ?


Edited by fir, 13 September 2013 - 02:36 PM.


Sponsor:

#2 TiagoCosta   Crossbones+   -  Reputation: 1846

Like
3Likes
Like

Posted 13 September 2013 - 03:07 PM

The only good reason to use linked lists is, IMO, if the size of the array isn't fixed and you have to resize it very frequently

Or if you need to insert or remove elements in the middle of the array very frequently while keeping the overall order of the elements (if the order doesn't matter removing an entry from an array is as easy as copying the last element to the position that you want to remove and decrement the size).

 

Most of the time (always) arrays will be faster due to better cache utilization and direct access to elements.


Edited by TiagoCosta, 13 September 2013 - 03:10 PM.

Tiago Costa
Aqua Engine - my DirectX 11 game "engine" - In development

#3 SimonForsman   Crossbones+   -  Reputation: 5721

Like
1Likes
Like

Posted 13 September 2013 - 03:11 PM

I am writing programs a couple of years (in c) but I never ever

used a linked list - it is always arrays - arrays are sufficient and

more efficient than linked list (as many say but i do not measure the

thing) Are there a real practical cases where usage of linked list 

would be better from efficiency reason han arrays - are they realy

used ?

 

The main advantage linked lists have is that you can remove or insert items in them at any position and still preserve the order of the data without having to move other data around, there are situations where that makes them more efficient than arrays or vectors.

 

Arrays and vectors on the other hand have the advantage of having all their memory in one large continous block which allows you to quickly access any element (as long as you or the compiler knows the size of each element you can calculate the adress for any element in the array) and as long as you don't store pointers the linear memory layout of the array will be far more cache friendly. (if you store pointers in an array you'll get the cache benefit when accessing the pointer but lose it when you try to access the data the pointer points at)

 

For games most data does not need to be sorted and when it has to be sorted you usually won't need to remove or insert elements in the middle of the set all that often, resizing arrays/vectors is however also very expensive but you can avoid that by allocating more memory than you need.

 

That said though, you should still learn about datastructures, there are far more ways to store data than arrays and linked lists and in games there are tons of situations where other structures are far more suitable.


Edited by SimonForsman, 13 September 2013 - 03:13 PM.

I don't suffer from insanity, I'm enjoying every minute of it.
The voices in my head may not be real, but they have some good ideas!

#4 Khatharr   Crossbones+   -  Reputation: 2775

Like
2Likes
Like

Posted 13 September 2013 - 06:26 PM

Stroustrup actually says that vectors are more efficient overall. Apparently the savings in insertion and deletion just don't add up to the cache misses that occur when traversing the list, or even the element search time to reach the insertion/deletion point. The vector can find an element and shove its data up or down very quickly, but the linked list takes a lot of cache-inefficient time to reach the element, and that outweighs the disadvantage of the shove.

 


Edited by Khatharr, 13 September 2013 - 06:33 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#5 fir   Members   -  Reputation: -402

Like
0Likes
Like

Posted 14 September 2013 - 12:42 AM

@up

 

so some say it is good to be used when there is a need for insertion when you need a specyfic order of records to be save -

but when in practice you really need correct order in such extent to use linked list ? - that is what I am asking about when you hold a characters or bullets or something like that you do not need an order (I never yet found such case ehere you need, and I am programming a couple of years)



#6 PeterStock   Members   -  Reputation: 371

Like
0Likes
Like

Posted 14 September 2013 - 01:41 AM

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.



#7 fir   Members   -  Reputation: -402

Like
0Likes
Like

Posted 14 September 2013 - 07:29 AM

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.

 

this i could call maybe an array for content + list of pointers  not pure list maybe

 

When you would need such approach (interconnected with pointers) in practice ? Wouldnt it be easier rewrite it in array way stil?

 

(I am searching for the case when list is  really better than array because from my practic experiense it may seem, that it is a practically dead way of doing things - though maybe not, and I am writing oldschool c down here)


Edited by fir, 14 September 2013 - 07:32 AM.


#8 dougbinks   Members   -  Reputation: 477

Like
3Likes
Like

Posted 14 September 2013 - 08:15 AM

A common technique I use is an array containing the items and a next index. Using indices rather than pointers gives access as fast as a pointer (using unsigned so as to avoid sign conversion), and simple load/save since you can binary write and read the data without any pointer fix ups. For an example use case see this blog post.

 

I also tend to use a number of fixed sized arrays to contain the items, so the index now becomes a block-index and node-index. To add more memory you create a new block, which gives good cache locality and no need to copy data when growing the size of data.



#9 PeterStock   Members   -  Reputation: 371

Like
0Likes
Like

Posted 14 September 2013 - 08:35 AM

 

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.

 

this i could call maybe an array for content + list of pointers  not pure list maybe

 

When you would need such approach (interconnected with pointers) in practice ? Wouldnt it be easier rewrite it in array way stil?

 

(I am searching for the case when list is  really better than array because from my practic experiense it may seem, that it is a practically dead way of doing things - though maybe not, and I am writing oldschool c down here)

 

 

I mean multiple lists of different objects, with each object having pointers to objects of the other types (in different lists). In my case, I have one list of physics objects, and another list of joints, with each joint having pointers to the 2 objects it joins. I.e. not pointers within a single list, but between lists.



#10 HappyCoder   Members   -  Reputation: 2204

Like
0Likes
Like

Posted 14 September 2013 - 11:40 AM

You probably going to use an array list over a linked list when you want to store list of something as a member variable, but understanding the idea of linked list is important because at times you need to implement the linked list data structure as part of an algorithm. The best example I can come up with is the memory heap. Free memory on the heap is stored as a doubly linked list. An array list would make memory allocation much more complicated and/or less dynamic. You will probably never implement a heap, but there are other examples.

#11 Norman Barrows   Crossbones+   -  Reputation: 1835

Like
0Likes
Like

Posted 14 September 2013 - 11:51 AM


Are there a real practical cases where usage of linked list 
would be better from efficiency reason than arrays - are they realy
used ?

 

linked lists tend to be superior in performance at in-order insertion and deletion. they tend to be lower in performance at everything else.   in-order insertion and deletion is not used much in game development, but is quite common in other types of software such as database applications.

 

for anything other than in-order insertion and deletion, the overall speed of array type data structures is as follows (fastest to slowest):

 

statically allocated array of fixed size.  fastest.

dynamically allocated array of fixed size. adds overhead of malloc & free.

statically or dynamically declared vector. adds new, dispose, constructor, destructor, and possibly type checks overhead - have to look that last one up.

std list.   as vector, adds run time type check overhead. 

 

note that this is overall speed, including memory allocations and init.

 

once these are created, all run at the same speed, except std:list, which still has type check overhead beyond the others.  


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#12 SiCrane   Moderators   -  Reputation: 9340

Like
2Likes
Like

Posted 14 September 2013 - 12:50 PM

One area where linked lists make a lot of sense is when doing memory management. For example, if you have a fixed size pool allocator you can store free chunks in a singly linked list where the pointers are stored in the free chunks. Since there's no need for traversal, the indirection for traversal costs don't matter, and since you're using space in otherwise unallocated memory there's no extra storage cost for the pointers.



#13 frob   Moderators   -  Reputation: 18419

Like
1Likes
Like

Posted 14 September 2013 - 08:12 PM

You might also find this series of 5 articles to be useful in understanding the differences between the core data structures.
Check out my personal indie blog at bryanwagstaff.com.

#14 wodinoneeye   Members   -  Reputation: 664

Like
2Likes
Like

Posted 15 September 2013 - 04:43 AM

A common technique I use is an array containing the items and a next index. Using indices rather than pointers gives access as fast as a pointer (using unsigned so as to avoid sign conversion), and simple load/save since you can binary write and read the data without any pointer fix ups. For an example use case see this blog post.

 

I also tend to use a number of fixed sized arrays to contain the items, so the index now becomes a block-index and node-index. To add more memory you create a new block, which gives good cache locality and no need to copy data when growing the size of data.

 

Ive done that when I have chunks of a gameworld which get rolled in and out of memory frequently (very large world with windowed areas and server of multiple machines).  No need to translate any data when saving it to a file - all the 'pointers' are really offsets so the chunk can be restored to any memory location and used immediately.  Objects within the chunk are on that chunks local heap - all self contained.


--------------------------------------------Ratings are Opinion, not Fact

#15 dougbinks   Members   -  Reputation: 477

Like
0Likes
Like

Posted 15 September 2013 - 04:58 AM


Ive done that when I have chunks of a gameworld which get rolled in and out of memory frequently (very large world with windowed areas and server of multiple machines).  No need to translate any data when saving it to a file - all the 'pointers' are really offsets so the chunk can be restored to any memory location and used immediately.  Objects within the chunk are on that chunks local heap - all self contained.

 

Yes, that's what I do for the octree data structure I'm using - you can see in this Youtube Video that a large level loads very quickly (in fact most of the visible delay is generating the vertex data from the voxels as the actual level loads in about 0.5s). For larger environments I plan to stream blocks (chunks), and then the block index becomes indirect, since I'll need a table of block indices to the loaded block. So far over 99.9% of indices are internal to a block since I defrag occasionally, so this indirection should add very little penalty.



#16 fir   Members   -  Reputation: -402

Like
0Likes
Like

Posted 15 September 2013 - 05:00 AM

A common technique I use is an array containing the items and a next index. Using indices rather than pointers gives access as fast as a pointer (using unsigned so as to avoid sign conversion), and simple load/save since you can binary write and read the data without any pointer fix ups. For an example use case see this blog post.

 

I also tend to use a number of fixed sized arrays to contain the items, so the index now becomes a block-index and node-index. To add more memory you create a new block, which gives good cache locality and no need to copy data when growing the size of data.

 

I ve used close way to but with static amount of arrays. 

if you use some alocated and dealocated chunks

you must reference through some pointers, ?

and this spoils a bit the image, what you got some

array of  pointers to chunk-arrays, also managment of 

alocating dealocating such chunk arrays seem to be

probably slightly complicated 



#17 dougbinks   Members   -  Reputation: 477

Like
0Likes
Like

Posted 15 September 2013 - 05:09 AM


I ve used close way to but with static amount of arrays. 
if you use some alocated and dealocated chunks
you must reference through some pointers, ?
and this spoils a bit the image, what you got some
array of  pointers to chunk-arrays, also managment of 
alocating dealocating such chunk arrays seem to be
probably slightly complicated 

 

The data in the container only uses indices - a node_index and block_index. The blocks are allocated and deallocated in the container and their pointers stored in an array (which can be of fixed size for many use cases). I can write up some simple example code at some point if there's interest.



#18 wodinoneeye   Members   -  Reputation: 664

Like
0Likes
Like

Posted 26 September 2013 - 03:40 PM

S

 


I ve used close way to but with static amount of arrays. 

if you use some alocated and dealocated chunks

you must reference through some pointers, ?

and this spoils a bit the image, what you got some

array of  pointers to chunk-arrays, also managment of 

alocating dealocating such chunk arrays seem to be

probably slightly complicated 

 

You have to maintain a 'window' of adjacent chunks anyway (in a system where only part of the world fits in memory at one time)

 

As for allocate/deallocate overhead, you can make use of 'chunk' free-pools of  regular sizes to minimize overhead (we have lots of memory these days so chucks with unused internal 'heap' space isnt that painful).  Compacting unit sized memory blocks simplifies the operation and you can have some easy auto-concatenation on freeing a 'chunk.    I used a system where the unit size was 64KB and had multiples of that when needed expansion in particularly large/detailed chunks.  You then have a slightly flexible file system which can change save location on the files if the chunk is resized.  

 

---

 

Another thing for link-lists is quick searches using simple list traversals for expected short lists  versus some much more complex hash/binarytree being used.

 

---

 

Boundry issues will always exist for any 'chunk' system going from simply ignoring whats across the boundry (chunks with walls), to 'smart' objects in a system of many adjacent chunks with registered  'watch-notification' subscription links (for chunks being run across a multi machine simulation server) and objects maintaining their own 'world representation'  to track their situation.

 

Fortunately a vast majority of game world objects are passive  (or reactive to infrequent events or have simple behaviors which the boundries can be ignored) and do not have to interact across boundries.     I usually seperated out the 'significant'/'smart' objects whos existance /influence crosses the chunk boundries for seperate more complex processing.   

 

For a large server with lots of 'chunks' rolling in and out of memory, the indexed pointer system saves a great deal of processing better used for AI and timely bookkeeping of the simulation.


--------------------------------------------Ratings are Opinion, not Fact

#19 wodinoneeye   Members   -  Reputation: 664

Like
0Likes
Like

Posted 26 September 2013 - 04:21 PM

 


I ve used close way to but with static amount of arrays. 
if you use some alocated and dealocated chunks
you must reference through some pointers, ?
and this spoils a bit the image, what you got some
array of  pointers to chunk-arrays, also managment of 
alocating dealocating such chunk arrays seem to be
probably slightly complicated 
 

 

The data in the container only uses indices - a node_index and block_index. The blocks are allocated and deallocated in the container and their pointers stored in an array (which can be of fixed size for many use cases). I can write up some simple example code at some point if there's interest.

 

I recall I used a rigorous system of forcing world chunks to stay in memory while a 'significant' object was adjacent (via subscription list/refernece count) and could use a chunk memory pointer  directly.    One of the more complex mechanism was having non-player 'significant' objects transition between 'realized' and 'abstract' operating modes   ('abstract' would be the object operating while the chunks they resided in were rolled out and they moved on a 'abstract' simplified map of the entire world and behaved in an abstract manner)

 

'dumb' objects inside the chunks just rescanned their vicinity for interactions (at a lower frequency).   The chunk itself had a 2D grid space partitioning system (link lists (indexees) in each grid cell for a list of chunk resident objects in that cell)

 

Many 'smart' objects scans likewise would do immediate scanning for interactions with dumb objects (there were such large counts that maintaining tracking lists for those was prohibitive  (so they didnt require pointer links).  Box searches in the chunks partioning grid...(and into any adjacent chunk the scanning object was close enough to)

 

 

----

 

again for efficiency most 'dumb' objects were fixed size data structures - facilitating the index+pool heap  scheme (a similar expansdion to double/triple size blocks was possible if needed.

 

Some objects were containers and had other standard object inside them (link list using indexes) and the inventor items also were in the chunk's local heap.

 

---

 

Space saving a somewhat lesser issue ??    2 byte index values (with flag values)   versus 4 byte (or bigger on 64bit systems??) for each pointer??

 

Offsets within a chunk bigger than 64 KB ?? - just multiply by 2 or 4 bytes and have the inner objects aligned on those multiples

 

These chunks also were not overly large (still with potentially hundreds/thousand  'dumb' object within them), but I was using a 15x15 2D window of regular grid chunks for the players avatar active area.

 

Terrain data (3D mesh)  was a seperate data chunk (because its full detail wasnt always required in-memory), while a simplified nav-mesh heightmap was part of the basic 'chunk'.

 

---

 

An added advantage was because this was a multiprocessor simulation an entire duplicate game world chunk could  be sent to the AI processing nodes (where significant objects ran) with low overhead processing of the transfer (roll in and discard, similar to the basic scheme) and the event/update messages could use the same indexing system.


--------------------------------------------Ratings are Opinion, not Fact

#20 Bregma   Crossbones+   -  Reputation: 4741

Like
0Likes
Like

Posted 26 September 2013 - 09:20 PM

The choice of which data structure to use where is generally the topic of a number of undergraduate courses you take to earn a computer science degree.  Many textbooks and these have been written on the topic.  To summarize all the advantages and disadvantages in a single forum post is a little simplistic.

 

Did you know you could implement a linked list using an array?  Have you considered the copy cost of the objects stored in your data structure?  What operations are going to be performed on the data (eg. splicing, projections, frequent reordering, Kruskal's algorithm for the APSP)?  Are there external references to contained data that could be invalidated by operations like insertions or removals?  Do you need indexed traversals? Random access? Atomic container modifications?


Stephen M. Webb
Professional Free Software Developer




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS