robert zubek / blog

Some time ago I found a fascinating paper on the history of Erlang, written by one of its main creators:

http://www.cs.chalmers.se/Cs/Grundutb/Kurser/ppxt/HT2007/general/languages/armstrong-erlang_history.pdf

It showed up on programming.reddit for about a day, and then disappeared right back into the deep waters - which is too bad, because the paper is illuminating.

Erlang is a language with strong built-in support for concurrency based on message passing. As the author describes it:

Erlang was designed for writing concurrent programs that “run forever.” Erlang uses concurrent processes to structure the program. These processes have no shared memory and communicate by asynchronous message passing. Erlang processes are lightweight and belong to the language, not the operating system.

Reading the paper, I had several delightful “aha!” moments, where the details of Erlang design just clicked together. And I don’t mean the mundane issues, like single-assignment variables (hello, Prolog!), or interactively modifiable code (hello, Lisp!). Rather, the history put some architectural bits in perspective.

At a certain level, I always knew that Erlang was designed for programming telephone exchanges. But this paper really conveys the feel for what that means: huge collections of loosely coupled finite-state machines, all running in parallel, doing little bits of protocol validation here and there, but mostly staying dormant.

Typically, the software for call control is modeled using finite state machines that undergo state transitions in response to protocol messages. From the software point of view, the system behaves as a very large collection of parallel processes. At any point in time, most of the processes are waiting for an event caused by the reception of a message or the triggering of a timer. When an event occurs, the process does a small amount of computation, changes state, possibly sends messages to other processes and then waits for the next event. The amount of computation involved is very small.

Which definitely explains a number of their implementation choices which, without this motivation, look highly unusual. Let me highlight just three of them.

Continue Reading »

(Edit: Welcome reddit readers. The following is a howto on setting up an embedded Jetty server in Clojure, and writing a minimal servlet that serves up dynamic content.)

Last week I discovered a very nice language named Clojure. It’s based on Lisp, but hosted on the Java platform, and running inside the JVM. It has some lovely features, like native support for Java collections, and a clean API that ditches a lot of the old ANSI CL library cruft.

But the best part for me was language interop: Clojure can effortlessly load and use any external Java library. And there is a ton of good ones out there, including a rich set that comes with the Java platform. (This may seem like a minor point, but most free Lisps lack good libraries; only the non-free Allegro CL has really extensive, cross-platform ones.)

So I decided to take the language for a spin, especially exercising the language interop bit. For example, by building a little web server to serve up some dynamic content. You know, web development 101 kind of stuff. This turns out to be really easy to do.

Since Clojure is backed by Java, we can use an existing server library to do the heavy lifting for us. Several high-quality ones are available - I went with Jetty, a servlet-based engine that’s really easy to embed in custom applications. Using a servlet container will take care of all the mundane bookkeeping for us.

In the following posting, I’m reproducing the steps required to get a Clojure-based web server up and running, in much less than 100 lines of code. Hope you find it interesting!

Continue Reading »

Game logic often gets split into “time-sensitive” and “blocking” parts. When dealing with I/O-bound components, we often want to let them run separately from the main game loop. This way they won’t block the whole game as they’re waiting for their data.

The typical example is reading from disk, or accessing a database. Disk operations are orders of magnitude slower than operations on memory. If the data we need is already loaded and in memory, that’s great, we can use it immediately - but if it isn’t, we’ll have to load it first. And we wouldn’t want to put the whole game on hold, while we wait for the drive to seek to the appropriate sector on the disk.

The standard solution is to split the work into multiple threads: the fast main thread, which handles time-sensitive processing, and a worker thread (or a pool of threads), which will handle anything that could potentially block. But how to implement this?

Continue Reading »

Here are my steps for setting up SBCL (Steel Bank Common Lisp) and Slime (Emacs Lisp mode) to work under Windows Vista.

It’s mostly straightforward, except for dealing with spaces in path names. It turns out that slime.el uses the (split-string) function to pull apart the Lisp command line, which won’t work with the default “c:\program files\…” location. Here’s how to fix that, using symbolic links (yes, Windows supports them too!).

The following was tested on a Vista box, SBCL 1.0.13, and Slime 2.0 on Emacs 22.2.1.

Installing SBCL:

1. Download and install SBCL. By default, it will install to c:\Program Files\Steel Bank Common Lisp\1.0.13
2. Run cmd.exe as Administrator (required for symbolic links)
3. Set up a link from SBCL install directory, to some location without spaces. Note that the syntax is an inverse of the Unix ‘ln’ command.
   

   C:\Users\Rob\Documents>ver
   Microsoft Windows [Version 6.0.6000]

   C:\Users\Rob\Documents>mklink /d SBCL “c:\Program Files\Steel Bank Common Lisp\1.0.13″
   symbolic link created for SBCL <<===>> c:\Program Files\Steel Bank Common Lisp\1.0.13

   C:\Users\Rob\Documents>dir sbcl*
   …
   04/09/2008 09:07 PM <SYMLINKD> SBCL [c:\Program Files\Steel Bank Common Lisp\1.0.13]

