Overooped

Japan, in 1991 and 2008 respectively. Same train, same platform; very timeless. And VERY crammed!

Mutable Adventure, Pedro and Erlang Text Processing

As some of you might know, I’m currently writing a game called Mutable Adventure, a 2D sidescrolling platformer MMOG with the editability of Second Life.

The thing about Mutable that interests me the most, however, is the networking. I’m using a library/protocol called Pedro, by Peter Robinson, which I found when Keith Clark presented it at work. Before I go on, I need to explain why this protocol is so goddamned cool.

Pedro and software agents

It’s based on Prolog, more specifically, his own implementation of QuProlog. It’s sort of a blackboard system, with a central messaging server that everyone connects to. It’s string-based, and what you send over the network are prolog fact-style messages, called a notification, for example:

  playerWasHit(152, 12388)

This is then broadcasted to everyone to subscribe to this message. A subscription might look like this:

  playerWasHit(PlayerID, ObjectID), PlayerID = 152

Notice that the expression contains Prolog variables, and a guard expression. This means that several clients may subscribe to the same notification, but with a guard expression that says they only want player info about their own player.

Each subscription is accompanied by a number, so that you on the client side can redirect the incoming notification to the right place. In Python I’ve implemented this so that individual objects may subscribe, and that individual objects may receive notifications. For example, say a ball is spawned in the game world. At the instance it’s instansiated, it may subscribe to information pertaining to this specific instance, by giving the subscription a guard expression with its own ID number. Boom, automatic network message propagation within your game client or server. As an example, in the client, the Tilemap class is appended with a category/mixin with the following code (notice the third argument, the guard):

  gClient.net.subscribe(self, "tilemap(TilemapName, NameOfTilesetTilemapUses, ScrollX, ScrollY, AutoScrollX, AutoScrollY)", 
                              "TilemapName = \"%s\""%self.name)
  gClient.net.subscribe(self, "tileInMap(TilemapName, TileX, TileY, TileIndexInRoomTileset)",
                              "TilemapName = \"%s\""%self.name)
  gClient.net.subscribe(self, "tilesInMap(TilemapName, FromIndex, ToIndex, TileIndexArray)",
                              "TilemapName = \"%s\""%self.name)

(Voxar has significantly improved the syntax in the Pedro python wrapper since then)

Suddenly, your objects aren’t mere objects; because they can communicate on their own with the outside world, and respond on their own, they’re now software agents. Also, because the messaging medium is now separate from the server instance, your game server may now be freely split as you see fit into several processes, both for load balancing and for division of labor into discrete entities, with higher cohesion and lower coupling.

The downside

Peter Robinson’s implementation of this concept isn’t perfect, however. First off, it’s written in plain c, and it depends on glib2. GObjects. I can’t stand GObjects. I can’t stand manual memory management. And it’s 5000 lines of code for a relatively simple concept.

Secondly, you just traded yourself simplicity for the price of a single bottleneck. A buggy, unstable, memory leaking single bottleneck with no means of load balancing or distribution. Written in C with a single maintainer, based on glib2 which is pretty hard to get running under Windows, if you would want to.

(I attended a 24 hour game development challenge a while back, where I wrote a networked 3D racer. Because I couldn’t get pedro running under Windows, I had to run it on my own server at home, while the judges tested the game from the other side of the country. >1sec lag and no lag compensation or similar whatsoever in the code = I certainly didn’t win that competition :( )

Erlang, The Savior

After reading Joe Armstrong’s book on Erlang, I was itching to write something. I tried writing a Twitter clone, thinking that Erlang’s highly distributed nature would come to great use there, but every line took a minute to write (because I’m so new to Erlang), and Twitter just felt too big and too difficult to write as a first project, so that got abandoned.

So, the next thing I’m trying is to write a Pedro clone in Erlang. It’s a good match, since the hardest part of of Pedro is the pattern matching, and Erlang got that as a part of being a functional programming language. I’ve set out to get it to work in 100 lines or less. So far I’m up to 60 lines, and I think I have a chance of making it.

In Erlang, processes are cheap and abundant. You spawn a lot of processes and then do all communication through erlang messaging. A common pattern is the middle man pattern. While cleaning the dishes I remembered this pattern, from its usage in an IRC client built in the book, and tried to apply it to Erdro (Erlang Pedro :P) conceptually in my head (Sorry, the following is a bit hazy as 1) I haven’t implemented it yet 2) it contains a lot of erlang terms). One problem with Erdro is that in its current implementation, even if you have a supervisor process watching the server and respawning if it does, restoring all the stack state, the process would be dead and the sockets meaningless, and all clients would have been lost and restring state would be pointless. However, if each client is abstracted away with a middle man process (meaning all socket communication goes to and from a separate process, and communication with the server is handled through erlang messages), you could store all the state including process pointers to these middle men in a mnesia database or similar, and if the server dies, respawn the server and its state and everything you’d have lost was a single message (the one that made the server crash); all socket connections would be alive and all clients just continue communicating.

