gareth_rees: (Default)
2015-12-14 06:42 pm

Plan to throw one away

When I had interviewed for the job, the interviewer had explained that I was needed to work on their JavaScript engine. The company was a web development tools startup, and they had spotted that it would be a good idea to have JavaScript code running on the server as well as on the client, so that you could share your business logic and validation code between the client-side and server-side parts of your application. There are now lots of products in this space but twenty years ago was probably too soon for this to be a success.

Anyway, the interviewer told me that the JavaScript engine was nearly done, but there were one or two features that were missing, and it was running a bit slowly, so I might have to do a bit of optimization. Sure, I said, that sounded like it would be fun … )

gareth_rees: (Default)
2015-12-14 06:40 pm

Exact cover II

The story so far: I wrote a solver for a generic exact cover problem in Python, and used it to find polyomino tilings. The reason for using Python was because Python’s simplicity, terseness, and flexibility makes it easy to write solvers for other combinatorial problems. So let’s have a look at a second problem … )

gareth_rees: (Default)
2015-12-14 06:34 pm

Exact cover

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

Instances of this problem often arise in the solution of combinatorial problems … )

gareth_rees: (Default)
2015-08-09 06:44 pm

A performance regression

So, another day at the customer site, another issue to fix:

Issue 234. Over the past three months, the performance of [PRODUCT] has regressed. In December, at commit 919074d, [TESTCASE] ran in 21 seconds, but now it takes 44 seconds.

The first step is to check that the problem is reproducible (it is), and the next is to run a git bisect to see if there was a bad commit … )

gareth_rees: (Default)
2015-08-07 09:20 pm

Emacs/Perforce integration: a retrospective

I’ve been maintaining the Perforce/Emacs integration for a couple of years now, so it’s time for a retrospective. … Perforce and Emacs are tools that I use all day every day, which means that small inconveniences in the integration stand out to me and I can see clearly cases where I have a frequently performed task that deserves some extra automation or assistance. I’m also in a position to check quickly that my change really fixes the problem. Here are examples of improvements I’ve made based on this approach… )

gareth_rees: (Default)
2015-08-07 07:11 pm

The ping that wouldn’t die

It was Friday afternoon at the customer site and I had completed my tasks for the week. I had implemented the new feature and its test cases, written a design justifying the implementation, and drafted a section of the user manual explaining how to use it, so now I was looking for something else to do. In any large program, there are always things that need fixing, so I poked about in the depths of the issue tracker to see if there were any interesting problems that could be appropriated from the other developers. The unluckily numbered and long unsolved issue 13 caught my eye… )

gareth_rees: (Default)
2015-05-01 11:23 pm


Joe sits in the office of his detective agency in Vientiane, drinking and smoking, watching the rain come down, and reading trashy fiction:

The book was a worn paperback with a garish, colourful cover. It showed a multi-story building in the final stages of collapse, a dusty African street, and people running away from the blast. The book was called Assignment: Africa and, in an only slightly smaller subtitle, announced it as the third title in the series Osama Bin-Laden: Vigilante. The unlikely named of the author was Mike Longshott.

A woman comes into in Joe’s office with a job for him:

At last, she said, ‘I want you find him,’ and her fingers caressed the book; he couldn’t put a name to the look she had in her eyes then; he thought she looked lost, and sad, and a little vulnerable.

‘Find who?’

‘Mike Longshott,’ she said.

( What follows is a pastiche of the hard-boiled detective genre... )

gareth_rees: (Default)
2015-05-01 11:21 pm

The Quantum Thief

Jean le Flambeur, gentleman thief, is sprung from prison by the beautiful Mieli, who persuades him to undertake one last job. Author Hannu Rajaniemi works hard to obscure the familiar outline of this hoariest of heist plots, by layering on the worldbling with a trowel:

The hidden Sobornost tech beneath the Oortian sapphire coral wakes up. The spidership reconfigures itself. The scattered modules pull themselves together along their tethers and fuse together into a tight, hard cone. The q-dot winglets transform from a perfectly reflective material into a diamond-hard firewall. Just in time, before the Archon’s nanomissiles hit.

I do like the experience of being confronted by a complex fictional world and having to make sense of it. ( But I also like to feel that there is in fact some sense to be made, and in this novel I frequently failed to make it. )

