Swizzle Lists! A nonintuitive data structure for AI War 2.

[x4000]

It really seems like there ought to be a quicker explanation for this, but to explain the fundamental goals, the pitfalls, and the usage constraints of this data type... well, data types are hard to explain if they're off the beaten path. This one is really useful, but also pretty strange.

edit: Aaaand Badger figured out the bug, which was not in this code, while I was making the video. Hopefully someone else finds this useful or interesting. ;)

[Qoojo]

For more complex types (but not too complex types?), I think you might be able to increase performance further by utilizing a preallocated memory pool. Then in the loop where you are iterating over the active list, you have two options: add the item to inactive list, or reclaim memory.

The memory pool is simply a linked list of the max number of items. When you reclaim item, it's nothing more than adding item back to the tail. To "alloc" an item, you simply get head, and set head to next item. Standard linked list stuff.

Something a bit like this:

Code: [Select]

class SwizzleListWithHeap<T> : SwizzleList<T>
{
// I don't know if you want to write your own linked list or if .NET's is good enough
LinkedList<T> linkedList;

void ReclaimItem(T item) { // Add to tail by typecasting to LinkedList<T> }
T AllocItem() { // Get head and move to next item in linked list }

}

class SwizzleListVector : SwizzleListWithHeap<Vector>
{

void? AddToInactiveList(int x, int y, int z, int w)
{
   Vector v = AllocItem(); // Pull already allocated item from head

   // set or clear all members
   v.x = x;
   ...
}

}
So what this does is avoid a bunch of memory allocation and junk, and should help performance for some usages I think.

Another thing to keep in mind is that you are not really handing out or storing just T (aka Vector in example). You would need to create something like this:

Code: [Select]

class LinkedList<T>
{
LinkedListItem<T> head;
LinkedListItem<T> tail;

class LinkedListItem<T> : T
{
LinkedListItem<T> next;
}

}
edit: Chris updated to have code blocks.

[x4000]

Very interesting -- in fact, with the classes that we have, we are doing this, basically.  So the ArcenShot class works pretty much like you describe, which is what I was referring to with pooling.  For things like Vector3, does alloc actually work?  That's a value type (struct), and so I didn't think that sort of thing would work since it's all on the stack anyway and the GC doesn't even get involved.

[Qoojo]

That's one thing I could not get a grasp fully in your video, how are the objects allocated that are placed in the swizzle list. So if they are on the stack, and no actual allocation, then this would not be useful.

To answer your question, Alloc does not allocate anything. It's tied to getting the next item in linked list.

So the LinkedList idea is to facilitate items that would be on the heap and help cut down on allocations from heap. It would allocate an array like this

LinkedListItem<T> heap[] = // allocate array of max items as determined for list

Alloc and initialize the array/linked list by setting next to the next item, then the tail's next = null;

for (int i = 0; i < (listSize - 1); i++)
{
item.next = item[i + 1];
}

head = item[0];
tail = item[listSize - 1];

So Alloc() would be nothing more than taking the head item, and pointing head to next:

if (head == null)
{
tail = null;
// List full
return null;
}
LinkedListItem<T> item = head;
head = head.next; 
item.next = null;
return item;

Then ReclaimItem would simply add item to tail

LinkedListItem<T> theItem = (LinkedListItem<T>) reclaimItem;
if (tail == null)
{
head = tail = theItem;
}
else
{
tail.next = theItem;
tail = theItem;
}

So this builds on your idea with the swizzle list by allowing you to use objects on the heap in an efficient manner. The idea is that you ask for the object, then have to manually initialize items with the equivalent of a C++ copy constructor, or simply clear the item and fill as needed, which I tried to give an example with the first post function, AddToInactiveList(...).

[x4000]

Ah, okay, I see -- in my case it wouldn't matter much.  The items that I've got are pooled elsewhere, meaning that they are generated in an order that I can't control, and are in RAM both as a managed entity and as unmanaged code attached to them via interop.  It's a bunch of objects, but they never get destroyed until program termination.  They are held in their own list, separately, and "pulled in and out of the list" (though that's not quite true, that's the effect) as needed.

Basically every time a shot of type X is fired, it just grabs the first unused shot of type X from the shot type X pool, puts it where it is supposed to be, then uses it for a while.  Later it hides it when the shot dies, and later something else uses it.

These are the objects being used in the swizzle list: I'm needing to keep track of these pooled objects in a different way while they are in use, then when they're not in use I want to efficiently forget about them.  All of the shots are allocated prior to the game even getting past the main menu, so all the allocs are long done before the swizzle list even gets any data (because nothing is put in there until a shot is actually fired).

[Qoojo]

Yep, totally pointless for your implementation of shots fired. I used a form of the above when writing simulator (non-game) to improve performance and memory allocation.

I do like your solution for compacting lists with the SwizzleList. It does appear to have the potential to lose some shots if used in a multi-threaded manner if you have the game loop adding to inactive list as a separate thread adds new shots to inactive list too.

[x4000]

Oh yes, this is definitely not threadsafe.  But for a single worker thread or the main thread, it does well.

[keith.lamothe]

Yea, we kinda take an "antelope and lion" approach to thread-safety: it's not safe at all, but as long as the antelope stays waaaay over there, everybody's fine.

[x4000]

Well, I mean, that's kind of the C# way of doing things.  Nothing is assumed to be threadsafe unless marked explicitly with the threadsafe flag.  We don't use that flag.