DSByte: Scala-based DSL for binary data structures

About a year ago, I wrote about a tool for creating binary structures more easily. It was inspired by Erlang's binary packing syntax, and was for a scenario where a server was creating small binary for a client that didn't speak Java (i.e., so simple serialization wasn't a possibility)

I recently decided to recreate it, but this new version is a whole new beast. It's still inspired by Erlang's syntax, but I'm enhancing that syntax, I rearchitected it, and I wrote it in Scala.

The very early version of DSByte, as I call it, can be found under my github account. It currently only supports packing from objects into binary, but I'll add unpacking from binary into objects soon.

One of the things I like about Scala is built-in support for simple DSLs, and this was a good opportunity to exercise that feature. While the parser combinator feature takes a bit of getting used to, it's quicker and friendlier than ANTLR, though it's also less powerful. But for my need, it fit the bill nicely.

All Together Now: A Look at Concurrent Languages

Over the past several months, I've been taking a look at various languages that advertise easy concurrency and scalability. It's too late to use any of them on SimCity, but I'm always thinking about what I'll build next and how I'll build it, and these languages are on my radar. Java is increasingly cumbersome to me as a language, and its concurrency constructs are too error-prone even for senior programmers, not to mention that the thread model Java exposes has serious performance issues if not carefully managed.

Here's my quick take on the three languages I focused on: Erlang, Scala, and Go. The TL;DR version: I'd use Erlang for infrastructure in a heartbeat, Scala will make your developers more productive at the possible expense of application performance, and Go is fast but less fun to work in.

For each language, I worked through at least one book on the subject and then built something for myself. The personal projects ranged from small to sizable.

Erlang

Erlang was my favorite of the three languages, and it would be hard to ever argue against using Erlang for back-end infrastructure pieces that require high scalability. Say, message queues, or chat systems, or NoSQL databases, or the backbones of prominent first-person shooters.

Like all these languages, it has a high-level abstraction for concurrency, but, unlike the others, it easily supports passing messages between machines, which bodes well for a cluster of servers. It has extensive fault tolerance mechanisms, even across machines, allowing for robust systems. It has support for hot code swapping, opening the possibility of upgrading a system while it's still live and reducing maintenance windows to nil. It has great support for extracting values out of binary data, which is invaluable when dealing with network traffic and proprietary data formats. It's a mature, proven technology. And it has the benefits of functional programming: more concise code that reduces the number of potential bugs and immutable objects that prevent weird thread-safety issues.

On the other hand, I can probably count on one hand the number of other Erlang programmers I've met. And it's not like taking a C programmer and teaching them Java; functional programming is a distinct mental shift from imperative programming, and it can be hard to get your head around it. That means that you can write your Erlang code all you want, but what about the people who will have to maintain your system beyond you? Its small community also means that while there are certainly lots of third-party libraries for it, it's not the vast universe that Java enjoys. And while immutable objects are easy to work with, they're also expensive because new ones are constantly being made.

Scala

While Twitter's Scala School argues for treating Scala as a separate language, it's hard not to compare it to Java, since it compiles down to Java bytecode and runs on the same virtual machine. And in terms of developer productivity, Scala rockets past Java in my book.

As an application layer language, it has tremendous advantages. You can accomplish complicated tasks with much fewer keystrokes. You can use functional paradigms and immutable objects, but also use imperative style and mutable objects if you need performance, or, crucially, if you need to bring another developer on board with your system. You can enjoy the same concurrency abstraction Erlang provides. You can leverage Java's seemingly infinite supply of open-source libraries. You can incorporate it into an existing Java application, giving you the ability to bring it in without rewriting everything. You can even easily build internal DSLs with it to make your system more expressive and easier to maintain.

But, in my own experiments and in anecdotal evidence, it suffers from sluggish performance. All that great functionality makes your developers more productive, but potentially at the expense of speed. This makes sense; all that pretty code needs to be contorted and converted into Java with who-knows-how-many object creations along the way. Obviously Twitter and Foursquare manage to be fairly fast, but how much engineering time is spent to get them there? On the other hand, a system that enjoys greater and easier concurrency than Java might be more scalable and have more consistent performance under load, even if any given call could be faster in another language.

Go

Go is Google's attempt to build a better C, with a focus on developing distributed systems at a scale that Google needs. Its concurrency model is distinct from Erlang and Scala's, preferring the notion of Communicating Sequential Processes to the Actor model, but neither is particularly superior; each has strengths and weaknesses that fit different situations.

The big win with Go is its speed: Go programs are compiled down to machine code. And while the built-in garbage collection probably means that C would win a horse race between the two, Go is a much less error-prone language to work in. Its community is still young, but it seems eager to improve the language, and a wide variety of useful go libraries already exist. It's hard to compete with the many years of robust Java libraries out there, but Go nuts seem to have filled in the most obvious needs.

I have to admit that I dislike working in the language itself; it lacks the cleanliness of Erlang and the depth of Scala. But there's no denying that its concurrency model is easy to work with, and the programs that you create are nice and zippy relative to their Java counterparts.

Others

I've yet to dig deep into Clojure, though it's the obvious next one. I figure if I'm going to be a fan of functional programming, I might as well go into crazy Lisp land. But I'd worry that it would suffer from the same performance problems — for the same reasons — as Scala.

It seems funny to mention node.js in this post, since in some ways it's all about zero concurrency: a single thread of execution is all you get. Of course, under the hood there's lots of asynchronous work, but it's tied directly to the operating system's I/O. We use it for a subsystem in SimCity, and it, like everything, has strengths and weaknesses. It can do lots of I/O tasks concurrently. Lots. But it's very sensitive to slow code, since that code will block the entire thread when it runs. It appeals to the game developers on my team, since single threads, event loops, and performance-sensitive code are the norm for them.

However, it's not very mature, and the libraries for it can be buggy and incomplete at this stage. I think we made the right decision switching our SimCity subsystem to node.js, since it outperforms its Java predecessor by a long shot, but it hasn't been simple or without issues.

Scala and Java: A Simple Application

My boss recently asked me how I'd build out SimCity's online systems today if I knew everything three years ago that I know now. I didn't hesitate. "I'd take a good, long look at Scala and, by extension, Lift."

Scala has a lot that appeals to the me of today. I like its hand-in-hand support for functional programming and emphasis on immutable objects. I've gotten used to both concepts with Erlang, and I've come to appreciate that programming paradigm for building robust, scalable systems. But Scala also offers imperative syntax and mutable objects if you need them.

Scala has native support for the actor model abstraction of concurrency, which I first encountered with Erlang (Scala's syntax is openly lifted from that language's). The actor model makes it much easier to manage and reason about concurrent code, and Scala supports two major implementations: actors tied to particular threads or event-based actors thrown onto whatever thread is available, maximizing resource utilization.

And, unlike something like node.js or even Erlang, Scala has a huge universe of libraries at its disposal thanks to its bytecode-compliance with Java.

All good stuff. I thought it was time to do something real with it.

Before I dove into a large system, I thought I'd write a simple application. We have a group of binary files on SimCity that are very important to the game but, being binary, aren't easy to debug when something goes wrong. So I thought I'd do a quick project on my own to write a Java-based parser for the files and compare it to a Scala-based version. Little admin tools like this or other low-risk sections of the code base are often good ways to try out new tech and see if it will fit into the larger project. This code didn't leverage any of the concurrency systems in Scala; I just wanted a simple program.

One reason people like Scala — and, indeed, the many other JVM-compatible languages — is conciseness. Spend any time at all with Scala, Ruby, or — it sometimes seems — any other language, and Java's verboseness begins to feel like cement around your hands, sucking time and productivity away from your programming. Plus, more code, even Java's boilerplate, means more potential bugs.

As a simple measure, I compared the the non-whitespace characters in my two versions. I structured the programs the same way, mirroring class structures and refactored methods. But I used the support that each language gave me for keeping things concise.

The Java version was 5258 characters. The Scala version? 3099. The Java version was almost 70 percent larger.

Java Code	Scala Code
5258	3099

Scala's biggest single win was with a file full of small classes that defined types of data within the file I was parsing. The Java version was 160 percent bigger than the Scala one.

This makes sense. Let's say you wanted an immutable class in Java to represent a point in 3D space. This is about as concise as you can get it.

public class Point {
   public final float x, y, z;
   public Point(float _x, float _y, float _z) {
      x = _x;
      y = _y;
      z = _z;
   }
}

Here's the equivalent Scala code.

class Point(val x: Float, val y: Float, val z: Float)

But Scala offers lots of little aids as well. You rarely need Java's omnipresent semicolons; you don't need to declare types as often, since Scala can usually infer them; you don't need to explicitly type "return" at the end of a function, because the last result in the function is the return value; you don't have to declare that you throw exceptions. The list of little things goes on and obviously adds up.

Functional programming, too, offers some conciseness. I needed a routine to read an unsigned int out of a variable-length byte array. In the Java version, I wrote this:

private static int byteArrayToInt(byte[] bytes) throws IOException {
long retVal = 0;
    for (int i = 0; i < bytes.length; i++) {
        retVal = (retVal << 8) | ((long)bytes[i] & 0xff);
    }
    return (int)retVal;
}

In the Scala version, I wrote this:

private def byteArrayToInt(bytes: Array[Byte]) = {
    ((0L /: bytes) {(current,newByte) => (current << 8).toLong | (newByte & 0xff).toLong}).toInt
}

(The references to longs in this int-parsing code are to cope with the fact that I needed to read very large unsigned ints from the files, which Java defaults to interpreting as signed integers. The way to get around that is to write into a larger memory space, namely a long.)

You could argue that the Scala version is concise to the point of obtuseness, even if you're familiar with the functional-programming mainstay foldLeft operation it represents. I agree that there's a balance to be struck. In particular, I'm not sold on the /: operator for foldLeft; I might opt for spelling it out to be more clear.

For functional programming geeks, note that, to the extent it can, Scala offers tail-call optimization on recursive calls.

But things weren't all sunshine and roses on the Scala side. Here is the average time to run my program for each version, timed over 1000 iterations.

Java Time	Scala Time
88ms	182ms

To some extent, I expected this. Scala has to compile down to Java bytecode, which means that all that syntactic sugar and functional programming and closure support must turn into Java concepts somewhere. Even my little program generates a slew of extra classes and, presumably, lots of extra code that has to be navigated. Also, I think it's reasonable to imagine that immutable objects necessarily mean that new objects have to be created more often than they would in mutable space, where you can change an object directly. Finally, I've been working with Java in one form or another for 16 years or so; I've been working in Scala for about three days. So I'm likely missing out on performance tips.

Though I admit this seems like a huge difference for some extra classes and objects and missing an optimization step or two. Even if it's correct, I'm still of the mindset that greater productivity and easier, safer concurrency are big wins. (Note that you could always switch to imperative mode in key sections if performance demanded it, in much the same way that some sites offload work to C programs.)

If I were really honest about how I'd rebuild SimCity, I'd probably use Erlang, where you have to do things functionally, have a virtual machine that supports what you're doing, and have native systems for handling failures with aplomb. But Scala at least offers the potential of hiring from the pool of Java programmers, whereas Erlang really doesn't. (On the other hand, the vast majority of Java programmers I've seen seem to be couched safely and comfortably in Java, so wouldn't necessarily adapt. But Erlang would be a way bigger change, I think.)

I'm going to keep plunking away at Scala and try to build something a bit more real with it. Event-based actors might be a bit slower, but if they can scale vastly better, that may matter more to a site.

Meaty Learning Projects

My job description implicitly includes understanding current technologies, philosophies, and methodologies. Usually, this is just a surface-level knowledge about what's going on in the industry, but occasionally I decide to dig deeper.

For instance, right now I'm learning Scala because I think it will solve some thorny performance issues at work. But it's a Catch-22: I don't want to introduce a whole new language without knowing if it will really benefit us, but I can't know if it will benefit us until I try it with a meaty project. And it's even worse than normal in this case: The feature I really want to explore — actors — requires a decent chunk of knowledge before I can take advantage of it.

Over the years, I've developed a solution to this problem. I have a substantial, but not overly complicated, program that I write whenever I come to a new platform. I write a program that assists me in finding solutions to the kind of thorny word puzzles you get from the National Puzzlers League. It requires me to open a file, read in words, and see if they match the pattern the user is searching for. No network connection. No database work. No scalability issues.

It's a problem space I understand, so I can dive in without much thought. I get a deeper knowledge of the language than I'd get from working through a tutorial's abstract problems. It forces me to probe and dig through the libraries to accomplish what I need. I don't get a thorough understanding of the language, but I get pretty far.

Overall, it's a plan that's worked well for me.