I had been looking for a pretext to put up a blog, and a programming challenge is as good a pretext as any other.
The challenge.
My solution:
using System;
using System.Collections;
using System.Threading;
namespace dev102progchallenge
{
class Program
{
const int Iterations = 100; // a nice large-ish number to get some meaningful time measurements
static private byte[,] byteArr = new byte[1000, 1000];
static private ManualResetEvent[] waitEvents;
static void Main(string[] args)
{
Fill(byteArr);
waitEvents = new ManualResetEvent[Environment.ProcessorCount];
DateTime time = DateTime.Now;
for (int n = 0; n < Iterations; n++) {
// this Floor() isn't really needed, since every operand is integer
int rowsPerCpu = (byteArr.GetUpperBound(0) - byteArr.GetLowerBound(0)) / Environment.ProcessorCount;
int lastCpuRemainder = byteArr.GetUpperBound(0) - (rowsPerCpu * (Environment.ProcessorCount - 1));
// spawn a thread for every cpu we have.
// this problem is perfectly parallelizable (minus the remainder of the rows / cpus division, in this implementation)
for (int proc = 0; proc < Environment.ProcessorCount; proc++) {
waitEvents[proc] = new ManualResetEvent(false);
Reverser rev = new Reverser(byteArr, rowsPerCpu * proc, proc == Environment.ProcessorCount ? rowsPerCpu + lastCpuRemainder : rowsPerCpu);
// a thread from the pool is nicer and lighter
ThreadPool.QueueUserWorkItem(new WaitCallback(rev.Reverse), waitEvents[proc]);
}
}
WaitHandle.WaitAll(waitEvents); // block until all threads are finished
Console.WriteLine(string.Format("Iterations: {0} - time: {1} ms", Iterations, (DateTime.Now - time).TotalMilliseconds));
}
/// <summary>
/// Utility method to fill the array
/// </summary>
/// <param name="arr">the array to be filled</param>
static void Fill(byte[,] arr)
{
Random rnd = new Random();
for (int i = arr.GetLowerBound(0); i <= arr.GetUpperBound(0); i++) {
for (int j = arr.GetLowerBound(1); j <= arr.GetUpperBound(1); j++) {
arr[i, j] = (byte)rnd.Next(255);
}
}
}
}
/// <summary>
/// A class to contain the thread method, to allow for more than one parameter to be passed to the thread
/// </summary>
class Reverser
{
private int begin, count;
private byte[,] arr;
public Reverser(byte[,] arr, int begin, int count)
{
this.arr = arr;
this.begin = begin;
this.count = count;
}
public void Reverse(object waitEvent)
{
for (int i = begin; i <= begin + count; i++) {
for (int j = arr.GetLowerBound(1); j <= arr.GetUpperBound(1); j++) {
// copied from http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
// post-modern programming: never reinvent what you can adapt
arr[i, j] = (byte)(((arr[i, j] * 0x0202020202UL) & 0x010884422010UL) % 1023);
}
}
((ManualResetEvent)waitEvent).Set();
}
}
}