After I lamented about missing key features for Erlang style tasks, Avish has told me about ThreadPool.RegisterWaitForSingleObject, which I was unaware of.

I bang out this implementation of parallel sort as an example. Hacking code, proof of concept, written at 3AM in the morning, etc.

public static WaitHandle ParQuickSort<T>(T[] domain, int lo, int hi)
	where T : IComparable<T>
{
	if (hi - lo <= 1)
	{
		return new ManualResetEvent(true); //already signalled, no wait
	}
	ManualResetEvent manualResetEvent = new ManualResetEvent(false);
	Semaphore semaphore = new Semaphore(0, 2);

	int pivot = Partition(domain, lo, hi);

	WaitOrTimerCallback releaseSemapore = delegate
	{
		int release = semaphore.Release();
		if (release == 1)
		{
			manualResetEvent.Set();
		}
	};
	ThreadPool.QueueUserWorkItem(
		delegate
		{
			WaitHandle leftWaitHandle = ParQuickSort(domain, lo, pivot - 1);
			ThreadPool.RegisterWaitForSingleObject(leftWaitHandle,
			                                       releaseSemapore, null, TimeSpan.FromDays(1), true);
		});
	ThreadPool.QueueUserWorkItem(
		delegate
		{
			
			WaitHandle rightWaitHandle = ParQuickSort(domain, pivot + 1, hi);

			ThreadPool.RegisterWaitForSingleObject(rightWaitHandle,
			                                       releaseSemapore, null, TimeSpan.FromDays(1), true);
		}
		);
	return manualResetEvent;
}

Yes, it is ugly, but bear with me.

The usage pattern is simple:

WaitHandle sort = ParQuickSort(data, 0, count - 1);
sort.WaitOne();

Obviously we can use a Future here instead.

What is interesting is that hacking approach thought me several things, RegisterWaitForSingleObject will crash & burn if you try to wait for over 369,846 objects, since at that point you will get this lovely exception:

Unhandled Exception: System.ApplicationException: Not enough storage is available to process this command. (Exception from HRESULT: 0x80070008)
   at System.Threading.ThreadPool.RegisterWaitForSingleObjectNative(WaitHandle waitHandle, Object state, UInt32 timeOutInterval, Boolean executeOnlyOnce, RegisteredWaitHandle registeredWaitHandle, StackCrawlMark& stackMark, Boolean compressStack)

...

Second, performance here is really a bitch, it took the impl above 5 seconds to sort through 100,000 items, while Array.Sort did it in a few milliseconds. In fact here are the numbers:

Parallel: 00:00:06.2656250
Array.Sort: 00:00:00.0156250

I actually had to get to 100,000 items before I could catch Array.Sort actually taking any time.

I am going to bet that what skews the problem is all the calls to events and semaphores, those are kernel calls, which are taking long time. Not nearly wake enough to try to implement user mode locking strategy that would work here.

At any rate, it looks like this approach, at least, is not really going to be a worthwhile one.