Going Overboard with Field Pointers

This is a follow up to the last field pointers post and I recommend you read that first. That post took a successful piece of code and used it as a hook to explain the whys and hows of field pointers in QuakeC. Today we’re going to start with another real bit of code, but this time it’s a promising-looking disaster! It does give us some more exercise with the field pointers but the new learning will be about something else entirely. Intrigued? Then read on…

A Modest Proposal

In stock quake, the following loop is used to fire entities with a targetname matching self.target:

act = activator;
t = world;
do
{
    t = find (t, targetname, self.target);
    if (!t)
    {
        return;
    }
    stemp = self;
    otemp = other;
    self = t;
    other = stemp;
    if (self.use != SUB_Null)
    {
        if (self.use)
            self.use ();
    }
    self = stemp;
    other = otemp;
    activator = act;
} while ( 1 );

This bit of code shows one of the few places that field pointers get used in the original codebase – the builtin find function takes a field pointer to specify which field is being searched over. As it stands, it doesn’t really need any more field pointers, so we’re going to extend it. Imagine that we define some extra .string fields called targetname2, targetname3, targetname4, and we want them to receive triggers just like targetname.

Today we’re going to reject the obvious solution of copy-pasting and changing the field names in each copy. This is because of a programming guideline called “Don’t Repeat Yourself”: when you find duplicated code, you should create a function housing the shared code, and call that function in each place. The reasoning goes that where the code is the same today, any change you make to one copy is probably applicable to the other copies – whether it’s fixing a bug or adding a new feature. When there is just one copy of that code, this is easy. “Duplicated” is interpreted loosely: obviously the guidance applies to blocks of identical code, but it also covers patterns where a few values change from copy to copy – these values become parameters to the new function.

We can extract the above bit of code into a new function called SUB_UseSpecificTarget, which takes a field pointer as a parameter. We can then just call it four times in a row, each time passing it the next targetname-type field. Since that was so easy, we can raise the stakes a bit more. Add some .string fields target2, target3 and target4, so that an entity can trigger multiple names at once. We can change SUB_UseSpecificTarget to also take a string parameter of the name to search for, and then call it 16 times, 4 times for each target (notice we don’t need to use field pointers this time). Finally, we can extract the pattern of calling SUB_UseSpecificTarget 4 times with the same target and different targetname fields into the SUB_UseName function, and our code looks like this:

void(string matchstring,
     .string matchfield) SUB_UseSpecificTarget =
{
    act = activator;
    t = world;
    do
    {
        t = find (t, matchfield, matchstring);
        if (!t)
        {
            return;
        }
        stemp = self;
        otemp = other;
        self = t;
        other = stemp;
        if (self.use != SUB_Null)
        {
            if (self.use)
                self.use ();
        }
        self = stemp;
        other = otemp;
        activator = act;
    } while ( 1 );
}

void(string matchstring) SUB_UseName =
{
    SUB_UseSpecificTarget(matchstring, targetname);
    SUB_UseSpecificTarget(matchstring, targetname2);
    SUB_UseSpecificTarget(matchstring, targetname3);
    SUB_UseSpecificTarget(matchstring, targetname4);
};

//inside SUB_UseTargets
    if(self.target)
        SUB_UseName(self.target);
    if(self.target2)
        SUB_UseName(self.target2);
    if(self.target3)
        SUB_UseName(self.target3);
    if(self.target4)
        SUB_UseName(self.target4);

So now our code looks lovely. We’ve managed to grow from 1 combination of target and targetname to 16, while following “Don’t Repeat Yourself”. The functions we’ve made even look reusable in other places – I can imagine calling SUB_UseName directly with a hardcoded name, or needing to only call SUB_UseSpecificTarget with the original targetname field. From the point of view of learning the code, it’s now obvious that each call is doing the same thing with a different name. If there were 4 copy-paste loops, it would take longer to conclude this. So everything is great until you run A Past and Future Secret, and the map crashes with a stack overflow after you shoot an ogre – what?

We’ve going to look at how the stack works, but I want to make something clear first. I suspect I’ve undermined Don’t Repeat Yourself somewhat by demonstrating it, then showing it introduces a crash. I apologise, that wasn’t my intent. Don’t Repeat Yourself is a really useful guideline when coding, I’d encourage this kind of refactoring wherever you can. Our code is not incorrect or buggy. What we’ve encountered here is a technical limitation of QuakeC, and getting round technical limitations sometimes means ignoring good guidelines. That’s why it’s a guideline and not a rule!

The Stack

To see what’s gone wrong, we need to know how the stack works. When one function calls another, eventually control will return to the first function. Our computer needs some way of remembering where it was in that function, and all the data that function was using. So it puts the data on a stack. If the second function calls a third then the second one is stacked on top of the first one, and so on until a function returns. The computer then takes the function at the very top of the stack and goes “ah, yes, that’s what I was doing before”. That function gets removed from the stack and made live again.

As Greg Evigan famously taught us, stack things too high and they will fall over. So how high can you stack functions in QuakeC? Well, the answer is 32 functions high – not an awful lot by today’s computing standards. Even so, you are unlikely to hit the limit in the normal run of things, especially since you get a fresh stack for every think function, every touch function – for every function that the engine starts. What caught us out is recursive calls.

A recursive call is where a function calls itself. In our case, SUB_UseTargets doesn’t call itself again directly; what’s going on is that the entities we fire call SUB_UseTargets in their own use functions. In mapping terms it’s a chain of entities targeting each other. Here’s what the stack looked like before we started tinkering:

SUB_UseTargets entity’s use function SUB_UseTargets entity’s use function SUB_UseTargets earlier functions
which set off the
chain of events

The way that we have multiple copies of SUB_UseTargets in the stack is the mark of recursion – and the stack is actually doing clever things behind the scenes to make sure they don’t clash with each other. Once we make our modifications, the stack looks more like:

SUB_UseSpecificTarget SUB_UseName SUB_UseTargets entity’s use function SUB_UseSpecificTarget SUB_UseName SUB_UseTargets entity’s use function SUB_UseSpecificTarget SUB_UseName SUB_UseTargets earlier functions

As you can see, our new code uses twice as much of the stack each time we hit SUB_UseTargets. Consequently, your chain of entities can only run half as long before you crash. Remember this digression spawned from an actual crash in a real release, this is a practical concern and we need to rethink our design a bit. Can we find a way to rewrite the code to reduce the depth of function calls, and still adhere to “Don’t Repeat Yourself”? Tune in next time to find out…

Advertisements

2 thoughts on “Going Overboard with Field Pointers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s