Archive for August, 2007

Oz Report – Part 3 – Sydney Day 1

Monday, August 27th, 2007

The first day:

After 14 hours, the sun caught up with us and we landed in Sydney a few minutes before sunrise. A SE wind meant a NW approach for our 747-400, which afforded us a lovely pre-dawn view of the downtown area.

Arriving at the hotel at about 7.30am, we went straight in to breakfast while waiting for a clean available room. I decided on a full breakfast (egg, sausage, bacon etc.) and supplemented it with a muffin and some vegemite on toast. Vegemite is milder than Marmite and to my taste, not quite as nice, but I could definitely eat it if I lived in Oz (apart from the problem of it being made by Kraft Foods, part of the Altria group).

Sydney, unlike LA, is a real city. We spent some time wandering downtown and through the botanical gardens. After some time looking at the ficuses, bromeliads and cypress trees, I became aware of noises in the treetops. Looking up revealed not birds, but bats – hundreds of flying foxes roosting, stretching and occasionally squabbling over space. That was unexpected! We headed down to the water – remarking that it was strange to be on the west of the Pacific – and towards the Opera House.

The Opera House didn’t disapppoint. We walked all around it, taking plenty of photos, then stopped at the cafe next to the ferry launches where we ate a couple of sandwiches and shared a hot chocolate. The wind was a little cold and it was drizzling, so the hot chocolate was welcome, and nice – although not nice enough to get one each at $4.50 a time.

