Archive for August, 2008

Project Euler Problem 6

Thursday, August 14th, 2008

Onwards to…

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Bit of a disappointment, problem 6; it’s too easy. It’s rated as the third-easiest, i.e. easier than problems 3, 4, and 5 which I’ve already covered. In fact, for my money it’s easier than problem 2 as well. Ah well, the difficulty ramps up soon enough, trust me.  Here’s the very simple python solution:

sum_sq = sum([ x*x for x in xrange(1, 101)])
sq_sum = sum(xrange(1, 101)) ** 2

print sq_sum - sum_sq

As you can see, it’s pretty intuitive. You sum the squares, square the sum, and calculate the difference. The answer is basically in the description, you just have to scale up a little.

There’s not much else to say about this one. Even if I abandon the functional approach and write a straightforward imperative solution it’s still very straightforward. In (deliberately non-idiomatic, so don’t whine at me) ruby:

sum_of_squares = 0
sum = 0

1.upto 100 do |x|
    sum_of_squares += x * x
    sum += x
end

p (sum * sum) - sum_of_squares

Magic Numbers and Other Numerical Nightmares

Wednesday, August 13th, 2008

There are many coding practices that are near-universally regarded as ‘bad’, yet somehow keep cropping up over and over again. Conditional-branch abuse (including, yes, gotos). Deep nesting. Cryptic variable names. Global variables. Tight coupling. Entangled business/presentation logic. I could go on.

Why do we keep doing it? Convenience? Laziness? Tiredness? Is unreadable spaghetti code some sort of steady-state/equilibrium for code? Is it a natural consequence of the vague and squidgy limitations of our evolved monkey-brains? Or is well-designed code abhorred like a vacuum and naturally atrophies into the sort of shambles you dread seeing on your first day at a new job, unless well-intentioned and dedicated people actively work to clean and polish it, like the Forth Bridge?

I don’t have the time or wit to give this subject the treatment it deserves, but I do want to rant a bit about another symptom of this disease, which has given me a couple of sleepless nights recently. I refer, as the title might suggest, to magic numbers.

Magic numbers are constants, unnamed in the most pathological cases, that represent an assumption or a limit in a piece of code. They often cause problems because soon they are forgotten about or their meaning is lost - and then something happens to invalidate the assumption, the code breaks, and all hell breaks loose.

Magic numbers, to stretch the definition a bit, can also be implicit. If you are using a 32-bit integer, your magic number is 2,147,483,647 - that’s the biggest number you can store in that type. Often, movement up to and beyond these ranges can trigger long-dormant bugs that are no fun at all to diagnose.

Three times in recent history I’ve been bitten by bugs of this class, triggered by auto-incrementing sequences in database. These are they:

  1. A table in a database had a 32-bit integer primary key. At the time this seemed like a perfectly reasonable default, but insanely fast growth in usage of the system meant that the ~2.1billion upper limit of that data type was quickly reached. The DB column was switched to a 64-bit integer, but some of the client applications reading that table were not identified as at-risk. When the sequence generator left the 32-bit range, those applications overflowed. This happened at 4:30pm on a Friday afternoon. Saturdays were peak-times for system usage. You can imagine the frantic hacking that ensued.
  2. A sequence generator for a particular entity was started at 20,000,000, so as not to clash with the ID sequence of a related entity (that had started at 0 a good few years earlier). The similarity between the entities and the need to not have the IDs overlap had valid business justification, but the magic number was selected arbitrarily and promptly forgotten. Inevitably, the latter sequence surpassed that number, causing bizarre and difficult-to-trace entity relationship corruption that manifested as strangely-disappearing data on the front-end.
  3. A stored procedure parameter was incorrectly declared as an OracleType.Float, when it should have been an OracleType.Int32. This resulted in the value being cast from an integer to a floating-point and back again. For the first 16,777,216 integers, this happens to work OK. For the value 16,777,217, however, the loss in precision means that the number changes during casting. This simple bit of (heavily contrived) code shows the problem:
    static void Main(string[] args)
    {
        for (int i = 0; i < 17000000; ++i)
        {
            if (i != (int)(float)i)
            {
                Console.WriteLine(“{0} != {1}”,
                    i, (int)(float)i);
                break;
            }
        }
    }

    There are many numbers above 16,777,217 that have this characteristic; 16,777,217 just happens to be the first, for reasons you can probably divine if you think the IEEE floating-point spec is a riveting read. A couple of weeks after the launch of a fairly major internal application, this time-bomb exploded due to a sequence reaching the magic number. The bug was nothing to do with the new application, but of course fingers were pointed at it since a long-running and stable system had mysteriously choked very shortly after deployment of the new application.

