Biilmann Blog

I spent quite a lot of the last two weeks completely rewriting the internals of a PHP based web-service in use at webpop.com.

The codebase was seemingly coded in an object oriented style taking advantage of the new class system of PHP5, but in reality all connection between objects was based on inheritance, meaning that in practice it was all one humongous class containing all the functions of a procedural program.

I wanted to turn this into a cleanly architectured application with small objects, each doing relatively little, but simply couldn’t find a way to evolve the huge inheritance blob of classes into something like that through small and gentle, gradual refactorings; so I decided more drastic steps was needed, and began a complete rewrite.

One beautiful characteristic of rewrites, is that they present us programmers with pretty much the only case of having a full specification that actually specifies what the customer wants in the end. My spec was an API specification of 26 methods for a REST based web-service, and I had a set of acceptance tests in place to make sure that those 26 method calls worked as expected.

With this foundation in place I carefully started building up a new architecture taking advantage of PHP5’s reworked OOP features, and with no over-abuse of inheritance. During the first week I implemented no more than 3 of the original 26 methods, and yet I confidently told my bass that I expected to finish the rewriting before the end of the second week. I avoided the question of how many of the methods I had gotten done so far, when asked, because I knew the number would be wildly misleading.

This was not due to wild optimism or pure insanity, but because of how OOP works and feels when it’s done right. What I did, while implementing those 3 methods, was extracting the basic generic building blocks of the web-service’s operations. Abraham Lincoln is supposed to have said once “If I had eight hours to chop down a tree, I’d spend six sharpening my axe.” While taking my time, carefully implementing those 3 small method calls, I was sharpening my virtual and object oriented axe.

When the second week started, I had basically all my small building block in place, and 3 days into the week I was done implementing all the remaining 23 methods – it was simply a question of putting existing blocks together in the right way. This is, to me, what OOP is all about: building small reusable blocks with enough flexibility that adding new functionality feels somewhat like a playing with LEGOs.

At the end of the two weeks the rewritten service passed all the acceptance tests, with a line-count around a fourth of the original code-base and with a far more flexible architecture, that has already made me implement several feature enhancements that would have been seriously big pains to add before the rewrite.

Since my comments started getting severely spammed I finally got around to implementing a simple anti spam meassure.

The comment form now comes with an invisible field not meant to be filled out. We’ll see if the bots falls for that one and happilly enters their pyload into the spam field.

It seems my webhost installed the Ferret gem recently. This is quite nice, but for now it seems to have created a conflict with my own local install of the Ferret gem and the ActsAsFerret plugin – so search throws an application error at the moment.

Wont have time to fix it before after the weekend. Hopefully search will start working again monday.

Update

Ok – couldn’t help taking a look at it anyway, and search should be working properly again now.

Had a few free hours and spent them on my Sudoku generator, and by now I have a nice little online Sudoku game

It now spits out nice symmetric Sudokus with a fairly mild difficulty level, and it times the solving of each puzzle.

I still have some more features in store (like better response from the check function), and I still need to slap up a little website around it, but its already great fun. Enjoy…

First a message to that one guy who added this blog to his RSS feeds: don’t worry it isn’t dead already, it’s owner was just away on some stressful vacation, had visitors, started on a new job and was celebrating his 30th birthday!

Then a message to whomever might read it: the next statement might seem to blatantly contradict the title of this post.

Ruby is really, really slow. While the benchmarks from the Computer Language Shootout might be misleading or biased or whatever, Ruby is so slow that from time to time you really don’t need a benchmark to notice it.

Solving Sudoku

With me on my vacation I had Donald E. Knuth’s paper about the Dancing Links algorithm. I wanted to use it to create my own little Sudoku generator in Ruby. Perhaps a geeky vacation activity, but if its fun solving a Sudoku, why shouldn’t it be fun solving Sudoku?

Knuth’s algorithm is really extremely beautiful. Implementing it gave me a bit of the same feeling as studying a Bach Fugue at the piano. What an amazing ability of abstract imagination Knuth must be in possession of!

