A Quantum Immortal

Lately I need to support task cancellation in a Java process I’m working on. The straightforward options I know to implement this are:

1. Thread.interrupt() – the caller interrupts the worker thread (either directly or using Future.cancel()). Some say this is an erroneous approach, but I still haven’t figured out why. However, it is buggy on some recent versions on the JDK, and it is a bit fragile (what if the worker threads create worker threads that also need to be canceled?).
2. Passing some object (AtomicBoolean?) down to every object you would like to support cancellation. These objects will check the value of this boolean, and should stop if it is false. They can pass the boolean to other objects / tasks. While this works, this boolean cannot be injected, and so must be manually passed along the call stack.

If you want the advantages of the second method, but don’t want to break IOC, here’s how:

First, the usage:

The listener object adds a dependency on ICancelor

public class Foo {
  public Foo(ICancelor cancelor) {
    this.cancelor = cancelor;
    ...
}

It then checks the cancellation state every now and then:

if (cancelor.wasTaskCanceled("TakeOverTheWorld"))
   return;

The top-level thread that wishes to cancel a task simply calls

cancelor.cancelTask("TakeOverTheWorld");

And whenever a task is started, you should call

cancelor.resetTask("TakeOverTheWorld");

I’ll admit using strings for task names is a bit ugly, but this is not a terrible price to pay, assuming you have a few core tasks you intend to support. All that remains is the cancellation service itself:

/**
 * A cancellation service.
 */
public interface ICancelor {
    /**
     * Resets a task to "Not canceled" state
     */
    void resetTask(String name);
 
    /**
     * Returns true iff the a cancelTask was called, and no resetTask was called afterwards.
     */
    boolean wasTaskCanceled(String name);
 
    /**
     * Cancel a task
     */
    void cancelTask(String name);
}
 
public class Cancelor implements ICancelor {
  private final ConcurrentHashMap tasks = new ConcurrentHashMap();
 
    public void resetTask(String name) {
        tasks.put(name, true);
    }
 
    public boolean wasTaskCanceled(String name) {
        Boolean value = tasks.get(name);
        return value != null & value;
    }
 