Put the middle men on a cluster of machines away from the messaging server, each with its own IP and bandwidth, and you’ve distributed your network load. The machine containing the messaging server could self-immolate, still only a single message would be lost (given that there is another computer that could act as messaging server).

Process load balancing of the server, however, is left as an exercise for the reader.

The nitty gritty details of text processing in Erlang

There’s a slight mismatch between Erlang and Prolog, given that they’re completely different languages (one is functional, the other is logical). In the context of Pedro, however, I could only think of a single difference that mattered, and had to be changed.

In Prolog, the term “myFunctor(atom, anotherAtom)” defines a fact. In Erlang, it’s a function call. So, for this to work, I’d have to convert that term to something equivalent that could be used in Erlang pattern matching: a tuple, like so, “{myFunctor, atom, anotherAtom}”. Since Pedro doesn’t have tuples, the transformation is reversible and fully equivalent (I hope! It’s not like I’ve tested my code yet…). How would you do this? The first thing on my mind, being a ruby coder, was regular expressions. My first realization was the erlang’s regexp support is really, really, really horrible. Not only is it slow, its syntax support is so basic you might as well do without. My second realization was that regular expressions were a really bad match for the task at hand anyway. So my first real piece of Erlang code was a text search-and-replace implementation with pattern matching specific to my task:

functor_to_struct(PrologString) ->
  [First|Rest] = PrologString,
  fts("", [First], Rest, false, 0).

fts(BeforeFunctor, Functor, [], _, _) ->
    BeforeFunctor++Functor;
