Templated list class?!?

Really? This isn’t 1996 dude. We have the STL and the fancy new ISO approved C++11 standard. We don’t need your stupid list class.

That’s fine. Sorry. How stupid of me – please feel free to ignore the rest of this blog.

I can only apologise for having wasted your time.

My favourite templated list class

If you’re still reading, well done – you have passed the test.

You receive the +1 Spectacles of Second-Hand Perspective, and the +2 Underpants of Questionable Enlightenment.

Please continue reading.

Prelude

As other ADBAD posts about data structures have already said, there’s no such thing as a one-size-fits-all data structure.

Obviously you should definitely avoid spending time writing new data structures unless you genuinely need to, and not optimise until you find a bottleneck; but sometimes there are cases where you don’t actually need to, but if you don’t then you will maybe sleep a little less soundly at night wondering what that generic class you used is up to when you’re not looking at it.

The templated list class I’m eventually going to give you the code for definitely doesn’t fit all, and I guess the absolute need for it is questionable, but it’s still my favourite templated list class.

Why, dear reader?  That’s what I’m about to tell you.

The Backstory

It was the last console hardware transition. Our middleware provider had been bought by a large publisher and had essentially gone out of business. New consoles were appearing daily. The company decided to do a couple of work-for-hire type projects whilst we planned how to hit the next-gen.

We looked at the other middleware available at the time. We decided that we didn’t want to use Unreal and that most other extant providers were no more likely to be around forever than our previous one. After much deliberation it was decided that a small group of us should roll our own in-house engine.

What we were doing

Going from mature bleeding edge middleware to a self built engine is a big shock to the system

Our initial platforms were PS3 / X360, but we made a conscious choice to leave the door open for Wii because even the early indications were that it might end up having the biggest install base. This meant that the multi-platform architecture had to be very flexible and modular to leave room for the various platforms to be different but for our libs to work the same.

Several of the guys involved were old hands at engine code and we knew what we were doing, but even working as fast as we could, we knew that the most we’d be able to get done in any sensible timescale was the basics; and that any features we added above that would need to be directly applicable to the target game in order to make it worth our while.

What was on our mind

A lot of our core concerns in writing this engine were to mitigate against problems we’d experienced on our previous projects.

There was big picture stuff – like making sure the tool chain enabled assets to be added without needing code to be written so that the art and design teams could work effectively and iterate content without code issues slowing them up.

There was also nitty gritty stuff – for example, our previous game had had no end of problems with OOM caused by heap fragmentation. It was no-one’s fault directly – more a symptom of the fact that team sizes were growing, games were getting more complex, and tools hadn’t quite caught up – everyone was doing their own thing to get the game done, and because the game was fine until it had been running for some time none of the programmers had noticed it.

Must… Allocate… Memory… Fragmenting.

At the time we were relying on a slightly tweaked version of the basic the memory manager that our middleware provider had given us. It didn’t have the ability to do any sort of checks for fragmentation.

Heap fragmentation sucks, especially if you don’t know it’s happening. We only really found out that it was happening between alpha and beta – when QA started hammering it.

A couple of us spent a very long time tidying it all up. It was a mess. So much code existed that was blithely doing temporary allocations in amongst long term ones. Some stuff was just ill considered decisions made at 2am when under time pressure, but it turned out that a lot of it was to do with either:

• Unexpected interactions between the asset management and graphics subsystems of the middleware when used in the way that our game was using them.
• Insanely naive / inappropriate use of STL and other library code in the front end tin the code that wrote the persistent data that the gameplay relied on for settings etc. This was the killer.

It was a fairly big job to sort out, and involved several large architectural changes to the loading system of the game, plus tearing out all the STL use in our game side code.

Just to be clear, the problem wasn’t directly caused by STL but the way in which it was being used; it was quicker to tear it out than fix it – imagine a situation where someone had used STL whenever possible as opposed to where it made sense to, like having a std::vector< std::tuple< int, float > > instead of an array of a struct with an int and a float in it. And not pre-allocating the size of the vector even when it was fixed.

