• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
fir

practica usability of linked lists

20 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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
1

Share this post


Link to post
Share on other sites

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.

 

http://www.youtube.com/watch?v=YQs6IC-vgmo

Edited by Khatharr
2

Share this post


Link to post
Share on other sites

@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)

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

 

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.

0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites


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.  

0

Share this post


Link to post
Share on other sites

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.

2

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.

2

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.

0

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 

0

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.

0

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.

0

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.

0

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?

0

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?

 

I was asking about real life example when linked list is really usefull - really usefull i mean here that it is better to use linked

list than rewrite a problem to be using array 

-1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0