Why hiring is all about elimination

Question: when hiring engineers, do you look for positive reasons to hire someone (they’ve done something good, have a good capability, a particular strength or good potential), or do you look for reasons not to hire someone (not enough experience, no degree, failed a question you asked)?

On some logical level, it seems a meaningless distinction.  People are either good enough for you or not, and whether you find the good ones directly, or implicitly by eliminating the bad ones, wouldn’t seem to matter.  In practice, however, there’s a huge difference, and something I believe strongly:

While positive reasons are important, elimination is the primary basis of good hiring

Why?

#1 Comparisons

Positive reasons to hire someone tend to be unique to the individual.  Evidence of high performance in their past is clearly very specific to them.  When you look at people’s strengths, they have unique capabilities or combinations thereof.

This matters because evaluating someone accurately in a short space of time is hard, and one of the most powerful tools at your disposal is relative evaluation.  Choosing the best of 4 candidates allows you to be far more confident than deciding whether an individual is good enough in isolation.  Performing relative comparisons is best done using standard criteria, and once you have those it becomes easy to eliminate based on them.

#2 Efficiency

Looking for positive reasons to hire someone takes more time.  To discover how good a contribution someone made to a past project, you need to spend a lot of time digging (asking them questions, chasing up colleagues, or looking at the code if it was open source).

Evaluating submitted demos takes time most game studios don’t have.  Asking open-ended questions that give people a chance to excel, and judging their performance on these questions, takes much longer than setting them problems with right/wrong answers.  Attractive places to work get overwhelmed with applicants, and hiring managers have lots of other work to do!

An efficient elimination-based approach involves starting with a large pool of applicants and finding the simplest possible relevant test that can eliminate a large proportion of them.  Repeat until left with a small number.  At each stage, you can afford to spend a bit more time evaluating the candidates.  Eventually, you get down to few enough that you can afford to spend real time to look at their positive qualities, and your tests have heavily reduced the chance of them wasting your time.

#3 Bad hires are disastrous

Hiring the wrong person is like bringing a cancer or a poison into your team.  It takes a huge amount of time and effort to fix the problem and they drain energy from your existing good employees in the meantime.  Given the choice between two types of hiring mistake: (1) eliminating a candidate that would have been a great hire, and (2) hiring a bad candidate, mistake (1) is far better.  Mistake (1) can be fixed, because there are always more candidates of sufficient quality.  Your project might be delayed, but it’s generally not disastrous.

All of this means that a good interview process has to be very sensitive to possible bad attributes.  You accept that it sometimes eliminates good people, provided it doesn’t let bad people through.  Setting up multiple independent elimination hurdles is a great way to do this.  Let’s say you have a test that a bad person could pass 10% of the time.  That’s no good on its own.  But put 6 independent tests in a row with the same 10% failure rate, and the chance of a bad individual getting through them all is 1 in a million.  That’s more like it (actually, it’s unrealistically high … but you get the idea)

Just for the sake of argument, suppose that same test tends to be passed by good candidates 90% of the time.  Their chance of getting through all 6 is then about 50%.  So you will eliminate quite a few perfectly good candidates, but if you start with a few good applicants, you’ll make a hire.

Cheer up

You often see job applicants get disheartened by this. The classic situation is where someone works their heart out to do something great, advertises this boldly on their CV, and can’t understand why they get eliminated for seemingly niggly reasons.  Take this tale for example.

Don’t take elimination personally.  Keep the above reasons in mind to understand why the elimination approach is important to the employer.  It doesn’t necessarily mean you’re not good enough.  There are plenty of jobs to apply for, and most companies won’t have a problem with you re-applying after a while.  If you’re good, you’ll get past those elimination stages soon enough, and then you’ll have a chance to show your strengths

Getting the best out of a programmer

Although I don’t write much code any more, I still think of myself as a programmer; I still have programmer tendencies in everyday life, like trying to “optimise” the world around me. When I was in hospital just last week, I was quietly infuriated when they did the scan before the blood test, forcing me to wait for the lab to analyse the blood.  I was going to point out to the nurse how much more efficient it would have been to analyse the blood while I was having the scan; luckily another of my programmer tendencies (avoidance of social interaction) saved her from my grumpiness!

Yes, “we” (programmers) are an odd bunch, and one of the fascinating things about game development is the number of other disciplines that must interact closely with us during development.  This post is for you.

Maybe you’re an artist.  You might be dependent on programmers to make your tools better, allowing you to work more efficiently; perhaps you need your art to look better, or perhaps you need it compressing so you can fit more in.  Never forget: we love you really.  If it wasn’t for you, we’d have “art” like this, and we know it:

Of course, it can be a bit of a love/hate relationship at times.  You drive us bonkers with your wacky organisation of source assets, mixing multiple logical changes in a single source control check-in, or going over your budgets.  I’m sure we inflict just as much frustration in return!

Or maybe you’re a designer of game mechanics – someone who theorises about how the game should work, and requires programmers to implement your concepts.  I think you may have one of the toughest jobs on the team.  Unlike the artists, your specialism isn’t so obviously expert, because everyone’s an armchair designer with an opinion on your work.  But programmers aren’t just everyone.  We’re liable to say exactly what we think of a design in a brutally honest way; we may be upset if there’s something even slightly illogical about it, and from time to time, yes, we may appear to imply that we could do your job better than you.  I feel guilty just writing about it.  Sorry!

Whatever your role on the team, I offer two tips to get the best out of your programmers.  As a small disclaimer, I certainly don’t mean to suggest that it’s your problem to make the relationship better – but I hope you find something of use here.

#1 Give me a problem

