In-Depth: Intrusive Lists

Author: by John McCutchan

[In this reprinted #altdevblogaday piece, SCEA's senior developer support engineer John McCutchan analyzes the intrusive linked list, the data oriented version of the linked list container.] I will finish off my series of articles on data oriented programming by discussing the linked list. I will detail the linked list implementation I use, the intrusive linked list, which I first encountered many years ago hacking on the Linux kernel. The intrusive linked list is the data oriented version of the linked list container. But, before I detail intrusive linked lists, I will detail the typical linked list, the external linked list, so I can easily point out it's limitations compared to the intrusive linked list. The external linked list of type T looks like this:

template<typename T>
  struct ListNode {
  struct ListNode* next;
  struct ListNode* prev;
  T node_data;
};

template<typename T>
struct List {
  struct ListNode<T> root;
};

This is straightforward enough. The node contains a pointer to the next node, the previous node and memory for a single instance of T. The list itself contains the root node. I trust we have all implemented this linked list, at school or elsewhere. I hope regular readers will notice this linked list couples memory allocation with algorithms, a pet peeve of mine. Whenever an instance of T is added to the list the following happens:

Depending on the type of T the copy could be very expensive. Another potential inefficiency is that root.next and root.prev can be NULL when the list is empty. Making the code to implement adding and removing nodes from the list unnecessarily branchy. Also, depending on the implementation the node_data memory in root is wasted or we make the code even more complex. The complexity comes from handling special cases, for example, are we adding the first node to the list, in which case put the result in root.node_data otherwise, allocate a new node and store the copy in it. Ugh. Okay, enough build up. Let me introduce the intrusive linked list:

struct IntrusiveListNode {
  IntrusiveListNode* next;
  IntrusiveListNode* prev;
};

struct IntrusiveList {
  IntrusiveListNode root;
}

Note that there is no mention of the type that the list stores. This probably seems strange at first. In particular, there is no memory to store the actual data item being stored in the list. Intrusive linked lists flip the memory layout inside out. Instead of the list node providing memory for a T, T provides memory for a list node. The 'intrusive' part of the name comes from the fact that we store the list node inside the type T. Another thing to note is that the list is circular. Upon creation this happens:

IntrusiveList () {
  // circular
  root.next = &root;
  root.prev = &root;
}

The circular nature of the list makes inserting and removing nodes simple and branch free. Add and Remove look like this:

// Add node between next and previous
void Add(palIListNode* node, palIListNode* prev, palIListNode* next) {
  node->next = next;
  node->prev = prev;
  next->prev = node;
  prev->next = node;
}

// Remove node
void Remove(palIListNode* node) {
  node->next->prev = node->prev;
  node->prev->next = node->next;
  node->next = NULL;
  node->prev = NULL;
}

The API looks like this:

// Add to head of list
void AddHead(IntrusiveListNode * node) {
  Add(node, &root_, root_.next);
}

Again, note that this list does not know or care what type T the IntrusiveListNode is stored in. Or that the IntrusiveListNode is even stored in a type that C/C++ is aware of- it can work inside a blob easily. At this point, at least one of you should be pointing out that Boost already has an intrusive linked list container type available. Great. Look everyone, it's that guy. First of all, stop using Boost. That is only half serious. But, I don't use it. It is just that the intrusive linked list that I am detailing is better than the Boost implementation because in my implementation, IntrusiveListNode, is just plain old data, allowing many of them inside a T. Unfortunately, the Boost implementation relies on T inheriting from the Boost intrusive linked list node type. Time for an example:

struct GameObject {
  char name[32];
  int health;
  IntrusiveListNode render_list_node;
  IntrusiveListNode update_list_node;
};

GameObject monkey;
GameObject crate;
GameObject banana;
IntrusiveList render_list;

To add our game objects to the render list you might write this:

Render_list.AddHead(&crate.render_list_node);
Render_list.AddHead(&monkey.render_list_node);
Render_list.AddHead(&banana.render_list_node);

Let us take a moment to look at how an intrusive list looks in memory: After looking at this diagram, you should note that as you walk render_list you don't actually point at a GameObject, but an IntrusiveList item. So, how do you recover the address of the GameObject from the update_list_node pointer that is actually used in the list? It is quite simple, you just subtract the offset from the address. Yes, you can do that. You get the offset with offsetof:

size_t offsetof(type, member);

What is that you say? offsetof is only valid for plain old data? You cannot use it when you have diamond virtual inheritance? Uh oh, that guy is back. Yes, you are correct. But, luckily no sane programmer would ever use such a thing. This might sound tedious to work with. Having to walk the list using IntrusiveListNode pointers and apply the offset when you want the data is definitely not as nice as the standard linked list implementation. To solve this, you create a list node iteration helper:

template <typename T, size_t offset>
struct IntrusiveListForeach {
  …
}

Aside from the expected, Next() and Prev() functions for moving along the list, the GetListEntry() function applies the negative offset and returns a pointer to data associated with the list. IntrusiveListForeach also has a Remove method that removes the node safely:

void Remove() {
  palIListNode* safe_next = current->next;
  list_->Remove(current);
  current = safe_next;
}

Compared to the external linked list, the intrusive linked list decouples memory allocation from the container itself. Meaning that to add something to the list, you do not necessarily need to perform an allocation. A side effect of this decoupling is that the linked list container never copies the data by calling the copy constructor. This will avoid many unnecessary copies. You could even add some static data to a list without creating a copy at run time. Another benefit of the intrusive list is that the list node and the surrounding data are guaranteed to be share a cache line, you can even place it strategically! The circular implementation allows the core list manipulation routines to be implemented without branches and very little code (Note: circular list implementations are not restricted to intrusive linked lists). Unlike the Boost intrusive linked list, this implementation does not use inheritance. A downside of this approach, as discussed in my previous article is that the debugger is not very helpful at displaying this structure out of the box. If you're going to spend the time implementing your own container structures, it is very little extra work to teach your debugger about them. I have both an intrusive and external in my container library. I have not done this, but, it should be possible to implement an external implementation on top of the intrusive. I should note that I rarely use linked lists anymore. Dynamically sized arrays are almost always more efficient because they are packed tightly. In cases where you need to add/remove items from arbitrary locations and keep the order (stability), a linked list is still a good bet. What do your linked list look like? Does it decouple memory allocations from the container work itself? Can it work inside a blob? I am always interested in hearing about your ideas. Yes, even if you are that guy. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]