Now, unquestionably, all these problems are avoidable, and a strong argument could be made that none of them should ever have been allowed to happen. Yet, for many reasons, they do. For example, first-mover advantage can mean the opportunity cost of taking the time to do things right first time is greater than the cost of fixing problems later.

Also, people make assumptions. The issue underlying the Millennium Bug hysteria was caused by well-meaning developers who knew that two-digit dates wouldn’t work after 1999 (effectively another magic number), but assumed the software would have been replaced or upgraded by then. No doubt that seemed a totally reasonable assumption in the 1970s, and it had genuine technical benefits (storage space was so tight that every byte saved was a battle won).

Anyway, I don’t have a magic bullet solution for this, I’m just venting spleen. Unit tests can help, but won’t magically eliminate this class of bug (no matter what some of the more extreme TDD fanatics might tell you), so I suppose the lesson to take from this is the importance of being able to recognise and diagnose potential magic number issues. Pay close attention to data types, type conversions, and current values of sequences in your database. Keeping a sacrifical goat on hand might pay dividends too, in case any blood-thirsty deities with a head for binary arithmetic are watching.

Ubuntu, Xmonad, and an Ode to Apt

Sunday, August 10th, 2008

This weekend I finally got around to updating my main Linux box from Ubuntu 7.10 to 8.04 (yes, I know, 4 months late - but moving fast!). The highly excellent xmonad has made it into the main Ubuntu repositories, so I discarded my own build and grabbed the packaged version - which promptly didn’t work as expected on my dual-head setup. Gah.

A bit of googling suggested that the problem lay with the upstream debian package, which contained a build of libghc6-x11-dev that was compiled without xinerama support. This left me with a choice of either waiting for the package to get sorted out, or to do the build myself again. I decided to do my own build rather than live without xmonad, but rather than mucking about with tarballs I could at least now get the source from the package repository.

The appropriate steps, for anyone interested or having the same problem, are:

  1. Make sure libxinerama-dev is installed
  2. Recompile libghc6-x11-dev and install it
  3. Recompile libghc6-xmonad-dev and libghc-xmonad-contrib-dev against the new X11 lib

The apt-get incantations are:

sudo apt-get install libxinerama-dev
cd /tmp
sudo apt-get source –compile libghc6-x11-dev
sudo dpkg -i libghc6-x11-dev_1.4.1-1_i386.deb
sudo apt-get build-dep libghc6-xmonad-dev
sudo apt-get source –compile libghc6-xmonad-dev
sudo dpkg -i libghc6-xmonad-dev
sudo apt-get build-dep libghc6-xmonad-contrib-dev
sudo apt-get source –compile libghc6-xmonad-contrib-dev
sudo dpkg -i libghc6-xmonad-contrib-dev_0.6-4_i386.deb

A quick alt-q restart, and all is well.

I only mention all this because it’s so easy in this day and age to take something like apt for granted, and every so often it’s worth taking a moment to appreciate just how spectacularly good it really is. Where I work, deployments are an endless source of headaches and grief, yet the complexity of those deployments absolutely pales against the task of updating literally millions of systems, all slightly different to each other, thousands of times a day. It’s just a joy to be able to say to apt “hey, go get me everything I need to build package x, then build package x, then install it for me. And get it right first time!”.