So we wandered through the CBD and downtown shopping districts before heading back to our hotel via a convenience store to pick up some staples (milk, juice, cereal, tim tams 🙂 Mini-Elbeno, no doubt a bit jet-lagged, slept a long time in the stroller and on arrival back at the hotel, told us “more bed”. We felt the same and forewent dining out in favour of room service and an early night.

Oz Report – Part 2 – The Flight

Monday, August 27th, 2007

The flight:

Mini-Elbeno: a gem. Sleeping, smiling, watching Bananas in Pyjamas on the in-flight entertainment system.

Food: mediocre, where it was edible at all. As expected.

Entertainment: Borat – hilarious. Sunshine – reasonable “hard science” content. Enjoyable. The Chaser’s War on Everything – an Aussie comedy sketch show I got by mistake while trying to watch Spiderman 3. Turned out to be the better deal, I think. Very funny, and Aussie humour is much closer to British humour than to American.

It was the quickest 14-hour flight I’ve had.

Oz Report – Part 1 – Pre-Flight

Monday, August 27th, 2007

I’m blogging this, rather incongruously, from an Aboriginal Cultural centre a little way south of Narooma in NSW. Here’s what I’ve prepared earlier while staying the hotel in Sydney for a few days:

Pre-flight:

Taxi 30 minutes late. But we are determined not to get stressed. Check in is a breeze, and security fine. But we discover at the gate that we need to be in a specific row(s) to use our car seat. This should have been handled at the checkin desk, but wasn’t, and leads to a trying conversation. Actually, it’s not a conversation, because “conversation” implies exchange of thought, and it’s clear to me that thought is only occurring on one side.

The gate agent seems helpful, but is incapable of formulating any steps in the solution to the problem. “Yeah… you can’t use the car seat in that row” he offers, with a sorry-about-that note of finality. I look at him expectantly. Nothing more. “Could we move to a row where we can use the seat?” I suggest. He punches some keys. “You could use it in rows 41 or 56.” “Can we move to one of those rows?” More keys. We wait. “They’re taken.”

An idea occurs to him: unfortunately not the right idea. “Let me get the something-or-other manager.” Before I can reply, he’s off. Mini-Elbeno passes the time by twisting and writhing in my arms and yelling good-naturedly in my ear. The something-or-other manager returns and fixes me with a steely glare that suggests that I will use the car seat in an unapproved row over her dead body, or (more likely) over my habeas-corpus-free-zone incarcerated body. I ignore her and return my attention to the gate agent, who is apparently re-checking that the approved rows are still taken.

I know he can solve this problem, so I ask, “Can we move to row 41?” But he is still unable to infer the final step of the solution, and merely notes, “It’s taken.” With an inward sigh I have known in many an interview, I suggest, “Perhaps we could swap seats with the people sitting in row 41?” The something-or-other manager says “You could absolutely do that.” Like I care about her opinion. She could sit down and start singing about gold for all I care.

But with her “approval” the gate agent is finally getting up to speed. He pages 41B & C who turn out to be a young couple who are happy to move to two otherwise identical seats in our current row. 41A has not yet checked in, and after a phone call she is bounced from her seat. The s-o-o manager disappears, frustrated by my calm persistence, and I walk down the jetway with family in tow. The flight attendant who helps me fix up mini-Elbeno’s seat has no idea of our recent tribulations, and in fact turns out not to care which row the seat’s in, or at least can offer no explanation why some rows are designated for seats. As in so many similar situations, once you’re inside the beehive, the bees allow you a lot more latitude. As we taxi on to the runway, I relax with cathartic thoughts of writing this blog post.

Exploring Pascal’s Triangle

Sunday, August 19th, 2007

Pascal’s Triangle (henceforth known as PT). You know – that thing you learned in maths. The Wikipedia entry, like most mathematical Wikipedia entries, reads (if your mathematical background is anything like mine) like “here’s a few things you might vaguely remember from school, oh and of course gleep = glorp”. Although I have to say, the PT entry is less opaque than most.

If you were lucky enough to have a “recreational maths” class then perhaps you studied PT more. I did have a recreational maths class in the 4th form (erm… 7th grade? I went to a public school with a nonstandard year numbering), but at the time I didn’t appreciate just how much higher level mathematics is intertwined (see trigonometry, complex numbers & calculus). Also, is it just me, or are curricula in general a bit light on actual number theory? I mean, we learn counting, and times tables, but after that it gets a bit fuzzy. Prime numbers? Some cursory investigation. But ISTM that students don’t really get to know the normal counting numbers very well. At least, I didn’t. I remember the occasions where we did take a lesson “off the curriculum” to study them as being some of my favourite maths lessons, e.g. the Hotel Cantor with a room for every positive integer, and the Infinity Bus Line which had a bus for every positive integer, each of which had a seat for every positive integer.

Anyway, PT. The thing I knew about but didn’t appreciate the significance of. Over the last week I’ve been tackling the Project Euler problems and there are a few concerning PT. (There are many inviting an exploration of number theory, which is also very cool). After solving 34%, I decided to skip down to problem 148, “Exploring Pascal’s Triangle”. Not many people have solved this, I thought: daunting! But also, this is my old friend PT. I’d like to get to know it better.

So after a couple of days of head scratching, I realised a way to attack the problem which would terminate before the heat death of the universe (always a useful approach to take). I also coded up some naive programs just to start exploring PT (as the problem says) – in the hope that they would give me some insight. Well, that and 3 or 4 pages of diagramming and scribbling later, I found out some quite interesting things. And I realised that I could solve the problem not just for multiples of 7, but for multiples of any prime. Now that’s cool.

I coded up a solution and ran it. It produced the wrong answer. I realised I’d missed something and corrected it. It produced the wrong answer. I tried again. Wrong answer. So I went to bed. Next morning, I realised my error, and also that I could simplify the program and speed it up. I coded it up again, and after ironing out a few non-algorithmic bugs, I ran it. Hooray! The right answer! I join the club of people who have solved problem 148.

Maths is cool.

Project Euler

Saturday, August 11th, 2007

I’ve just discovered Project Euler (from Osfameron, via Planet Haskell). This seems like great fodder for recreational mathematics and Haskell programming. Some of the simpler questions I might even co-opt for interviews (I have been known to ask the interview question “How many trailing zeroes has 100!” which has a similar flavour).

I haven’t programmed any solutions yet, but I did just solve number 5 (“What is the smallest number divisible by each of the numbers 1 to 20?”) using Google calculator.

Haskell – the videos

Thursday, August 9th, 2007

If you’re one of the approx 3 people left in the world who:

I suggest you get over there. It’s quite long, and it gets a bit difficult to follow without slides around 30 minutes into part 2, but it’s well worth watching. SPJ is an entertaining presenter, partly at least because he seems to be a bit of a stereotypical university lecturer type: very enthusiastic, clearly a towering intellect in the FP world, but on the other hand seems to bumble his way through the business of actually using computers!

If he’d been my lecturer back in the day, perhaps I’d have appreciated functional programming a bit more (“To do that, you’d have to solve the halting problem… so… it’s tricky.”).

Elevators in malls

Sunday, August 5th, 2007

People who aren’t (or who aren’t accompanying others) pushing strollers, in wheelchairs, or riding/propelling some other form of wheeled transport should not use lifts when there are perfectly good (and probably quicker for everyone, if you would just use them) escalators available about 50 yards away.

I mean, does anyone actually enjoy what are already the slowest lifts in the world? Wouldn’t it be better for everyone concerned if those capable just used the escalators? It’s not like using the lift saves you any energy anyway.

Concurrency in games

Sunday, August 5th, 2007

I’ve been programming next-gen consoles for a while now, and I have to say: it’s not getting any easier to write games to take advantage of multi-core systems. The conventional wisdom at my company is: writing multithreaded code is hard, so “ordinary programmers” should not be doing it – let’s leave it to the senior engineers who write the systems code to get it right. Ordinary gameplay/AI/animation/etc engineers shouldn’t have to worry themselves with this stuff.

I’m currently a lead engineer (which puts me in the “senior” category – although technically at my company “lead” is not a job rank per se). Lead engineers typically have a long history in the industry, and usually have a background in tackling the hard tasks of engineering lower-level systems in games. Many leads have done rendering, some have physics experience, many have experience of architecting games, and a few (myself included) also have a networking background. Basically, these correspond pretty well to the skills that one can’t hire for love nor money. As the highest-ranking engineers who still actually write code, it falls to us to provide technical direction for the projects in our studio and our company.

I can partly see why “leave it to the senior engineers” is a reasonable stance – for example, dealing with the intricacies of memory barriers is a task I wouldn’t wish on anyone. This stuff is hard enough to get right that the fewer people who have to touch it, the better. But on the other hand, I don’t think we’re doing enough to get safe forms of concurrency into the hands of the engineers who write the game code.

We (both internally, and I think, in the wider industry) are making some progress on some systems code being multithreaded. However, it’s not great progress. Of course, one problem is that PCs are still lagging behind next-gen consoles: the min spec target, even for games looking at shipping this time next year, is still a single-core P4 based system. Hyperthreaded if we’re lucky. Multicore PCs are out there, and are getting more numerous, but don’t yet have the market share to support dropping the lower end. And of course both Xbox 360 and PS3 still have more cores than a current top-end PC (6 hardware threads and 2 PPU hardware threads + 6 SPUs respectively).

For the most part, we are still moving single systems to other threads – there is nothing general about our approach to multithreading yet, and it’s not going to scale except in a very few cases. We have managed to separate “game” and “render” threads, but both of them are still fairly monolithic. There is some hope for physics simulation being threaded, and this is mostly being worked on by companies like Havok and Ageia. There is also some work being done on lower-level AI tasks like pathfinding. Some game tasks (like culling objects against the view frustum) can be relatively easily split onto another thread. And some game tasks continue to be threaded, the way they have been for years (audio and networking spring to mind).

But the major problem area for multithreading is where the actual gameplay happens: the intersection of animation, “high-level” AI, player control and to some extent physics. When I talk about “high-level” AI I mean the decision-making and glue code that controls what entities in the game do. The main game loop of object updates has multiple ordering dependencies among these systems and updating one system for a single object often causes cascading requests to other systems. For example: animation must be posed before physics is resolved (because posing animation may cause an arm to stick through a wall that a character is standing close to, and the physics system will then apply constraints to push the arm back outside the wall). Another example is that AI will decide to change what a character is doing and therefore will drive animation blending. A third example is that AI code will often want to know whether two characters can see each other in order to decide what to do. This involves asking the physics system to do a line-of-sight trace between the objects, and the result is needed to make the AI decision, so the call is typically synchronous.

So, animation, AI and physics are often tightly coupled in the update of a single object, and the update of a single object will often touch the data of half a dozen other objects (e.g. the weapon I’m carrying, what my enemy is doing, what state my buddies are in, etc). It doesn’t take a genius to realise that this is a pretty bad state of affairs if we’re trying to split parts of these tasks on to multiple threads. And these are not lightweight tasks either: posing animation involves evaluating state machines and a bunch of matrices and quaternion calculations; a physics trace often involves a heavyweight data structure traversal (octtree, BSP or similar); AI involves complex state machines, sometimes interpreted script, and a lot of conditions (something, incidentally, that the PowerPC architecture of the Xbox 360 and PS3 is quite poor at).

So what’s to be done? Well, I have a couple of ideas designed to make it easier for “ordinary engineers” to take advantage of multiprocessing in at least a semi-safe way. The first idea is Software Transactional Memory or STM. You’ll find the literature if you care to look around the web. I think this is the only practical solution to achieving some concurrency in updating the thousands of objects that we need to, each of which touches half a dozen others. And I think we should apply it at the object level. This will require a bit of extra memory, but if done right, the performance gains could be significant. And importantly, it will scale. For the first time, I think we have the potential to update thousands of objects across as many cores as we have. Of course, I don’t yet have any practical experience, and we may find that a new bottleneck (e.g. memory access) springs up.

The second idea I have to enable more multiprocessing of mid- and systems-level code (and perhaps some higher-level code) by functional programming. I bet that more than 90% of the loops we write can be implemented in terms of map and fold. The challenge is finding a way to abstract this in C++ (much as I would like to write games in Haskell, I don’t see it being adopted any time soon – but I may well experiment with a scripting language embedded in Haskell). Imagine if AI and player control engineers could, instead of writing a synchronous for-loop to find the closest enemy, write that same functionality in terms of map and fold (which is easy) and automatically have it be distributed across cores? The beauty of this idea is that the concurrency work is done once to make map and fold themselves multicore, and then (with appropriate forethought and data constraints) everyone can take advantage of that.

So the only thing I need to do now is actually write this code, get some preliminary use cases together, try it out, and then introduce it to my team. Wish me luck…

Building a MAME cabinet 9

Sunday, August 5th, 2007

I spent another couple of hours at it yesterday, and finished the cutting of the first side, and most of the second side (which was faster). Once the big cuts were out of the way, I moved from the floor onto sawhorses which made the work a lot easier to wrangle. I did use a plunge cut (if that’s what you call it) to do the “monitor edge” and finished the corner joins with a jigsaw. That was quite easy.

Here’s the first side cut and acting as a template for the second side.

First side complete

My plan is to clamp both sides together and sand them, then rout the slot around the edge for the t-molding to fit into. Which reminds me, I need to order the t-molding.

OpenID support

Saturday, August 4th, 2007

I’ve added support for OpenID. For those of you from LiveJournal, this means you have an easy way to post comments here. You’ll see an OpenID URL box when you comment. You already have an OpenID – LiveJournal invented it – and it’s simply the URL of your LJ: for example, mine is http://elbeno.livejournal.com. Put this in the OpenID URL box, and if you are logged in to LiveJournal, you’ll get a page asking whether you want to be identified to http://www.elbeno.com/blog. After you OK that, you’re done. Your ID will be known to this blog, and you won’t have to do register a username here, or type in an email address, or any of that nonsense.