Lexical Ambiguity

Back in wow

2009-04-04T01:57:00.002-06:00

I played wow for about 2 years--closed beta for a year and then for a year after launch.

The game was a lot of fun, but when I was right about to hit 60, I realized that I didn't want to raid. The end game held nothing for me, so I stopped playing.

After wotlk came out, Jason started hyping the game up like crazy. He was having a blast, and he finally talked me back into it.

I have to say that I've actually been having a lot of fun. They got a lot of things right this time around that were just wrong before.

Instances are short (generally less than an hour once you're properly geared), and they've added lots of paths to getting good gear. Jason and I are usually able to fill a group for any heroic in about 5 minutes.

I haven't tried any raiding yet, but I think I'm going to this time around.

Oh, and if you're on Stormrage, give me a shout sometime.

Python: Removing items from a list

2008-09-27T14:34:00.004-06:00

While sitting on a plane from Santa Clara to Austin (more on that in another post), I finally sat down and wrote simple test program to determine "what's the fastest way to remove a known item from a list in Python?"

Python has some surprising performance behaviors, and removing items from a list is no exception. I came up with five methods that I thought someone might implement for removing stuff from a list, along with a bit of glue code to time everything (I used the timeit module for that, hooray for 'coming with batteries').

I've posted the code in a file, (you can get that here), including the removal functions. I'll assume if you keep reading that you've looked at the source code. We have to have some basis for communication, after all.

Here are the results of running the module on my MacBook Air, while sitting on the airplane. Your mileage may vary.


McJohn$ python listremove.py 1024 4096
name            min      max      mean     median   
ghetto_remove   0.011734 0.024060 0.015157 0.014703 
repeated_remove 0.004583 0.025112 0.012059 0.010892 
comp_remove     0.009502 0.020047 0.012323 0.011900 
old_remove      0.017689 0.035935 0.022772 0.022382 
hard_remove     0.005304 0.014384 0.007783 0.007205

What's surprising to me about this isn't that the 'hard remove' is the fastest (on average), but that it's worst case is better than the average runtime for most of the other algorithms--except for the 'repeated remove' best case, which is staggeringly good. That's actually quite shocking in and of itself, but I suspect that it would get worse if there were more collisions in the list itsef. We can test this by reducing the number of random elements allowable in the list while maintaining the list length. Here are the results for that trial:


McJohn$ python listremove.py 16 4096
name            min      max      mean     median   
ghetto_remove   0.139576 0.214912 0.175577 0.177581 
repeated_remove 2.597167 4.307188 3.578634 3.592269 
comp_remove     0.090875 0.144086 0.116044 0.116585 
old_remove      0.168973 0.239456 0.206943 0.207778 
hard_remove     0.399565 0.668813 0.534192 0.542308

It turns out that this approach makes the repeated_remove case staggeringly bad, causing a massive increase in runtime. I wasn't actually prepared for it to get this bad (I was fairly certain there was a hang in my code somewhere, the perf tanked so badly). Unfortunately, that wasn't the case--it was just that repeated_remove gets really slow in the case of massive collisions. That shouldn't be too surprising, though. In the face of an element appearing many times in the list, the repeated_remove code has an O(N^2) worst case performance. It effectively could have to traverse the list up to N times (where N is also the length of the list). Of course, each traversal in that case should be very fast, averaging 1 lookup before finding the element. Something definitely seems to be going wrong, though.

Also a bit surprising in this case is that the hard_remove performance gets quite bad. In fact, only the 'comp_remove' seems to get good performance

Python: Surprising performance characteristics

2008-09-24T17:25:00.000-06:00

There are some interesting performance properties of python. One of those, that often surprises newbies to python and veterans alike is the relatively (okay very) poor performance of numbers, versus the excellent performance of lists.

This was actually something jra101 and I stumbled across at work, when implementing an xml writer (as it turns out, python doesn't already have one, which is a bit surprising). In any event, we discovered this fact while attempting to optimize our writer. Initially, we had an API that looked something like this:


class XMLWriter(object):
  def openTag(self, tagName, attributes=None):
    self._tagStack.append(tagName)
    # other stuff

  def closeTag(self, tagName):
    assert self._tagStack[-1] == tagName
    del self._tagStack[-1]
    # other stuff

Without profiling, jra and I both decided that we could optimize this at the expense of a little safety by replacing the safety code with something a little less safe. This also made it so we didn't have to make sure the code closing the tag knew who had opened it. That version looked something like this:


class XMLWriter(object):
  def openTag(self, tagName, attributes=None):
    self._openTagCount += 1
    # other stuff

  def closeTag(self, tagName):
    assert self._openTagCount > 1
    self._openTagCount -= 1
    # other stuff

Shockingly, this version wasn't any faster than the inital version! After I thought about this for a bit, I decided that this was actually intuitive with a bit of python knowledge, although it was a little scary. In Python, everything is an object. Everything. Everything. Even numbers. Moreover, python integers have infinite precision. The code below works correctly (although slowly, as you might expect):


pow(pow(2,136), 2)

In order to support this, python cannot take optimizations for numbers that would happen in C or C++. Moreover, python can never--even in the case of simple integers--treat integers as integers. It has to evaluate the mathemetical operation, determine the result, determine whether the result fits in the old type, then possibly create a new value, and finally overwrite the old value with the new. That's a lot of work, compared to what happens in (for example) C. In C, an add operation corresponds to a single ASM instruction. Hard to compete with.

Meanwhile, list code is almost universally dispatched to a C library that is exceedingly fast and efficient. The morale of the story is one that Olivier has covered in "Mutable Conclusions" before: profile early, profile often.

Game Engine Topologies: Peer-to-peer

2008-09-23T17:30:00.000-06:00

This is part two of a two-part post on game engine topologies (first part). The first-half is not required reading to grok the second half.

Peer-to-Peer
As I mentioned in the first part of this article, a client-server topology generally makes sense when you have relatively few objects that change, as each object update requires messages to be sent to the server and then to all the clients.

In a peer-to-peer topology, the server is only sent stimulus, and that stimulus is rebroadcast to all clients. Synchronization is maintained by having all machines take the same actions at the same time. Not exactly in the wall-clock sense, but in the simulation sense (close to wall-clocks, though).

A concrete example might clear up the differences here. P2P topologies are typically used in RTSes. Imagine that while playing, you select a group of units, then order them to move to a location, then follow-up with an order for them to attack a specific unit. Afterwards, you select another group of units and order them to defend a position.

In a client-server topology, you would send updates about all of those objects as their state changed, and you would periodically have to deal with discrepancies (for example, on one client a unit is out of range but on another client the unit was killed, etc).

In a P2P topology, the messages look something like this:


StartSelection(PlayerID)
AddUnit(1)
AddUnit(2)
AddUnit(3)
StopSelection(PlayerID)
MoveSelectionTo(location)
SelectionAttack(TargetObject)
ClearSelection(PlayerID)
StartSelection(PlayerID)
AddUnit(4)
AddUnit(5)
StopSelection(PlayerID)
SelectionDefend(location)

While this seems like a lot of messages, it's actually quite sparse, particularly considering each message fits in 12 bytes or less. This means the total byte cost for all above messages is around 112 bytes. By comparison, 7 positional updates from a client-server topology would cost about the same. This could be less than one frame of movement!

So these messages are sent, and 'at some point in the future', they are executed. Even on the local machine, commands are not executed immediately! You generally (okay, always) get some sort of client feedback, the unit acknowledges via sound, or a client-only effect is played (for example, a UI element flashes), and then nothing happens for a bit. This is because of the architecture under the covers. The message has to be sent to the server, the server figures out how much time to allow for the latency of all clients, and says 'at this point in the future, everyone execute this command'.

P2P topologies have one other packet that they send 'every so often', a synchronization packet. In order to ensure that the clients are all still in sync--that is, they all still agree on the state of the universe--they need to send a packet that indicates what the state of their universe is. Although there are many ways to accomplish such a task, in practice I've only seen one implementation: CRC the entire simulation, then send the results to the server. If a client goes out of sync, you have only two choices: abort or try to regain syncronization. Although regaining syncronization is possible, I've yet to see a production title attempt it. The reason is simple: a synchronization error is often a sign that one player is trying to cheat.

Peer-to-peer topologies are effectively the 'inductive proof' of game engine topologies. We all start in the same state, and we all issue every command on the same tick. We better all be in the same state on the next tick.

An Exercise in Sanity

2008-09-14T19:42:00.001-06:00

I hate to post another "blogvertisement," but I finally started reading Braxton's blog, "An Exercise in Sanity." It's pretty interesting.

Braxton is my next-cube mate, and a pretty nice guy. He and I don't always agree (in particular, he both likes Perl and doesn't have any problems with C++), but he does have some pretty savvy views about "the real world." Anyways, go check out his blog, maybe I'll post some rebuttals whenever he gets it wrong. :)

Game Engine Topologies: Client-Server

2008-09-14T00:06:00.009-06:00

In multiplayer games, you have to communicate information between the clients to keep the game in sync. This simple requirement actually has quite a far-reaching impact in your game engine. Although there are many variations on the theme, there are two primary topologies that are used to achieve communication between clients: "Client-Server and Peer-to-peer". These topologies are used all the way from the simplest multiplayer game (think Worms), to the most complicated MMO. In a two-part post, I'll cover the topologies used by games today.

Client-Server (examples: WoW, every multiplayer FPS ever)
In a client-server topology, you have one (or possibly more) servers, and you have many clients. The clients are each responsible for a set of one or more objects, and whenever a change occurs in one of these objects, the client communicates those objects to the server, who takes appropriate action. Likewise, when other game entities change, the server pushes that information to the various clients. The clients can be thought of as basically dumb, they aren't doing much (or possibly any) world simulation and instead are just rendering the state of the world as they were told on any given frame. It's probably obvious--but worth saying anyways--that in a client-server environment, all clients are lagging behind the server by some amount of time, known as their latency. That is, while the server may be processing simulation time 30, clients might all be processing at time 27, 28, 29, or 26, depending on how long it takes for them to receive network traffic as well as render the results of the current state of the simulation.

The values of client-server topologies are that they are generally low-latency. You press a button, and the results are immediately sent to the server. The downside of such a system is that the network requirements scale linearly with the number of objects that exist in the game universe.

In Client-Server topologies, there are two basic modes: Client Authoritative (CA) and Server Authoritative (SA). Valve has also clever spin on this approach, which I'll discuss seperately below.

The primary difference between CA and SA involves the messages that are sent along with who validates that the message is legal. In a CA environment, the client sends messages like "Spawn a rocket here, travelling in this direction with this velocity," or "I hit this entity for XYZ points of damage." The server doesn't perform additional validation of these messages, which leads to an obvious problem: cheating. In fact, even if you have a completely robust and bulletproof client (which is pretty much impossible), these types of architectures are vulnerable to man-in-the-middle (MITM) attacks. It would be trivial, for example, to write a client that sat next to your game, listening for a global hotkey that would insert an automatic 'kill shot', for example. The upside of CA servers, however, are that the game feels virtually lag free for all players, because if it looks like a hit on your machine, it is a hit.

By contrast, SA architectures validate the messages on the server, and the messages are typically more of an "I tried to take this action" message. For example "I pressed fire", or "I moved forward". The server validates that the messages are legal, and then sends the appropriate response (or issues the action). The upside of this sort of architecture is that cheating becomes enormously more difficult, because there typically isn't a "I hit so-and-so for 400 points of damage" message, and even if there is, the server will take steps to validate that the message occurs in a valid and well-formed state. The downside is, of course, latency. This leads to some complex architecture to try and deal with the latency, generally called Client Prediction. I'll cover this topic in another post at some point in the future.

Team Fortress 2, along with other Valve FPS games based on the source engine, perform an interesting spin on client-server engine design. They try to pretend to be client authoritative, but are actually server authoritative. They do this by keeping a window backwards in time of up to a second (this is configurable) of where all the simulation objects have been. As said before, all clients must be running at some time slightly behind the leading edge (where the server is) due to latency (both rendering and network), even though this latency is very small. When a player takes an action (the most obvious of which is firing a weapon), he sends a timestamp to the server along with the "I've fired" message. The server gets the time stamp and essentially rolls the world backwards to that time to determine whether the player got a hit or not, and then sends the appropriate messages to all other clients. As long as the client and server agree on where objects are at a particular time, which is known as being in sync, then the client prediction is effectively completely accurate.

The effect of this logic is great for the person shooting, but can be a bit surprising for the person being shot. Imagine that you're running across the battlefield, duck behind a wall and think "I'm safe," only to find out a half-second later that you've been headshot. It's happen many-a-time to me and my friends, and it's always a little surprising.

The long way home

2008-09-10T23:06:00.003-06:00

On Friday, I'm heading back to Austin. From Lake City, it's a long drive, about 980 miles. I'm doing it in two days, because 14 hours of driving is too much for one day. I've decided to stop in Abilene, which should only be about 11 hours on the first day, and a nice short drive the next day.

There are some logistical issues with travelling with a dog as large as Samus (she weighs right around 75 pounds now), but dogfriendly.com has a listing for motels that are animal friendly, so that helps tremendously.

We've had a great time out in CO. Samus has been playing with her "cousins" Penny and Nickel. They're english pointers, and they're cute. Penny is super hyperactive and Nickel has hip dysplasia. Otherwise, they are happy and healthy. Meanwhile, we've hiked about 50 miles while we've been in colorado, plus about 5 vertical miles. I have to say that the last year of working out has made a tremendous difference for me. During a short but steep hike, we maintained a rate of 1 1/3 mph, which is actually pretty impressive as we were also doing 1100' vertically per hour. In general, I haven't been getting overly tired on or after our hikes, so that's been really great.

Although we've had fun, I'm ready to get home. I miss my wife a lot, and I think she's finally had time to miss me.

The cheapest code is the code that doesn't exist

2008-09-08T17:02:00.001-06:00

We have a common idiom in software: the fastest code is the code that doesn't execute. For non-nerds, this basically means that you want to structure your code so that you don't execute unnecessary computations.

As a corollary, I'll propose that every line of code you write (or every line of code you generate through C++ template facilities) is a line that costs you something in maintenance. Thus, the cheapest code is the code that doesn't exist.

It seems obvious, and it should be. The problem (imho) is that programmers are drinking the kool-aid. There's this myth that programming is a really hard, complicated problem. For some classes of programming, it's true. It is hard. Most programming is not hard, though. You think about a problem, you think about how you would sove the problem by hand and you speak another language to solve the problem in a more automatic way.

Unfortunately, it seems that oftentimes programmers overthink problems. They solve problems that don't exist or they try to build scaffolding around an otherwise simple problem. And that results in an unmaintainable blob. This is often done in the name of 'code reuse.' Debunking the notion that code reuse is always a good idea is a subject for another post, though.

Cheers.

Go read Cass's blog

2008-09-07T23:30:00.003-06:00

Cass used to work with me at NVIDIA. In fact, when I got hired at NVIDIA, he was my mentor in arch. He's stupidly brilliant, and yet somehow not a social retard, which is great. He's over at id now, which is a bummer because he and his family aren't in Austin anymore, but it's cool going up to visit them next to Lake Elron Hubbard.

Anyways, he writes somewhat more regularly than I do over at his blog The Hypothetical Third Dimension. Some of it is math-centric, but he usually follows that up with a segway into his second favorite topic: beer.

Has it really been 7 months?

2008-08-30T21:53:00.004-06:00

It seems like it's been awhile since I've posted, and if google isn't lieing (and I have no reason to assume they would), it's been eight months! Anyways, life has been good.

I'm currently out visiting my dad for a month or so in Lake City, CO.

View Larger Map

Lake City is a paradise if you are into outdoor activities such as hiking, camping, fishing or even hunting (I'm not a hunter, but apparently it is a popular activity here).

Samus and I have been hanging out with my dad and his two dogs, and we've been having a good time. We've been on a few hikes since we got here, including Williams Creek and Water Dog Lake Trail.

Our trip is half over, and while I'm having a great time, I'm ready to get home to see TheFish as well.

The Dude Abides

2008-01-05T13:52:00.000-06:00

I've been off work for the last couple of weeks, mostly hanging out with my wife and the in-laws.

I had a chance to watch The Big Lebowski a few times, which is one of the greatest comedies of all time. Apparently the movie sticks to me more than I'd like to admit:

Your Score: His Dudeness

You scored 89%!

"Huh? wait wait, let me, let me explain something to you. Uh, I am not Mr. Lebowski; you're Mr. Lebowski. I'm the Dude. So that's what you call me. You know, uh, That, or uh, his Dudeness, or uh Duder, or uh El Duderino, if, you know, you're not into the whole brevity thing--uh."

You are the Dude, you're keeping your mind limber by sticking to a strict drug regimen, you enjoy bowling, driving around, the occasional acid flash back. Maybe a little too much, actually, as you have failed in even the modest task that is your charge, and couldn't get to the next level of this test. But then, what else would the Dude do?

Link: The Big Lebowski Trivia Test

I am a five-year-old ass-kicking machine

2007-12-15T13:15:00.002-06:00

Through digg, I found this amusing site... You complete a shorty survey and it indicates how many five year olds you could take in a fight.

I'm proud to say that I could take 32 of the little jerks in a fight.

32

Check out your score over at their website. (Oh, but make sure you edit the HTML they give you before you post it somewhere, they include a link to a payday advance website. boo).

Integration strategies

2007-09-27T14:22:00.001-06:00

We use perforce at work. Although people talk a lot of smack about perforce, I actually find it to be generally quite acceptable at what it does.

However, I've been hitting some snags as of late. Ultimately, the issue comes down to branching, and how to keep multiple trees in sync for a particular set of tools.

Although the perforce website has a lot of white papers on various subjects, I haven't really found anything there that describes what I'm looking for. Even the white paper on branching describes exactly what I don't want. What I really want is a way to say: "Hey, even though I need to have this file replicated to these 17 different locations, they're really the same file. And if someone changes one of them, I want you to think of that as changing all of them."

Unfortunately, this is functionality that perforce adamently denies has any place in the real world. Well, here I am, maintaining around 17 trees, and I'm telling you that this functionality would probably remove about three hours a day from my work day.

The usual way we deal with this is to relocate the relevant tools outside of the branched codebase, and then point everything at the new location. Unfortunately, this is a manual, time consuming process. It sucks, and I don't like repeating work again and again (which is pretty much what I'm doing now).

So the question I put out there is: does anyone have a better way than these two methods? To sum up, here they were:

Code lives in an area that's branched, and changes need to be propogated everywhere to keep everything in sync.
Code lives in an area that isn't branched, but this is usually a hindsight realization so it requires manual updates of all related tools to pick the tool up from the new location.

Oh, and as an added complication, what do you do when 99% of the code is independent of the release branch, but the last little bit depends on code in a branch? What then?

Where are the books for experienced programmers?

2007-09-26T21:13:00.000-06:00

Recently, I've been reading books on how to develop websites using "Web 2.0" techniques (basically AJAX). What I've noticed about these books--and even other coding books in my library--is that there is a serious lack of books for the experienced, well-disciplined programmer.

I honestly find it a little insulting that every book on C++ feels the need to re-explain to me APIE (Abstraction, Polymorphism, Inheritance, Encapsulation). As does every Java book. As does every Python book. Even books that claim to cater to the experienced or advanced programmer always recover these topics.

Of course, I've heard of projects like Rosetta Code, but that's not really what I'm looking for either. For one thing, there are only 87 examples, not even covering topics I'm really interested in. (An example of a topic I'd like to see is, "How to remove items from a collection based on a predicate?") Yes, it's wiki. Yes, I could go write the article myself. No thanks.

I guess what I really want to find are books that tell you the right way to perform tasks in a certain language, or why you would prefer one method over another. For example, in which situations should I prefer to use a vector instead of a map? (I'll give you a hint, even in key-value situations there are reasons to sometimes prefer a vector to a map).

For example, let's say I'm writing a new piece of C++ code. Should I use the stl? Almost always. Is there a good logging subsystem out there that I could use to avoid rewriting a new one? Are there any libraries I should avoid? Boost.

I don't need to relearn why I should write objects or what should go into an object. Tell me how to define an object, how to use inheritance, how abstraction is implemented. Give me actual, realistic costs of making design tradeoffs. For example, how much will it cost me to call a virtual function? Is there a way I can mitigate this inside of a single class, if I really know what the type of the class is?

I'm sure, one of these days, someone will get it. Till then, I'll just continue to suffer in silence.

Thread-safe printing in Python

2007-09-26T12:23:00.000-06:00

Recently, a coworker was having issues printing from multiple threads in his python program.

After a little googling, I came upon this discussion which covered this exact topic.

At the lowest level, python appears to be threadsafe wrt a single file handle, which is good. Unfortunately, when you use the print statement, an implicit '\n' is added for you, and this apparently results in a second low-level write call, which is a seperate mutex grab.

As a result, you often get lines of text that look like this:


This text comes from Thread 1.This text comes from Thread2.
< Empty Line >
This text comes from Thread 1.This text comes from Thread2.
< Empty Line >

In this situation, you basically have two choices. You could replace your print statements with a custom written print function that grabs a mutex and adds a trailing '\n', or you could use the logging module. Even though the threadsafe print module is very short, I'd still suggest that the 'right thing' to do here is to just use the logging module.

When you decide in the future that you want to log to a tcp connection on another server, your future self will pat yourself on the back that you just used logging up front.

Cheers,

Olivier could be a Visual Studio Installer Model

2007-09-25T07:00:00.000-06:00

One of my fellow nvidians, Olivier, writes in his blog Mutable Conclusions. Prominently on his website, he features a picture of himself. I've included a copy here:

I've teased him about this mercilessly, but I think his picture would've been a perfect include in the Microsoft Visual Studio installer. Judge for yourself.

I'm a comic!

2007-09-24T21:50:00.000-06:00

A friend of mine is a (yet undiscovered) great artist. She does phenomenal 2-D work, and keeps up a daily sketch site. I only recently discovered her site, but I was excited to see that I'd been rendered as a comic.

I feel the representation is fairly accurate.

Python: Enforcing Interface Requirements

2007-07-15T14:48:00.002-06:00

I write a moderate amount of Python code for work. Not necessarily as much as I'd like, but that's a topic for another post.

A short while back, one of my coworkers asked this question at lunch: "If I'm writing an interface that I want other people to be able to use with their own new types, how do I ensure that I write my code in such a way that they can clearly and easily understand the interface that they need to implement? As an additional problem, how do I ensure that I don't accidentally break my interface requirements?"

Now, if you've written much python code at all, you're probably familiar with the term 'duck typing', which basically exerts that "if it quacks like a duck and walks like a duck, it might as well be a duck." This is probably one of python's greatest strengths as it reduces the syntactic complexity of 'templated' code; by default all functions work with all types that match the implicit interface that is their implementation.

The unfortunate side effect of duck-typing is that in order to see the exact interface that you would need to implement for an API to work with, you'd have to pore through the entire codebase of the API (!!). Clearly, that wouldn't work at all. After a bit of discussion, we came up with the following solution:

API Interfaces should begin by asserting that the arguments passed in match a specified, required Interface. This takes care of the first half of the problem, because a developer needs only to look just inside the function to determine which Interface class needs to be implemented (or derived from, if the developer so chooses).
The objects passed in should be limited (for the duration of the function) to only expose the explicit members that the interface allows for. This solves the second half of the problem, because it makes it impossible to peek under the covers other than what the Interface allows for.

After some discussion (and mail on the topic), we came up with the following implementation:

class __frozen_iface (object):
    def __init__ (self, ifspec, instance):
        for member in inspect.getmembers(ifspec):         
            if member[0].startswith ("__"):
                continue

            if not inspect.ismethod (member[1]):
                continue

            instance_attr = getattr (instance, member[0])
            if instance_attr.im_func == member[1].im_func:
                raise AttributeError, "Class '%s' has interface class implementation of attribute '%s'" % (instance.__class__, member[0])

            # bypass our internal __setattr__ since that will raise an exception
            object.__setattr__ (self, attr_name, instance_attr)

    def __setattr__ (self, name, value):
        # prevent anyone from accidentally assigning new attributes
        raise AttributeError, "Attempt to set an attribute '%s' for frozen interface class '%s'" % (name, self)

def UseInterface(ifspec, instance):
    return __frozen_iface (ifspec, instance)

Then, client code would do something like this:

class Renderable(object):
    def Draw(self, context):
        abstract # Raises an execption if we get here.

def RenderObject(someRenderable):
    someRenderable = UseInterface(Renderable, someRenderable)
    dir(someRenderable) # Outputs only 'Draw'

This could also be trivially wrapped into a decorator so your code could look like this:

class Renderable(object):

    @Interface(Context)
    def Draw(self, context):
        abstract # Raises an execption if we get here.

PS: Thanks to JimR for the cool implementation of __frozen_iface.

Structured Cleanup: Avoiding gotos

2007-05-04T00:45:00.000-06:00

I think everyone in our profession has to write code, at some point, that grabs multiple resources, then do something.

And unconditionally, that code needs to make sure to back out any resource acquisitions in cases of intermediate failure, and only back out the resources that are actually grabbed.

Normally, you see this kind of code for that purpose:


int doStuff(void) {
  char* a = (char*) malloc(100);
  if (!a) goto failure_a;

  char* b = (char*) malloc(100);
  if (!b) goto failure_b;

  // do some stuff

  // Want to keep a and b around.
  return 0;

  // Future proofing, for when we add c.
  free(b);
failure_b:
  free(a);
failure_a:
  return -1;
}

I have two problems with this code:

Updating this code requires updating both the allocation semantics and the 'free' semantics.
This doesn't lend itself towards any sort of 'pattern' which we can reuse for other things, like grabbing a mutex, semaphore, etc.

Instead of the above code, I propose that we use a system of Rollback objects. I haven't seen these in Design Patterns, but maybe they'll make their way into the next release of the book. :)


template <typename T>
class RollbackAllocator
{
  RollbackAllocator(int countToAlloc) : mAllocated(0) { mAllocated = new T[countToAlloc]; }
  ~RollbackAllocator() { if (mAllocated) delete [] mAllocated; }

  // For easy-to-read client code, no one should take ownership of allocated
  // objects until there are no further failure conditions possible. This same
  // technique can be used for 
  // ANY resource acquisition, whether it's an allocation of memory,
  // grabbing a socket, mutex, semaphore, reading a file, etc.
  T* TakeOwnership() { T* retVal = mAllocated; mAllocated = 0; return retVal; }

        T* mAllocated;
}

int doStuff(void)
{
  // If any fails, it'll throw an exception and the others will be cleaned up.
  RollbackAllocator<char> aAlloc(100);
  RollbackAllocator<char> bAlloc(100);

  // do additional things that could fail.            

  a = aAlloc.TakeOwnership();
  b = bAlloc.TakeOwnership();

  return 0;
}

The beauty of this code is its simplicity. By taking advantage of the guarantee that destructors will always be called upon exiting scope*, we ensure that a and b will always either be dealt with properly, or will be freed. Furthermore, while we do have to update the function in two places when we add a new resource acquisition, we do not have to worry about what order we TakeOwnership! Additionally, this pattern lends itself towards all sorts of resource acquisitions, whether they are mutex grabs, file reads, allocations as we've done above, etc. We can make this pattern fit virtually any resource acquisition pattern, and ensure that we have consistent, future-proof, goto-free code.

Don't get me wrong, gotos have their place. Just not in structured cleanup code.

* C++ doesn't always guarantee that destructors will be called. Any abnormal program termination, including explicit calls to exit, abort, terminate, pure virtual calls, exceptions thrown from exceptions (or destructors), or infinite loops will prevent destructors from being called.

I don't normally do this...

2007-04-25T10:59:00.000-06:00

... journaling (I refuse to call this blogging) is not something I normally do.

Anyways, my actual website, Lexical-Ambiguity is perpetually down because I'm too busy with other things to actually spend time making it work.

Here, the three of you that read this will probably find the following categories of information:

Code related topics
Exercise, fitness and weight-lifting information
Stuff about gaming
Stuff about books

That's pretty much all I've got right now. Maybe this will become more natural soon-ish. Don't color me hopeful, though.

Oh my God!! Are you serious?!

2006-08-28T20:09:00.000-06:00

On Saturday, Jim and I attempted to summit Handies.

We got up at 6:30 am, and finished prepping for our trip: filling our Camel Backs and eating a light breakfast of cereal. We commented on how neither of us had slept well. In addition to the fact that we both were really excited about attempting to climb our first fourteener of the trip, a large cold front moved into the area around 3:00 am, bringing lots of rain with it.

We left the house just after 7:00 in the Tahoe, and headed towards American Basin and Handies. As we came into view of Lake San Cristobal, we saw a sight that neither of us were prepared for: snow atop all of the mountains in the distance. I was concerned that the snow might prevent us from even reaching the trailhead, let alone summiting.

We drove on, shocked at how much snow had fallen, and arrived at the trailhead around 9:00. There wasn’t any snow in the basin itself, but all of the mountains surrounding the basin were totally covered. Shortly after we geared up for our hike, another vehicle arrived. We spoke with the driver for a few minutes, and he was also planning on hiking Handies. I joked with him that he would pass us in a few minutes, and he laughed but said he certainly wouldn’t. He said he was from Denver and the extra 5000′ of elevation was hard on him.

We started our hike up at 9:15, and signed into the log book about 10 minutes later. Five minutes later, a thunderstorm–complete with sleet–blew into the basin from the southwest. The storm totally snuck up on us, and we had just about decided to go back down and wait it out in the car when it cleared off. Jim and I discussed giving up for the day so I could go back and get more equipment (gloves, rain pants and my waterproof boots), but we decided to push on.

About 30 minutes later, we came to a fork in the trail. Unfortunately, neither of us had remembered to bring a map, so we were at a loss as to which way to go. Jim decided to go on up and scout ahead, and I said I’d wait for “Denver” to catch up with us, as he appeared to know what was going on. After “Denver” caught up with us, we decided to all hike together. We introduced ourselves, and “Denver” became Joe. We learned that Joe was an experienced 14er, and we were glad for the company. (At the time, he had summited 28 fourteeners, with plans to do seven more during the week).

The next two hours were largely uneventful, except that Jim and Joe were able to keep better pace than myself. I’m not the most physically fit person on earth to begin with, but being 10-14,000′ higher than my normal stomping grounds was hard on me. Plus the fact that my shoes were totally waterlogged and provided little traction on the 2-4″ of snow we were encountering made for a trip where I was roughly 1/2 a rest behind Jim and Joe.

About 200′ (vertical) from the summit, it got very interesting. We heard thunder coming in over the same southwestern portion of the basin. Only this time, instead of being surrounded by cliffs, we were one ridge from the summit. We discussed for a minute or two whether we should turn around and go back or whether we should press on to the summit. I wanted to go back, but said nothing because I really, really wanted to finish up Handies. Jim and Joe clearly also had summit fever and we decided that with 10 minutes of effort we could be at the summit. We would stick around at the summit for a minute or two, rest, and then head back down as quickly as possible.

Jim and Joe started heading up, when we heard another thunderclap, even closer than the last. Joe turned and began to run towards us, indicating that it was time to go. He asked us quickly if we knew what to do for lighting. For those of you who don’t, (I’d be with you), I’ll reiterate what he said:

If you feel a tingling, static charge feeling, that means that the ground around you is charged for a lightning strike.
Assume the lightning strike position. The position is crouched on the balls of your feet, your heels together, your hands over your ears and your eyes closed. You want to form a ball balancing on your feet.
Direct strikes are generally fatal.
Lightning travels along the ground. An indirect strike can cause your heart to stop, but usually (70%) you can be revived with CPR.
When caught in a thunderstorm, members of the party should keep at least 100′ between each other. The reason is that if one person is struck, the other members of the party can revive them.

Jim and I were, needless to say, terrified. Joe took out his hiking poles and began to run down the mountain. Not down the trail, the way we had come up, but straight down the mountain. After a single switchback, I realized that Joe was getting down the mountain significantly faster than I was, and I decided to take off straight after him.

I fell several times, and my hands began to get tingly. Remembering his warning, I yelled an expletive and tucked into the crouch position. I threw the metal walking stick I was using as far as I could away from me (horizontally, so I could recover it later). From behind me I heard Jim yell “Oh my God!! Are you serious?” I yelled back that I was and waited for the worst.

It never came. Thirty seconds later I realized that the tingling I was feeling in my hands was the result of their being wet and cold–from falling in the snow–not static buildup. I ran over and grabbed my walking stick and again began running down the mountain. The storm intensified, sending sleet nearly horizontally at our faces, and dark, frightening clouds up the basin towards us. I can safely say that I’ve never run for my life before… This was a first for me.

Twenty-nine minutes after we had began our descent we all caught up with one another. We had managed to drop 1000′ (vertical) in less than half an hour–the ascent up the same distance had taken us nearly three hours. By this time, the storm had almost entirely abated.

Although we weren’t technically out of the woods, we all felt much safer as there were now many more advantageous lightning targets than ourselves. We had a reasonably comfortable walk the rest of the way down the trail, back to the register and to the car.

Back at the car, we met up with some other folks who had been chased off of Redcloud due to the first thunderstorm (that had nearly sent Jim and I back home). We spoke with them for a few minutes and traded numbers with Joe, offering to buy him a meal if he called us when he came to Lake City in the next week.

I learned a few important things on this trip:

Thunderstorms while hiking at altitude are not something to mess around with.
The best path down might not be the path taken up, especially in cases of emergency.
Having a map with you is key at all times.
There are more important things than summitting. (Like living to summit another day).

Although we didn’t make it to the summit, I felt we made the right decision in turning around. My only regret is that we didn’t turn around and start back sooner.