Installing Emacs and Slime:

1. Download Emacs, unzip it to any location (eg. c:\Program Files\emacs). If desired, run the emacs\bin\addpm.exe program to add a link to the start menu.
2. Download Slime, and unzip it under your emacs/site-lisp directory.
3. Add the following to your ~/.emacs file:
   

   (setq inferior-lisp-program “c:/users/rob/documents/sbcl/sbcl.exe –core c:/users/rob/documents/sbcl/sbcl.core”)
   (require ’slime)
   (slime-setup) 

4. Restart Emacs, and then run M-x run-lisp to test whether Lisp starts up.
5. Start slime with M-x slime. Happy hacking!

 

Here’s what I’ve been working on all this time: Whirled is now in public beta!

Below is a live view into my room - stop by and say hello!

Casual games are fun to play and fun to make, but can a developer make a living from them? Funding the casual business was one of the prominent questions at this year’s GDC. I want back and forth between the Casual Games and Worlds in Motion summits, and managed to gather a few interesting tidbits. Here are my impressions.

The popular funding models are: 

• Indirect ad sales - ad rotator networks, etc., which let people participate in a larger pool of ad space providers
• Direct ad sales - such as doing a deal with a specific client, for banner or in-game ads
• Shareware model - aka try-and-buy, typically with a content lock (e.g. first level free) or a time lock (first hour free)
• Subscription - the standard MMO approach, pay per month
• Virtual goods model - aka free to play, pay for items

Of these, advertising is the most popular entry-level option, but it has its pros and cons.

Indirect ads are the easiest to get into - just sign up with AdSense or one of the other ad networks, and watch the money come flowing in! Except apparently it’s not that much money. People were mentioning ad revenue figures on the order of a few cents per thousand impressions. ¹ 

Direct ad sales seem to fare better, since you can deal with clients who want to target specific demographics. In their Worlds in Motion session, the WarBook devs praised this model. But they also admitted to 700 million pageviews per month (across all of their games), and their access to players’ demographic info makes them very appealing to advertisers. A brand new project won’t be able to play in that league.

The other popular model is shareware - downloadable games with free trial versions, and full versions available for purchase. It’s a classic model (Doom and Quake come to mind), with the trial version typically limited in content (e.g. first level or chapter free) or game time (e.g. first hour free).

This model was the focus of much discussion, since it’s the primary model for the established players. It’s clear that it can do wonders for hit games, especially since the full game price is customarily set at $10 or $20. But standard games don’t fare as well. Only ~1% of players end up buying the full version, and even then, distributors take a significant chunk. Additionally, most downloadable games get their players from portals, which exhibit significant churn due to a large number of very similar games being created - so differentiation and getting to the top of listings are both difficult.

The other two models are subscriptions, and “free to play, pay for items.” The latter has worked very well for us, while the former works for others, including the 800-pound gorilla of MMOs. Both systems have a significant optimal case, however - they’re best for games where players are compelled to keep coming back to the game, over and over again. Fitting this against ”consumable” games is non-trivial.

So the dominant model is still content-limited shareware, but it’s not an optimal case: budgets can be brutal unless your game becomes a huge hit. But banking on blockbusters is a classic hit-driven studio funding scheme, with familiar drawbacks, only recapitulated on a smaller scale. A more stable model is something like subscriptions or virtual items, which scale nicely, but they require a larger, continuous kind of a game.

---

1. This roughly fits with announcements I’ve seen elsewhere, e.g. MSN Games offering developers 10% of ad revenue from the games they publish.

Viral Coefficient and Growth

The viral coefficient is a measure of how many new users are brought in by each existing user. It’s a quick and easy way to measure growth: if the coefficient is 1.0, the site grows linearly, and if it’s less than that, it will slow down. And if the coefficent is higher than 1.0, you have superlinear growth of a runaway hit.

In an invite-only situation (e.g. gmail closed beta), it’s easiest to calculate this directly, based on how many people are being invited by each new user, and how many of the invitees create new accounts themselves. The viral coefficient is simply:

v = new user invites accepted / new users
   = accepts_t / δp_t-1

where δp_t denote the number of new users who join in time slice t (ie, the increase in population between p_t-1 and p_t). 

But most sites have an open account creation policy. For those, we’ll have to estimate population acceleration from raw population deltas. Let’s assume that each accepted invite is quivalent to creating a new account at the next time slice. Then we can estimate virability as:

v ≈ δp_t / δp_t-1
   = (p_t - p_t-1) / (p_t-1 - p_t-2)

which is an acceleration metric, easy to compute from historical data. 
 

