Friday, June 02, 2017

Why I love linked lists

Some people might think I hate them as they are one of the more attacked container types by data-oriented design people, but there's always a reason for using even the worst algorithms. Hence SleepSort.

Anyway, why would someone who cares about performance like linked lists? The answer lies in what they allow that other containers might not. Also it lies in the fact that I am a C++ fan, not a C# or other managed language fan.

In C++, you can have intrusive linked lists quite easily, but you also know exactly where your data is. This makes it possible to have a single item in multiple linked lists.

Q: What is the reason for having linked lists in the first place?
A: For fast delete and insertion!

Bzzz, wrong. A linked list is great for making insertion and deletion not just fast, but also to allow maintaining order (try making a map-like container that stores data in contiguous ram like an array). This order element of the linked list is for me the major reason why I use them. Even for large structures, I still prefer an array (vector), and prefer reducing the size and promoting move semantics over changing core containers. No, the linked list is a great structure for having things stay where they are, whether in memory, or in order.

So, firstly, why would you want a thing to be in multiple lists? Let's start with something simple. Rendering. I want all my "mooks" to be in a "mooks" list for updating, but I want all the "red mooks" to be in the "red mook" list for rendering specific to material. Consider how I rant about existence based processing? Well, you can have an entity that represents the behaving AI of a creature, and when and only when it's meant to be active, add its "Behaving" intrusive link into the Behaviour tick list. Even if it's not behaving, it's still got to be rendering... well, until it's two rooms away, in which case it get's dumped from that list too, but if you make a noise, then it will start behaving, but still not be rendering. In this example, the order isn't important, but you can immediately see the benefit.

What about multiple orders? Some things need to tick very infrequently, but there are a lot of them. In this case, we can add a tick time, then insert into a list based on that time. This way we only check the first few entities until we run out of time delta. Sometimes we have objects that are waiting for resources to rise. We can order them by cost, and show highlights on only the first n up to the cost.

It's worth remembering that this doesn't often work well for dynamic value calculations, where each element in the set can change value, and thus require sorting every frame. Use this technique to provide a benefit when it reduces the amount of work even attempted. If the sorting has to happen more than on just insert, then it's probably not worth the effort.

Linked lists are a data-oriented design container, because of their nature of being ordered, or being simple to extract or insert into list or rings, because they offer a way to stop processing when you are sure you are done.

Anyone caught checking to see if an item in a linked list "needs to be updated" will be shot.
Anyone caught doing a foreach over an ordered linked list will be shot.