Necessary and Sufficient

A while ago I reviewed basic sorting algorithms in Java and C#. I've been playing a lot with F# over the past 6 months so I'd thought it would be worthwhile whipping up the same algorithms in F#.

The earlier posts with Java and C# implementations are here:
Sorting Fundamentals: Part 1
Sorting Fundamentals: Part 2

Bubble Sort

Everyone knows this is an inefficient algorithm but none-the-less it has "educational value". In my F# implementation I've defined 2 recursive functions, sink and outer. Both functions accept a list and return a new list. The sink function makes a single pass through the list sinking the largest value to the rightmost/last position in the list using simple pattern matching semantics. In lines 7-8 the cons operator (::) is used to separate the first 2 items in the list from the remainder of the list so a greater than pairwise comparison can be make on the leading pair. Note that lists, and indeed all identifiers not explicitly marked as mutable, are immutable so a new list is created rather than returning the original list. In other words, it is not in-place.

The second function, outer, is logically equivalent to the outer loop in the C#/Java implementation that you've no doubt seen before. We pass a list and the list size to this function. The function sinks one value using the function described above, then calls itself recursively on a new list that is a copy of the original list but has one fewer items - the "sunken" element is removed from the end.

Insertion Sort

The insertion sort algorithm works by inserting each item into an already sorted sub-list. In F# I've implemented it using 2 recursive functions, insert and insertionSort. Both functions take a list and return a new list. The insert function takes an item and a list and creates a new list which is a copy of the one passed but it inserts the passed item into the new list. This function is designed to take a sorted list or an empty list - which then becomes a sorted list.

The insertionSort function picks off the first item in the list and inserts it into the already-sorted sublist .

QuickSort

The quicksort algorithm is a classic divide-and-conquer algorithm. It selects a pivot from the list then creates 2 sub-lists containing all items less than, and greater than the pivot. The result is a new list which is the concatenation of the less-than list, the pivot, and the greater-than list. And, in order to sort the 2 sub-lists it calls itself recursively.

#light

open System

let rec quickSort ls =

  match ls with

  | [] -> []

  | p::r -> 

     quickSort [for i in r do if (compare i p) <= 0 then yield i] 

     @ [p] 

     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          

let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

let mylistsorted = (quickSort mylist)

print_any mylistsorted

Console.ReadLine() |> ignore

MergeSort

Of all the sort algorithms, quicksort is perhaps the most amenable to functional programming as it can exploit parallelization. If I had 10 billion records in numerous files over many machines a modified version of mergeSort is what you'd want top use, but that's a topic for another post...

As you can see, F# code is succinct and highly expressive. I liken it to Python in it's terseness without the performance penalty! The beauty of F# is a lightweight syntax where whitespace is used instead of block- and scope-defining curly braces, and the clever use of type inference within a strongly-typed type system, so I needn't get bogged down defining explicit types which makes the code's purpose clearer.

Modern multi-core processors make it easier for programmers to achieve parallelism and improve concurrency. In order to do this programmers can make use of threads to perform multiple tasks concurrently in an effort to improve expected speedup, as defined by Amdahl's Law. To improve speedup the programmer needs to employ an algorithm that is amenable to parallelization and be conversant with multi-threading techniques. There's lot of references to algorithms elsewhere on this blog so I'd thought I examine some basics patterns/issues of thread use...

For a review of basic concurrency issues see this post.

Caveat Emptor

Threads are a nifty way to improve concurrency but they come at a cost - added complexity. You need to be very sure you really need the benefit that comes with concurrency before venturing down this path.

Also, be aware that creating more threads than there are available cores can only lead to context switching which might be detrimental to performance.

Spawning a Worker Thread

Want to create a fire-and-forget operation that runs on a new thread? Create an instance of the Thread class in the System.Threading namespace, assigning it a ThreadStart or ParameterizedThreadStart delegate in the constructor. Give the thread a name if you like, and set it on it's way by invoking the aptly named Start() method.

In the following example you'll notice the console output of both threads is interleaved - letters from the main thread mixed in with numbers from the "worker" thread - demonstrating the time-slicing and preemptive multi-tasking used by modern operating systems.

