My employer ibuildings is currently running a competition. The challenge provoked some disccussion amongst my fellow developers, so a separate internal competition was announced with the same challenge but slightly smaller prizes.

The challenge is an interesting one and has quite a lot in common with the sudoku problem I published. I’ve been working on a solution for a little while now. Initially my first working solution took 5 seconds to run. But then while driving along a motorway I had sudden inspiration about how to shorten the algorithm. A little more work I was fairly happy with my solution which was taking just under a second to run and weighed in at 150 or so lines of code. Never the less I decided to profile what I’d written. To run a script with xdebug profiler I did this

 XDEBUG_CONFIG="profiler_enable=1" php myScript.php

This created a chachegrind dump in my /tmp directory. The initial dump was 20 Mb not a good sign! To look at the cachegrind output I used webgrind. The features implemented are a small subset of those of kcache grind but I didn’t have a linux desktop to hand.

By moving some code around to create less function calls I halved the size of the dump file and also the execution time.

Next I noticed that a array_key_exists was being called 12000 times. Hmmm isset would do and and is marginally faster the two functions differ in their treatment of nulls. Normally I’m not in favour or micro optimizations like this but when a function is being called that many times the choice of function can make a huge difference. A few more tweaks and the cache grind dump file size continued to fall. I’m now pretty pleased to say execution time is about 0.2 seconds and the code has actually shrunk to 146 lines.

Profiling certainly proved it’s worth no matter how well I thought I knew how the code was executing there were some suprises.