Prereqs: Watch this talk by Google's Chandler Carruth
What I call a "vectorized list" is a list that's implemented within a vector or array container, and thus can be cached on the CPU if the list is small. I first heard of the idea from that very video, and was excited when I figured out how to implement it. (excited enough to write this post, at least)
As a quick refresher, lists operate by having their elements contain a reference (or link) to another element that's next in line. Doubly linked lists have both a forward reference (next in line) and a reverse (previous in line) reference. In order to access a specific element, you must iterate through each of the members. Thus, random access is slow, but you can insert/remove an element anywhere within the list far quicker than it would be to do so in an array or vector. Another disadvantage lists have is that the elements can potentially span the entire memory space, disrupting CPU caches whenever the next list element is not within the cache. A worst-case scenario with lists is when each iteration between elements is a cache miss.
Cache misses with lists can be mitigated if they are restrained within a contiguous memory block, such as when they are in an array or vector container. Even though cache misses are still possible with large lists, the issue is less problematic than it would be if the list elements were scattered in memory since there is a higher probability of a cache hit. Should the data be significantly huge, the links could be held in a separate array/vector for faster iteration/seeking at the possible cost of a slower access time.
FreeSpace already has an example of a vectorized list with a fixed size, just take a look at object.cpp. The object class has two pointers in it that point to other objects, and all object instances are contained with the Objects array. There are three notable object instances that are not within the array, which are obj_free_list, obj_used_list, and obj_create_list.
These objects are in fact heads to lists within the Objects array, and have a specific function within the object management code.
- is the head of the list of objects which are unused,
- is the head of the list of objects which are in-use, and
- is the head of the list of objects which are in the process of being created
For FSO's purposes, the links there serve to speed up execution time when it needs to do iterations across Object for its various tasks. For example, when doing physics and AI routines, you'd iterate over the obj_used_list and not worry about needing to check if the instance is used or not. Likewise, if you are creating a new object you'd use the first element on the obj_free_list, init a few things, then pass it to the obj_create_list for some potential parallel processing goodness. (As far as I'm aware, FSO doesn't do a parallel process here, it allocates objects first then proceeds to create them, but it is entirely possible for the two to run in separate threads).
To get a vectorized list with a flexible size, you'd use a vector instead of an array as the container, and then implement the various management functions. Of particular interest is the resize() function:
resize() - grow
- Easiest to implement. Resize the containing vector to a larger size, then quickly add the new elements to the unused_list. (If a move is required, the list pointers will need to be refreshed)
resize() - shrink
- Somewhat difficult to implement. You'll have to defrag the vector so that the unused elements are the only ones lost. This can be quickly done by creating a new contiguous memory block and then moving the used elements into the front of the vector, and then refresh all of the list pointers within them.
- If you wanted to shorten the used list like what std::list::resize() does, you'd have to identify and skip over the used elements that would be deleted. This could be done at the first stages of the shrink, by iterating through the used list to the tail that'll be removed and move it into the unused list, or just simply stop once a counter reaches the new size of the list.