Lastly, note that by default threads created in this fashion are foreground threads that cause the application to stay alive until they are finished. To create background threads, use the provided ThreadPool (see below) or explicitly mark your threads via the IsBackground boolean property. Running background threads does not cause the application to wait for them on shut down, so be advised that cleanup tasks might not get run in this case.

        static void Main()
        {
            var t = new Thread(DoSomeWork);
            t.Start();
            for (char c = 'a'; c <= 'z'; c++)
                Console.WriteLine(c);

            Console.ReadLine();
        }

        static void DoSomeWork()
        {
            for(int i=0; i< 1000; i++)
                Console.WriteLine( i );
        }

Forcing a Spawned Worker Thread to Yield

If you sleep the thread for 0 or more milliseconds the thread will yield to any other thread waiting to process. By "yield" I mean give up it's allocated CPU time-slice. Here's an example where the first thread created calls a function that writes out "B"s and this thread yields after printing 10 of them, allowing the second spawned thread to output "A"s to the console.

Note that we're now using a lambda expression to define an anonymous method rather than passing in a ThreadStart-compatible delegate. This allows us to pass strongly-typed parameters to the method. If you use the ParameterizedThreadStart delegate you can only pass in a System.Object parameter which kind of defeats the purpose of using a strongly-typed language IMHO.

        static void Main()
        {
            var t1 = new Thread(() => RepeatedPrint(100, 10, "B"));
            t1.Start();

            var t2 = new Thread(() => RepeatedPrint(1000, 1000, "A"));
            t2.Start();

            Console.ReadLine();
        }

        static void RepeatedPrint(int UpperLimit, int yieldAfter, string output)
        {
            for (int i = 0; i < UpperLimit; i++)
            {
                if (i % yieldAfter == 0)
                    Thread.Sleep(0);
                Console.Write(output);
            }
        }

Signalling a Spawned Worker Thread using EventWaitHandles

If you want to send a thread a signal - and that signal can mean whatever you like - you can use several .NET constructs but the easiest are EventWaitHandles. Think of a signal as a traffic light - when it's red the signaled thread can't proceed and must wait; when it's green the thread goes on its' merry way.

There are in fact 2 different types of EventWaitHandles - AutoResetEvent and ManualResetEvent. The best analogy I've heard is in Joe Albahari's C# book where he likens AutoResetEvent to a single-ticket turnstile, and ManualResetEvent to a gate. The turnstile (AutoResetEvent) only lets one item through at a time and only after a "'ticket" is provided. Conversely, the gate (ManualResetEvent) is either open or closed and if open all threads can pass, if closed all threads queue in arriving order. The table below details the actions of the 3 critical methods.

In the code below 2 threads are created but we only signal once so only the first thread gets to the point where it spews out characters on the console. The second thread is in fact a background thread so it's existence in a blocked state does not keep the application alive.

        private static EventWaitHandle turnstile = new EventWaitHandle(false, EventResetMode.AutoReset);

        static void Main()
        {
            var t1 = new Thread(DoSomeWork);
            t1.Start();
            Console.WriteLine("Waiting");
            Thread.Sleep(5000); // wait 5 seconds
            Console.WriteLine("Signalling");
            turnstile.Set(); // open the turnstile 

            var t2 = new Thread(DoSomeWork) {IsBackground = true};
            t2.Start(); // never gets signalled
        }

        static void DoSomeWork()
        {
            turnstile.WaitOne();    // wait indefinitely for the turnstile to open 
            for (int i = 0; i < 1000; i++)
                Console.Write("a");
        }

And for completeness, here is an example where the meaty part of the worker thread is never reached because on 1 too many calls to WaitOne(). Had the t1 thread been a foreground thread instead of a background thread the program would have hung with an indefinitely blocked foreground thread. Not good!

        private static readonly EventWaitHandle turnstile = new EventWaitHandle(false, EventResetMode.AutoReset);

        static void Main()
        {
            var t1 = new Thread(() => SomeBackgroundStuff('A')) {IsBackground = true};
            t1.Start();
            Console.WriteLine("Waiting");

            Thread.Sleep(5000); // wait 5 seconds

            Console.WriteLine("Signalling");
            turnstile.Set(); // open the turnstile 

            Thread.Sleep(5000); // wait 5 seconds
        }

        static void SomeBackgroundStuff(object data)
        {
            turnstile.WaitOne(); // wait to be signaled
            turnstile.WaitOne(); // wait to be signaled (BAD CODE HERE)
            var c = (char)data;
            for (int i = 0; i < 10; i++)
                Console.Write(c);
        }

