I <3 Steve McConnell*
Coding Horror
programming and human factors
by Jeff Atwood


June 16, 2008

Physics Based Games

I've always been fascinated by physics-based gameplay. Even going back to the primeval days of classic arcade gaming, I found vector-based games, with their vastly simplified 2D approximations of physics and motion, more compelling than their raster brethren. I'm thinking of games like Asteroids, Battlezone, and Lunar Lander.

Accurately simulating the physics of the real world has been the domain of supercomputers for decades. The simulation of even "simple" physical phenomena like fire, smoke, and water requires a staggering amount of math. Now that we almost have multicore supercomputers on every desktop, it's only natural that aspect of computing would trickle down to us.

This topic is particularly relevant in light of today's introduction of NVIDIA's newest video card, the GTX 280, which contains a whopping 1.4 billion transistors. That's a lot. For context and scale, here's a shot of the 280 GPU next to a modern Intel dual-core CPU.

gtx-280-vs-penryn.jpg

I've talked about this before in CPU vs. GPU, but it bears repeating: some of the highest performing hardware in your PC lies on your video card. At least for a certain highly parallelizable set of tasks.

We were able to compress our test video (400 MB) in iPhone format (640*365) at maximum quality in 56.5 seconds on the 260 GTX and 49 seconds on the 280 GTX (15% faster). For comparison purposes, the iTunes H.264 encoder took eight minutes using the CPU (consuming more power overall but significantly less on peaks).

While one of the primary benefits of manycore CPUs is radically faster video encoding, let's put this in context -- compared to the newest, speediest quad core CPU, you can encode video ten times faster using a modern video card GPU. It's my hope that CUDA, Microsoft's Accelerator, and Apple's Grand Central will make this more accessible to a wide range of software developers.

All this physics horsepower, whether it's coming from yet another manycore x86 CPU, or a massively parallel GPU, is there for the taking. There are quite a few physics engines available to programmers:

There are no shortage of physics games and sandboxes to play with this stuff, too. Here are a few of my favorites.

Perhaps the most archetypal physics based game is Chronic Logic's Bridge Construction Set, the original version of which dates way back to 1999. I'm showing a picture of their fancy NVIDIA branded version below, but it's hardly about the graphics. This is pure physics simulation at its most entertaining. Who knew civil engineering could be so much fun? Highly recommended.

Bridge It! screenshot

Oh, and small hint: after playing this game, you will learn to love the power and beauty of the simple triangle. You'll also marvel at the longer bridges you manage to drive across without plunging into the watery abyss underneath.

I've professed my love for The Incredible Machine and other Rube Goldberg devices before. The physics based game Armadillo Run is a modern iteration of same. Get the armadillo from point A to point B using whatever gizmos and gadgets you find in your sandbox -- rendered in glorious 3D with a full-blown 2D physics engine in the background.

armadillo run screenshot

The latest physics based game to generate a lot of buzz is Trials 2: Second Edition. I haven't had a chance to try it yet, but the gameplay movie is extremely impressive. Like Armadillo run, the action is all on a 2D plane, but the physics are impeccable.

Trials 2: Second Edition screenshot

I'm sure I've forgotten a few physics based games here; peruse this giant list of physics games to see if your favorite is already included.

See, physics can be fun -- and increasingly complex physics engines are an outstanding way to harness the massive computational horsepower that lies dormant in most modern PCs.

[advertisement] Read the largest case study ever published about lightweight peer code review in Best Kept Secrets of Peer Code Review. Free book, free shipping.

Posted by Jeff Atwood    Comments (25)    View blog reactions

June 14, 2008

Don't Go Dark

Ben Collins-Sussman on programmer insecurity:

What do you do when somebody shows up to an open source project with a gigantic new feature that took months to write? Who has the time to review thousands of lines of code? What if there was a bad design decision made early in the process -- does it even make sense to point it out? Dropping code-bombs on communities is rarely good for the project: the team is either forced to reject it outright, or accept it and deal with a giant opaque blob that is hard to understand, change, or maintain. It moves the project decidedly in one direction without much discussion or consensus.