fts(BeforeFunctor, Functor, Rest, InStringEscapeMode, Prev) ->
  [Next|Rest2] = Rest,
  case Next of
    34 when (Prev == $\\) and InStringEscapeMode -> % \"
      fts(BeforeFunctor++[34], "", Rest2, true, Next);
    34 -> % "
        fts(BeforeFunctor++[34], "", Rest2, not InStringEscapeMode, Next);
    Char when InStringEscapeMode ->
      fts(BeforeFunctor++[Char], "", Rest2, true, Next);

    $( ->
      fts(BeforeFunctor++"{++Functor++", " , "", Rest2, false, Next);
    $) ->
      fts(BeforeFunctor++Functor++"}", "", Rest2, false, Next);
    Char when ((Char >= $a) and (Char == $A) and (Char == $0) and (Char =
      fts(BeforeFunctor, Functor++[Char], Rest2, false, Next);
    Char ->
      fts(BeforeFunctor++Functor++[Char], "", Rest2, false, Next)
  end.

Half-way through the code, it felt so horrible, I felt like I was writing the worst code in the universe. Now that it’s done, though, I find it pretty nice. It’s relatively short for what it accomplishes (replaces function calls with tuples, being careful not to interpret parens inside a quoted string) imo. However, after a good night’s sleep, I realized that this was a really stupid way of doing it. Why? Because Erlang has a code parser in its standard library.

  {ok, Scanned, _} = erl_scan:string("foo(bar)."),
  {ok, Parsed} = erl_parse:parse_exprs(Scanned)

yields [{call,1,{atom,1,foo},[{atom,1,bar}]}], a perfectly fine nested Erlang data structure that can be traversed and parsed. So that’s what I did!

  transform_calls_to_tuples(ParseTree) ->
    tctt(ParseTree, []).

  tctt([], Collected) ->
    lists:reverse(Collected);
  tctt([Token|Rest], Collected) when element(1, Token) == call ->
    {call, 1, FunctorNameAtom, ArgumentList} = Token,
    tctt(Rest, [{tuple, 1, [FunctorNameAtom | tctt(ArgumentList, [])]} | Collected]);
  tctt([Token|Rest], Collected) ->
    tctt(Rest, [Token|Collected]).

… which yields the same result, but in a parse tree (which you can turn into a string again with erl_pp, the pretty printer).

That’s it! I’ll get back to you when Erdro is done.

Weekend Hacking

I had a lot to do this weekend and decided to do none of it, and instead ported sfxr to Cocoa, with a native UI and proper save/load :) My version’s called cfxr (as in “Cocoa sfxr”) and is available at http://thirdcog.eu/apps/cfxr . I’m not saying it’s better than sfxr, only different and more native. If you’ve got a 10.5 Mac, check it out and let me know what you think :) It’s basically just an experiment to learn Core Data and Bindings (Thanks, Scott!), and a reason to make save/load work better on the Mac.

The sfxr code (more specifically, the sdl port), when I first saw it, seemed like the worst mess I’ve ever seen. Sure, it’s a quick hack, but not even keeping state in a struct? OMG. But after working with this code for a weekend, it’s surprisingly good for what it is! “Porting” it to Cocoa was as easy as finding out which globals were properties of the sound (that is, attributes), and adding “sound.” before all accesses to those, and #defining objc syntax as C syntax for the four major playback methods. I guess I could’ve #defined the sound attribute accesses as well, making an upgrade as easy as a copy-paste, but I felt I had already done enough code generation for one day :P (Check out the legacyAccessors.m in the source to see what I mean :P Not very good looking code but it got the job done.)

It’s a rough 0.1 and might need some work. I was also thinking about making the playback part an AudioUnit or VST (just for fun) to make the playback more flexible. It works pretty nice as it is though, so do check it out :)

Lazy Man’s Logging

file_put_contents(…, FILE_APPEND) to log is a bad idea and you know it, but it’s sometimes good enough, or you just don’t get paid enough to make something serious. I just let you make it a tiny bit more serious, a whole lot more dependable, and still just change a single line of code.

  /// Creates a table called $table as (id, when, message) if none such exists, and inserts a row with $message in it.
  /// If no connection details are given, it uses the current database connection. Same goes for $database and $when.
  ///
  /// @returns TRUE on success or FALSE on failure.
  ///
  /// @example mysql_put_contents("orders", "I CAN HAZ CHEEZBURGER?", "mysite", NULL, "127.0.0.1:3306", "mysite_user", "secret") or die(mysql_error());
  /// @example mysql_put_contents("guestbook", "Longcat says: I'm loooooooooooong") or die("Errorz!");
  function mysql_put_contents($table, $message, $database = NULL, $when = NULL, $host = NULL, $user = NULL, $pass = NULL) {
    if($host)
	    mysql_connect($host, $user, $pass);
	  if($database)
	    mysql_select_db($database);
	
	  $qry = "CREATE TABLE IF NOT EXISTS `$table` (
             `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
             `when` TIMESTAMP DEFAULT NOW(),
             `message` TEXT NOT NULL
           );";
    $result = mysql_query($qry);
    if($result === FALSE)
      return FALSE;
      
    $qry = "INSERT INTO `$table` VALUES(NULL, ".($when ? $when : 'NULL').", '".mysql_real_escape_string($message)."');";

    $result = mysql_query($qry);
    if($result === FALSE)
      return FALSE;
      
    return TRUE;
  }
	

Re: Firefox 3 vs. Safari 3

I agree with everything that Gruber writes about in his latest article. A friend of mine went majorly goddamned-mac-zealot on me and his article (had to explain not once but *twice* that Gruber wasn’t saying “FF should be exactly as Safari” but “Safari beats the Mac port of FF on a number of points” :P) All is well and good though, as he found a fix for the most annoying UI element of FF3 for me: single-click-selects-entire-URL. I almost screamed from frustration from just trying to edit the URL a few days ago. Here’s how to fix it, though:

1. Go to about:config (type it in the location bar and type enter)
2. Filter on “clickSelects”
3. Double-click on the row that says “browser.urlbar.clickSelectsAll” to set it to false.

Now when you single-click in a Firefox location bar, it’ll place the caret in it; double click will select word; and triple-click will select the whole line, just like in a Mac app.

Addendum: Okay, so Voxar tried to convince me that Safari’s location bar was idiotic and illogical (of course only from reading Gruber’s article and not trying it out, even though he has a Mac on his desk :P), and challenged me: if Safari always highlights the first autocomplete entry when you type an url, wouldn’t it be VERY cumbersome to enter e g “http://daringfireball.net/2008/” when the only URL in your history is “http://daringfireball.net/2008/04/firefox_3_safari_3”? The answer is of course, no :) In Safari, you type “da[right-arrow]2008[backspace][enter]” and you’re done with it. The same scenario in Firefox would require you to type the entire URL in by hand, since the autocomplete would be completely useless (even the AwesomeBar would be stumped!). Now I remember why I love Safari :) (Watch It In Full Motion.)

Nevyn’s First Rule of Singleton Evilness

I finally figured out a litmus test for whether being a singleton is okay or evil for a particular class:

If a class is thread-safe and has no state that can be changed, it may be a singleton.

NSFileManager: OK. RMS::Sound::Gateway: Not so much.

I suppose there are ways to circumvent this rule; e g most of Apple’s singletons may be created either through the+[defaultManager] method, or instantiated on-the-spot, e g if you want several separate NSNotificationCenter inside the same application.

This discussion came up during the creation of the RMS game engine, among many other times. Now that I’m ripping out parts of the engine for re-use, I realize that it was a very bad design decision to use singletons the way we did. For example, my 2D modeler prototype for my candidate thesis is document-based, thus it needs an RMS::Sound::Gateway for each window. This is no-can-do until I fix the code, because for example the Voice class has the delegated play method, and the way it works is that it gets the global gateway and adds itself to the gateway’s list of playing voices.

“State that can be changed”? Oh, right. +[NSColor redColor] has state, but it can still be a singleton since that state can’t be changed by my code. Same for NSEvent’s singleton methods, and so on.

Not sure why Core Audio isn’t an Objective C API

It’s for performance, right? It’s the only good reason I can think of. And, you know, it sounds sensible. I mean, ultra-low latency and all that, you probably don’t want that objc dispatch overhead.

I just did an experiment, however. I dislike working with C APIs, so I’m writing Cocoa wrappers for Core Audio, just exposing those pesky Component properties that take five lines to set or get, with simple methods. Suddenly I thought, “Wait, what if I try to use an objc method as a render callback? Those require very low latency and are called often. So I should be seeing some of that objc overhead.”.

Very unscientific comparison, comparing a simple sine renderer in c and objc, on an MBP 1.83x2 (source available on request):

• CPU usage in app using C callback: 3.0%
• CPU usage in app using ObjC callback: 3.1%

This isn’t, by far, any compelling evidence that Core Audio should be Objective C; I’m just saying it seems more feasible than I originally thought it’d be. Also, actually thinking about the problem, I realize that the callback’s only called 44100/512 ≈ 86 times a second and has about 10 ms to complete (astronomically long in computer terms).

But NeXT did it that way, didn’t they? I want to remember that NeXT had basically /everything/ in objc, including drivers and audio and such things. So, why not Mac OS X? NeXT was hardly known for being a slow OS. Tell me what I’m missing in the comments.

These are my children. They join me on all my journeys.

So I use a lot of small utility classes that just jump between projects. Not enough to warrant a library, but still code I can’t live without. For example, ary(id first, …) instead of [NSArray arrayWithObjects:…], dict(id key, id value, …) for a dictionary, sf(NSString *format, …) instead of [NSString stringWithFormat:…], a zooming and delta-scrollable CALayer, vector class with most linear algebra, line class, simple macros to turn of CoreAnimation animations… You get the point.

Anyways, from my last blog entry you might have gathered that NSOperationQueue, CoreAnimation and garbage collection don’t really work well together. It seems to be a problem with ensuring that only a single is committing changes/transactions at a time (hence a crash in CALayerEnsureTransaction). NSOperationQueue sets up a full thread with a run loop for every single operation. I have no idea why they chose this wasteful approach; personally, I’d reuse a set of threads. And since NSOperationQueue isn’t working, and my entire acoustic modeling simulation is built around NSOperations, I decided to do just that. Thus, FakeOperationQueue joins my army of utility classes. It has the exact same interface as NSOperationQueue (almost, I only covered what I use), and works on NSOperations. Note that it doesn’t consider dependencies! It’s a very simple class, only a hundred lines of code.

Rentzsch seemed somewhat interested in my fake queue. Thus, I decided I might as well put my stuff online.

• FakeOperationQueue.m FakeOperationQueue.h
• NCCommon.m NCCommon.h — ary, sf, dict; foreact macro stolen from somewhere; probably more
• BNZVector.m BNZVector.h (I was planning to join a contest for BNZ but I enver got around to it, hence the prefix)
• BNZLine.m BNZLine.h BNZLineTest.m
• CALayerAdditions.m CALayerAdditions.h
• CAScrollDeltaLayer.m CAScrollDeltaLayer.h — Sort of embarrasing code, I’m probably mixing some spaces up, but it’s very handy when scrolling from -[NSResponder mouseDragged] with mouse deltas