Incoherent and disjointed opinionated drivel from somewhere near London

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.

So, yesterday saw the end of a weird week of Whedon wonderfulness when the third and final episode of Dr Horrible’s Sing-Along Blog was released. All three episodes are now free to view until the end of the day, so run, don’t walk, over there now. After all, how often do you get the chance to see a musical comedy about a supervillain who video blogs? With Doogie Howser and Malcolm Reynolds!

On to the next Project Euler problem (after a bit of a hiatus)…

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

In common with many of the other Euler problems, there’s a brute-force way to solve this, and a clean algorithmic way. And in common with my other Euler posts so far, I’ll start with the brute-force way

This problem can be tackled head-on with the following approach: Start from n=1 and increment in a loop. Test each value of n by attempting to divide it by all numbers m from 1 to 20. The first number to pass the test (i.e. n mod m is 0 for all values of m) is the answer.

private static long BruteForceSolver()
{
    long result;
    for (result = 1; !Check(result); ++result)
        ;
    return result;
}

private static bool Check(long result)
{
    for (int i = 1; i <= 20; ++i)
    {
        if (result % i != 0)
            return false;
    }

    return true;
}

This works, but it takes >12 seconds to execute on my PC, so it’s not what you’d call efficient (though it is well within the Euler execution time guidelines).

Some speed gains can be achieved by exploiting the information provided in the question itself. We are told that 2520 is the lowest number evenly divisible by all numbers from 1 to 10. Since the problem space (1 to 20) includes all these numbers, the answer must also be evenly divisible by 2520. This allows much bigger increments each loop – rather than incrementing by 1, why not increment by 2520? And since the answer must be greater than or equal to 2520, why not start the loop there instead of 1? Finally, since we already know that 1 to 10 divide evenly into 2520, each inner loop only needs to check numbers 11 to 20.

That should speed things up a bit:

private long BruteForceSolver()
{
    long result;
    for (result = 2520; !Check(result); result += 2520)
        ;
    return result;
}

private bool Check(long result)
{
    for (int i = 11; i <= 20; ++i)
    {
        if (result % i != 0)
            return false;
    }

    return true;
}

And indeed, on my machine this is now down to 150ms or so. It’s still not a very nice way to tackle the problem, though.

Thinking about it from a different angle yields an altogether smarter approach. Imagine we are looking for the lowest number evenly divisible by the numbers 1 to 2.

[1, 2]

Well that’s easy; since there are only two numbers we just find the lowest common multiple (LCM), which in this case is 2 (since 2 % 2 == 0, and 2 % 1 == 0). If we call this sequence s₁, we can say that LCM(s₁) = 2.

OK, now imagine we are solving the same problem for s₂, which contains the numbers 1 to 3.

[1, 2, 3]

You’ll notice that s₂ contains s₁ in its entirety. LCM(s₂) must therefore be a multiple of LCM(s₁), so we can rewrite s₂ as [LCM(s₁), 3], or [2, 3] (since we know LCM(s₁) = 2). Now we are down to two numbers again, so we can calculate the LCM of 2 and 3, which is 6, so LCM(s₂) = 6.

OK, now we solve the problem for the first 4 numbers (s₃).

[1, 2, 3, 4]

This sequence contains s₂, therefore LCM(s₃) is a multiple of LCM(s₂). We can rewrite s₃ as [LCM(s₂), 4], or [6, 4]. Thus, LCM(s₃) = 12.

This can be repeated as many times as necessary. Generally, we have s_n = [LCM(s_n-1), n+1] where n > 0.

This looks recursive, but a better way to think of it is as an excellent example of a fold. A fold is one of the fundamental tools of functional programming. In fact, it is perhaps the most fundamental, since map, filter etc can be implemented as right folds^[1].

I won’t inflict my pitiful Photoshop skills on anyone by trying to graphically represent a fold – try looking at this Wikipedia article if you want to try and visualise it.

Broadly, the behaviour of a fold is to apply a combining function to elements in a list (or other data structure) and accumulate the results. That’s exactly what we want here – our combining function is LCM, and our accumulating value is the LCM of the whole list. Effectively, for list s₃ above, we have

LCM(s₃) = LCM(LCM(LCM(1,2),3),4) = 12

Note how the result of the innermost LCM (applied to values 1 and 2) becomes a parameter to the next LCM, which in turn becomes a parameter to the outermost LCM which returns the result we want.

By using a fold, we can generalise. In Haskell, the whole problem is a one-liner:

foldl lcm 1 [1..20]

The 1 passed in as a parameter represents the terminating value to use when the end of the list is reached. It is common for this value to be the first element of the list, so Haskell provides a convenience function that removes the need to specify it as a parameter:

foldl1 lcm [1..20]

Not all languages and platforms provide an LCM function right out of the box, so to take this neat Haskell solution and port it to .Net, the LCM function needs to be implemented. This is easily done in terms of the greatest common divisor (GCD) like so:

.Net doesn’t provide a GCD function either, so I’ll implement it using Euclid’s Algorithm as an extension method on long ints:

public static long GCD(this long a, long b)
{
    while (b != 0)
    {
        long tmp = b;
        b = a % b;
        a = tmp;
    }

    return a;
}

With GCD defined, LCM can be implemented as above:

public static long LCM(this long a, long b)
{
    return (a * b) / a.GCD(b);
}

With this in place, it’s a simple matter to use .Net’s equivalent of fold – a method on IEnumerable called Aggregate – to get the answer^[2]:

return LongEnumerable.Range(1, 20)
    .Aggregate(1L, (curr, next) => curr.LCM(next));

And indeed, the same basic pattern can be used to solve the problem in a number of languages. In F#, given implementations of LCM and GCD as above, we have:

List.fold_left lcm 1 [1..20]

And in ruby:

require 'rational'
(1..20).inject { |c, n| c.lcm n }

Given that the right algorithm makes this problem a fairly trivial expression in all these languages, it’s pretty hard to identify which is the nicest. I think overall I’ll give the nod to Haskell, however, for not making me implement LCM and because I find ruby’s ‘inject’ a less intuitive function name than foldr (but that’s probably because I learned the technique in Haskell in the first place and am set in my ways…)

---

^[1]For example, in F#:

let filter p lst =
  List.fold_right (fun x xs -> if p x then x::xs else xs) lst []

let map f lst =
  List.fold_right (fun x xs -> f x :: xs) lst []

^[2]Note that in this code LongEnumerable is just a very simple partial reimplementation of Enumerable, using longs instead of ints