Implementing the algorithm in Ruby didn’t make it any less beautiful, but it did make it seriously slow. The algorithm needs an initial matrix of circularly linked lists to be setup, before it can work its magic. To solve Sudoku this involves setting up a matrix of 3.241 linked Nodes. While 3.341 is generally a really small number for a computer, it’s a pretty big number for Ruby, and on my good, old, trusty iBook G4, setting up this matrix in Ruby takes time. Perhaps not a huge amount of time in the grand perspective of things, but enough time that a web-based Sudoku generator running on Ruby on Rails would feel slow.

Of course I could just try to hide the slow nature of the generator by some Ajax trickery, or I could generate a huge batch of Sudokus overnight and feed them to a database, but the first solution is a shoddy excuse for not just creating something that’s fast enough from the outset, and the other option was just not what I wanted for my own little online Sudoku generator.

More to Ruby than Ruby

So why am I still claiming in the title of this post, that Ruby is more than fast enough?

Because all this led me to discover how insanely easy it is to extend Ruby with C. And while C might lack objects, classes and all the niceties of a dynamic OOP language like Ruby, it sure has speed.

Programming Ruby: The Pragmatic Programmers Guide provides an excellent guide to extending Ruby in C, and with the help of this guide and the README.EXT file in the Ruby source directory, I was able to quickly create a Sudoku extension for Ruby.

I started out by creating a quick implementation of the Dancing Links algorithm in C. Since I had already implemented the algorithm once in Ruby, it was quite easy getting a command-line Sudoku solver up and running in C – this one just as blazingly fast as the Ruby version was slow. Now it was just a matter of including ruby.h, setting up a few interface functions, letting ruby generate a makefile for me and running “make” – and bam! – I had my Sudoku extension.

A Tiny Tutorial

Just to give you an idea how easy this whole process is, here’s a small tutorial on creating an incredibly useful “Hello World” extension to ruby:

First we make our “Hello world” C program in an empty folder:

hello_world.h:

#include <stdio.h>

void say_hello();

hello_world.c:

#include "hello_world.h" 

void say_hello() {
printf("Hello, World!\n");
}

int main() {
say_hello();
}

Compile and run to check that your new fantastic hello world program works.

Time to make it a Ruby extension. Remove the int main() function from hello_world.c and lets start interfacing. Here are the c files:

hw_extension.h:

#include "ruby.h" 
#include "hello_world.h"

hw_extension.c:

#include "hw_extension.h" 

VALUE cHello;

static VALUE h_init(VALUE self) {
return self;
}

static VALUE h_say_hello(VALUE self) {
say_hello();
return Qnil;
}

void Init_HelloWorld() {
cHello = rb_define_class("HelloWorld",rb_cObject);
rb_define_method(cHello, "initialize", h_init, 0);
rb_define_method(cHello, "say_hello", h_say_hello, 0);
}

The Init_HelloWorld() function is needed to define our new Ruby classes and methods. Our class is defined as “HelloWorld”, HelloWorld.initialize is set to the h_init function and HelloWorld.say_hello is set to our h_say_hello method.

Now we need to tell Ruby to create a makefile for us. For that purpose we make a config file:

extconf.rb:

require "mkmf" 

dir_config("HelloWorld")

create_makefile("HelloWorld")

Now run “ruby extconf.rb” and Ruby will search the directory for .c files and add them to the make files instructions. When that’s done all there’s left to do is type “make” at the command line and we’re good to go.

Fire up irb and lets test our new extension:

> require "HelloWorld" 
=> true
> h = HelloWorld.new
=> #<HelloWorld:0x1bafbc>
> h.say_hello
Hello, World!
=> nil

Y-ay! We now have a lighting fast hello world extension and all your worries about your hello world programs running way to slowly in Ruby should be a thing of the past! At least the excellent extendibility of Ruby made my worries about the speed of my Sudoku generator go away.

I put up the current Rails driven version of my Sudoku generator at sudoku.mathias-biilmann.net It currently generates very hardcore Sudokus with few hints and no testing to see if they are solvable without backtracking. But it works, it’s fast and I hope to get time to improve upon it during the months to come.

[Update – The Sudoko game is now far more enjoyable. It generates fairly easy aesthetically pleasing Sudokus, and let you challenge a friend to beat your time at any Sudoku you manage to solve.]