    public void cancelTask(String name) {
        tasks.put(name, false);
    }
}

Because we rely on task names, there is an assumption here that all classes that play in the cancellation game belong to the same task semantically. If a class is a common class that doesn’t belong to a single task or flow, this approach does not work – in fact, I cannot think of an approach that will work in this case with dependency injection. The common class has to accept the cancellation signal somehow, it must either get an boolean explicit and not from the IOC container, or must check its interrupted state (or some other thread-local state) itself. Any smart ideas on how to solve this problem?

Come hear about .Net tools in a “no bullshit” evening (more details here).

I recently downloaded Visual Studio 2010 beta, and took the chance to play with PLINQ. PLINQ, for those of you in the dark ages of .Net Framework 2.0, is parallel LINQ – an extension to the famous query language that makes it easy to write parallel code (essential to programming in the 21th century, in the age of the many-core).

A code sample, as usual, is the best demonstration:

public static int CountPrimes(IEnumerable<int> input)
{
    return input.AsParallel().Where(IsPrime).Count();
}
 
private static bool IsPrime(int n)
{
    for (int i = 2; i*i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

This code sample, regardless of using an inefficient primality test, is fully parallel. PLINQ will utilize all your cores when running the above code, and I didn’t have to use any locks, queues, threadpools or any of the more complex tools of the trade. Just tell PLINQ “AsParallel()”, and it works.

I hit some gotcha when I tried to compare the parallel performance with the sequential one. Do you spot the problem in the following code?

public static void CountPrimesTest(IEnumerable<int> input)
{
    // parallel benchmark 
    var timer = new Stopwatch();
    timer.Start();
    CountPrimes(input.AsParallel());
    timer.Stop();
    Console.WriteLine("Counted primes in parallel took " + timer.Elapsed);
 
    // sequential benchmark
    timer = new Stopwatch();
    timer.Start();
    CountPrimes(input);
    timer.Stop();
    Console.WriteLine("Counted primes sequentially took " + timer.Elapsed);
}

This is all fine and dandy when the task at hand is CPU bound, but works pretty miserabbly when your task is IO bound, like downloading a bunch of web pages. Next, I simulated some IO-bound tasks (I used Sleep() to emulate IO – basically not using a lot of CPU for every task):

[ThreadStatic]
private static Random _random;
 
public static List<string> FindInterestingDomains(IEnumerable<string> urls)
{
    // select all the domains of the interesting URLs
    return urls.AsParallel().Where(SexFilter).
                Select(url => new Uri(url).Host).ToList();
}
 
public static bool SexFilter(string url)
{
    if (_random == null)
        _random = new Random();
 
    // simulate a download
    Thread.Sleep(1000);
    var html = "<html>" + _random.Next() + "</html>";
    return html.Contains("69");
}

Testing this with a list of 10 URLs took 5 seconds, meaning LINQ again spun only two cores, which is the number of cores on my machine. This really sucks for IO bound tasks, because most of the time the threads are idle, waiting on IO. Let’s see if we can speed this up:

// Use WithDegreeOfParallelism to specify the number of threads to run
return urls.AsParallel().WithDegreeOfParallelism(10).Where(SexFilter).
              Select(url => new Uri(url).Host).ToList();

This appeared not to work at first, because WithDegreeOfParallelism is just a recommendation or upper bound. You can ask PLINQ nicely to run with ten threads, but it will only allocate two if it so chooses. This is yet another example of C# being more magical than Java – compared to Java’s rich ExecutorService, PLINQ offers less fine grained control.

However, further testing revealed the damage is not so horrible. This is what happened when I put the above code in a while(true):

Tested 10 URLs in 00:00:05.0576333
Tested 10 URLs in 00:00:03.0018617
Tested 10 URLs in 00:00:03.0013939
Tested 10 URLs in 00:00:03.0013175
Tested 10 URLs in 00:00:04.0018983
Tested 10 URLs in 00:00:03.0024044
Tested 10 URLs in 00:00:01.0004407
Tested 10 URLs in 00:00:01.0007645
Tested 10 URLs in 00:00:01.0007280
Tested 10 URLs in 00:00:01.0003358
Tested 10 URLs in 00:00:01.0003347
Tested 10 URLs in 00:00:01.0002470

After some trial and error, PLINQ found that the optimal number of threads needed to run this task under its concurrency guidelines is ten. I imagine that if at some point in the future the optimal number of threads change, it will adapt.

P.S.
If you found this interesting, wait till you read about DryadLINQ – it’s LINQ taken to the extreme, run over a cluster of computers.

I’ve posted a lot lately,  but I think this post is well deserved. Tomer has recently finished an open source project he’s been working on for quite some time – ant-intellij-tasks. It is an ant task that takes an intellij-format project structures, builds and tests it. We have been using it for the past two months or so, and I must say it has brought great joy to the CI. Before that, we used to maintain two separate sets of files – IntelliJ project files, because that’s our IDE of choice, and Eclipse files, because … that’s how the build system worked. Many a times the build broke because one did not apply a change to the eclipse file, and “it all worked on his machine“. No more (we still have broken builds, but usually not because of compilation errors).

In related news, JetBrains recently open-sourced IntelliJ itself. Tomer’s work is still worth while, simply because there is no other tool we know of that does what it does – however the code there might use some refactoring now that he can simply use portions of the IntelliJ codebase. If you want to help, go on to the project homepage.

As you probably know, I joined the new wave and got my own Stack Exchange site. It’s really amazing how many different SE sites are emerging so rapidly. There’s a strong sense of (meta) community with most of the site owners heavily participating in discussions on meta stackexchange.

There is some overlap between different sites, but most sites I’ve seen are original and useful. The owner/s of one SE site have been nice enough to post links to other SE sites, including Draw3Cards, at the top of their homepage!

Today I convinced a friend at work to open his own website, and I think you should to – before all the good ones are taken. Come and join us, it’s really that easy.

For the last couple of days I’ve been obsessing over a new toy. Jeol & Jeff, the powers behind StackOverflow, have launched a public beta of StackExchange – a platform for hosting Q&A sites. Browsing the list of stack exchange sites, I saw several more and less successful sites, including:

• The (already-profiting) site on World of Warcraft (and site has barely been online for 2 weeks!)
• AskSci, in which I’ve been made moderator, but has been rather desolate since
• And MathOverflow, which seem to be already useful

I decided to try and open my own site, about Magic: The Gathering. The setup itself was rather easy. I:

• Bought a domain and set it up, with some help
• Seeded the site with some questions and answers
• Tweaked the color scheme, logo and favicon (thanks Eran)
• Got some friends to help out (though so far they’ve only posted answers, not questions)
• Setup Google Analytics, and noticed incoming search traffic only stayed for 42 seconds on the site
• Opened a small AdWords campaign, paying 1.5$ a day to test the water.
• Post the site on this blog, of course.

Now what remains to be seen is whether the site can accumulate the needed critical mass. For now, the site is in beta, meaning I don’t have to pay anything to keep it running (except time and effort). When the beta is over, the cost will be $129 a month, which is quite challenging to make using adsense.

Keep your fingers crossed for me

P.S.

Just got a $100 coupon for AdWords by visiting Google Webmasters Tools – how cool is that? In a second look, it appears the coupon was lying in my Webmasters Tools inbox for two months now, just waiting for the perfect opportunity.

I also forgot to mention opening a uservoice forum (+ adding the widget to my site).

Chcek out my recent draft walkthrough on monored Zendikar.

Well, I said this would happen.

StackOverflow’s flood gates are open, and there are many new sites based on the stackoverflow engine.

One of those that I think has great potential is Ask Science, though at the moment it’s rather desolate:

A devilish problem I’ve had in the past week is the the Windows “System” process was locking a folder or two. This was on a build agent, and was causing problems deleting that folder as part of the build. This was all happening while I was introducing a new build type to our collection – automated system tests using Selenium – and I initially thought some voodoo in Selenium was causing the problem.

LockHunter (a 64-bit Unlocker equivalent) wasn’t able to unlock the folder (though it did well on folders locked by other processes). The problem seemed to go away after a reboot of the build agent, but then came back to haunt me. I tried asking this on SuperUser (StackOverflow’s colorful twin), but to no avail.

Well, last night I finally found the problem – my own computer had an open explorer window on one of the folders in the build server. I believe this window persisted even after an agent reboot. Closing it solved the problem, and achieved world peace.

A new year, a new Magic block. Get the latest draft walkthrough here.