A lot of Intelligent Design proponents believe that cells are too complex to have arisen randomly. They point to the micro-machines of the organelles and say that there is no way this could happen randomly.

This is a total fallacy.

Here’s the trick:
You only need to create ONE reproducing structure for it to multiply. At that point, things are self-sustainable.

Once you have one thing that reproduces, it’ll reproduce like wildfire. Every time it reproduces, you now have two things which can reproduce, until they exhaust their environment.

Now in a small environment, you’ll quickly exhaust the source of raw materials needed to make new things. Which means that unless you provide more raw materials, that particular strain of life is gone.

There is another solution though – more random changes. Until you end up with something that more effectively uses those resources – or can cannibalize the other entities.

This, in and of itself, pretty solidly ensures the direction of evolution – the pressure to more efficiently cannibalize resources form the environment ensures that complexity will increase in the long term. The only other alternative is the whole system stalls and dies out.

So that first guy happens randomly. Pure chance.

And it has millions of years, and changes on the orders of milliseconds within which to do it (chemistry works fast).

That's just for the first one. Once you have one, you can have random variations. But the one that works still exists. And it can change any way it likes, as long as it keeps making new ones that reproduce and compete better. Otherwise, again, something else that competes better will win. And that will gain the upper hand instead.

By the way, on the timeline of the Earth, a million years is nothing. If you have one variation per millisecond, that's about 31,536,000,000,000,000 opportunities for one combination of chemicals to turn into something useful.

Cool it down, and long-range low-entropy effects take hold, allowing some protein machinery to work differently - forming interesting configurations which are necessary for life. (A guy did an experiment a while back with some chemicals in ice (sorry for the pay-only NewScientist link); after 25 years he checked back, and he had amino acids in there. And RNA can replicate without its usual need for enzymes if it’s cold).

But let's ignore the cooling for now. That 31,536,000,000,000,000 opportunities? That's in one place. If we allow one of these experiments to happen per square meter on the earth's surface, the changes we can have over a million years start looking like 6,312,000,000,000,000,000,000,000,000,000,000,000. Or 6x10³⁶.

The universe started - as best as we can tell - about 1.37x10¹⁰ years ago. So if you want the number of chances you have for life to randomly happen in its simplest form, it’s more like 8x10⁴⁰ opportunities. That’s per Earth-like planet. Assuming that Earth-like conditions are required for life (which they probably aren’t).

There are roughly 100,000,000,000,000,000,000,000 (or 1x10²³) Earth-like planets in the universe.

So let’s run that experiment again. We now have 8x10⁶³ chances for life to happen. While you were reading this blog post, life had the chance to spontaneously arise approximately 1x10⁴⁰ times.

The question you should ask yourself is not how unlikely is it that life would arise purely by chance, but rather, why don't we see it everywhere we look?

Next time… The Pyramids, Skyscrapes & Evolution. I promise you that all these things really do go together - like Peanut Butter & Jelly.

So, I bought this for ONE thing.

Namely, the unlockable Space Harrier – one of my favorite arcade games of all time.

And guess what? The music & audio are all OFF. Something’s wrong with the pitch. Someone massively screwed up. It’s all off key. And it sounds like the bass-line may even be out of sync.

Oh, and the sampled speech? Too high.

Bah humbug. And this is even after I had to complete the first level of Super Thunder Blade to unlock the damn thing. Quite why I’d need to unlock it, I have no idea.

If Space Harrier is the only reason you want this compilation, don’t buy it. It’s like they got the wrong ROMs, compiled MAME, and then shipped it. Not only that, but there’s the occasional audio glitch on the attract screen which certainly wasn’t there on the arcade.

Oh, and it looks like (as with many versions of Space Harrier, including the Mame one) they’ve not got the gamma right.

*sigh*

Now if only the Sega Ages remake of Space Harrier would come out on the 360.

Games programming on current architectures require that a certain amount of attention be paid to your algorithms to make sure that they’re cache friendly.

It takes a long time for a memory access to be brought back from a page that isn’t in the cache. And cache lines are getting longer and longer.

Interestingly, software engineers solved this problem a long time ago, with algorithms meant for databases with really really slow IO pipes, and disk sector sizes of anywhere from 128 to 1024 bytes.

Those sizes should be a big hint to any seasoned programmer; they’re similar to the size of cache lines in modern systems. Which means that we can take algorithms that were designed to work really well for those old systems and later discarded, dig them up, dust them off and use them to create really blazingly fast routines for handling in-memory data.

Everything that’s old is new again.

So without further ado, here’s a few recommendations:

Prefer M-ary trees to Binary or Red/Black trees.

M-ary trees store several keys per node. Binary trees only store one key per node. If you store as many keys per node as you can fit into a single cache line, you’ll benefit.

If data you need to search changes rarely, use Indexed Sequential Access

This is a bi-level lookup scheme. It’s related to M-ary trees.

If your data needs to be flexible and searchable, use B-Trees

B-trees are M-ary trees, but you don’t require that each node has M items.

If you really must use a hashtable, consider using Extendible Hashing

Extendible hashing combines the properties of B-Trees, Indexed Sequential access and Hashtables to help keep pages coherent.

If you need to do lots of data filtering, and then perform the same operation on each object, use a Gather/Scatter approach