Killing off a Spawned Worker Thread

If you've dispatched a thread to do some work and later change your mind you'll want to abort the spawned thread. The .NET Framework provides the Thread.Interrupt and Thread.Abort method but you don't really want to use these by themselves. The Interrupt() method does not interrupt a non-blocked thread immediately - it waits until the thread is next blocked which may never happen! Thus it really works only on blocked threads, and forces you to put in messy exception handling in the worker thread method to ensure cleanup happens. The example below demonstrates the inability of the main thread to immediately interrupt the spawned thread by calling Interrupt() on it, because the spawned thread is not in a blocked or waiting state - it's just busy counting to 1 million.

        static void Main()
        {
            var t = new Thread(DoSomeWork);
            t.Start();

            Thread.Sleep(3000);

            t.Interrupt();
            Console.WriteLine("Have interrupted the thread");
            Console.ReadLine();
        }

        static void DoSomeWork()
        {
            for (int i = 0; i < 1000000; i++)
                Console.WriteLine(i);
        }

The Abort() method does kick in immediately for both blocked and non-blocked threads but this in itself causes problem because we can't be sure all items in the call stack, including framework code, are abort-safe. Thread.Abort is generally considered harmful (see IanG's post) since its' use of "asynchronous exceptions" can cause unreleased locks and other nastiness. According to MSDN, if a thread calls Abort() on itself "the effect is similar to throwing an exception; the ThreadAbortException happens immediately, and the result is predictable" which is good to know and can be exploited in our preferred pattern...

My preferred pattern to use is for the master thread to set a flag (ideally a volatile bool field or an EventWaitHandle) that is visible to both the master and the worker thread, and for the worker thread to periodically check this flag. The immediacy of the abort can be controlled by the programmer by manipulating the flag polling frequency in the worker thread, and the worker thread has an opportunity to perform any necessary cleanup. The code below demonstrates this:

        private static readonly EventWaitHandle cancelFlag = new EventWaitHandle(false, EventResetMode.ManualReset);

        static void Main()
        {
            var t = new Thread(DoSomeWork);
            t.Start();

            Thread.Sleep(5000);
            cancelFlag.Set();   // single the worker thread to cancel
            Thread.Sleep(5000);
            Console.ReadLine();
        }

        static void DoSomeWork()
        {
            for (int i = 0; i < 1000000; i++)
            {
                if (cancelFlag.WaitOne(0))  // check if cancel flag is set
                {
                    Console.WriteLine("...asked to cancel by master thread...");
                    break;
                }
                Console.Write("A");
            }
        }

To Pool or Not to Pool

When you create a thread as shown above there is a small performance hit whilst the thread is created. Since you are using threads to improve performance through concurrency this thread creation penalty may not be what you want. To minimize it you can pre-create threads, or pull one out of the provided thread pool (you get one of these per application). There is a system-provided ThreadPool class and a static method ThreadPool.QueueUserWorkItem(WaitCallback) to make this easier. The following code sample demonstrates both concepts and quantifies the creation penalty. Note that, whilst pooling minimizes thread creation time, thread start time now become non-deterministic because the pool will enforce a concurrent thread execution limit and thus threads may be forced to wait.

        static void Main()
        {
            int workerCount, ioPorts;
            ThreadPool.GetMaxThreads(out workerCount, out ioPorts);
            Console.WriteLine("Thread pool size =" + workerCount  );
            Console.WriteLine("IO Ports =" + ioPorts);

            var threads = new List<Thread>();
            var sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < workerCount/2; i++)
            {
                threads.Add(new Thread(() => DumbCounter("A")));
                threads[i].Start();
            }
            Console.WriteLine( "Elapsed time =" + sw.ElapsedTicks );
            sw.Reset();
            sw.Start();
            for (int i = 0; i < workerCount / 2; i++)
                ThreadPool.QueueUserWorkItem(DumbCounter, "B");

            Console.WriteLine("Elapsed time =" + sw.ElapsedTicks);
        }

        // this is a WaitCallback Delegate compatible method
        static void DumbCounter(object data)
        {
            int j = 0;
            for (int i = 0; i < 100; i++)
            {
                j++;
                //Console.Write(data);
            }
        }

