Saturday, 10 May 2008

Dev102.com programming challenge

First post.
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();
        }
    }
}