Being Shifty with Minecraft — Blue Sky Thinking
After spending a bit over three months at LShift, I am proud to leave LShift’s mark in the Minecraft Universe.
Frolicking over Minecraft’s cubic pastures and passing by interesting arrangements of hovering dirt blocks suspended in mid-air is all in a Minecrafter’s day’s work. But if you ever see light-blue wool blocks hanging around in the air, you can be sure that someone’s been . . . Shifty 
. . .
The ones you see in the picture above, in fact, have been put into the Minecraft world by a tool I wrote in Haskell. In this multi-part series, I want to share with you how I did it.
“Duck-finding” for testing your Theories
A while ago I wrote a semi-port of Haskell’s QuickCheck. Easy enough - a property is like a test method but with arity 1, into which you inject data - potential counterexamples to your theory. In Haskell, the type system can, through unification, figure out the type of the generator required for that property. What to do in a dynamic language?
The unreasoned Javan
I really hate null!
Reflect on that statement. Apparently Tim has a strong dislike for a concept found in lots of programming languages (even brainiac languages like Haskell) and successfully used in millions of programs. He must be crazy I wouldn’t like to have a discussion with him about something contentious like tabs versus spaces.
(Re-)adding a tray icon to Rhythmbox
One of the features I used to particularly like about Rhythmbox was it’s ability to minimise to tray. This meant with a simple click of an icon I could briefly bring it up on my current workspace to play/pause and then hide it again. However, in the new 2.90.x releases, the upstream has decided to remove this, which has been annoying me over the last few days.
Luckily, Rhythmbox has a nice plugin system, so I can fix that. Having done this sort of thing a little bit before, but not for a while, I started at the plugin writing guide. As it turns out, in the 2 weeks between starting writing this and doing this post, they’ve updated that guide a lot, but at the time it was very out of date. My major guide was in fact the ‘Remember the Rhythm’ plugin off of the 3rd party plugins list. Read more…
Unifying parts of structures
Those with even a passing familiarity with Prolog should recognise statements like [H|T] = [1,2,3]. In particular, = here is not “is equal to” but rather “unifies with”. So that statement causes the variable H to unify with 1, and T with the rest of the list, [2, 3].
Clojure’s abstract bindings provide much the same capability - (let [[h & t] ‘(1 2 3)] <do stuff>) - modulo the difference between pattern matching and unification, of course.
There’s a subtlety in something like [H|T] = [1,2,3], at least, if your lists aren’t built of nested cons cells. Consider Smalltalk arrays. Suppose we have some ListUnifier that will rip a SequenceableCollection’s head off, like #(1 2 3). We’d like the tail to unify with #(2 3) in other words. But that’s not a node in the original structure - it’s an entirely artificial node we wish to construct from the original collection. Firstly, how can we unify with only part of a structure and, secondly, how can we determine a solution from that partition?
Translating a persistent union-find from ML to Smalltalk
When I wrote my unification library a while back, I tried to add an “or matcher”. That is, something that would allow
| matcher mgu |
matcher := OrUnifier
left: (TreeNode left: #x asVariable)
right: (TreeNode right: #x asVariable).
mgu := matcher =? (TreeNode left: (Leaf value: 1)).
mgu at: (#x asVariable) "=> (Leaf value: 1)".
mgu := matcher =? (TreeNode right: (Leaf value: 1)).
mgu at: (#x asVariable) "=> (Leaf value: 1)".
Easy enough… until one tries to use an OrUnifier as an operand on the right hand side. See, as the unification progresses, if the first option fails, you’d like to backtrack part of the equivalence relation calculation, and with the imperative union-find in Nutcracker that’s not possible. What to do, what to do?
Finding new albums by old bands
I’m once again visting music-related problems, with a look at a different aspect of the “discovering new music” problem. Now, the LShift jukebox is very good at introducing me to new and weird artists, and it also occasionally tells me about other work by artists I’m already aware of, but this is all rather haphazard.
The core problem I’m trying to address is as follows: you find a new artist, and you really like them and buy all their CDs. Problem is, is that there’s nothing notifying me when they do a new release, and given new releases are a relatively rare event, I forget to check… essentially I want Songkick, but for CDs (or MP3 albums, but the principle still applies). Read more…
Benchmarking simple JSON generation in Java
What is the fastest way to produce JSON output in Java? Well if you have a complicated object tree to turn into JSON I would guess it is probaby Jackson. However, not all JSON output is complicated so maybe we can find quicker and simpler alternatives.
My test class is simple, I call him Thing, he has two fields name and content, he isn’t a Java bean because he doesn’t need to be (maybe your classes don’t need to be Java beans either!), here he is:
public class Thing {
public Thing(String name, String content) {
this.name = name;
this.content = content;
}
final public String name, content;
}
We will use JUnitBenchmarks to test my theory that you can be simpler and faster than Jackson. JUnitBenchmarks allows unit tests to be run multiple times and measurements taken, it also allows the code to be warmed up so any JIT compilation should have been carried out before measurements are taken. I’ve set my tests to run a warmup period of 50 iterations followed by 1000 measurement iterations. The Jackson code being tested looks like this:
public class JacksonStreamingSerialiser implements Serialiser {
public String toJson(Thing thing) {
StringWriter out = new StringWriter();
try {
JsonGenerator generator = jsonFactory.createJsonGenerator(out);
generator.writeStartObject();
generator.writeStringField("name", thing.name);
generator.writeStringField("content", thing.content);
generator.writeEndObject();
generator.close();
}
catch (IOException e) {
e.printStackTrace();
}
return out.toString();
}
private final JsonFactory jsonFactory = new JsonFactory();
}
When tested we get a mean measurement for writing 250 objects using Jackson of 0.95 seconds
json-lib is usually a worse performer than Jackson. Here is the equivalent code using json-lib:
public class JsonLibSerialiser implements Serialiser {
public String toJson(Thing thing) {
JSONObject object = new JSONObject();
object.put("name", thing.name);
object.put("content", thing.content);
return object.toString();
}
}
When tested we get a mean measurement for writing 250 objects using json-lib of 10.74 seconds. Not so good!
Who needs library code? Maybe that new fangled String.format will be quicker and simpler. Here is the code:
public class StringFormatSerialiser implements Serialiser {
public String toJson(Thing thing) {
return String.format("{\"name\":\"%s\",\"content\":\"%s\"}", thing.name, thing.content);
}
}
When tested we get a mean measurement for writing 250 objects using String.format of 5.26 seconds. Better than json-lib but Jackson isn’t looking worried!
I guess that format string must be expensive to parse so lets try a StringBuilder. Here is the code:
public class StringBuilderSerialiser implements Serialiser {
public String toJson(Thing thing) {
StringBuilder builder = new StringBuilder();
builder.append("{\"name\":\"").append(thing.name).append("\",\"content\":\"").append(thing.content).append("\"}");
return builder.toString();
}
}
When tested we get a mean measurement for writing 250 objects using StringBuilder of 0.91 seconds. Finally a winner, faster than Jackson but you had better quote those strings properly!
People have always told me that StringBuilder is unsyncronised so should be faster than an old fashioned StringBuffer so lets check. Here is the code:
public class StringBufferSerialiser implements Serialiser {
public String toJson(Thing thing) {
StringBuffer buffer = new StringBuffer();
buffer.append("{\"name\":\"").append(thing.name).append("\",\"content\":\"").append(thing.content).append("\"}");
return buffer.toString();
}
}
When tested we get a mean measurement for writing 250 objects using StringBuffer of 0.60 seconds. Hang on! That is the fastest yet! What is going on?
What is going on is that I have been playing fast and loose with statistics by only presenting the mean times in seconds for each benchmark. By extracting the raw data and applying the power of statistics (well I looked at the distributions and standard deviations) it turns out you cannot tell the difference between the StringBuilder and the StringBuffer, so all is well, and String[Builder|Buffer] are both winners! Jackson is also a winner since for more complex object trees it will allow you to write more maintainable code than using a StringBuilder combined with loops and conditional logic and is almost as fast as a StringBuilder (or StringBuffer).
So what have we learnt? Firstly, use Jackson if you have to serialise your objects into JSON. Secondly, JUnitBenchmarks is a very handy library. Thirdly, if you don’t present a standard deviation with your benchmark results then your results may not mean what you think they mean.
Implementing maps and folds using Zippers
Zippers continue to fascinate me. Let’s recap a bit: a zipper is a data structure representing the navigation and mutation of an otherwise immutable structure. We’ve looked at several different implementations here on the LShift blog, in several different languages.
Today, we’re going to see what else we can do with zippers.
Randomly testing Ruby
I recently ran into the need for testing the behaviour of a parser of a modelling language. The parser processes a number of model descriptions in gem files, as well as local definitions. Until recently, the parser would process the gems in an arbitrary order. However the language while ostensibly declarative, isn’t, because of a huge restructuring of the parser. As a result, some bugs lurk in the changed code. These bugs, because of the arbitrary processing order of the model gems, manifest on some machines and not others. Forcing an ordering on the gem processing masks the underlying issues, even while letting the users of the parser to get on with their lives.
What to do? Random testing to the rescue! I cast around for Ruby ports of QuickCheck, and found two: rushcheck and rantly. Rushcheck hasn’t been wrapped up in a gem, so I decided to take rantly for a spin.