And yet over and over, I'm gathering stories that point to the fact that programmers do not want to write code out in the open. Programmers don't want their peers to see mistakes or failures. They want to work privately, in a cave, then spring "perfect" code on their community, as if no mistakes had ever been made.

hidden behind a window

I don't think it's hubris so much as fear of embarrassment. Rather than think of programming as an inherently social activity, most coders seem to treat it as an arena for personal heroics, and will do anything to protect that myth. They're fine with sharing code, as long as they present themselves as infallible, it seems. Maybe it's just human nature.

Ben's talking about open source development, but this anti-pattern exists in commercial software development, too. The very same phenomenon is documented in Jim McCarthy's 1995 book Dynamics of Software Development. It's presented as Rule #30: Don't go dark.

You have to manage the granularity of development tasks in such a way that you emerge with visible deliverables over short intervals. In our group, we argue back and forth over how big the intervals should be: five days, ten days, three weeks? In our world, three weeks is going dark.

I don't know what's appropriate for your world, but we want team members to have contracts with the other parts of the team so that they surface pretty often with visible components. When somebody surfaces and the deliverable isn't done, we know right away. We know that this week we slipped one day. That's worth knowing, much better than getting to the end of the project and observing, "Oh, we slipped six months!" At that point it's too late to even bother counting up how much you've slipped.

Rule #30 is directly followed by a related rule, Rule #31: Beware of a guy in a room.

Specialist developers who lock themselves away in a room, who go dark for long stretches, are anathema to shipping great software on time. No matter how brilliant a developer might be, don't give the developer a significant assignment unless he or she understands and buys into the type of development program you intend to run. The brilliant developer must be capable of performing on a team, making his work visible in modest increments and subjecting it to scrutiny as it matures. Some people find this intolerable, and although there is a role for people of this disposition in the software world, it is not as a part of a team devoted to shipping great software on time.

This is easier to deal with in the workplace, because you typically have some kind of (theoretically) rational project management in place, and everyone works under the same umbrella. It's effectively impossible to go dark if you're practicing any form of agile software development. For example, Ron Jeffries borrowed this concept from Jim McCarthy's book and codified it into extreme programming lore. Tasks are always sliced up so they fit into a single iteration, and you never let them spill over into multiple iterations. You'll always have something to show at the end of each iteration. You can't go dark without quitting the project or, perhaps, your job.

An open source project is a very different animal. It's a motley collection of widely distributed, loosely coupled volunteers. There's no project manager breathing down your neck, urging you to break your work into short, shareable increments. The risk of going dark is severe. The burden of proof falls on the individual developers, not only to make their work on the project visible in modest increments, but also to get over their code insecurity and share their in-progress code with other people working on the project. How do you expect your fellow coders to take you seriously if you aren't regularly showing them code? It's the only form of currency that matters on an open source project.

Don't go dark. Don't be that guy in the room. Hiding your code until it's "done" may feel safer, but it isn't. Sharing your ongoing code with your coworkers is scary, much less the world -- but it also results in feedback and communication that will improve your code and draw you closer to the project you're working on. And isn't that why we all write code in the first place?

[advertisement] Peer Code Review. No meetings. No busy-work. Customizable workflows and reports. Try Jolt Award-winning Code Collaborator.

Posted by Jeff Atwood    Comments (94)    View blog reactions

June 12, 2008

ASCII Pronunciation Rules for Programmers

As programmers, we deal with a lot of unusual keyboard characters that typical users rarely need to type, much less think about:

$ # % {} * [] ~ & <>

Even the characters that are fairly regularly used in everyday writing -- such as the humble dash, parens, period, and question mark -- have radically different meaning in programming languages.

This is all well and good, but you'll eventually have to read code out loud to another developer for some reason. And then you're in an awkward position, indeed.

How do you pronounce these unusual ASCII characters?