In most cases, it does just that. It’s an astonishing piece of software.

Dynamic Async Batching with PFX

Friday, August 8th, 2008

The PFX Team blog has been posting some excellent articles recently on the subject of task batching using the June 2008 CTP release of the Task Parallel Library. It’s really cool to see some of these techniques abstracted properly in .Net, and I hope it eventually becomes part of the core libraries.

I’ve been playing around a bit recently with the June CTP in the context of batching up web service calls, as that’s something I do quite a lot. One particular problem that comes up occasionally is a two-stage series of requests to download a complete set of paged data. I might do this if I wanted to download an entire discussion thread, for instance, or a large account statement from my online bank.

Typically in this situation the web service will limit the number of records I can retrieve in one request, and allow me to specify start and count parameters to the request. The response will also include a total record count, so I know how much data there is.

The normal use case for this is to request the first page of data, and use the total record count to display a list of page links that my user can click on to navigate the data or jump to any page. In my case, however, I want ALL the data as quickly as possible.

So, imagine a situation where I am using a service that lets me download a maximum of 200 records per request. My first step is to request the maximum 200 records starting from index 0, i.e. the first page of data. In the response will be a total record count - if that number is equal to the number of records I got back (i.e. <= 200) I’ve got everything in one hit and can stop. But what if the total record count is, say, 1000? I need to make four more requests (since I’ve already got records 1-200, I have 800 more to get in batches of 200 each).

Naturally I want to do this asynchronously, using as few resources as I can. This means all webservice calls should be using the APM pattern (thus using IO completion ports, and not consuming worker threads from the thread pool or creating my own threads) and, preferably, not blocking anywhere except when I actually need some data before continuing.

The two-stage process can be successfully captured asynchronously by combining a future and a continuation. I encapsulate the initial request in a Future object (which is a subclass of Task), and handle the check-record-count-and-get-more-records-if-required logic in the continuation. The code for this basically looks as follows:

public Future<List<Item>> GetAllItemsAsync()
{
    var f = Create<GetItemsResponse>(
            ac => Service.BeginGetItems(0, ac, null),
            Service.EndGetItems);

    var start = 200;

    var resultFuture = f.ContinueWith(
        r =>
            {
                // Batch retrieval here…
            });

    return resultFuture;
}

In order to support the APM pattern neatly, I’m using the following method from the PFX blog:

private static Future<T> Create<T>(
        Action<AsyncCallback> beginFunc,
        Func<IAsyncResult, T> endFunc)
{
    var f = Future<T>.Create();
    beginFunc(iar =>
        {
            try
            {
                f.Value = endFunc(iar);
            }
            catch (Exception e)
            {
                f.Exception = e;
            }
        });
    return f;
}

This could be coded as an extension method, though I haven’t bothered yet as I’m hopeful this immensely useful snippet will be integrated into the library itself.

Now I need to make a number of calls to get the rest of the data, so I loop until I’ve made the required number of async service calls:

var resultFuture = f.ContinueWith(r =>
    {
        var items = new ConcurrentQueue<Item>();
        var handles = new List<WaitHandle>();

        while (start < r.Value.TotalRecordCount)
        {
            var asyncResult = Service.BeginGetItems(200,
                ar => Service.EndGetItems(ar).Items
                    .ForEach(items.Enqueue), null);

            handles.Add(asyncResult.AsyncWaitHandle);
            start += 200;
        }

        handles.ForEach(h => h.WaitOne());
        return items.ToList();
    });

I’m about 85% happy with this as an approach. I’m not completely happy, however, because of the WaitOne calls, which mean that I’m blocking on a threadpool thread until all the calls complete. Given that this is all wrapped up in a future, I may not actually need to access the data until well after the calls have completed, in which case I am wastefully consuming a threadpool thread for some period of time. So the $64,000 question is, how do I get rid of it? I’m sure there’s a way to do it, but my brain has gone on a protest march about all the time I’m forcing it to spend thinking about this stuff.