Jump to content
  • Advertisement
Sign in to follow this  
fir

practica usability of linked lists

This topic is 2157 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


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.  

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites


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.

Share this post


Link to post
Share on other sites

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 

Share this post


Link to post
Share on other sites


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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

 


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.

Share this post


Link to post
Share on other sites

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?

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!