We all do it, but we don't necessarily think much about the words we choose. I certainly hadn't thought much about this until yesterday, when I read the following comment left on Exploring Wide Finder:

A friend sent me a Java code fragment in which he looped through printing "Thank You!" a million times (it was a response to a professor who had extended the deadline on a paper). I responded with a single line of Ruby to do the same, and a single line of Lisp.

He wrote back: "Underscores, pipes, octothorpes, curly braces -- sheesh... I'll take a mild dose of verbosity if means I don't have to code something that looks like it's been zipped already!"

What the heck is an octothorpe? I know this as the pound key, but that turns out to be a US-centric word; most other cultures know it as the hash key.

I'm often surprised to hear what other programmers name their ASCII characters. Not that the words I personally use to identify my ASCII characters are any more correct, but there's far more variability than you'd expect considering the rigid, highly literal mindset of most programmers.

Perhaps that's why I was so excited to discover the ASCII entry in The New Hacker's Dictionary, which Phil Glockner turned me on to. It's a fairly exhaustive catalog of the common names, rare names, and occasionally downright weird names that programmers associate with the ASCII characters sprinkled throughout their code.

How many of these ASCII pronunciations do you recognize? Which ones are the "correct" ones in your shop?

  Common Names Rare Names
! exclamation mark
bang
pling
excl
not
shriek
factorial
exclam
smash
cuss
boing
yell
wow
hey
wham
eureka
spark-spot
soldier
control
" quotation marks
quote
double quote