gareth_rees: (Default)
2015-02-11 12:28 pm

Completion colours

In ‘Completion annotations’, I illustrated the interactive completion feature in Emacs with a screenshot showing what happens if you type M-x set-cursor-color RET Dark TAB: you get a *Completions* buffer containing the colour names starting with ‘Dark’. Nick Barnes posted a comment pointing out a potential usability improvement:

It would be nice to have a bit more control still, so that (for instance) when completing on colour names one could see the colours.

To do this, just evaluate the following expression:

(dolist (c (defined-colors)) 
 (put-text-property 0 (length c) 'face `(:foreground ,c) c))

and then run any command that prompts you to pick a colour, for example read-color. At this point, if you are used to the way strings work in most programming languages, you ought to be asking yourself, how does this work? )

gareth_rees: (Default)
2015-02-09 05:27 pm

Completion annotations

One of the most useful features of Emacs is its interactive completion. Whenever you need to input the name of some item, Emacs allows you to type some parts of the name and then type TAB to see a list of items that match what you have typed so far. But completion is more sophisticated than just prefix-matching. You can use wildcards (for example *green TAB will show colour names containing the substring ‘green’) and when the completion items have multiple words (separated by hyphens or spaces), completion works on each word individually, so that you can type M-x t-d-o-e RET to run the command toggle-debug-on-error. Naturally you can customize the set of completion mechanisms using the completion-styles setting.

The Emacs/Perforce integration that I maintain, p4.el, implements completion for each kind of Perforce item that you might need to name: branches, numbered pending changelists, clients, filespecs, groups, help topics, jobs, labels, and users. However, this works poorly in the case of changelists and jobs, because all you get when you type TAB is a list of opaque identifiers that give you no help in choosing the item you want. )

gareth_rees: (Default)
2015-02-07 08:29 pm

Five Whys

Toyota’s ‘Five Whys’ process is well known to engineers: it’s one of the basic problem-solving tools in modern engineering management systems like Six Sigma and Total Quality Management. Here’s how Taiichi Ohno introduces the process in Toyota Production System: Beyond Large-Scale Production (1978):

When confronted with a problem, have you ever stopped and asked why five times? It is difficult to do even though it sounds easy. )

gareth_rees: (Default)
2015-01-21 07:42 pm

The Bug

I have been working on a project recently where there has been a lot of tricky debugging to do. The code I’m working on has to live in the same process as third-party code that is not under my control, and which calls into my code unpredictably, often from multiple threads or signal handlers. This is an application environment that’s particularly prone to rare crashes and deadlocks that somehow elude my own thorough test procedures but crop up nonetheless on the machines of potential customers during product evaluations. I used to find these kind of bugs intimidating and nerve-wracking, but (at least on this project and for the moment) I seem to be a match for them.

The process of debugging is (or ought to be) one of calmly, methodically and steadily gathering data that narrows the location of the problem until it can no longer hide and is forced to reveal itself. In my current project the first step is to acquire the log and (in the case of a crash) the backtrace from the customer and analyze it for the sequence of events leading up to the crash or deadlock. This identifies important features of the environment (which programs were running? are they multi-threaded? do they handle signals?) and usually pinpoints a suspect area of code which can be inspected for race conditions and deadlocks. Inspecting the code usually leads to a hypothesis or two about the cause; but even if it doesn’t I develop a test case that thoroughly exercises the problem area. With some experimentation and a lot of thought I’ve so far always found it possible to reproduce the problem under controlled conditions, whereupon it can be analyzed in the debugger.

Writing this is of course a form of hubris: no doubt I will return to work on Monday to find in my inbox a customer report describing a bug that I lack the skill to track down and fix. This hasn’t yet happened in my career, though there have been a few occasions where I have been in doubt as to the outcome, one of which I described in my post ‘The last lousy bug’. Programmers like to call these accounts “war stories”—joking, of course, but joking seriously. It is stressful to know that something is wrong in your code, but not to know what it is or how to find it, and to have it hanging over your head day after day as you fail to make progress towards solving it.

( This nightmare scenario is the driver behind Ellen Ullman’s 2003 novel The Bug. )

gareth_rees: (Default)
2014-05-08 10:37 pm

Software inspection and the Heartbleed bug

