Smartness overload – addendum

In my previous note I mentioned that IDs are my favourite form of weak references. By pure coincidence, just recently Noel made one of his Inner Product articles public and it deals with very related subject. As a matter of fact Noel’s implementation of HandleManager has been a starting point for the one I use for my home projects. I use it not only for dealing with resources, but as a general ID->pointer resolver. It can be made a little bit easier if you don’t need to handle heterogenous objects. My modifications include:

• getting rid of a type field (instead, I have multiple pools/managers),

• optimizing Get() method a little bit. I do not test if entry is active, I only compare counters. To make sure it works as intended, I modify counter when releasing resource/object, not when acquiring it. This let me to get rid of one comparison, not a big deal, but every little bit helps.

Noel made his implementation public, I encourage everyone to download it and take a look, it’s very simple, yet helpful piece of code.

One thing we still need to bear in mind is: regardless of all the optimizations, ID->ptr resolving still is quite expensive. I removed one conditional, but biggest problem here is that it’s almost guaranteed cache miss (as we’re accessing a random ID in array). Luckily, it’s one of the few places, where it really doesn’t make much sense to worry about optimization too early. In most places overhead won’t matter, in those where it does - it’s trivial to retrieve pointer and cache it.

One of the most common anti-patterns when using IDs is ID->ptr ‘cascading’. It occurs, when we call n functions in a row, each taking ID of same object and each performing conversion (or, even worse, multiple conversions in the same function). As been said before - it’s quite trivial to eliminate, though. At one point I experimented with additional debugging/optimization helper that would record every ID->ptr conversion result. Then, I’d analyze how many of them result in non-NULL pointer and replaced IDs with pointers in places where it resulted in same value in 100% of calls. For bigger projects it would probably be leass feasible, as you’d have to excercise every given scenario, but hey, food for thought, maybe worth trying.

Last thing that I cannot stress enough. You might be tempted to create a nice Handle wrapper and provide implementations of ‘>/* operators hiding ID->ptr conversion, so that Handle ‘feels’ like an ordinary pointer. Two words: DO NOT. It is a costly operation that you do not want to perform if you don’t have to and should be treated as such. If anything, it should be made as cumbersome to use as possible (ie. name it GetPointerForID instead of Get). It’s a similiar situation as I mentioned previously when talking about reference counted pointers - we don’t want ‘invisible’ methods to perform heavy/important work, let’s make it obvious.

Old comments

Mikko Mononen 2010-07-05 11:11:54

One thing I have used in the past to speed up the ID->ptr conversion is to guarantee that the pointer will be valid until the end of a frame.
Say, for a given AI, the perception system update could first check if the enemy entity is valid, query pointer and create a temporary record of it. Then the rest of the AI system can just use that pointer.
If you do such queries in a batches it may help the cache too. As another example, I have noticed very little slowdown when using handles to reference navigation mesh polygons versus using plain indices.