On my PC the manually created threads are approximately 3000 times slower to create in this small test.

As mentioned earlier, threads taken from the system-provided ThreadPool are created as background threads, meaning they do not keep the application alive if an application shutdown happens. If you are unsure whether a thread has been drawn from the pool or not check the value of the Thread.CurrentThread.IsThreadPoolThread boolean property.

Waiting for a Thread

Say you've created your own thread and you want to wait for whatever it is doing to be completed. To do this make use of the Join() method, or if it is a thread taken from the pool, use an event wait handle (described above). In the example below, the main thread is tasked with writing out a bunch of "M"s after it has created 2 worker threads to print out "A"s and "B"s. The Join() call forces the main thread to wait until t1 has finished, which can be seen in the output - no "B"s appear after the "M"s appear. The parameter passed to the Join method is the timeout interval in milliseconds. It's prudent to set a timeout so you don't get left waiting for a renegade thread.

        static void Main()
        {
            var t1 = new Thread(() => RepeatedPrint(100, 10, "B"));
            t1.Start();

            var t2 = new Thread(() => RepeatedPrint(1000, 1000, "A"));
            t2.Start();

            t1.Join(30000);
            RepeatedPrint(10, 10, "M");

            Console.ReadLine();
        }

        static void RepeatedPrint(int UpperLimit, int yieldAfter, string output)
        {
            for (int i = 0; i < UpperLimit; i++)
            {
                if (i % yieldAfter == 0)
                    Thread.Sleep(0);
                Console.Write(output);
            }
        }

Waiting for Background Threads

As mentioned earlier, background threads do not keep an application alive on application shutdown. Abruptly ending threads is not a good idea so here's a crude pattern to keep track of manually created background threads and to let them finish up before aborting the app. All we do is join all the background threads to the main thread that is ending the program. That way they all finish, or if they take longer than the specified timeout we go ahead and exit without terminating them gracefully. Depending on the thread creation logic you want to employ it's often best to use a thread factory method that gives you a single point for thread naming, parameter setting, adding to internal registers/list, etc.

        internal static readonly List<Thread> myBackgroundThreads = new List<Thread>();
        public const int ThreadTimeout = 5000;

        static void Main()
        {

            for(char c='a'; c<= 'z'; c++)
            {
                var t = new Thread(() => SomeBackgroundStuff(c)) { IsBackground = true };
                myBackgroundThreads.Add(t); // locking protection skipped for brevity
                t.Start();
            }
            Thread.Sleep(5000);
            AppShutdown();
        }

        // gracefully WAIT for all background threads
        static void AppShutdown()
        {
            foreach (var t in myBackgroundThreads)
                t.Join(ThreadTimeout);
        }

        static void SomeBackgroundStuff(object data)
        {
            var c = (char) data;
            for (int i = 0; i < 1000; i++)
                Console.Write(c);
        }

Getting 2 Threads to Start Concurrently

This can be achieved by using the static method WaitHandle.SignalAndWait(). This method calls WaitOne() on one wait handle and calls Set() on another atomically! That is very useful. What we need to do is have both threads call this method but swap the wait handle parameters around. Doing this ensures that neither thread fires until both are ready and then it happens concurrently as required.

        private static readonly EventWaitHandle wh1 = new EventWaitHandle(false, EventResetMode.AutoReset);
        private static readonly EventWaitHandle wh2 = new EventWaitHandle(false, EventResetMode.AutoReset);

        static void Main()
        {
            var t1 = new Thread(PartAStuff);
            var t2 = new Thread(PartBStuff);
            t1.Start();
            Thread.Sleep(5000); //pause for 5 seconds
            t2.Start();
            Thread.Sleep(5000); //pause for 5 seconds
        }

        static void PartAStuff()
        {
            WaitHandle.SignalAndWait(wh1, wh2);
            Console.WriteLine("Part A started at {0}", DateTime.Now );
        }

        static void PartBStuff()
        {
            WaitHandle.SignalAndWait(wh2, wh1);
            Console.WriteLine("Part B started at {0}", DateTime.Now);
        }