I’m honestly not trying to start an STL fight. This code was so insane that it managed to read the data out of a 15kb XML file and take up 750kb in memory. That was nothing to do with STL itself, but the way it had been (ab)used really didn’t help.

The upshot of all this? Our Technical Director ended up as an anti-STL extremist, and he and several others (myself included) ended up borderline paranoic about memory fragmentation.

What we did about it

When we started writing out new in-house engine, the first thing that was done to address these issues was that the technical director banned STL and we wrote our own templated container classes. Sure there were other things that could have been done, but that’s what was done.

Another thing was the creation of a memory management subsystem that had all sorts of nice features including fragmentation detection, multiple heaps for different sizes and types of allocs etc. etc.

We also set out one of our prime directives to do whatever we could to prevent fragmentation at the architectural level to make it harder for people to accidentally cause fragmentation.

So, about this template list class you mentioned…

I’ve not forgotten. Honestly.

The asset management system was on my schedule. Sure it’s pretty dry stuff, not everyone’s cup of tea, and definitely not a glory area like implementing a deferred bipolar thrumble edging render pass or whatever; but someone had to do it.

I’ll be honest, I like this sort of stuff. You get to stroke your chin and consider the “best way to do it ™”, and also have a good chance of getting the rare treat of writing code once and never having to change it again – other than the odd bug fix for a real life edge case you missed in your test runs.

With a prime directive of “prevent memory fragmentation”, I found it became very interesting. I stroked my chin and contemplatively nommed the arm of my glasses many times, discussed it over many cups of tea with other programmers, and eventually I came up with a plan that would work.

It did work, and it’s possibly the only bit of code I’ve ever written that I’ve been 100% happy with.

Simple, elegant, and competely bulletproof. Anti-fragmentation asset handling. The future.

There were a couple of teeny weeny little caveats on usage – much of the underlying architectural fragmentation resistance came from the fact it was sort of stack like; so it always unloaded assets in the opposite order to loading – but it was a small price to pay for being awesome and fragmentation proof.

That’s another story though. The important thing is that my main architectural concern was preventing memory fragmentation, and the best way that I know of to entirely reduce the risk of fragmenting memory is not to allocate or deallocate anything.

So, in an ideal world, this asset manager needed to store the managed assets in a data structure that didn’t have a fixed size, and which also didn’t allocate or deallocate memory.

Just one more tangent.

After I had been made paranoid about memory fragmentation and unintended allocations, I started to worry about the STL container classes.

Once I found out that you can mostly handle that sort of thing with an appropriate STL allocator I got over it (it still bothers me that so few programmers I’ve known seem to worry about this stuff, but that’s largely out of my control).

However, I eventually came up against a use-case with generic containers that still bothered me, and it was essentially a property of the way a generic containers have to work in order to be generic – so AFAIK there’s no work around other than a different approach.

Consider a common situation where you’ve got a known number of pre-allocated objects and you’re using a dead list and an active list to manage which are being used and which are not.

What happens when you take something out of one list and put it into another?

The link element used to store the object in the list doesn’t move with the object, but it still has to go somewhere.

I reasoned that what’s actually going on in any given templated list implementation is likely to be somewhere between the following two cases:

Worst case: a list element is newed every time I insert something into a list, and deleted every time I take it out. This is potentially one free store alloc + constructor and one destructor + free store dealloc per object moved between lists.

Best case: list elements are pre-allocated for each list so elements are used when an object is inserted and recycled when they’re removed. This still has an overhead for internal list element management, and also has to pre-allocate the maximum number of elements in both lists which is wasteful.

I honestly doubt there are many situations where this has become a bottleneck, but I just couldn’t bring myself to feel happy about the list element not moving with the object as it moves from one list to the other – it just seems wasteful and sloppy.

The way to work around this is bleedingly obvious, and is how most – if not all – heaps keep track of the memory they manage. You just put the list element into the object you’re going to store in the list.

This, as it happens, is also where the allocationless data structure comes in.

Ladies and Gentlemen…

It is my profound pleasure to present to you my favourite template list class.

(Note: 12/10/2011 – I found a bug in the code and have put the fixed code into the pastebin…)

In fact, it’s in a pastebin: 1) It doesn’t allocate.