Hi I’m developing game with SDL2.0 and C.
I’m currently using Linked list for it but that is kinda slow for searching.
I heard array is faster than it because of high Cache Hit Rate,
But with large amount of data array requires a long time to add/del.
I would apreciate any advice.
This is only true if the order of the elements in the array must be preserved after an element is deleted/inserted. If the order is not important, adding, inserting and removing elements may have O(1) complexity.
Since arrays are much better cached, using them is often a better solution, especially for large sets of elements. You can also consider using multiple arrays instead of one (for specific types of objects separately), so that you have easily cacheable sets on the one hand, and on the other hand, to reduce the time-consuming search.
For more advanced data sets, it is worth using more sensible structures, such as trees. However, it all depends on the specific case — there is no one best solution for all problems.
Appreciate for your reply
First time, I tried 2 methods for array, 1 is the method that write tail data to deleted data
and another 1 is the method that push deleted data number to stack and insert data to number in stack when I need to insert
Then I realized I need to or I should sort in order of drawing.
In this case, is linked list still better?
Does this work well with a large sized struct? my struct has more than 200Byte(perhaps).
If it doesn’t work, I will separate it with adding pointer to access data
Sure, to reduce searching cost, I separete it to wall, character, moveless wall,etc…
But its linked list
Alright, I’m going to learn more data structs.
Not necessarily.
Note that if you can’t or don’t want to copy the objects for whatever reason you can still sort an array of indices or pointers.
If you don’t have many objects then it probably doesn’t matter much what you do (as long as it works correctly) but if you have very many objects then more sophisticated algorithms might be needed. Note that some sorting algorithms that are normally not the fastest, such as insertion sort, can be very efficient when the elements are almost sorted.
With larger objects it might be tempting to use an array of pointers. At least you get cache locality within the objects and moving the elements will be faster because you just need to copy pointers.
A linked list might also be fine if you don’t need random access.
Also think about if and how you’re going to refer to the objects from other parts of your program. If you’re storing long-lived pointers to the objects throughout the code then you need to pick a strategy that doesn’t copy the objects around because the memory locations need to stay the same. If you instead hold on to indices then you need to make sure the positions in the array don’t change.
There are many trade-offs and sophisticated algorithms and data structures that can be used but for a “simple” game it doesn’t have to be optimal in terms of performance, it just needs to be good enough, so don’t overcomplicate things.
Oh, so you already have a performance problem? It’s difficult to say too much about this without knowing more about the situation (e.g. what you’re searching for and why). Most efficient is of course if you can avoid searching all together. If you divide the objects into smaller groups then you might be able to reduce the number of objects that you need to search.
For example:
- Accessing the object directly using a pointer or index is faster than searching for it using a name or ID.
- Look-ups by key (e.g. name or ID) can still be relatively efficient if you use a hash table. The look-up performance will normally not get worse even if you have many elements.
- If you’re “searching” for objects that have a certain property (e.g. is walking, is animated, is solid) then it might be faster if you keep a special list with those objects so that when you need to do something with them you don’t have to loop over all the objects.
- Similarly, if you’re “searching” for objects that collide with (or are close to) another object then it would be good for performance if you didn’t have to check all the objects. You might for example divide the level into “tiles” and keep a list of objects for each tile. Then you only need to loop over the objects of the tiles that are nearest. Another option to reduce the number collision checks is the “sweep and prune” algorithm (look it up if you’re interested, I’m no expert).
1 Like
It is also worth adding that Quadtree or Octree are used for very large sets of objects, depending on the number of dimensions. If it is necessary to sort the data before rendering, the matter is not so obvious, because in some cases it will be more profitable to insert elements maintaining the order, and in others, ignoring the order and sorting once, just before rendering.
Unfortunately, there is no clear answer, it all depends on the specific case. Without testing and profiling, you will never be sure whether you have chosen the best solution or not.
1 Like
Off topic, but a good optimization if you are using tiles:
If you have any walls that are long and straight, then combine those boxes all into one hit-box to test against. For complex walls with turns and corners, then try wrapping them in un-crosable lines.
This can vastly reduce time spent on collision test calculations.
If all tiles have the same size and are aligned in a grid (which is what I think about when I think about “tiles”) then you just need to check the tiles that the object overlap. Combining tiles doesn’t make sense in this scenario so I guess you’re talking about a system where sizes and positions are more dynamic.
Tile-based video game - Wikipedia
A tile-based video game, or grid-based video game, is a type of video game where the playing area consists of small square (or, much less often, rectangular, parallelogram, or hexagonal) graphic images referred to as tiles laid out in a grid.
I misspoke. … I was not thinking of a traditional tile-based game, sorry about that.
I was thinking more along the lines of non-grid based walls that use tiled images to reduce complexity.
In this situation I keep objects that I call tiles that track where I need to stamp the image on the screen as needed per frame. Then I test collision against all solid objects in the level against player and mobile enemies.
It was a big boost when I stepped back and realized that most walls are aligned and I could combine all of those aligned “tile object” wall segments back into single hit boxes.
I am admittedly a hobbyist, there probably is some kind of proximity calculation or pattern that could reduce complexity in this situation as well.
Linked lists are virtually never better, for anything. There are some edge cases where they’re useful if you really know what you’re doing, but as a general rule, anything you can use a linked list for, you can do more conveniently as an array-backed list or some other, fancier data structure.
Linked lists were the first method that computer scientists discovered, decades ago, to make a list-like structure without needing a fixed size like arrays have. But they come with a lot of drawbacks in exchange for that benefit: they’re slow to iterate, they don’t have memory locality, they aren’t indexable, and getting the size of a list is an O(N) operation.
These days, we have dynamically-resizing array-backed list structures which don’t have any of these problems. C++ calls them Vectors; most other languages simply call them Lists. Any time you might want to use a linked list, try an array-backed list instead.
1 Like
The nodes of a linked list can be more or less tight in memory because it ultimately depends on the allocator, not the list itself. So typically yes, locality is poor.
Typically no, but nothing prevents them from being indexed and the search for a node with a given index reduced to the range from O(n) down to even O(1).
Many years ago I implemented such a list whose elements were referenced by indexes, just like arrays. Additionally, I kept the pointer on the last used node for read/write so that I would always iterate away from it (towards the head or tail of the list) to reduce the number of iterations.
Only if the list implementation is limited to having a pointer to the head of the list, which is always a very poor solution and unfortunately commonly taught (from my observation).
Every time I needed to use a linked list, I declared it as a structure with a number of nodes and a head and tail pointer. Thanks to this, some common operations were simplified to O(1), such as adding a node to the end of the list and removing the head (both needed for FIFO) or such simple thing as reading the number of nodes.
However, this still doesn’t change the fact that arrays are almost always better and perform better than lists these days.
Does it have same problem as linked list? I mean locality problem.
I don’t have it yet. I’m not sure I have the plan to do it but past time when I increased number of objects as 4000(as I remembered) It happened.
But my progress is still early time, I want to reduce costs as long as I can.
I think It’s hard to change when my progress has almost done
I was only thinking about the method that reduce collision check as distance check.
I will think about this method.
I’m not sure my method is correct but, I have the plan to make similar method to this with using both I/O stream and multi-thread. I will have some “loaded tile”, and few “pre-loading tile” when center position tile changed, change some loaded tile to pre-loading tile, some pre-loading tile to loaded tile. then save old pre-loading tile with stream and load new pre-loading tile so that it will be open-world game like minecraft
…perhaps.
I don’t have reference book or something else to develop game, I only do it with my knowledge so I m not sure what the correct answer is.
I will to explain about what my objects are
They are not only rectangles,
They may be triangles, or whatever else.
And it has rotate angle.
i’m sorry for giving only few info.
I’m using C. Does C has data struct(or library someone created) such as you suggest?
Since I realized malloc in <stdlib.h> is slow to allocate/free memory,
I made similar function which returns static array address not heap one.
these arrays are categorized with size of what demanded (0B~64B,64B~256B)
Additionaly, I will add “group” as argument. Then when linked list need to do alloc, function returns specific grouped static array(closed memory) so that locality will be a bit improved perhaps. Is this true?
My linked list has next ptr and prev ptr. And head’s prev ptr is not NULL, it links tail. also, tail’s next ptr is not NULL, it links head. so I can access tail O(1), and easily searching with inversed order
How did you do?
alright,
The reason why I decided to use linked list was
that array size is not changeable. also , personally, I dislike realloc.
But I need to think about using array.
It depends… I expect it to be a little better than a linked list where the nodes have been allocated with malloc. Here I assume it’s either an intrusive list or the objects are being stored directly inside the nodes without using a “data pointer” because otherwise I don’t think the linked list would stand a chance, in terms of locality/cache friendliness that is. There are obviously other things that affects performance too.
I think the importance of locality should not be exaggerated. The problem, as I understand it, is when you access large amount of data in unpredictable ways (so that the prefetcher cannot guess what memory you will access next) but if all memory fits in cache or was accessed recently (so that it’s still in cache) then it’s not a problem.
Even linked lists can be pretty cache efficient if the nodes are stored sequentially in memory.
True, but it’s also easy to end up spending a lot of time optimizing things that doesn’t need to be optimized.
Have you used a profiler to check where your program spends most of its time? That’s where optimizations will have the most effect. Optimizing a function that takes 0.1 ms and runs once every second is most likely a waste of time.
Make sure to turn on compiler optimizations and disabled any “debug mode” when measuring performance if you haven’t already done so.
Did you use an array of pointers to the nodes? Otherwise I cannot understand how indexing can be O(1).
1 Like
When using arrays, a common technique to improve performance is to always allocate a block with spare space. This way, if you need to insert a new element into the array, you don’t have to relocate the whole thing each time. When deleting elements, the size of the array is not reduced — the space is left for the future.
The size of the new (larger) block of memory for the array can be calculated arbitrarily, often by simply multiplying the current capacity by two. Exponential growth allows you to significantly reduce the number of relocations, which significantly increases performance, at the expense of slightly higher memory consumption. The advantage is that if you always double the size, you can always shrink the block by half. and so on until I reach the starting point (in my case, the minimum is a block for 4 elements).
I recommend watch the How I program C video from Eskil Steenberg.
Additionally, there are many techniques for optimizing the use of dynamic arrays, such as allocating a fixed-size block and, when it runs out of space, allocating another block and connecting it to the previous one just like you do with list nodes. In this case, relocation of the list block never occurs. The downside is a bit more calculations during access/iteration.
Simply by storing pointer to the last used node and its index in the list. The API for using such a list provides functions that take the index of a node (just like an array), and every time data is written to or read from the node, this node is remembered. If you read a node data with a different index, the list searches for that node, always starting from the last one used, in the appropriate direction (simple index math).
A typical iteration from the first to the last node based on indexes from 0 to n-1, e.g. using a for loop, always means O(1) access, because the node next to the last one used is always taken into account. The closer the indexes of consecutively used nodes, the fewer iterations the loop will perform to search for a new node.
Random access gives complexity from O(n) down to O(1). A O(n) complexity will occur when, for example, the last used node was the one with index 0, and we jump to the node with index n-1 (from one edge of the list to the other). The closer the index of the next node is, the complexity decreases. Referring to the same node over and over again (giving the same index) gives the complexity O(1), because in this case the same node is constantly used (it is remembered) and the loop iterating through the nodes is never executed.
I wrote an article on this in 2016 and provided an example implementation in Free Pascal — Implementing a doubly-linked list with marker. The article is in Polish, here it is autotranslated into English. Today I know much more and I could probably better optimize this implementation, but it’s more about the idea than the code itself.
It is true that access to the nodes of such a list is more efficient compared to a classic list, but it still does not change the fact that such a list must iterate through the nodes and perform additional calculations related to indexes (including branching), so it will never be as efficient as typical array. It is a kind of hybrid, combining a double-linked list with arrays, i.e. with the ability to access nodes based on indexes.
1 Like
Technically nothing prevents you from trying this. However, the ability to insert a node into the middle of the chain, or to delete one at any arbitrary position, prevents you from doing so well, at least without a lot of high-overhead bookkeeping.
I disagree; I think the importance of locality can not be exaggerated. Not when it can affect performance by an order of magnitude or more.
Excuse me.
This is not about topic of datastructure but about locality.
using switch or if state with a large amount of instructions work as jump over a large amount of instructions in assembly I guess.
Does this also cause locality problem?
Should I put it to functions?