Thread Sequencing

Say you have a few worker threads that need to perform their tasks in sequence. One way to achieve this would be to use a controller thread and have each worker thread signal back to the controller. Here is a simple example using the main thread as the controller:

        private static readonly EventWaitHandle finished = new EventWaitHandle(false, EventResetMode.AutoReset);

        static void Main()
        {
            var tA = new Thread(PartAStuff);
            var tB = new Thread(PartBStuff);
            var tC = new Thread(PartCStuff);

            tA.Start();

            finished.WaitOne(); // block until A finishes
            tB.Start();

            finished.WaitOne(); // block until B finishes
            tC.Start();

            Thread.Sleep(5000); //pause for 5 seconds

        }

        static void PartAStuff()
        {
            Console.WriteLine("Part A started at {0}", DateTime.Now );
            Thread.Sleep(5000);
            finished.Set();
        }

        static void PartBStuff()
        {
            Console.WriteLine("Part B started at {0}", DateTime.Now);
            Thread.Sleep(5000);
            finished.Set();
        }

        static void PartCStuff()
        {
            Console.WriteLine("Part C started at {0}", DateTime.Now);
            Thread.Sleep(5000);
            finished.Set();
        }

The disadvantage of this technique is that an exception in any thread causes the controller thread (the main thread in this case) to hang since we didn't use timeouts.

To be continued in Part 2...

Here's a collection of C# quirks that aren't actually quirks just implementation side effects of the compiler and the specification.

Type Inference and the Conditional Operator

The conditional operator (?:) returns one of two values depending on the value of the Boolean expression. Sounds straight forward enough but try and figure out why a compile error is thrown on line 4.

   1:              int i = 9;

   2:              int j = 8;

   3:              int max = i > j ? i : j;                // works fine 

   4:              int? nullableMax = i > j ? i : null;    // compiler error

The answer lies in Section 7.13 of the C# 3.0 specification which states on page 200-201:
The second and third operands of the ?: operator control the type of the conditional expression. Let X and Y be the types of the second and third operands. Then,
• If X and Y are the same type, then this is the type of the conditional expression.
• Otherwise, if an implicit conversion (§6.1) exists from X to Y, but not from Y to X, then Y is the type of the conditional expression.
• Otherwise, if an implicit conversion (§6.1) exists from Y to X, but not from X to Y, then X is the type of the conditional expression.
• Otherwise, no expression type can be determined, and a compile-time error occurs.

In other words, the compiler sees an integer, i, and a null, and since there's no conversion between the two it throws a "no implicit conversion" error.

By default, integer overflow is silent for runtime-evaluated items, but active for compile-time constants

This catches many programmers out until it has bitten them. I'd prefer to see it ON by default. If the programmer knows exactly what they are doing and wants to suppress it they can go and turn overflow off.

int a = Int32.MinValue;
a = a - 1999;                   // no exception
int b = Int32.MinValue - 1999;  // compile-time error

Yes, you can go in to the Advanced Build Settings in Visual Studio and force the use of the /checked+ command-line switch, but this will only happen after the programmer has been bitten by this issue. A lesser evil is to let the programmer suffer the performance overhead of, perhaps unwanted, overflow checking rather than unusual program behaviour.

Arithmetic operators are not defined for bytes and shorts

In the code shown below we are trying to add two shorts, but since the addition operator (+) is not defined for shorts, the operands are promoted to 32-bit integers and then the addition takes place. This upcast is implicit since it is a widening conversion however the addition operation produces an System.Int32 result which now needs to be explicitly downcast to a short because it is not a widening conversion. That leaves many programmers scratching their head!

short x = 1;
short y = 1;
short z = x + y;            // compile-time error
short zz = (short)(x + y);  // no error

Division By Zero on Floating Points

Take a look at the code below. Will a DivisionByZero exception by thrown on line 3?

   1:              double i = 7.5;

   2:              double j = 0;

   3:              Console.WriteLine( i/j );   // will this throw at run-time?

The answer is NO is won't. If the data types were integral it certainly would, by dividing a floating point number by zero results in infinity and no exception!

Bankers Rounding By Default

