A little over 18 months ago I was talking to Stephen Toub (he of the Parallel Computing fame) about parallelism and the kinds of problems it could solve.
I said, naively, "could we solve the million monkey's problem?"
He said, "the what?"
"You know, if you have an infinite number of monkeys and an infinite number of keyboards they will eventually write Shakespeare."
We brainstormed some ideas (since Stephen is a smarter than I, this consisted mostly of him gazing thoughtfully into the air while I sat on my hands) and eventually settled on an genetic algorithm. We would breed thousands of generations of (hypothetical) monkeys a second and then choose which ones would be allowed to perpetuate the species based solely on their ability to write Shakespeare.
We used the .NET 4 Task Parallel Library to make it easier for the algorithm to scale to available hardware. I mean, anyone can foreach over a million monkeys. But loops like that in parallel over 12 processors takes talent, right? Well, kinda. A lot of it is done for you by the Parallelism Features in .NET and that's the point. It's Parallel Processing for the Masses.
We created a WinForms version of this application and I've used it on and off to demonstrate parallel computing on .NET. Then Paul Batum and I went to the Keeping It Realtime conference to demonstrate SignalR this last week. I didn't want to do the same "here's a real-time chat app" or "here's a map that shows its results in real-time" demos that one always does at these kinds of things. I suggested that we port our WinForms Shakespeare Monkey demo to ASP.NET and SignalR and that's what Paul proceeded to do.
When doing something that is crazy computationally intensive but also needs to return real-time results you might think to use node for the real-time notification part and perhaps spawn off another process and use C or something for the maths and then have them talk to each others. We like node and you can totally run node on IIS or even write node in WebMatrix. However, node is good at some things and .NET is good at some things.
For example, .NET is really good at CPU-bound computationally intensive stuff, like, I dunno, parallel matrix multiplication in F# or the like. ASP.NET is good at scaling web sites like Bing, or StackOverflow. You may not think IIS and ASP.NET when you think about real-time, but SignalR uses asynchronous handlers and smart techniques to get awesome scale when using long-polling and scales even more in our labs when using an efficient protocol like WebSockets with the new support for WebSockets in .NET 4.5.
So, we wanted to see if you combined asynchronous background work, use as many processors as you have, get real-time status updates via SignalR over long-polling or Web Sockets, using C#, .NET 4.5, ASP.NET and IIS.
It takes about 80,000 generations of monkeys at thousands of monkey generations a second (there's 200 monkeys per generation) to get the opening line of Hamlet. So that's ~16,000,000 monkeys just to get this much text. As they say, that's a lot of monkeys.
Here's the general idea of the app. The client is pretty lightweight and quite easy. There's two boxes, two buttons and a checkbox along side some text. There's some usual event wireup with started, cancelled, complete, and updateProgress, but see how those are on a monkey variable? That's from $.connection.monkeys. It could be $.connection.foo, of course, as long as it's hanging off $.connection.
Those functions are client side but we raise them from the server over the persistent connection then update some text.
<script src="Scripts/jquery-1.6.4.min.js"></script>
<script src="Scripts/json2.min.js"></script>
<script src="Scripts/jquery.signalR.min.js"></script>
<script src="signalr/hubs"></script>
<script>
$(function () {
$('#targettext').val('To be or not to be, that is the question;\nWhether \'tis nobler in the mind to suffer\n\The slings and arrows of outrageous fortune,\n\Or to take arms against a sea of troubles,\n\And by opposing, end them.');
var monkeys = $.connection.monkeys,
currenttext = $('#currenttext'),
generationSpan = $('#generation'),
gpsSpan = $('#gps');
monkeys.updateProgress = function (text, generation, gps) {
currenttext.val(text);
generationSpan.text(generation);
gpsSpan.text(gps);
};
monkeys.started = function (target) {
$('#status').text('Working...');
$('#targettext').val(target);
$('#cancelbutton').removeAttr('disabled');
};
monkeys.cancelled = function () {
$('#status').text('Cancelled');
$('#cancelbutton').attr('disabled', 'disabled');
};
monkeys.complete = function () {
$('#status').text('Done');
$('#cancelbutton').attr('disabled', 'disabled');
};
$.connection.hub.start({}, function () {
$('#startbutton').click(function (event) {
$('#status').text('Queued...');
monkeys.startTyping($('#targettext').val(), $('#isparallel').is(':checked'));
});
$('#cancelbutton').click(function (event) {
monkeys.stopTyping();
});
});
});
</script>
The magic start with $.connection.hub.start. The hub client-side code is actually inside ~/signalr/hubs. See how that's include a the top? That client-side proxy is generated based on what hub or hubs are on the server side.
The server side is structured like this:
[HubName("monkeys")]
public class MonkeyHub : Hub
{
public void StartTyping(string targetText, bool parallel)
{
}
public void StopTyping()
{
}
}
The StartTyping and StopTyping .NET methods are callable from the client-side via the monkeys JavaScript object. So you can call server-side C# from the client-side JavaScript and from the C# server you can call methods in JavaScript on the client. It'll make the most sense if you debug it and watch the traffic on the wire. The point is that C# and Json objects can flow back and forth which blurs the line nicely between client and server. It's all convention over configuration. That's how we talk between client and server. Now, what about those monkeys?
You can check out the code in full, but StartTyping is the kick off point. Note how it's reporting back to the Hub (calling back to the client) constantly. Paul is using Hub.GetClients to talk to all connected clients as broadcast. This current implementation allows just one monkey job at a time. Other clients that connect will see the job in progress.
public void StartTyping(string targetText, bool parallel)
{
var settings = new GeneticAlgorithmSettings { PopulationSize = 200 };
var token = cancellation.Token;
currentTask = currentTask.ContinueWith((previous) =>
{
// Create the new genetic algorithm
var ga = new TextMatchGeneticAlgorithm(parallel, targetText, settings);
TextMatchGenome? bestGenome = null;
DateTime startedAt = DateTime.Now;
Hub.GetClients<MonkeyHub>().started(targetText);
// Iterate until a solution is found or until cancellation is requested
for (int generation = 1; ; generation++)
{
if (token.IsCancellationRequested)
{
Hub.GetClients<MonkeyHub>().cancelled();
break;
}
// Move to the next generation
ga.MoveNext();
// If we've found the best solution thus far, update the UI
if (bestGenome == null ||
ga.CurrentBest.Fitness < bestGenome.Value.Fitness)
{
bestGenome = ga.CurrentBest;
int generationsPerSecond = generation / Math.Max(1, (int)((DateTime.Now - startedAt).TotalSeconds));
Hub.GetClients<MonkeyHub>().updateProgress(bestGenome.Value.Text, generation, generationsPerSecond);
if (bestGenome.Value.Fitness == 0)
{
Hub.GetClients<MonkeyHub>().complete();
break;
}
}
}
}, TaskContinuationOptions.OnlyOnRanToCompletion);
}
If he wanted, he could use this.Caller to communicate with the specific client that called StartTyping. Inside ga.MoveNext we make the decision to go parallel or not based on that checkbox. This is where we pick two random high quality parent monkeys from our population for a potential future monkey. Hopefully one whose typing looks more like Shakespeare and less like a Regular Expression.
By simply changing from Enumerable.Range to ParallelEnumerable.Range we can start taking easily parallelizable things and using all the processors on our machine. Note the code is the same otherwise.
private TextMatchGenome[] CreateNextGeneration()
{
var maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;
var sumOfMaxMinusFitness = _currentPopulation.Sum(g => (long)(maxFitness - g.Fitness));
if (_runParallel)
{
return (from i in ParallelEnumerable.Range(0, _settings.PopulationSize / 2)
from child in CreateChildren(
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
select child).
ToArray();
}
else
{
return (from i in Enumerable.Range(0, _settings.PopulationSize / 2)
from child in CreateChildren(
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
select child).
ToArray();
}
}
My 12 proc desktop does about 3800 generations a second in parallel.
_thumb.png "Hexacore Super Computer!")
Big thanks to Paul for the lovely port of this to SignalR and to Stephen Toub for the algorithm.
The code for the SignalR monkeys demo is on my BitBucket. Right now it needs .NET 4.5 and the Visual Studio Developer Preview, but you could remove a few lines and get it working on .NET 4, no problem.
Note that that SignalR works on .NET 4 and up and you can play with it today. You can even chat with the developers in the SignalR chat app in the 'aspnet' room at http://chatapp.apphb.com. Just /nick yourself then /join aspnet.
No monkeys were hurt in the writing of this blog post.
Hosting By
_fce5c215-1b4f-42e4-a3d6-16526e86c325.png "First, switch to 16x9")
_b0b972e9-e488-4d4e-9afa-eadc21560dee.png "Step two, change the scale up and down")
_a5608596-cac4-4cf3-9169-89c6aa3c469a.png "My enormous corectly ratio-ed head. Or IS IT?!")
_2.png "Hexacore Super Computer!")
In the near future, all browsers and servers will support Web Sockets, a technique by which a persistent connection is negotiated over HTTP and then a protocol switch happens from http:// to ws://. However, not every browser or server is there yet (IE9, for example) and there's some arguing about versioning, etc. If you don't support Web Sockets, falling back to "Long Polling" is a way to get effectively the same behavior that works everywhere. 
_3.jpg "CC BY-NC 2.0 Creative Commons Clock Photo via Flickr ©Thomas Hawk")