GSoC: the now and the next

As you may recall, I have the great pleasure to participate again in Google Summer of Code this year with Mono.

Since we are nearing midterm evaluation, I thought about doing a kind of status report like last year. Unfortunately, I haven’t been as active as I wanted to this time (exams were more time consuming this semester). However there is still some cool stuff that have already landed and which are described next.

What has been done since last year

Actors and Software-transactional-memory goodness

I took some time to implement rudimentary version of those two parallel programming paradigms earlier this year.

See this post which describes in more details the ideas behind them and some examples.

New more efficient scheduler’s deque

The scheduler’s deque that was used before was quite complex due to the fact that the inherent storage mechanism was based on a doubly linked-list which is rather hard to get right when you add parallel and concurrency constraints (see ABA problem for instance).

The algorithm I was using was mostly designed with C++ in mind where you can mess up with pointers pretty easily and make freely use of CAS on pointers as integers. Since I wanted to avoid any kind of unsafe or native code in the library, I tried to port that algorithm down to C#.

After some mail exchange with a fellow person (hey Susan o/) who was using Mono’s ParallelFx on a big box in a laboratory, we started to see some concurrency problems with my code. Turns out that the ABA prevention code wasn’t really working with my C# rewrite. Therefore I decided to hunt for another, more C#-friendly, type of scheduler’s deque.

Actually, I did find it and it’s the one used now under the CyclicDeque name. It’s particularly swift because it only do integer manipulations that are particularly fast with the C# Interlocked methods and doesn’t suffer of the ABA problem because, using the vast range of values available with 64 bits integers, it’s based on a forward-only algorithm.

With the tests I was able to do, this new deque works more reliably and faster than the precedent. It’s currently enabled by default but I need to do some 32 bits checks to see if it behaves as expected on those plateforms.

New types

Following the new type introduced as part of my first SoC and the two parallel paradigms I described above, I have done some other parallel and concurrent code to be used both internally and publicly.

One of those is a new collection, ConcurrentSkipList that provides a thread-safe implementation of a skip-list (a nice tree-ish list container). This skip-list implementation is also used for the ConcurrentDictionary type.

The other is a stripped down CountdownEvent called Snzi (Scalable non-zero indicator) that basically do the same thing except that instead of keeping a count record, Snzi just tells in a binary fashion if there is or not a count remaining. That weaker semantic opens the door for more scalable and efficient optimizations.

Optimizing, fixing and hardening

The final task that occupied me during the inter-soc period was mostly tuning and bug-fixing the existing parts with a focus on Task reliability and PLinq performance and correctness.

What have I begin to do for this SoC

Currently I’m hard working on the .NET 4 port of Mono’s ParallelFx as it comes with a whole lot of new stuff and API changes.

The ParallelFx team over at Microsot has been publishing posts these last months about the new things coming down the pipe (check out their blog if you still haven’t do so).

At the moment, the System.Threading.Tasks namespace port is fairly complete and Tasks/Future unit tests are all back to green.

I’m now working a bit on the Collections namespace, adapting some of my code to the new API (notably ConcurrentDictionary) and seeing how to implement the new Partitioner pattern.

What to expect next

First of all, the following weeks are going to be quite more productive as, with big thanks to Alan and Miguel, I’m going to spend a month in Dublin hacking in the Novell offices. Looking forward to this.

As for the next, the plan is to continue porting the existing code to .NET 4, first with the Parallel loops class (with probably some further optimizations on data source partitioning) and then PLinq.

In addition, since Mono recently enabled the .NET 4 profile in SVN, some of the ParallelFx code will also soon transition from the google code repository to official Mono’s trunk for early mass consumption.

Finally, last but not least, I’m going to devote the rest of the summer to testing ParallelFx more extensively with, both, improving the existing test suite with harder parallel stress-testing and the development of a Chess-like parallel correctness checker.

See you at the end of the SoC for another full report .

MD quick feature : switch support in Autotools deployment project

Just to let you know that MonoDevelop’s Autotools deployment projects now allow you to add specific switch for the configure script.

Let’s say for instance that you want to enable at compile time a specific feature in your project. Now what you can do is add a switch to your deployment project which will be turned in something like --enable-super-feature on configure side (i.e. you will be able to run configure like ./configure --enable-super-feature).