Population Forecasting 

Viral estimate calculated as momentary acceleration will fluctuate over time. But we can use it for some short term forecasting.

To calculate expected future population p_t some t steps in the future, given the viral coefficient and present population p₀, we first invert the above:

δp_t = v δp_t-1 = … = v^t δp₀

and plug this right back in:

p_t = δp_t + p_t-1
    = Σ_k≤t  δp_k + p₀
    = Σ_k≤t  v^k δp₀ + p₀

This describes a geometric series. When v ≠ 1, p_t  = δp₀ (1 - v^t+1) / (1 - v) + p₀ 

Here are the results of a little benchmark I ran a while back, trying to figure out how expensive are the different primitive operations in Flash 9 (ie. bytecode compiled ActionScript 3).

Quick note on methodology: I ran these primitive operations in a tight loop of a few million iterations, to get average runtime per iteration (subtracting out the runtime of an empty loop, of course), and then repeated this a handful of times. I’m reporting mean numbers below, and standard deviations only when they’re unusual.

The raw times aren’t very important (benchmarks were done on an old Athlon 2400+ that’s living out its retirement years under my kitchen table). But the proportional differences between them can be surprising - especially the order-of-magnitude ones.

Now, on to some delicious results!

Numbers

Some obligatory numeric operation benchmarks:

Signed integer addition: 6.3ns
Signed integer multiplication: 13.1ns
Signed integer division: 15.3ns

Unsigned integer addition: 9.6ns
Unsigned integer multiplication: 28.3ns
Unsigned integer division: 32.4ns

Double addition: 9.4ns
Double multiplication: 7.4ns
Double division: 7.1ns

There’s really no reason not to use doubles for virtually all math operations; they’re much cheaper (possibly because they don’t try to do any bounds checks).

The one exception would be array indexing, where one really wants to guarantee that the index is an integer. Fortunately, conversions are pretty inexpensive as well:

Integer -> Number conversion: 7.3ns
Number -> integer conversion: 5.0ns

Now for some math library operations:

Math.sqrt: 137.9ns
Math.sin: 183.3ns
Math.round: 197.9ns
Math.floor: 160.2ns

That’s pretty good, much faster than regular function calls (see below) - probably because these are native, instead of bottoming out in bytecode like everything else. Still, a square root is on the order of about 20 times more expensive than arithmetic operations.

Function Calls

Speaking of which, here are the regular function calls - just the call, with no body:

Function call (no arguments): 239.8ns
Function call (unary): 257.6ns
Function call (binary): 269.0ns

Pretty standard stuff, with cost increasing (linearly?) as a function of the number of arguments. It’s more expensive than calling native functions, but not significantly higher. Still, it does put an upper limit of about 4 million function calls a second, or 100,000 calls per frame, on my test machine.

By the way, this was completely unexpected:

Anonymous function declaration: 11368.8ns (s = 105.3)

Creating an instance of an anonymous function costs 11 microseconds? Ouch. I’m a big fan of treating everything as lists of data, and map-filtering them with ad-hoc anonymous functions. But now I have to be more careful.

Arrays

For array access, I’ve only checked access of a single array element, many times over. Some numbers:

Writing from variable to array: 69.0ns, s = 1.9
Reading from array to variable: 106.3ns, s = 105.5
Reading from object with integer keys: 72.0ns, s = 1.9
Reading from object with string keys: 242.8ns, s = 1.8

First, I thought it was interesting that an object with integer keys is just as fast as an array with integer keys, suggesting a shared underlying implementation. An object with string keys is slower, however.

Two, the array reading measurement is not only pretty high, it also has a very high standard deviation, as if the measurements included a few really expensive outliers. Am I running into intermittent delays when accessing array data; perhaps cache stalls?

Finally, some results trying to iterate over a large array:

Iteration over array using ‘for each’ special syntax: 8576.8ns, s = 2.4
Iteration over array using int: 20483.5ns, s = 4.6
Iteration over array using uint: 19665.3ns, s = 2.8
Iteration over array using forEach: 31416.8ns, s = 47.7

I’m not susprised that code inside a for loop is faster than code inside a function called via forEach. What I am surprised about, is that the “for each ( … )” special form is much faster than the standard “for ( ; ; )” iteration with array lookup. That’s not what you’d expect in a language like C; I’m curious what’s going on under the hood.

AIIDE starts tomorrow at Stanford. We have a very impressive array of speakers this year, and an intriguing collection of papers. Hope to see you there!

Ayman invited me to give a talk at Y!RB this week, about our web-based game whirled world. The talk was a lot of fun, though a little technical - I did go into fairly painful details on both our software and community development efforts.

Afterwards, I got to hang out with some nice Yahoo people, and chat about their research and the future of web-based social interaction. Very stimulating. I wish I could do that more often.