Since 2005, when a train crashes in the UK, a professional body of investigators—the Rail Accident Investigation Branch—is tasked with determining the cause of the incident and making recommendations to reduce the likelihood, or mitigate the severity, of similar events occurring in the future. There are similar branches tasked with investigating Air and Marine accidents.

There is nothing like this for computer security incidents. )

gareth_rees: (Default)
2014-04-19 10:36 pm

“Double Dutch” audax

Martin Malins has been organizing the “Double Dutch” 200 km audax for four years now. I rode the first edition back in 2011, when we had the most amazing luck with the weather, and I was looking forward to riding it again. The route is a tour of the Fens: starting at Huntingdon, you head north-east via Ramsey, March, and Nordelph, then north up the River Great Ouse to Kings Lynn for the fourth control and lunch. Then you cross the Ouse and head northwest to an info at Holbeach St Matthew close to The Wash, southwest to the sixth control at the Springfields shopping centre in Spalding, Lincolnshire, and back to Huntingdon for the finish.

I set my alarm for 06:00 )

gareth_rees: (Default)
2014-04-15 10:35 pm

Password purgatory

Since the Heartbleed bug rendered all our passwords insecure, we’ve all been going through the purgatory of upgrading servers and changing passwords. This isn’t the first time I’ve done a mass-reset of my passwords, but I thought I’d try something new. This time I’m seeing what it’s like to try to follow “best practices.” )

gareth_rees: (Default)
2014-04-05 10:34 pm

DIY 200 audax to Wendover

It’s not easy designing a “DIY” audax route. The way these rides work is that you nominate a series of controls, then you ride around and visit each one in turn, collecting “proof of presence” in the form of receipts or cashpoint slips. The tricky bit is that you only get credit for the shortest distance between each pair of controls. So you pick two nice cafés about 50 km apart, but then it turns out that they are only 40 km apart via the A1, so that’s all you get credit for. Add up all those little diversions, and soon your DIY 200 is actually 240 km.

On a calendar ride, the organizer can put in “information” controls anywhere on the route (or at least, anywhere that it’s possible to ask a question), and so bring the distance ridden closer to the nominal distance. When I ran a calendar event a couple of years ago, with judicious placement of controls I managed to get the distance ridden down to 200 km exactly, and so reasonably friendly for beginners. But that’s not possible on a DIY.

So it was only after many experiments with Google Maps that I settled on a route with five controls )

gareth_rees: (Default)
2014-03-23 10:32 pm

“End of Hibernation” audax 2014

Today was the "End of Hibernation", a 200 km audax organized by Terry Dickinson of Cambridge Cycling Club. Starting at the village hall in Hauxton, it visited controls at Adam’s Café near Stradishall, the Riverside Lakes Café at Onehouse near Stowmarket, and Bosworth’s Café at Finchingfield (plus two information controls).

Today was the third time I’ve ridden this event. )

gareth_rees: (Default)
2013-10-27 10:30 pm

Emitremmus 2013

The “Emitremmus” is a 100 km audax, run by Stevenage CTC each autumn for the last 19 years, on the Sunday that the clocks go back. The route starts at Fairlands Valley Park in Stevenage and heads east via Great Munden and Hare Street to Saffron Walden, returning via Great Chishill and Therfield. The start of the ride is almost exactly 50 km from my house )

gareth_rees: (Default)
2013-08-09 10:24 pm

Drawing square triangulations

The story so far:

  1. I introduced the tabular method by showing how to count the triangulations of a convex polygon;

  2. I used the tabular method to count the number of ways to triangulate an oriented n×n square using only lines joining the 4n integer points around the edge of the square and so solve Project Euler problem 270;

  3. I used the svgwrite Python package to draw the triangulations of a convex polygon using Scalable Vector Graphics; and

  4. I read Appendix J of the SVG specification and used the advice therein to shrink the size of the generated SVG.

( So now I’ve got all the pieces in place for the last step. )

gareth_rees: (Default)
2013-08-02 10:22 pm

Shrinking SVG

In “Scalable vector triangulations” I used the svgwrite package to draw the 429 triangulations of an oriented convex nonagon. But there was something unsatisfactory about the size of the resulting image: 1.2 MiB seems rather large for an image which has 3003 triangles and 6435 lines. A look at the source reveals three sources of wasted space )