1. Filter your dataset using a given set of criteria
2. Generate a sequential list of matching objects in scratch space.
3. Prime the cache as you start processing the list, and keep pumping it every few objects.
4. Generate a sequential list of results if further processing is necessary, or Scatter the results back out to the objects (priming the N+Wth object as you go; you’ll need to tune W based on the size of your cache).

Consider Batch Sorting Operations instead of Quicksort

Don’t use Quicksort. If you have a large dataset, you’ll quickly run into cache issues as it bounces all over the place. Use Merge Sort instead (look it up in Knuth if you don’t remember that one) – which also has the nice property that you can run it in parallel on multiple cores.

Shadow Your Most Accessed Data Inside Your Keys When Necessary

Store data you need for your most common comparisons alongside the pointers to the objects – make them part of your key. You can ignore that part of the key if you’re searching the database for anything else, and your most common operation will be optimized because you won’t have to hit a random chunk of memory to pull out the value for comparison. (Good candidates for this might include an NPC’s location and bounding-sphere radius, which could be stored alongside the pointer to the NPC itself).

Defrag / Sort your Data On the Fly

As you operate on data, if you keep a secondary buffer around, you can generate a new data set. At the end of the operation, you just swap the pointer to the first dataset for your new one. This massively reduces cache thrashing, and if you plan it right and your data is temporally coherent, if you perform a sort of the data each frame, you’ll keep most of it sorted naturally for minimal cost – it just kind of drops out in the mix. You can always perform this check as you go along, and only re-sort if necessary. (If you’re clever, you can even figure out if you just need to resort the current cache-line, or if you need to be more exhaustive).

Another advantage here is that your secondary buffer? You don’t need to synchronize on it. Your first buffer? You don’t need to synchronize on that either, so you can get MASSIVELY parallel. You’re performing something akin to finite element analysis on your dataset. The only time you need to worry is when one calculation affects the output of the other – but if you make a list of those, you can special-case them.

If you’re dealing with small chunks of data, go Linear

With small amounts of data, the cost of accessing main memory to pull it into the cache massively dwarfs the cost of performing calculations on the data.

So don’t be afraid to use bubble-sorts, or linear searches on data that’s tiny and doesn’t use indirection. Of course, use this in moderation, and test first.

Further Reading

Look up “Batch Processing Algorithms” and “External Searching” on Google.

Read Database books. I personally can recommend the “Inside SQL Server” books for ideas on how to handle slow memory access (just take anything that refers to disk IO, and replace that with cache-line).

(This article is part 2 of a series)

Back to “Argh!” or “Arrggghhhh!!!!!”:

You can make an Arrggghhhh!!!! sound much more frustrated by mixing it up a bit. Try this:

Arrghghhhgghgggggghhhh!!!!

Although now we’re descending into the realm of sillyness, but it does kind of convey a blood-curdling (or at least, blood in the throat) scream filled with rage much more than even Arrggghhhh!!!!! does. The mixing of the g’s and the h’s swirl around as if one were gargling.

Here’s another trick I came up with a while back… How to make something sound as if it’s fading in:

He could hear it coming down the corridor towards him…

.         .        .       .    .   . .. ... .... ...t ..th .thu thud thuD thUD tHUD THUD THUDD THUDDD THUDDD THUDDDDD

It helps if you can keep it to a single line, but it’s interesting how this works. The number of spaces between the initial period drops by one for each one, until there’s none left. Then we get more periods until we hit the length of the word… then the letters start coming in, in lower case. Then, the uppercase comes in (which always sounds like shouting anyway), and then finally, alliteration of the final letter of the syllable which gives the word THUD its … well... thuddy sound.

The cool thing is, done right, this will pretty nicely convey something getting louder – or nearer. Visually at first it’s all to do with the space. You could go further than this with a little typography – italics would help convey more of a silent sound (the font weight is lighter), from which you’d go to a normal font, and then to something bold, and finally, use italics again for stress. Eg:

thud thud THUD THUD THUD!

… but it doesn’t work quite so well straight; you’ll need to mix and match. In the above example, the italics give a sense of surprise – like the thud is off beat, or unexpectedly louder – not a fade in.

So in closing… play with your words. It’s fun :)

What’s the best way to write “Argh”?

I guess it depends on how you’re using it. To me, “Argh” sounds like a groan, in response to a bad joke.

“Argh!” is a little better, but it’s kind of a suprised yelp more than anything else. A little like someone jumped up in front of you and smacked you over the head with a shovel – and then you drop. It’s curt.

I much prefer – if I’m going for some kind of blood-curdling scream as if all of your fingers got ripped off in some kind of threshing machine – something like this:

Arrggghhhh!!!!!

I was in secondary school when I started playing with words in this way. Something about the number of repeats of each of the letters works really really well in the word “argh”.

It works even better when italicized:

Arrggghhhh!!!!!

Now that’s a blood curdling scream.

Here’s where it gets interesting though. Any word which is meant to have emotional impact – or a sound – can be modified in this way. You can take regular words and make them onomatopoeical (sp?). Or you can even stress the hell out of them, and make them even more boisterous.

For example:

Howl becomes Howwwwwl

Growl becomes Grrrrrrrrrowl

Words convey emotion and images. They trigger memories. You shouldn’t be afraid to occasionally screw around with them for effect. The trick is not doing it so often that you piss your reader off.