Please install or update your Adobe Flash Player to view this content.
Deep within the well looked after bowels of Media Molecule, is the Lab. A non existent room of much importance, where our best brains sneak off to when they think no one is looking. It is here that we develop… things.
These things are essentially by-products - the result of squeezing the creativity from so many talented people all day long, skimming best frothy bits off the top, and leaving the other bits well alone.
They are experiments, or things made by braniacs to help us do our jobs in a slightly different way. They are random little side projects, they are tools, they are toys, they are pretty pictures or snippets of writing.
It is also here, that we slack off and tinker with things, or let our minds wander and think about the things that we’ve been reading or about stuff that inspires us .
We believe in sharing, and we want to share these things with the world. No matter how useless they may seem to be, there might be someone somewhere with a use for them, and for everyone else, they provide a fun insight into our jumbled and constantly whirring brains. And so, we invite you now to peek inside the Lab, and see what peculiar pieces brain fluff have come tumbling forth from the minds of our many splendid creators, or read about the topics that fascinate and tickle them.
The Lab has its very own Twitter feed, and you can subscribe to this blog via RSS - you can even subscribe to individual categories, which means you can subscribe to just the arty stuff, or just the codey stuff, etc, if you like. Check out the feeds page for more info.
Back in the day, computers were much simpler things. They had a CPU and they had some memory. Getting data to/from memory took a fairly reliable amount of time, and when optimising you’d just try to make sure that memory speed wasn’t the block in the pipeline that caused your application to slow down. Today however, things have changed, primarily due to the fact that CPUs have gained speed at a much faster rate than memory has. Where a CPU might go up in speed by 10x over a few years, the speed of the memory it’s paired with might go up by just 3x, making it become a much larger culprit for slowing games down…
Alex recently voyaged over land and sea to attend Siggraph 2011 in Vancouver. There he gave a talk entitled ‘Two Uses of Voxels in LittleBigPlanet2’s Graphics Engine’ as part of the Advances in Real-Time rendering in 3D Graphics and Games course.
The slides from that talk are now available to interested people, along with some other talks on the same subject matter too, from Bungie, Crytek, EA and DICE!
Making use of Amazon for our server hosting gives us access to a host of neat features that allow us to do good stuff with our server environments.
We make use of a feature in Amazon called EBS (Elastic Block Store), you can think of it like a hard drive that exists on the network. While it is true there has been a lot of doom and gloom surrounding the EBS devices (http://aws.amazon.com/message/65648/) they can give you some advantages if you are careful how you use them.
One of those advantages is the ability to create snapshots and then create new EBS volumes based on those snapshots. Snapshots are quite quick to take, get saved in S3 (Amazons Simple Storage Service) and protect the data for long term durability. Using these techniques you could quickly copy data from one environment to another, for example from your production to staging environments. Or while snapshots are *not* a backup solution, you could snapshot a volume, create a new volume from the snapshot, attach it to a machine and take a backup from that volume. Allowing you to backup from a certain point of time without affecting the running of the main server (of course depending on your applications and technologies this may not be appropriate and you might need to take extra steps to ensure you got a consistent data backup).
The other day I was writing some code that needed to build up a list of strings in a large file, and identify any duplicates that occurred. On average, the file would contain about 10000 unique strings, and I’d be looking at finding at least 500 duplicates per string. That means that throughout the parsing of my file, I’d have to add about 10000 strings to the list, and probably do about 5000000 lookups on them. This needed to be a fast process…
This blog entry is about an awesome trick that Mr Alex Evans taught me when I went and asked him for advice about this problem. It’s such a good lesson I thought I’d write it up and shove it on the blog. I’d come up with various ways I could approach this – hash tables, maps, binary trees, specialised string trees and couldn’t pick how to attack it. His advice was that if an algorithm can do anything at all that you don’t need it to do, it’s probably slower than it needs to be.
A perfect solution to a problem will do exactly what it needs to – no more, no less. That way you know that even if the code isn’t perfectly optimised, it’s not spending time doing things it doesn’t need to. It occurred to me that even nature follows this approach – a perfectly evolved creature for some scenario will be exactly as good as it needs to be at things – anything extra is a waste of valuable resources. Cheetahs don’t run at 150mph because 70mph is enough! Clearly it’s a good way of thinking of things, so I set about this approach for my string searching.
First, my requirements:
- I only ever add to the list – I never remove
- I never need to extract any sorted data from it or anything fancy like that
- I never need to iterate over the list
- I’m going to be doing on average 500 times more lookups than I am adds, and the majority are likely to be successful (i.e. they will find an entry)
- The strings themselves will always be in memory (as they’re loaded when I load the file), so they don’t need copying when adding
- I have loads and loads of memory to burn!
I started off with a std::map, which could do:
Adds, gets, deletes
- Any sort of types for the key and value, with any sort of comparison function
- Easy iteration of the list
- Easy extraction of sorted data from the list
- Automatically manages memory allocation
Clearly the map does way too much – it supports lots of operations I don’t need, and can deal with any arbitrary types, whereas I just need a null terminated string for a key and a single unsigned int for the value. To cut a long story short, after several rounds of following Alex’s advice, I found myself with:
- A custom hash table – uses a very simple 64 bit hash algorithm on the string, then uses the bottom 20 bits as an index into a table
- Each entry in the table is a list of strings, their full 64 bit hash, their length, and their corresponding unsigned int.
- This means my lookups can identify mismatches very fast – only in the event of 2 strings having exactly the same hash and length will I need to do an actual strcmp to verify they’re identical. The odds are I’ll end up doing 1 strcmp per lookup
- All memory in the table is allocated linearly in one big mega chunk (which gets bigger if it really has to). This avoids lots of dynamic allocation, but prevents me being able to delete things.
- Specialised to deal with strings + unsigned ints – doesn’t handle arbitrary class types at all
- It’s only 150 lines of code
The result – parsing my file and doing all the string lookups goes from 22.5s to 1.8s.
Anyway, the moral of the story and the lesson this blog post is all about:
If an algorithm is capable of more than it needs to be, it’s probably doing more work than it needs to!
Shaun and his partner Vivi have embarked upon a new art project!
These photos are an ongoing project that extends our interests first developed in a series of video/gallery installations begun in 2005. We’re fascinated by the potential for confusion, discomfort and other emotional responses to environments (and images of environments) that blur the distinction between actuality and simulation. In these photographs we’re using commercially available doll’s house furniture, which are carefully painted, composed and lit, combined with other “found” bits and pieces.”
Mm is excited to be moving towers soon, to a new shiny office inside a new shiny tower… and in the new tower, for reasons too pedestrian to recount here, the boring standard office ceiling tiles are being replaced with clear acrylic ones. This, of course, is awesome. But in what particular way?
Over a few cocktails and glasses of champagne at Guildford’s entirely un-legendary and slightly creepy The-Shining-esque hotel-bar-blue-light-travelling-salesman-horror-venue ‘The Mandolay’, the Molecules put their heads together. ‘What’, slurred Paul ‘Aggie’ Davis, ‘about adding coloured lights above the tiles?’
What indeed! I feel a lab project coming on…
A little drunken 3 am googling session later, whilst contemplating how one might wire up and control 2000 ceiling tiles with coloured lights, I discovered this rather wonderful chip: the Allegro A6281.
Are all my dreams answered?
Whilst some Molecules were out in San Francisco at this years Game Developers Conference, I was a lone ranger out in the not-so-darkest-depths of Texas. Every year, Austin plays host to South by Southwest (SXSW) - a huge festival merging the worlds of music, film and interactive in one big melting pot of win. I was mostly there for there for the Interactive bit (SXSWi), to discover what’s cooking in the land of the internets and maybe discover some new stuff. It’s nicknamed spring break for geeks.
So, what is hot? What’s buzzing in the land of the internets? Commence Tom-rant-rabble! :)
I set myself a task last week: write 750 words every day. I have not succeeded. However I’m getting married in 8 days so I have an excuse I think.
The story “Rain Patrol” was my first effort under this short-lived regime, a piece of flash fiction written in an hour. It was inspired by this painting:
It’s called In The Rain and it’s by Vitaliy Smyk, a Ukrainian artist. It turns out that the painting itself was a two hour speedpaint, so it seems pretty fitting!
One Hour Fiction: Rain Patrol
For days, it had rained. He had forgotten when it had started and forgotten what being dry was like, becoming accustomed to the mud, the constant companion of damp and the sheer brown of his existence. And then, as suddenly as it always started, the rain had stopped. The clouds parted just long to let the twin suns of this barren, forgotten rock peek through to remind him they did in fact exist.
Three stinking months. That’s how long he had been here, this time round. He still wondered quite why he had signed up to return, knowing that the promises of forging new worlds and bringing hope to oppressed peoples were nothing but empty marketing drivel. Instead, all that awaited him was foot rot, tepid meals consisting mostly of rainwater and a near statistical certainty that he would return in one or more body bags.
His company of men lived in close proximity in what seemed to be a plughole for the whole planet. How did all the water drain here, from both the ground and the sky? Last week a mobile command post had been washed away. Three guys now missing – dead, really – after the building had been torn from its moorings and swept down the valley. He had heard them yelling for help on the radio, but what could be done?
Click me to read the full story, and a few others too.