literal mark
double-glitch
dieresis
dirk
rabbit-ears
double prime
#
hash
pound sign
number sign
pound
sharp
crunch
hex
mesh
grid
crosshatch
octothorpe
flash
square
pig-pen
tictactoe
scratchmark
thud
thump
splat
$ dollar sign
dollar
currency symbol
buck
cash
string
escape
ding
cache
big money
% percent sign
mod
grapes
double-oh-seven
& ampersand
amp
amper
and
and sign
address
reference
andpersand
bitand
background
pretzel
' apostrophe
single quote
quote
prime
glitch
tick
irk
pop
spark
closing single quotation mark
acute accent
( ) opening / closing parenthesis
left / right paren
left / right parenthesis
left / right
open / close
open / close paren
paren / thesis
so/already
lparen/rparen
opening/closing parenthesis
opening/closing round bracket
left/right round bracket
wax/wane
parenthisey/unparenthisey
left/right ear
[ ] opening / closing bracket
left / right bracket
left / right square bracket
bracket / unbracket
square / unsquare
u turn / u turn back
{ } opening / closing brace
open / close brace
left / right brace
left / right squiggly
left / right squiggly bracket/brace
left / right curly bracket/brace
brace / unbrace
curly / uncurly
leftit / rytit
left / right squirrelly
embrace / bracelet
< > less / greater than
bra / ket
left / right angle
left / right angle bracket
left / right broket
from / into (or towards)
read from / write to
suck / blow
comes-from / gozinta
in / out
crunch / zap
tic / tac
angle / right angle
* asterisk
star
splat
wildcard
gear
dingle
mult
spider
aster
times
twinkle
glob
Nathan Hale
+ plus
add
cross
intersection
, comma cedilla
tail
- dash
hyphen
minus
worm
option
dak
bithorpe
. period
dot
point
decimal point
radix point
full stop
spot
/ slash
stroke
slant
forward slash
diagonal
solidus
over
slak
virgule
slat
\
backslash
hack
whack
escape
reverse slash
slosh
backslant
backwhack
bash
reverse slant
reversed virgule
backslat
: colon dots
two-spot
; semicolon
semi
weenie
hybrid
pit-thwong
= equals
gets
takes
quadrathorpe
half-mesh
? question mark
query
ques
quiz
whatmark
what
wildchar
huh
hook
buttonhook
hunchback
@ at sign
at
strudel
each
vortex
whorl
whirlpool
cyclone
snail
ape
cat
rose
cabbage
commercial at
^ circumflex
caret
hat
control
uparrow
xor sign
chevron
shark (or shark-fin)
to the
fang
pointer
_ underline
underscore
underbar
under
score
backarrow
skid
flatworm
` grave accent
backquote
left quote
left single quote
open quote
grave
backprime
backspark
unapostrophe
birk
blugle
back tick
back glitch
push
opening single quote
quasiquote
| bar
or
or-bar
v-bar
pipe
vertical bar
vertical line
gozinta
thru
pipesinta
spike
~ tilde
squiggle
twiddle
not
approx
wiggle
swung dash
enyay
sqiggle (sic)

If you're curious about the derivation of some of the odder names here, there are an extensive set of footnotes (and even more possible pronunciations) at the ascii-table.com pronunciation guide.

So the next time a programmer walks up to you and says, "oh, it's easy! Just type wax bang at hash buck grapes circumflex and splat wane", you'll know what they mean.

Maybe.

[advertisement] Peer code review without meetings, paperwork, or stopwatches? No wonder Code Collaborator won the Jolt Award.

Posted by Jeff Atwood    Comments (323)    View blog reactions

June 11, 2008

Markov and You

In Finally, a Definition of Programming I Can Actually Understand I marvelled at particularly strange and wonderful comment left on this blog. Some commenters wondered if that comment was generated through Markov chains. I considered that, but I had a hard time imagining a text corpus input that could possibly produce output so profoundly weird.

So what are these Markov chains we're talking about?

One example of Markov chains in action is Garkov, where the long running Garfield cartoon strip meets Markov chains. I present below, for your mild amusement, two representative strips I found on the Garkov hall of fame:

garkov-sample-1.png

garkov-sample-2.png

Garfield's an easy target, though:

  • Garfield Minus Garfield. What it says on the tin. Surprisingly cathartic.
  • Lasagna Cat. Almost indescribably strange live action recreations of Garfield strips. If you only click one link in this post, make it this one. Sanity optional.
  • Garfield Variations. Hand-drawn versions of Garfield in underground "comix" style, usually on paper napkins.
  • Barfield. Garfield strips subtly modified to include amusing bodily functions.
  • Permanent Monday. Literary commentary on selected strips.
  • Arbuckle. Strips faithfully redrawn by random internet "artists", with one dramatic twist: Jon can't actually hear Garfield, because he is, after all, a cat.
  • Garfield Randomizer. Sadly defunct -- combined random panels to form "new" Garfield strips.

So let's proceed to the "kov" part of Garkov. The best description of Markov chains I've ever read is in chapter 15 of Programming Pearls:

A generator can make more interesting text by making each letter a random function of its predecessor. We could, therefore, read a sample text and count how many times every letter follows an A, how many times they follow a B, and so on for each letter of the alphabet. When we write the random text, we produce the next letter as a random function of the current letter. The Order-1 text was made by exactly this scheme:

t I amy, vin. id wht omanly heay atuss n macon aresethe hired boutwhe t, tl, ad torurest t plur I wit hengamind tarer-plarody thishand.

We can extend this idea to longer sequences of letters. The order-2 text was made by generating each letter as a function of the two letters preceding it (a letter pair is often called a digram). The digram TH, for instance, is often followed in English by the vowels A, E, I, O, U and Y, less frequently by R and W, and rarely by other letters.

Ther I the heingoind of-pleat, blur it dwere wing waske hat trooss. Yout lar on wassing, an sit." "Yould," "I that vide was nots ther.

The order-3 text is built by choosing the next letter as a function of the three previous letters (a trigram).

I has them the saw the secorrow. And wintails on my my ent, thinks, fore voyager lanated the been elsed helder was of him a very free bottlemarkable,

By the time we get to the order-4 text, most words are English, and you might not be surprised to learn that it was generated from a Sherlock Holmes story ( "The Adventure of Abbey Grange'').

His heard." "Exactly he very glad trouble, and by Hopkins! That it on of the who difficentralia. He rushed likely?" "Blood night that.

So the text in Garkov strips is generated in exactly this way, but using words instead of letters. The input corpus is, as you'd expect, the text of many old Garfield strips.

What's amazing to me about Markov chains is how unbelievably simple they are. A Markov chain has no memory of previous states: the next state (word, in our case) is chosen based on a random dice roll and a lookup into a table of the states that tend to historically follow the current state in the input corpus. Given an adequate input corpus, they work almost uncannily well, a testament to the broad power of rudimentary statistical inference. Garfield's been around since 1978, and still going str.. well, going, so there's no shortage of material to work with.

Now let's try it ourselves. I fed the text of the last twelve Paul Graham essays to this online Markov generator, using two word groupings -- what Bentley refers to as "Order-2". Here's what I got back:

You can feel the need to take advantage of increased cheapness, however. You're not all playing a zero-sum game. There's not some fixed number of startups; we fund startups we fund to work on matters of passing importance. But I'm uncomfortably aware that this is part of any illusions about the problem of overeating by stopping eating. I couldn't simply avoid the Internet had become, because the company is the new trend of worrying obsessively about what it meant for someone, usually an outsider, who deliberately stirred up fights in a startup than just start it. You know how the A List is selected. And even that is more work.

But Markov chains aren't just useful for automatically generating Paul Graham essay parodies. They're also quite practical. You might even say Markov chains are a large part of what powers today's internet. Most remarkably, to me at least, Markov chains underly Google's trillion dollar PageRank formula:

The [PageRank] formula uses a model of a random surfer who gets bored after several clicks and switches to a random page. The PageRank value of a page reflects the chance that the random surfer will land on that page by clicking on a link. [PageRank] can be understood as a Markov chain in which the states are pages, and the transitions are all equally probable and are the links between pages.

As a result of Markov theory, it can be shown that the PageRank of a page is the probability of being at that page after lots of clicks. This happens to equal t-1 where t is the expectation of the number of clicks (or random jumps) required to get from the page back to itself.

Incidentally, if you haven't read the original 1998 PageRank paper, titled The PageRank Citation Ranking: Bringing Order to the Web (pdf), you really should. It's remarkable how, ten years on, so many of the predictions in this paper have come to pass. It's filled with interesting stuff; the list of the top 15 PageRank sites circa 1996 in Table 1 is an eye-opening reminder of how far we've come. Plus, there are references to pornographic sites, too!

Markovian models -- specifically, hidden Markov Models -- are also related to our old friend, Bayesian spam filtering. They're even better! The most notable example is the CRM114 Discriminator, as outlined in this excellent presentation (pdf).

How to Turn a Bayesian into a Markovian

If you play with the Markov text synthesizer, you'll quickly find that Markov methods are only as good as their input corpus. Input a bunch of the same words, or random gibberish, and that's what you'll get back.

But it's sure tough to imagine a more ideal input corpus for Markovian techniques than the unimaginable vastness of web and email, isn't it?

[advertisement] Read the largest case study ever published about lightweight peer code review in Best Kept Secrets of Peer Code Review. Free book, free shipping.

Posted by Jeff Atwood    Comments (113)    View blog reactions

June 09, 2008

Exploring Wide Finder

I have decidedly mixed feelings about the book Beautiful Code, but one of the better chapters is Tim Bray's "Finding Things". In it, he outlines the creation of a small Ruby program:

counts = {}
counts.default = 0

ARGF.each_line do |line|
  if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
    counts[$1] += 1
  end
end

keys_by_count = counts.keys.sort { |a, b| counts[b] <=> counts[a] }
keys_by_count[0 .. 9].each do |key|
  puts "#{counts[key]}: #{key}"
end

Tim calls Ruby "the most readable of languages"; I think that's a bit of a stretch, but I'm probably the wrong person to ask, because I've learned to distrust beauty:

It seems that infatuation with a design inevitably leads to heartbreak, as overlooked ugly realities intrude. Love is blind, but computers aren't. A long term relationship -- maintaining a system for years -- teaches one to appreciate more domestic virtues, such as straightforwardness and conventionality. Beauty is an idealistic fantasy: what really matters is the quality of the never ending conversation between programmer and code, as each learns from and adapts to the other. Beauty is not a sufficient basis for a happy marriage.

But I digress. Even if you have no idea what Ruby is, this simple little program isn't too difficult to decipher. It helps if you know that Tim Bray's blog URLs look like this:

http://www.tbray.org/ongoing/When/200x/2007/09/20/Wide-Finder

This is a program to count the most common HTTP GET URL entries in a webserver log file. We loop through the entire log file, building up a key-value pair of these URLs, where the key is the unique part of the URL, and the value is the number of times that URL was retrieved.

Maybe it's just the Windows developer in me, but one might wonder why you'd bother writing this code at all in the face of umpteen zillion free and commerical web logfile statistics software packages. After all, the best code is no code at all.

Well, perhaps there is a reason for this code to exist after all. Tim eventually turned this snippet of code into a benchmarking exercise -- The Wide Finder Project.

It�s a classic example of the culture, born in Awk, perfected in Perl, of getting useful work done by combining regular expressions and hash tables. I want to figure out how to write an equivalent program that runs fast on modern CPUs with low clock rates but many cores; this is the Wide Finder project.

A noble experiment, indeed. The benchmarks were performed on the following hardware:

  • Sun T5120
  • 8 UltraSPARC T2 CPU cores @ 1.4 GHz
  • 64 GB RAM

The input data is as follows:

  • The complete set of Tim's web logfiles from March 2007
  • 926 MB
  • 4,625,236 lines

The results are sort of.. well, all over the map. I'll summarize with the worst and best scores for each language:

SlowestFastest
Perl44.291.51
Erlang37.583.54
Python41.044.38
OCaml49.6914.64
Ruby1:43.7150.16

I'm simplifying quite a bit here, and omitting languages with only one submission, so do head over to the actual results page for more detail.

While you're there, I also suggest reading Tim's analysis of the results, wherein he argues that some of the code optimizations that "won" the benchmarks should be automatic and nearly transparent to the programmer. He proposes that, in a perfect world, a one-character change to the original Ruby program would be all it takes to enable all the necessary multicore optimizations:

ARGF.each_line* do |line|

I heartily agree. Personally, I think that's the most important result from the Wide Finder Experiment. When it comes to multicore performance, choice of language is no silver bullet. How else can we explain the massive disparity between the fastest and slowest versions of the code in each language?

As experiments go, Wide Finder was a reasonably successful one, if somewhat incomplete and perhaps too small. Tim has addressed both of those criticisms and rebooted with The Wide Finder 2 Project. It's bigger, badder, and brawnier, but the goal remains the same:

The problem is that lots of simple basic data-processing operations, in my case a simple Ruby script, run like crap on modern many-core processors. Since the whole world is heading in the slower/many-core direction, this is an unsatisfactory situation.

If you look at the results from last time, it�s obvious that there are solutions, but the ones we've seen so far impose an awful complexity cost on the programmer. The holy grail would be something that maximizes ratio of performance increase per core over programmer effort. My view: Anything that requires more than twice as much source code to take advantage of many-core is highly suspect.

Check the Wide Finder 2 Project Wiki for all the key details. The naive Ruby implementation currently takes 25 hours -- yes, hours -- to complete. Some clever programmers have already beaten this result by almost two orders of magnitude, per the results wiki page.

Wide Finder isn't a perfect experiment, but it is a relatively simple, easily understandable summary of the problems facing all of tomorrow's software developers in the coming massively multicore world. Can you do better on the time without exploding either the code size, the code complexity, or the average programmer's head?

[advertisement] Complimentary paperback book on lightweight peer code review. 10 essays from industry experts. Free shipping. Order Best Kept Secrets of Peer Code Review.

Posted by Jeff Atwood    Comments (97)    View blog reactions
Read older entries »
Content (c) 2008 Jeff Atwood. Logo image used with permission of the author. (c) 1993 Steven C. McConnell. All Rights Reserved.