This will actually define (as in #define) a symbol that you can use with #if … #endif constructs in your code to activate your specific feature.

Since we are at it, here is a little screenie :

I will add support asap for simple makefile projects. The UI is also probably a bit rough, if there are any usability expert out of there I will gladly accept any sensible criticism .

Zencomic 0.1.3

This is a release that was lying around on my desk. It contains a little set of new features.

Summary

Zencomic is the comic strip-driven productivity enhancer that periodically makes your day funnier by showing comic like Dilbert or XKCD in a bubble.

ChangeLog

• Added a ‘Show now’ button for immediate pleasure consumption
• Image processing is now deferred to a separate thread
• Tentatively try to see if the screensaver is active

Download

Tarball : http://netherilshade.free.fr/mono/zencomic-0.1.3.tar.gz

Enjoy !

Rupert’s going famous

As I speak, paparazzi are getting crazy all over the world after hearing that Rupert (Mono’s mascot) has been making his debuts on an international music scene.

Indeed, Mr Rupert was seen in company of Mr Gnarly Snag (of Smokin’Fez Monkey band) and a fellow Monoïste, playing at FIMU (International Student Music Festival).

Mr Rupert also liked Mr Austin Walkin’Cane performance and sent his buddies to get some group picture :

All in one, Mr Rupert is pretty happy of these 3 festival days and he is now enjoying some well deserved rest.

Zencomic 0.1.2

Edit: And two releases in the same day. Thanks to goto for discovering the CPU issue.

A bunch of fix and improvements for Zencomic, the comic strip-driven productivity enhancer.

Changelog

• Fix CPU usage bug
• Geekscottes addin contributed by Frederic Forjan
• Added conditional compiling for Timeout.AddSeconds (--enable-timeout-second switch). Fix build error for non-svn Gtk#
• Intercept SIGINT and SIGTERM signals to save configuration before exiting
• Added COPYING file

Tarball : http://netherilshade.free.fr/mono/zencomic-0.1.2.tar.gz

Fantasy book list

Almost ever since I was able to read, I was always found the nose in a book during my free time. Even though computer is filling most of that time these days, I continue to enjoy a lot immersing myself in the book worlds.

Very soon, the books that hold most of my attention were fantasy ones and more specifically of the high fantasy kind (a genre popularized by Tolkien and Lewis among others). It’s this passion that I want to share here.

I had this idea of a list floating around the corners of my mind, a list where I would put the books I most liked. The kind of book that leaves you stunned and dazed after you have finished the whole series in a row. Recently, a friend told me that this sort of list would be a good inspiration for him as he was looking into entering that wonderful world too.

So, here we go :

My Pillars

• Lord of the Ring – Tolkien
• Narnia – CS Lewis
• Royal Assassin – Robin Hobb
• Raven Chronicles – James Barclay
• The Wheel of Time – Robert Jordan
• The Sword of Truth – Terry Goodking
• Shannara – Terry Brooks

Other excellent series

• Ages of the Fives – Trudi Cavanan
• Black Magician – Trudi Cavanan
• The Belgariad – David Eddings
• Everworld – K. A. Applegate
• Eragon – Christopher Paolini
• Bartimeus Trilogy – Jonathan Stroud

Fantasy a little bit different

• Tales of the Otori – Lian Hearn
• The Wind of Fire – William Nicholson
• Darren Shan – Darren Shan
• Chronicles of Ancient Darkness – Michele Paver
• The Reindeer People – Megan Lindholm

Of course, this list can’t possibly be exhaustive. Fantasy books are like Internet websites, after finishing one you still have another dozen that have appeared in the meantime.

Now, I hope this friend will feed me with his own list of science-fiction books .

Book meme²

It’s like I’m trying to complete my monthly blogging quota in just one evening but, anyway, here is for me :

“Reliquat d’une époque depuis longtemps révolue ; symbole d’une ère plus heureuse à venir”

Tentatively translated : “Remaining of an epoch long gone ; symbol of an happier era to come”

Instructions :

• Grab the nearest book.
• Open it to page 56.
• Find the fifth sentence.
• Post the text of the sentence in your journal along with these instructions.
• Don’t dig for your favorite book, the cool book, or the intellectual one: pick the CLOSEST.

Spread the love.

Mathematical digression : Buffon’s needle

Buffon’s needle is a statistic experiment created by Comte George-Louis Leclerc (sounds so frenchie).

The principle is to drop needles on a parquet floor and check if the needle cross one of the parquet line (providing each parquet’s strip has the same height).

The experiment can be modeled as two random variables representing, for the first, the distance between the center of the needle and the closest parquet line, for the second, the acute angle between the needle and the line. Both random variables follow a uniform distribution, respectively of parameters (0, ) and parameters (0, ).

A needle cross a line when the angle is superior to 0 and, depending on the previous angle, the distance is less than :

Thus, the condition “the needle cross the line” can be summarized by this equation :

Where a is the length of the needle, θ the angle and x the distance.

The cool part is that computing the joint probability of the two random variable with the crossing condition gives you an expression of π :

Where N is the number of needle dropped, l the height of a strip and n the number of needle that crossed the line.

Therefore, for a good number of needle drop you can get a value fairly close to π.

The following C# source code is doing precisely that :

using System;

namespace BuffonApp
{
  class BuffonNeedles
  {
	public static void Main ()
	{
	  // Number of time we will drop a needle
	  const int N = 1000000;
	  // Interval between each line
	  const int a = 10;
	  // Size of a needle
	  const int l = a - 4;
	  // Our random number generator
	  Random r = new Random ();
	  // Number of time we cross the line
	  int n = 0;

	  for (int i = 0; i < N; i++) {
		double x = r.NextDouble () * (a / 2);
		double theta = r.NextDouble () * (Math.PI / 2);
		if (x <= (l / 2) * Math.Sin (theta))
		  n++;
	  }

	  Console.WriteLine ("Pi approximation : " + ((double)(N * 2 * l)) / (n * a));
	}
  }
}

Which give us a rather good approximate of :

Because useless is always a must-have

If you are a webcomic fan like me and wouldn’t mind a strip from time to time disturbing a little your workflow, here is a little application I wrote up that might interest you.

I called it Zencomic. It simply displays a notification bubble with a random comic regularly. Everything is implemented as addins via Mono.Addins and currently you have a Dilbert addin and an xkcd addin coming with for free.

Screenie :

Tarball : http://netherilshade.free.fr/mono/zencomic-0.1.tar.gz

Yet another round of Summer love

This year again, I will have the pleasure to participate in GSoc, continuing my work on ParallelFx with the Mono folks. Yay !

Basically, my three main tasks will be :

1. Port the code over the new ParallelFx API which is coming in the .NET 4 framework beta
2. Improve the testing and reliability of the library
3. Integrate all that stuff into Mono trunk for widespread consumption

You can find the summary of my proposition on the GSoC website.

In other news, I opened an identi.ca account where I will report my progress over the summer among other stuff. Check it out at : http://identi.ca/garuma/all