This is truly bizarre. The Math.Round() function in .NET doesn't really follow the Principle of Least Astonishment. Check this out...

        static void Main()
        {
            Console.WriteLine(Math.Round(-2.5));    // -2
            Console.WriteLine(Math.Round(-1.5));    // -2
            Console.WriteLine(Math.Round(-0.5));    // 0
            Console.WriteLine(Math.Round(0.0));     // 0
            Console.WriteLine(Math.Round(0.5));     // 0
            Console.WriteLine(Math.Round(1.5));     // 2
            Console.WriteLine(Math.Round(2.5));     // 2
        }

Math.Round() uses Bankers' Rounding which is not what most people would expect. To get what you'd think it would do by default you need to do this:

Math.Round(0.5, MidpointRounding.AwayFromZero )

Method Overload Resolution

I originally came across this on Jon Skeet's website, who apparently got it from Ayende. Try and figure out which method is called and what is printed to the console...

   1:          static void Main()

   2:          {

   3:              Foo("Hello");

   4:          }

   5:   

   6:          static void Foo(object x)

   7:          {

   8:              Console.WriteLine("object");

   9:          }

  10:   

  11:          static void Foo<T>(params T[] x)

  12:          {

  13:              Console.WriteLine("params T[]");

  14:          }

It hits the generic Foo(params T[] x) function but why? According to Section 7.4.3 of the C# 3.0 Specification overload resolution works in 2 parts: the first part identifies the set of applicable function members and the second part finds the "better function" match. In this case there are 2 applicable functions with slightly different parameter lists: object x, and params string[] x. Because the second candidate has a parameter list the compiler considers both the "normal form" and the "expanded form". To quote the spec...

"For a function member that includes a parameter array, if the function member is applicable ..., it is said to be applicable in its normal form. If a function member that includes a parameter array is not applicable in its normal form, the function member may instead be applicable in its expanded form. The expanded form is constructed by replacing the parameter array in the function member declaration with zero or more value parameters of the element type of the parameter array such that the number of arguments in the argument list A matches the total number of parameters "

Section 7.4.3.2 of the specification defines the logic for the "better function" and to cut a long story short, it picks (string x) - the expanded form of the parameter array argument list - to be a better argument list match than (object x).

More Method Overloading Intrigue

Look a the code below (shamelessly stolen from Jon Skeet's website) and try and figure out what is printed to the console.

   1:      class Base

   2:      {

   3:          public virtual void DoSomething(int x)

   4:          {

   5:              Console.WriteLine("Base.DoSomething(int)");

   6:          }

   7:      }

   8:   

   9:      class Derived : Base

  10:      {

  11:          public override void DoSomething(int x)

  12:          {

  13:              Console.WriteLine("Derived.DoSomething(int)");

  14:          }

  15:   

  16:          public void DoSomething(object o)

  17:          {

  18:              Console.WriteLine("Derived.DoSomething(object)");

  19:          }

  20:      }

  21:   

  22:      class Test

  23:      {

  24:          static void Main()

  25:          {

  26:              Derived d = new Derived();

  27:              int i = 10;

  28:              d.DoSomething(i);

  29:          }

  30:      }

Jon Skeet explained it best..."Derived.DoSomething(object) is printed - when choosing an overload, if there are any compatible methods declared in a derived class, all signatures declared in the base class are ignored - even if they're overridden in the same derived class!"

Nullable Type Boxing

Saw this one on StackOverflow - original creator was Marc Gravell. Try and guess why a NullReference exception is thrown...

   1:          static void Foo<T>() where T : new()

   2:          {

   3:              T t = new T();

   4:              Console.WriteLine(t.ToString()); // works fine

   5:              Console.WriteLine(t.GetHashCode()); // works fine

   6:              Console.WriteLine(t.Equals(t)); // works fine

   7:   

   8:              // so it looks like an object and smells like an object...

   9:   

  10:              // but this throws a NullReferenceException...

  11:              Console.WriteLine(t.GetType());

  12:          }

  13:   

  14:          static void Main()

  15:          {

  16:              Foo<int?>();

  17:   

  18:          }

Answer: All the methods are overridden, except GetType() which can't be; so it is cast (boxed) to object (and hence to null) to call object.GetType()... which calls on null. Interestingly an empty Nullable boxes to null, not a box that contains an empty Nullable.