02.04.07

Moving Boggle to C++

Posted in boggle, programming at 11:55 pm by danvk

Last time, we talked about Tries, the perfect data structure for Boggle. To take full advantage of Tries, we need to move to a lower-level language than Ruby, which leads to today’s task: convert our Ruby code to C++.

Premature optimization is the root of all evil, so our main goal here is to get a working C++ Boggle solver. We’ll use STL strings and hash tables to produce code that’s as close to the last Ruby program as possible. That being said, I’m going to take this opportunity to extract the Boggle-solving code into its own class. Here’s the interface I came up with:

#include <ext/hash_set>
#include <string>
using namespace __gnu_cxx; // for hash_set
using namespace std;       // for string

class Boggler {
 public:
  Boggler();
  int LoadDictionary(const char* filename);
  int Score(const char* letters);
  	
 private:
  bool ParseBoard(const char* lets);
  void Solve(int x, int y, const string& sofar);
  
  hash_set<string> words_;
  hash_set<string> stems_;
  hash_set<string> found_;
  string bd_[4][4];
  bool prev_[4][4];
  int score_;
};

The routines mostly do what their names imply. LoadDictionary populates the words_ and stems_ hashes based on a word list. ParseBoard takes input like “a b c d e f g h i j k l m n o p” and populates the bd_ array. Score parses and scores a board, while Solve is its recursive workhorse.

Before getting to the implementation of this interface, let’s look at a few programs that use it. Here’s one that tests some boards with known scores (try the online boggle solver to test them):

#include "boggler.h"

#include <string>
#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	Boggler b;
	int words = b.LoadDictionary("words");
	cout << "Loaded " << words << " words." << endl;
	cout << "b.Score(abcd...) => " << b.Score("a b c d e f g h i j k l m n o p") << " == 18?" << endl;
	cout << "b.Score(qu...) => " << b.Score("t c e e v w h b t s t u qu a a e") << " == 94?" << endl;
	cout << "b.Score(catd...) => " << b.Score("c a t d l i n e m a r o p e t s") << " == 2338?" << endl;
}

This program is just a quick sanity check. If the Boggler correctly scores those three boards, then it’s doing a whole lot right. Here’s another program that reads boards from standard input and scores each of them. We can use it to test correctness and measure performance:

#include <iostream>
using namespace std;

#include "boggler.h"

int main(int argc, char** argv) {
	Boggler b;
	b.LoadDictionary("words");

	char linebuf[256];
	while (cin.getline(linebuf, 256)) {
		cout << b.Score(linebuf) << endl;
	}
}

Now for the implementation, boggle.cc. The interface requires four functions: LoadDictionary, ParseBoard, Score and Solve. The last is the most interesting, and it can be translated directly from Ruby:

def solve(x, y, sofar)
  Prev[x][y]=true

  wd = sofar + Bd[x][y]
  Found[wd]=true if Words[wd]
  
  Dirs.each do |dx,dy|
    next unless (0..3)===(x+dx)
    next unless (0..3)===(y+dy)
    next if Prev[x+dx][y+dy]
    solve(x+dx,y+dy,wd) if Stems[wd]
  end
  
  Prev[x][y] = false
end

void Boggler::Solve(int x, int y, const string& sofar) {
	prev_[x][y] = true;
	
	string wd = sofar + bd_[x][y];
	if (words_.find(wd) != words_.end()) {
		if (found_.find(wd) == found_.end()) {
			found_.insert(wd);
			score_ += kWordScores[wd.size()];
		}
	}
	
	for (int dx=-1; dx<=1; ++dx) {
		int cx = x + dx;
		if (cx<0 || cx>3) continue;
		for (int dy=-1; dy<=1; ++dy) {
			int cy = y + dy;
			if (cy<0 || cy>3) continue;
			if (prev_[cx][cy]) continue;
			if (stems_.find(wd) != stems_.end())
				Solve(cx, cy, wd);
		}
	}
	
	prev_[x][y] = false;
}

The STL syntax for looking up an element in a hash_set is hideous: words_.find(wd) != words_.end()? I can’t understand why there’s no equivalent of Ruby’s has_key? function. What else do you do with hashes? Here’s Score:

int Boggler::Score(const char* letters) {
	if (!ParseBoard(letters)) return -1;

	score_ = 0;
	for (int i=0; i<16; ++i)
		Solve(i/4, i%4, "");
	found_.clear();
	return score_;
}

Simple enough. The other two functions require some STL-fu, but aren’t especially interesting. You can check out the complete source and Makefile from here.

First the sanity check:

$ make
g++  -g -Wall -O3 -march=i686  -c -o test.o test.cc
g++  -g -Wall -O3 -march=i686  -c -o boggler.o boggler.cc
g++   test.o boggler.o   -o test
g++  -g -Wall -O3 -march=i686  -c -o scorer.o scorer.cc
g++   scorer.o boggler.o   -o scorer
$ ./test
Loaded 172233 words.
b.Score(abcd...) => 18 == 18?
b.Score(qu...) => 94 == 94?
b.Score(catd...) => 2338 == 2338?

So we’ve got correctness. Now the big question: how’s the performance? We’ll get a baseline by scoring zero boards with scorer and then feed it 5,000 boards from a list of 50,000 that I created:

$ time echo '' | ./scorer

-1

real    0m1.431s
user    0m1.294s
sys     0m0.052s
$ time head -5000 test-boards | ./scorer > /dev/null

real    0m17.525s
user    0m17.412s
sys     0m0.107s
$ echo "5000/(17.412-1.294)" | bc -q
310.212185134632088

That’s an 18x improvement over last time, exclusively from moving to C++. There is a Ruby penalty, and 18x is a perfectly believable value for it. I suspect that, if Ruby had a VM, (as it will soon and kind of does already) then this factor could be entirely eliminated. What can’t be eliminated is where we’ll go next. There are some times when it really is worth getting your hands dirty hacking around for performance tweaks. C++ makes those hacks possible, whereas Ruby does not. A simple example: rather than doing all the string addition in Boggler::Solve, we could use a pre-allocated character buffer. I could easily see this gaining a 2-3x performance improvement. But you can’t easily break the string abstraction in Ruby.

Next time we’ll add Tries to the C++ program. You can get the full source for today’s Boggle from here.

Permalink