Use cases for CHANGE-CLASS in Common Lisp

Posted on 2015-07-27 in Lisp

This is a post on use cases for Common Lisp's CHANGE-CLASS operation [0]. As the name suggests, it changes the class of an object without changing its object identity. It's an operation that a certain class of programmers would consider totally abhorrent. I think it's both cool and useful.

As far as I an see, the class of an instance has three effects in Common Lisp. It determines the set of slots the object has, it determines which methods will be executed when a generic function is called with that object as one of the arguments, and it determines how the object interacts with the rest of the system based on the metaclass of the class of the object.

... Continue reading ...

Detecting cheaters in an asynchronous online game

Posted on 2015-07-22 in Games

Introduction

This post is a description of some tools and data analysis I did for detecting players using multiple user accounts in an asynchronous online game. The code is available at GitHub.

A couple of months ago one of the players on my Online Terra Mystica site had some concerns that some of the players in the tournament were playing with multiple accounts. So I decided to do a bit of digging into the logs to see whether it was really happening or just paranoia.

... Continue reading ...

Unit testing a TCP stack

Posted on 2015-07-09 in Networking

Last year in an online discussion someone used in-kernel TCP stacks as a canonical example of code that you can't apply modern testing practices to. Now, that might be true but if so the operative phrase there is "in-kernel", not "TCP stack". When the TCP implementation is just a normal user-space application, there's no particular reason it can't be written in a way that's testable and amenable to a test driven development approach.

... Continue reading ...

Updated zlib benchmarks

Posted on 2015-06-05 in General

Last year I wrote a small benchmark suite to benchmark the various zlib optimization forks that were floating around. There's a couple of reasons to update those results. First, there were major optimizations added to the Cloudflare fork. And second, there's now a new entrant, zlib-ng which merges in the changes from both the Intel and Cloudflare versions but also drops support for old architectures and cleans up the code in general.

I'll write a bit less commentary this time, so that the results will be easier to update in the future without a new post. The big change compared to the 2014-08 results is that the Cloudflare version is now significantly faster particularly on high compression levels, but there are smaller improvements on all compression levels. Except for compression level 1, it seems like the preferable version now for pure speed.

... Continue reading ...

What's wrong with pcap filters?

Posted on 2015-05-18 in Networking

Introduction

I recently watched a video of a great talk on the early days of pcap by Steve McCanne. The bit on how the filtering language was designed - around the 26 minute mark but you might want to start at 20 minutes if you're unfamiliar with BPF - was one of the best stories about creating a new "little language" I've heard.

But that got me thinking a bit. This language is a tool that I use daily, that I'm generally happy with, but that also drives me absolutely crazy sometimes. This post is an attempt to look at some classes of problems that the pcap filtering language fails on, why those deficiencies exist, and why I continue using it even despite the flaws.

Just to be clear, libpcap is an amazing piece of software. It was originally written for one purpose, and it really is my fault that I end up too often using it for a different one. There's three very different use cases that I have for a packet filtering language (others may have more).

  • Small and simple filters to pick out a specific slice of traffic (single protocol, single flow, or single host). I believe it's fair to say that this is what the language was originally designed for.
  • Potentially complex filters for classifying traffic with real-time constraints and with no state, usually when using the filters for configuration rather than as an exploratory tool. This is where pcap is clumsy even when it generally works.
  • Offline analysis at higher protocol layers that'd benefit also benefit from tracking the high level protocol state between packets. You can sometimes coerce pcap to work for this use case, but it's super-awkward. It's also worth noting that features that are beneficial for this use case would not be welcome in the others. (Being able to run an arbitrary PCRE regexp on the packet payload? Great when doing offline analysis, unacceptable for real-time classification).

I try to do the third case with tools better suited for that, and only have a couple of complaints (e.g. VLAN support) on on first case. Mostly the pain comes from the middle case. So as we start the tour of annoyances, keep in mind that I'll often complain about a tool not doing a job it wasn't meant for.

... Continue reading ...

"It's like an OkCupid for voting" - the Finnish election engines

Posted on 2015-05-11 in General

Have I ever told you about the time I built an "OkCupid for elections" for the communists?

No? That's strange, I tend to get good mileage out of that story during election season. Unfortunately for the story to make any sense, you'll need a bit of absolutely fascinating background information on how elections work in Finland, and especially how websites that tell people whom to vote for became an integral part of it.

... Continue reading ...

A Monte Carlo simulation of Red7

Posted on 2015-03-30 in Games, Lisp

Red7 is a very clever little card game, and one of my favorite 2014 releases. But I have wondered about the density of meaningful decisions in the game. Sometimes it doesn't feel like you have all that much agency, and are just hanging on in the game with a single valid move every time it's your turn.

So here's some automated exploration of what a game of Red7 actually looks like from a statistical point of view. The method used here is a pure Monte Carlo simulation, with the players choosing randomly from the set of their valid moves.

Why a Monte Carlo simulation? I started trying to do a full game tree for a given starting setup but to my surprise the game tree is actually too large for that to be feasible; 2 weeks of computation even for a single two player game and a lot of optimization. The branching factor is just much bigger than it feels like when playing the game.

... Continue reading ...

Can't even throw code across the wall - on open sourcing existing code

Posted on 2015-03-19 in General

Starting a new project as open source feels like the simplest thing in the world. You just take the minimally working thing you wrote, slap on a license file, and push the repo to Github. The difficult bit is creating and maintaining a community that ensures long term continuity of the project, especially as some contributors leave and new ones enter. But getting the code out in a way that could be useful to others is easy.

Things are different for existing codebases, in ways that's hard to appreciate if you haven't tried doing it. Code releases that are made with no attempt to create a community around it and which aren't kept constantly in sync with the proprietary version are derided as "throwing the code across the wall". But getting even to that point can be non-trivial.

... Continue reading ...

Podcast on mobile TCP optimization

Posted on 2015-03-14 in Networking

I was recently a guest on Ivan Pepelnjak's (ipspace.net) Software Gone Wild podcast, talking about TCP acceleration in mobile networks, as well as whining in general about how much radio networks suck ;-) Thanks a lot to Ivan for the opportunity, it was fun!

You can listen to the podcast episode here.

Command languages as game user interfaces

Posted on 2014-12-08 in Games, Perl

In the previous post in this series, I promised to discuss in detail some of the positive and negative consequences of the less conventional design choices of my online Terra Mystica implementation. If you have no idea of what that is, reading at least the intro of that post might be a good idea. This post will just deal with one design choice, but it's the elephant in the room: the command language.

The canonical internal representation of a game in my TM implementation is as a sequence of rows, each describing a some number of player actions specified in an ad hoc mini language, or administrative commands that change the game setup in some way (for example setting game options, or dropping a player from the game partway through). This is what it might look like:

yetis: action ACT4
cultists: upgrade E6 to TE
cultists: +FAV6
giants: Leech 3 from cultists
giants: pass BON4
yetis: Leech 2 from cultists
cultists: +WATER
dragonlords: Decline 2 from cultists
dragonlords: dig 1. build G6
yetis: send p to EARTH
cultists: action FAV6. +AIR
dragonlords: pass BON7
yetis: upgrade E7 to TE. +FAV11
giants: Leech 3 from yetis
dragonlords: Leech 2 from yetis
cultists: Leech 2 from yetis

That's a short excerpt from the middle of a random game. A full game generally runs for about 400 rows.

... Continue reading ...