Programmers live to solve problems: there’s really nothing we love more.  We don’t just love finding solutions: we love finding the best, most elegant solution.  So there’s nothing we find more infuriating than being handed a solution to a problem and told to go do it – particularly when the request feels inelegant or arduous. We’re going to be immediately suspicious that we’re wasting our energy, that there’s a better way to solve your problem.  If you ask a programmer to go do something and they react with doubt, negativity or a grudging manner, this is often why – and they may not even realise it themselves.  [As a programmer, it's important to become self-aware in this regard so you can respond with "hey, what are you really trying to achieve with this thing you've just asked me to do?" rather than being grumpy]

I’ve seen some artists achieve a certain degree of success by getting closely involved and specifying very precisely how they’d like their tools to work.  That’s fine, but the best artists I’ve known (best in terms of getting what they need from programmers) took the time to explain their job to the programmers: explain the challenges they face, explain what it’s like to be in an artist’s shoes using the software.  They always got better results.

Think of it another way: if you just describe a solution without the problem, even if the solution is a brilliant one, a programmer will often struggle to implement it well.  A thousand little decisions need to be made when implementing something, and without a good understanding of the problem being solved, these decisions aren’t going to be made well, adding up to a sub-par result.

On the other hand, if you explain the problem first, there’s nothing stopping you from giving solution ideas too.  We’ll understand them all the better now they’re in the context of a problem.

#2 Explain why

Sometimes, you simply have to deliver a solution rather than a problem.  It’s not practical to go to a programmer with every single problem you come across.  If you’re designing game mechanics, your entire job is to come up with a solution (the game mechanics) to a problem (a high-level project vision).  Nobody wants to take your job away from you.

When this happens, remember that programmers crave understanding.  We need to know the answer to “why?”  We can be like a five-year-old-child asking it over and over, just as maddeningly persistent and without the cuteness.  Logic rules our world, and to see someone do something illogical is hard for us.  So, take the time to explain why you took some of the big decisions.  Explain the other roads you considered and why you didn’t take them.  It might seem like a lot of effort, it might seem unfair to have to justify your work (after all, we don’t necessarily do a good job of explaining the technical decisions we’re making), but I’m not suggesting you do this simply to keep programmers happy.  You should do this because you’ll better results out of them.  By understanding why, we can implement your intentions, capture the spirit of your vision – not just the letter of a specification document.  We might disagree with your decisions sometimes, but we’ll respect the careful thought you put into them.

I’ve sometimes seen designers write out their designs in minute detail in an attempt to improve how closely the implementation matches their vision.  This is generally a big mistake.  If you use design documents as part of your process, the best thing you can do to improve them is to explain “why”.  Going one step further though, a design document isn’t a great format for explaining the process of reaching the design – so the best thing you can really do is to collaborate closely, involve other disciplines throughout, and iterate.

Universals?

I set out to write a piece about programmers, but I actually think these two tips apply generally to any human being.  You don’t go into the doctor’s and tell them what medicine you need; you tell them your symptoms.  You don’t do this just to humour the doctor, you do it because they’re experts in the problem domain.

Don’t tell experts what to do; describe the problem you want solving.  Separate your goals from your solution ideas.

And you already know that explaining why is important when asking people to do something for you.  Think of the trickier requests you make of other people in everyday life … asking a favour, demanding a refund … you know instinctively that explaining “why” improves your chances.  A famous experiment by Ellen Langer at Harvard showed that significantly more people let someone skip ahead of them in a photocopier queue when they gave a reason (90% when the word ‘because’ was used in the request, 60% without); the part I don’t like about this is that it can be used as a bit of a trick: the technique worked equally well when the reason given was completely meaningless (”because I need to make some copies”).  That’s certainly not what I was suggesting!  Apart from the fact that a good programmer would probably see through a bogus reason, always go for methods of influence that are genuine, that leave both parties better off, and that build a good relationship.

Explain ‘why’ to give people motivation and a context to what they’re doing.

Choosing a business model for a game

I just came across this post by Nicholas Lovell in response to Dave’s talk at the GameHorizon conference.  I don’t want to get into debating all of it (obviously I disagree on the “epic fail” bit!!), but item #2 really got me thinking:

My view: different business models require different gameplay. A subscription business needs a very different set of hooks to a microtransaction business or an advertising-funded business. Trying to shoe-horn a business model onto a game not designed for it is very very hard and is likely to cause huge difficulties in the future.

I think this is very much missing the point.  I wouldn’t dispute that “shoe-horning” a business model onto a game not designed for it is hard, but it doesn’t logically follow that you should build your game around a business model.  I’ve no idea what Dave actually said, still less what meaning he intended to convey, but I think there are two key reasons why Dave was right (and this is all just my personal opinion rather than RTW’s).

#1 Basic economics of consumer software

Here are the variables in how much profit you make from software:

• Development cost
• Number of users
• Pricing and payment model – how much each user pays you
• Operational costs, if your software is a service (online game, website, etc)

It’s a tricky equation because they’re all intertwined (pricing affects the number of users; number of users could affect the price you think you should charge; spending extra development cost could allow you to reduce running costs, increase price or increase users; etc etc).  But, a few simple observations help to clarify:

• Number of users is incredibly important.  The beauty of consumer software compared to other products is its ability to scale.  It costs you nothing to produce copies of the software, and the number of users has enormous scope for increase: this is the variable with the leverage in the equation, and if you want to be really successful, this is the key.
• Development cost is less important than you think, because it’s a one-off cost.  I’m not saying it doesn’t matter, but it doesn’t scale.  There’s a limit to what you can do by trying to play with that variable, particularly as any significant reduction is going to hurt quality so much that you fail entirely.
• Operational costs are far more important, because they do affect your ability to scale.  It would obviously be a mistake to price your software below its running costs unless you had a plan to change that relationship over time.
• Pricing isn’t something you can tweak to cover your costs.  Correct pricing strategy has nothing to do with your costs; it’s all about value to the consumer. So this factor is critically important, but it’s not a variable in the sense of a number that you can just play with in a spreadsheet to get the profit you want (incidentally, this fact about pricing has nothing to do with software specifically … as you’d expect, Joel Spolsky has a good article and book recommendation here).  In a creative endeavour like an online game, you typically don’t know in advance exactly what the customer’s experience will be like; you don’t know what aspects of your game will be most fun.  So you can’t possibly know what the perceived value will be, and it’s therefore very hard to think up-front about how you charge the consumer.

I would suggest that these four factors imply that your main “business model” concerns early in development should be, in order:

1. Making a great product that lots of people want to play.  Without this, you stand no chance, whereas with this, you’ll find a way to make money from it.
2. Operational running costs, as these are the main thing that could prevent a great product from being profitable.

Although I have no idea how Dave and the board approached APB’s business model, I do know for sure that the development team has paid close attention to both of these.

#2 Development (creative and engineering) considerations

Naturally, you may need to build software features to support the business model, but as an engineer, I’d say these features are always likely to be more straightforward (read: lower risk) than the creative/gameplay/fun features.  I would much rather focus on the creative stuff early on the project, when the time is right for heavy iteration and exploration of design space, and then build the business features near the end when you know what you’ve got.  I suspect this is part of what Dave was getting at: he’s a creative person and wants to nail that part of the project above all.  He understands that you can’t just plan a game design up front and implement it from a spec.  You have to iterate, you have to experience what you’re building to guide further decisions.

Finally, whichever route you take, this isn’t a binary decision.  There’s a continuum between the extreme positions of building a game entirely around a business model, and the opposite extreme of building a game with absolutely no thought to the business model.  I would expect either extreme to be a bad idea, and I’d personally interpret Dave’s position as leaning toward one end of the scale, rather than not caring at all about the business model.  The fact that we’ve managed to raise $80m of VC, and the fact that the engineering team have paid close attention to things like bandwidth, suggest that we haven’t been completely blase about the business model during development!

Debugging web traffic

I had a curious little problem recently: in our new bug database, we couldn’t play video attachments within the browser (e.g. with the VLC plugin for Firefox, or Windows Media Player embedded in IE).  You could download the video as a file and play it – fine.  You could launch a media player as an external application and play it – fine.  But embedded in the browser window, it just didn’t work.  It’s also worth pointing out that our old bug database worked fine in all cases, so it didn’t seem to be a problem in the video playback/codec department.

I’ll put the solution at the end – the question you want to ask yourself is, how does a browser plugin behave differently from the browser saving the file to disk?

I started out by using Firebug to have a look at what was going on.  If you haven’t tried Firebug, I can’t recommend it highly enough – it allows you to do all kinds of powerful debugging of what’s going on in Firefox: way, way more than I’ll describe here.  For my problem, I just used the ‘Net’ tab – it shows you all the network requests made by the browser, allowing you to inspect both the request and the response, including all the headers.  This is pretty cool but I wasn’t able to spot the problem from this: the data appeared to be transferred correctly … weird!

Oh WordPress, you make so many requests for one page!

I wondered whether the plugin was doing anything directly over the network and bypassing Firebug, and it was suggested to me that I try Wireshark.  It’s the first time I’ve used it, and it was impressive.  Within a minute or two I was inspecting all the traffic between my PC and the bug database.  It goes down to lower level protocols (you can see the raw network packets) but also provides a nice high-level (HTTP-level) summary.

Not sure what it all means, but it looks cool!

Within seconds of looking at the data, I had the solution.  Turns out, the browser plugins don’t send the cookies that the browser does.  Our bug database was configured to require everyone to log in to view data, and without the cookies, it figured you weren’t logged in.  Rather than getting video data back, the plugin was getting an HTML page saying “Access Denied”!  Interestingly, when playing the video with the plugin, the browser firstly requests the data itself (until it gets some data back, it doesn’t even know it’s going to find a video at that URL), and of course gets it successfully.  The plugin then makes a fresh request to get the data itself.  Since Firebug was showing the first request, I foolishly thought I was looking at the data being transferred correctly (and wasted a lot of time looking into slight differences in the response headers, thinking they might cause the plugin to interpret the data incorrectly).

That’s it.  Not a big deal (we quickly reconfigured the bug database so as to allow anyone to view data without logging in), but I rather enjoyed the solution.  Most of all, I thought Firebug and Wireshark were both totally awesome – highly recommended

Just making a boot

I’ve been working on APB for a little while now.  It didn’t seem worth posting about at first as there wasn’t much to see of the game publicly, but after E3, there’s plenty:

I still feel like a total newbie.  Much like Timothy at the end of the (excellent) first podcast, just “making a bloody awesome boot”, I have plenty to learn about the project.  It’s been a big change, from a project starting out to a project finishing off, from a team I helped build to a team I hardly know, from being involved hands-on with the code to having not opened the IDE once: a world of new challenges.

I don’t suppose it’s often you get to work on something this cool, and I’m very excited to be a part of it.  Here’s to shipping a bloody awesome game

Overtime, done right

We’ve all heard the games industry overtime horror stories.  ea_spouse is still the most famous example but if you work in games, you’ll know more.  I’ve heard of people that were forced to stay late every night because of a “nobody leaves until everybody’s finished” policy – with people challenging the policy losing their bonuses.  I’ve heard of another employer criticising a programmer for not looking tired enough (they started playing WoW at work).  And I’ve worked some fairly brutal weeks myself!

But how much overtime is reasonable to work on a software project?  I suspect it’s a question every software developer must confront at some point in their career (if you haven’t, count yourself lucky!).  Let’s start by caricaturing two opposing points of view I’ve heard:

1. Overtime should be avoided at all costs.  Nobody looks back at the end of their life and wishes they’d spent more time at work.  You’re much more likely to regret missed time with family and friends, or experiences you missed out on in life.  Overtime is a direct result of poor management – why should the developers pay the price for this?  You get paid your salary for a standard working day – if the project requires more effort than this, the employer should extend the schedule, hire more people or cut features.  Making great software requires top quality work, not just a great quantity – and excessive overtime leads to tiredness, reducing quality – thereby harming the product over the long run.
2. Greatness is not achieved by working 9-5 and viewing your work as just a way to pay the bills.  Making great art requires sacrifice.  If you don’t work overtime, you’re missing the chance to ship sooner and add polish.  You’re saying “that’ll do” rather than “I gave it my all”.  Adding more people doesn’t work because it’s tough to maintain quality when you hire lots of people, and increasing team size introduces all kinds of new problems (possibly even making you later).

Personally, I can see both points of view.  Part of me is highly driven, loves my work with a passion and measures myself by my success at work.  I have some definite workaholic tendencies as a result.  At the same time, I have a wonderful family that I love spending time with.  Our 3-year-old daughter changes at a frightening rate, and each stage of her development needs to be treasured before it’s gone.

Learning functional programming

Nowadays, I definitely lean more towards the “overtime is bad” end of the spectrum.  I got turned off overtime back at VIS.  It took me a while to realise, but we were working some crazy hours with no end to the project in sight.  We suffered from a basic inability of management to balance the scope of the project with the budget.  We were trapped in a classic bad publisher/developer relationship, constantly hanging by a thread, driven to a spineless position where feature creep and random changes in direction were normal.  When we finally realised NARC had slipped way behind schedule, we “renegotiated” a longer timescale that came with a ton of new work.  It wasn’t more time to put us back on schedule, it was more time so we could catch up ourselves by working harder (and an on-site producer to check up on us).  The real killer, of course, was that NARC was clearly destined to be crap (and I do say that with love).  Once I realised how futile the overtime was, I started looking for something else.

Moving to RTW

Moving to Realtime Worlds was a hugely pleasant surprise after that background, as they’re definitely an enlightened employer in this respect.  I no longer work overtime as a result of blatantly unrealistic scope or underfunding.  I do still work overtime, generally a steady-but-low amount – and always out of choice, to turn something good into something great, to satisfy my own pride.

We manage our projects pretty carefully, we have sufficient funding to achieve our goals and no publisher applying arbitrary external pressure.  We value the wellbeing of our employees and respect their own preferences on overtime.  In other words, we’ve eliminated all the wrong reasons for doing overtime.  That leaves us with an interesting question: what should you do then?  What place does overtime have in our projects?  What does it look like when it’s done right?  If it’s useful, what are the right reasons for doing it?

Here’s how we do it right now:

• Overtime is voluntary.  This allows people to make their own choice, depending on what they value more (achievement at work versus life outside work).  It’s easier said than done, especially when you take into account things like peer pressure that can quickly slip out of your control.
• Overtime is paid for.  I wasn’t fully sure about this at first; I thought we might be in danger of displacing intrinsic motivation.  That may still turn out to be the case; it’s too early to tell.  But I like the positive intent: it says “we value our employees’ time”, loud and clear.  I’ve noticed that it looks attractive when we’re recruiting.
• Overtime is valuable in moderate, sustainable amounts.  For one thing, it’s incredibly hard to hire top quality developers – so a bit of overtime from your existing team can make a lot of sense.  Secondly, the resourcing demands of a project aren’t constant across time, and standard hiring mechanisms are too slow to react to short-term adjustments (plus, reducing headcount is best avoided whenever possible, for obvious reasons).  Finally, strategic use of overtime can unlock rewards out of proportion to the effort invested – for example when one programmer stays late to make a critical pipeline improvement for the art team to use the next day.
• Extended, excessive periods of overtime are harmful, and we can make world-class products without them.

We’re definitely still finding our way; this is very much an emerging view that changes over time (hopefully always for the better!)

The finishing line

The main question I’ve been struggling with recently is whether overtime really needs to be weighted more towards the end of the project.  This weighting seems to be pretty standard, but does it have to be that way?  My first thought is, why should it be more valuable at the end?  Couldn’t it be equally valuable early on, where discovery of new techniques, invention of new gameplay concepts, and large boosts to artist productivity (by tool and pipeline improvements) are most likely?  And isn’t it best (as an employee) to spread your overtime relatively evenly across a project, ensuring a sustainable level and avoiding all-out crunch?  Sure, it’s psychologically easier to accept overtime when the finishing line is in sight – particularly when your product has a chance to be great – but it still doesn’t seem good for your personal life, particularly when “the end of the project” can last quite a while!  And whether it’s good or bad, the curiosity inside me wants to understand why things are the way they are.

The main reason I can see is that the end of a project is your only real deadline.  Every other deadline is non-final and has wiggle room.  You can easily choose to polish later, cut features, hire extra developers or delay the ship date when you have trouble meeting an intermediate deadline.  But the end is different:

1. Once you’ve arranged a ship date with distribution and marketing, it becomes outrageously expensive to move it.
2. Once you’ve placed expectations of feature set with the press and the public, it can really harm your product’s public image (and hence sales) to cut things.
3. Simply being “final” means there are no opportunities to make adjustments and change the course of the project.

These reasons seem compelling to me.  Here are a couple of other reasons I’ve heard:

• Once you prepare to release your game for real, your quality standard goes up; very few people are able to retain that kind of quality bar early on.
• The amount of work required to truly reach “done” is always more than you think.

I don’t like these two.  These two, in principle, come under the “bad management” category for me.  Granted, they aren’t the most outrageous examples of bad management; they’re more like the difference between decent and outstanding management.  But ultimately, ensuring that there isn’t a huge pile of unexpected work at the end of the project is a management responsibility and not an excuse for overtime.

It all depends

Views on overtime are highly context-sensitive.  It depends on the project (I’d work overtime far more readily on a project that has a chance to be great), the employer (particularly whether they’re a new start-up or an established place with a revenue stream) and most of all the employee.  My own views are constantly developing.

How do you view overtime?  If you’ve worked somewhere that’s “done it right”, do tell

Stupid evil cancerous liars, I hate you!

Everyone knows singletons are bad, right?  I mean, they’re stupid, they’re evil, they’re pathological liars, they cause cancer, this guy hates them, and they bring people down.

But in the rush to condemn, sometimes people lose precision.  I can understand why, as the problems can be infuriating, but it’s important to be precise about exactly what aspects of singletons cause problems.  For example, I love some of Miško Hevery’s writing on the testability implications, but he gets pretty confused when he starts talking about how static functions are bad in themselves and forgets entirely about a functional style of programming.

Steve Yegge doesn’t have a problem being precise, but he does throw in some generalisations on top:

the Singleton pattern is a throwback to non-OO programming. It’s a lifeline for people who didn’t understand a single word that the Gang of Four were trying to say. I don’t know how it got in there in the first place — some political OOPSLA pressure, no doubt — but it doesn’t belong in there. It’s Evil.

That’s fine – his writing is hilarious – but it’s a bit dangerous to imitate it without fully understanding the real substance of the argument.

Being precise is particularly important when people create non-standard singletons: classes that don’t follow the design pattern to the letter, but which have similar features (and problems).  So, here are three separate aspects of singletons that I thought were worth teasing out.

Enforced singularity

Most obviously, a singleton enforces the fact that there’s a single instance of some data.  The classic pattern achieves this by hiding the constructor and only creating one instance internally, but this can also be done with static data (in the extreme, an all-static class).

Now this enforcement can be good or bad.  If it’s genuinely important that you only have one instance for your application, then it’s good.  Using the tools of your language and having the compiler enforce a desirable invariant for your application seems like a good idea.

It’s bad, however, when the situation changes and you suddenly want more than one.  It’s amazing how often you think “we could never have more than one of X” and later find that you do.  If your code allows you to change your mind quickly, this doesn’t have to be a big problem.  The big problem is when your mechanism for enforcing singularity precludes the change to ‘n‘ instances.  Some examples of hard-to-change mechanisms include:

• A purely static class
• Using a global point-of-access, like the “getInstance” method in the classic implementation (more on this in the next section)

It’s also worth noting a great rule of thumb I heard once: never enforce the singleton property in a library that you intend for reuse.  The decision on whether to allow more than one of something is an application-level one.  Don’t cripple your library!

You also often hear a similar point, expressed in terms of the “Single Responsibility Principle”: enforcing the singleton property is a separate responsibility from the logic of your class, and should therefore be separate.  Personally I find this to be rather abstract and weak – certainly not much use on a practical level in convincing someone who likes singletons!!

Global access point

In the classic pattern, restricting instantiation and providing a global point of access are one and the same, because they’re implemented in one mechanism.  But it’s worth teasing out as a concept in its own right: you can easily create a globally-accessible, widely-used instance of any class, whether it has a single instance or not.

The argument in favour of this is essentially convenience.  No matter where you are in the code, you can immediately access this functionality – no need to parameterise the current class or function with that object.

Unfortunately, this single point of access has multiple problems:

• The single-instance assumption becomes woven and entangled throughout your code.  Changing to more instances in future becomes very difficult.
• Code that uses the global access point is hiding that dependency, lying about what it uses and depends on.
• Multiple global instances communicating through global access points are tricky to initialise in the correct order.  Implementations typically devote a lot of effort to correct ordering of initialisation and termination – and these can get pretty contorted.
• Testing becomes harder as you can’t pass in a mock implementation to isolate components.

Dependency injection is the modern in-favour approach, with DI frameworks providing a level of convenience that might otherwise be missing.

Global state

There’s one final consideration: how stateful is the class?  How much does it rely on you calling its methods in the correct order, with state carrying over from one call to influence the next?  APIs that work this way are hard to use correctly, and make the calling code brittle to change.

I talked about this last time – these classes are hard to use whether or not they’re singletons.  It’s just that the problems are exacerbated by how widely an object of this type is used.  When it’s used as a local variable, it’s not a huge deal: it may make writing that function frustrating (as in my date example), but nothing more.  At the other end of the scale is an object referenced and used widely throughout your application.  A singleton is one way this can happen, but it’s by no means necessary.  It could be a “normal” object that just happens to have been passed around a lot.

Here’s where just saying “singletons are evil” could be lazy thinking.  Suppose you spent a lot of time removing the singleton pattern from a class: removing use of ’static’, removing a global point of access, refactoring all code to get access another way (perhaps introducing dependency injection).  Now suppose this class was highly stateful.  You’d still have a huge number of problems that your hard work wouldn’t have addressed.  Just a thought, but you may have been better off addressing the nature of the API before the singleton pattern!

The trouble with state

Today’s post is a slightly random collection of stories and observations, all tied together under the common theme of “state” in programming. I feel that just in the last year or so, I’ve come to understand this better as an abstract concept in its own right.  I feel that it’s helped me to connect a variety of different things from my experience – things I already knew, but hadn’t related to one another.

Anyhow, enough abstract twaddle.

State causes problems.  It causes problems because it’s not visible in your source code.  When you inspect a piece of code, you want to be able to see exactly what it does.  The more your code has hidden or unclear dependencies on external state, the more you’re missing part of the picture, and the less reliably you can reason about what the code does.  In the worst case, you have to perform some kind of global reasoning about the behaviour of your application – which can be more or less impossible to do in a watertight way.

At the same time, state is a fact of life.  Your computer is stateful.  The world is stateful.  The game worlds we simulate are stateful.  If your software doesn’t alter the state of something, it has no effect on the world, and might as well not exist.  We give a CPU a list of instructions to go and interact with the computer’s state, and most languages don’t hide this from us at all.  Why should they, when imperative programming is such a natural beginner’s metaphor?  We naturally grasp the analogy of giving a person instructions to go and interact with the world (of course, the statefulness of the world is what makes giving precise instructions so brittle – even to a person who can apply some intelligence and initiative to deal with edge cases!)

Leaving const behind

One of the triggers that set me on the path of thinking about state was moving from C++ to C# for most everyday programming.  I don’t think I was alone in thinking, “how can you write good software without const?”  Check out how angry people get about this!!

At first I thought I was just upset at missing a language feature.  It took some time to realise why missing this particular feature was so upsetting, when others (multiple inheritance, most features of templates, deterministic destruction) weren’t.  I now believe that it’s because dealing with state is completely unavoidable, and tricky to do well – and  ‘const’ is one of the main tools for dealing with the problems of state in C++.  In other words, it becomes a truly essential tool in the C++ programmer’s chest (whereas advanced features of templates, while powerful, are non-essential).  Const member functions promise not to change the state of their object, and const references restrict you to call only these functions.  Careful use of const allows you to put a great deal of automatic checking around how you deal with state, letting the compiler do the grunt work.  I now think that my level of upset was simply an indication of how much problems of state mattered to me.

Meeting immutability

While I still think ‘const’ is a great tool, C++ programmers never seem to talk much about entirely immutable data structures.  I must have read more or less all the classic books on C++, and I can’t think of any references to the topic.  I guess it’s partly because you have const, and partly because immutable data structures naturally work better with garbage collection.  It was only when moving to C#, wondering how to cope without const, that I discovered and understood immutability.  I guess it’s one thing I missed out on by doing maths instead of CS at university, although I wonder how many CS students really grasp the significance of immutability in a functional programming course.  I think it’s one of those things you learn so much better when you’ve suffered first-hand from the problems it solves.

Immutable objects give you all the benefits of const correctness: you can hand them out to people and be sure they won’t change them.  But they’re even better: when you receive a const reference in C++, sure, you can’t change it, but someone else could still pull the rug from under your feet.  So they vastly simplify the reasoning involved when you look at a piece of source code.  They even simplify reasoning about how local variables work within a function.

One of the more startling illustrations I’ve seen of how immutability can simplify your code is the red-black tree.  When you write a stateful RB-tree, the tree balancing routine is rather fiddly.  Here’s one part of the insertion routine for a red-black tree, from CLR:

RB-INSERT(T, x)
  1   TREE-INSERT(T, x)
  2   color[x] ← RED
  3   while x != root[T] and color[p[x]] = RED
  4       do if p[x] = left[p[p[x]]]
  5           then y ← right[p[p[x]]]
  6                if color[y] = RED
  7                   then color[p[x]] ← BLACK
  8                        color[y] ← BLACK
  9                        color[p[p[x]]] ← RED
 10                        x ← p[p[x]]
 11                   else if x = right[p[x]]
 12                            then x ← p[x]
 13                                 LEFT-ROTATE(T, x)
 14                        color[p[x]] ← BLACK
 15                        color[p[p[x]]] ← RED
 16                        RIGHT-ROTATE(T, p[x])
 17           else (same as then clause with 'right' and 'left' exchanged)
 18    color[root[T]] ← BLACK

This is actually only about a third of the total code: the “else” clause on line 17 doubles this function, and then there are the two rotation methods that aren’t listed here.  If they hadn’t used a sentinel node, it would be even worse.

In contrast, here’s the complete insertion code for an immutable red-black tree in ML:

fun balance( (B, T(R, T(R, a, x, b), y, c), z, d)
           | (B, T(R, a, x, T(R, b, y, c)), z, d)
           | (B, a, x, T(R, T(R, b, y, c), z, d))
           | (B, a, x, T(R, b, y, T(R, c, z, d))))= T(R, T(B,a,x,b), y, T(B,c,z,d))
           | balance body = T body

fun insert(x, s) =
    let fun ins E = T(R, E, x, E)
          | ins (s as T(colour, a, y, b)) =
                if Element.lt(x, y) then balance(colour, ins a, y, b)
                else if Element.lt(y, x) then balance(colour, a, y, ins b)
                else s
        val T(_, a, y, b) = ins s
    in
        T(B, a, y, b)
    end
end

If you don’t know ML, it might look a bit alien, but you can see that it’s incredibly short, and highly symmetric: even without understanding it, there’s an elegance to it (and if you do know ML, you can see more or less at a glance that it’s correct).  Now part of its elegance (particularly its extreme compactness) is down to ML’s awesome pattern matching.  But the simplicity of verifying its correctness is substantially down to the lack of mutability, which eliminates a whole class of bugs from consideration.  If we’re being completely honest, of course I’ve chosen an example that happens to work well in immutable form.  Some data structures just don’t work at all, or don’t work well, in this form.  But I still find this eye-opening

If you enjoyed that, this book is fascinating.

Being a chump

What’s wrong with this pseudocode?  It’s something I’m sorry to say I actually wrote not so long ago:

363 currentDate.SetYear(newYear);

364 currentDate.SetMonth(newMonth);

365 currentDate.SetDay(newDay);

This was within an event handler on a calendar widget, updating the current date used by the rest of the page, based on the newly selected date in the calendar.

Here’s a gratuitous picture so that you can think about it for a second.

The answer, of course, is that those “Set” methods do more work than a straightforward setter, in order to prevent you from creating invalid dates.  Suppose the current date is initially 31st October.  Now suppose the user clicks on the day after, 1st November.  First we set the month to November: uh-oh, there’s no such thing as 31st November, so the date object helpfully wraps around to become 1st December.  Now we set the day to 1, and we’re left with 1st December – a whole month out.

How about this instead:

363 currentDate = new Date(newYear, newMonth, newDay);

On top of being correct, that’s clearer and more succinct.  I actually laughed out loud when I found that bug, and then had to explain it to Andrew next to me, whose immediate response was “Ha!  That’ll teach you a lesson for using mutable state!”  Although it’s not the best code sample, I love the fact that Andrew made the words “immutable” and “state” part of standard vocabulary for our technical discussions, to the point where we could laugh about them.

Why beginner graphics programming frustrates me

Once these concepts around state clicked for me, other things started to make sense: most noticeably, why I’ve never enjoyed using DirectX that much.  I’m one of those programmers that’s never really gotten into graphics programming, but tends to dabble with a few of the samples when a new version of DX comes out.  The classic frustration is that you have a sample which appears to render three things, let’s say sky, objects, and text overlay – and you have another sample that renders some lovely particle effects – but when you try to mix them by pasting snippets in, stuff goes wrong.  Everything’s subtly dependent on what came before, and needs to be exactly in the order given.  You insert some new particle effects, and the text display goes bonkers.  You delete the sky rendering, and objects disappear.  And so on.  It’s not that bad, but still … annoying.

It partly explains why the source code for student graphics demos is usually horrible: some poor kid has copied and pasted, randomly changed things and moved stuff up and down until it seems to work, and then it becomes magic voodoo code that they daren’t touch.

It’s a classic leaky abstraction.  Graphics is one of those interfaces to the outside world, so it’s pretty stateful to start with.  The graphics hardware itself has a whole load of state.  DirectX (and OpenGL) is just a monstrous state machine wrapping it.  While all I/O has this problem, the graphics API is just so much bigger and richer than most of the other I/O APIs, that the problems seem much worse.

Most games create further abstractions on top that take state seriously (primarily to minimise state changes for performance), and often simplify these problems.  And I’m sure it’s just the way the graphics hardware abstraction layer needs to be, so it’d be silly to complain.  It’s more just that I now understand why it can be frustrating.

Multi-core

Multi-threading is another area where state causes headaches.  Essentially, the only reason multi-threading is hard is that sharing state is hard.  Now that our machines will only go faster by adding more cores, it seems we’re being forced to embrace multi-threading where we’ve maybe shied away from it before.  In turn, we’re being forced to understand the problems state causes in ways we haven’t before.  I think this is one of the reasons for a recent rise in interest in immutable data structures and functional programming.

What about globals?

Global state is the worst kind, because global state is the hardest to reason about.  If a piece of code depends on global state, then by definition, you depend on something that could be changed by any other part of the software.  You have to understand and reason about your entire codebase, in order to understand one little bit of code.  This is not good.

The solution is to minimise those dependencies, and advertise the unavoidable ones as constructor arguments and function parameters.  That tightens the scope of your reasoning, and helps your caller: they now have some idea what factors might influence your code’s behaviour.  But it’s not always simple …

I think I’ll leave that for next time as a topic in its own right

Asteroid action!

A few people have asked for video of the asteroids game from the RTW programming contest.  Unfortunately I didn’t have time to organise capturing the actual run in the final, but I re-ran the entries just now and captured the output.  Interestingly, I’ve run the entries a few times now and the winners on the day (team 7) do seem to win consistently every time (there was a perception on the day that they were fluky with their close escapes!):

Teams 1 and 2 crash after level 1 every time too.  I followed up the comment on my previous post, and Andrew’s right – their entry wasn’t dealing with the case where there are 0 rocks around.  Our verifier didn’t check that

Organising a programming contest

A couple of weekends back, we held a team programming contest for students of Scottish Universities.  I had a great time taking part in contests like this back at school, and it was no less fun being on the organising side!  This was an unusually light-hearted event, with each team of 5 sharing a single computer (adding a bit of time-management strategy on top) – and a USB-key submission process which added some mayhem on top of everything!!

There are a number of people to thank for making this successful: from Realtime, Alex, Andrew, Riccardo, Mathew and Gorkem helped prepare and select questions, produce test data, and write software to mark the solutions.  Special thanks are due to Mathew and Gorkem for coming along and helping on the day.  Michael in HR did a great job of penetrating the defences of universities and actually finding students to take part.  Finally, Abertay provided a great venue, and their Information Officer David Grayland helped set up and make the whole thing run smoothly.

The questions and a short write-up are on our website, here; if you read on below, there are some solution hints – you’ve been warned!

Chess

(Question here, test data here)

Question 1 was supposedly there to ensure nobody got zero.  Alex told me we’d chosen something too hard, and I didn’t believe him, but he was so right.  Not only that, but nobody managed a full score, and even the winning team seemed to spend quite a large proportion of the time limit on this one.  I think the point is that it was frustratingly fiddly to implement, even though it was trivial from a problem-solving point of view.

Programmers in action!!

Circles

(Question here, test data here)

Question 2 was intended to be our ‘medium difficulty’ question, and being a videogame developer, we really wanted to get in some kind of spatial or geometric algorithm.  There were actually quite a few possible solutions here.  Firstly, you could try a naive brute-force solution:

 1 for i: 0 to n - 1
 2   for j: i + 1 to n - 1
 3     overlap? C[i], C[j]

Clearly, that’s not going to cope with the larger allowed values of N in the time limit.  There were actually a few points available for this solution, but everybody got either 0 or 100 so I guess nobody did this, at least not correctly!  The next solution I expected was to sort all the circles on their X coordinate first, and then make a small modification to the previous algorithm:

 1 for i: 0 to n - 1
 2   for j: i + 1 to n - 1
 3     if C[j].X > C[i].X + 2R
 4       break
 5     overlap? C[i], C[j]

This would actually have scored 75 points, because for typical input, the break statement ensures the inner loop runs few enough times.  Algorithms of this type are actually pretty good for real usage in a game collision system, particularly because they are easily extended to take advantage of frame coherence: in other words, the set of potentially colliding entities in one game frame tends to be nearly the same as the set of colliding entities the next frame, and you can use algorithms that benefit from the work done last frame.  Check out Sweep and Prune, for example.

So why just 75 points?  Well, the problem with the previous method is that if all the circles had the same X coordinate, you’d be back to quadratic performance.  So we had a test case worth 25 points like this.  You could sort on Y instead, of course, but our test case was actually a cross shape, so either way you’d fail.  I guess you could rotate them all a bit and then sort, but that’d be turning into slightly more work.  I like the simplicity of this code; even though you’d have lost some points, I think this solution would have been a good choice given how trivial it is to implement.  Of course, contestants didn’t know how many points they’d have lost in advance.

So, how to get full marks?  I know of at least 2 solutions that would work.  Firstly, for any kind of spatial question, it’s worth asking whether a simple spatial partitioning data structure can help – for example, a simple quadtree.  You only really need two operations on the quadtree: a recursive overlap test that counts all overlaps of a given circle with existing circles in the tree, and an insertion operation:

 1 t := Quadtree
 2 total := 0
 3 for i: 0 to n - 1
 4   total += t.overlaps(C[i])
 5   t.insert(C[i])

I’m not sure of the precise running time characteristics of this, but it would have scored full points in practice.  For a guaranteed O(N log N) method, there’s a divide-and-conquer solution.  This is a recursive method that finds all overlaps within a set S of circles as follows:

 1  find-overlaps(S):
 2   if size(S) < 4
 3     use brute force
 4   else
 5     L,R = partition(S)
 6     find-overlaps(L)
 7     find-overlaps(R)
 8     find overlaps between L and R

We partition S in half, based on X coordinate, and recurse onto the left and right subsets.  We then have to find the overlaps crossing the partition line, which involves sorting on the Y coordinate and using something similar to our brute-force-loop-with-break solution.  To get the true O(N log N) performance, you have to implement in a way that involves sorting on X and Y just once, up front.  It’s similar to one of the standard closest pair of points solutions, which is discussed in quite a few algorithms books.

I’m sure there are many more ways to do this question.  Leave a comment at the end if you have any interesting ideas

Pebbles

(Question here, test data here)

This was the really interesting question of the lot, and definitely the difficult one!  It’s a shame that the overall time limit meant nobody really had a chance to get into it.  Alex did point out that a cheeky “always-print-Bob-wins” submission would have picked up 10 points, but nobody tried it!

Part 1 was actually not too hard.  Since each square has 0 or 1 pebbles, viewing boards as integers via their binary representation is an obvious step.  Now suppose we apply a brute-force recursive solution: to see if board position ‘b’ is winning, try all possible moves (i, j, k), and recursively ask if the resulting position is winning or not.  If you can put the board in a losing position, you’re in a winning position, and if you can’t, you’re not!  The recursion bottoms out when there are no moves left.  Provided you memoize the results of board positions, this solution only needs to look at 2^20 board positions at most, and easily meets the time limit.

Part 2 was trivial to implement: the solution to part 1 still works!  The key is that the actual number of pebbles on a square doesn’t really matter.  All that matters is whether it is odd or even

Part 3 was just plain mean.  I won’t go into all the details, but the verification routine provided gives some big clues.  You’ll want to read about the Sprague-Grundy theorem to understand it

Spaceships

(Question here)

The final part of the contest consisted of this interactive question.  We firstly ran all entries through a verification routine, which checked that programmes performed their I/O correctly and could run at a reasonable sustained speed over a period of time.  We then ran the entries head to head on the big projector screen (the source code for the game is here – all based on this project).  This was hugely entertaining, perhaps the best part of the day.  Two of the programmes crashed at the end of level 1 (I’m still not sure how they passed the verifier and yet did this – to be investigated!!) leaving two teams to battle it out.  One of them seemed to be shooting fairly randomly but moving quite sensibly, while the other one more or less stayed still but aimed at rocks.  There were a few hilarious moments where one ship was about to be destroyed by a massive rock, and was inadvertently saved by the other team’s ship

Watching the asteroid solutions fight it out

Lessons learned

Organising a programming contest for the first time, we were always going to make some mistakes.  Hopefully we’ll get to do this again next year and improve.  The biggest lessons I’m aware of were:

1. Organising the venue took much, much longer than I expected.  This left us really squeezed for time, because we couldn’t even advertise the event until we had this, so we didn’t have any applicants, which in turn meant I didn’t feel it was worthwhile spending time creating questions.
2. Our easy question clearly should have been easier.  Even though there wasn’t really any problem-solving involved, it was quite slow and fiddly to implement so it took clock time away from even the best team.
3. I’d like to expand the feedback on submission to tell candidates whether or not they passed the sample test case given with the question (on the day, we just told teams whether their solution compiled or not).  A number of teams were obviously new to this type of contest and struggled with the mechanics of getting the I/O correct, which wasn’t the point of the contest at all.  Alternatively, we could perhaps have helped out with some sample code.
4. The USB key submission process was clearly rubbish.  We didn’t expect it to be good (it was all we could do with limited preparation time), but it was worse than I thought.  Versioning of submissions was a nightmare (we had to get out ‘diff’ at one point and ask the team to point out which of 2 USB keys contained the latest one).  We lost some of the source code afterwards and were unable to send it to that team when they asked for it.  And I ended up with some malware on my laptop somehow.
5. The code we used to mark the solutions was actually very good considering the time we spent on it.  The main thing it lacked was the ability to archive the output of the solution, which would have been useful for auditing the results.  Luckily everyone enjoyed the day and entered into the (slightly amateurish!) spirit of things, so there weren’t any disputes, although a couple of teams did express surprise at getting zero on certain questions.
6. Our timetable for the day didn’t work out quite right.  The contestants clearly needed a break between part 1 and part 2, and we hadn’t allowed enough time for that (we spent that time scrambling to make up for the USB key submission process).  Then the time allowance for part 2 was too short.  We ended up extending this a fair bit, but it would have been nice to have that arranged properly in advance so we didn’t have to call security and check that we could stay in the building!!
7. We had a lot of technical problems with the interactive problem.  If you look at the source code for that, you can see we used an XNA app that started up the submissions by creating child processes and redirecting their standard input and output.  I thought this would be a nice way to do things: it kept the I/O consistent with part 1 of the contest, it ensured that a buggy submission couldn’t play havoc with the main game or the other entries by trampling on their memory, and it let us support multiple programming languages with no extra effort.  It turned out to create its own problems though: firstly, it’s fiddly to debug code that way (having to attach the debugger after the process was started); secondly, C++ entrants using cin were able to cause an I/O deadlock when their code expected a different data type to that given (and this took a long, long time to spot!); and finally, the winning team were unable to submit a working solution of any kind because the process creation call failed every time saying their exe was a bad image (recompiling it on a variety of machines didn’t seem to help … we never got to the bottom of this).
8. Having said all that, the interactive question was clearly a massive success.  Watching the entries battle it out directly on the big screen was a definite high point.  We’ll have to keep this for next year but leave more time for it and fix the technical issues.  It would also be nice to have some kind of recording or replay so we could save off a video of the final.
9. Pizza: good.

If you were there, and have any other thoughts on what was good or bad about the day, do please leave a comment below