Long Method

25 08 2011

The longer a procedure is, the more difficult it is to understand. Lots of long methods often lead to code duplication. By breaking these down into smaller methods you can find ways for logic to be shared. Older languages carried an overhead in subroutine calls, which deterred people from small methods. Modern OO languages have pretty much eliminated that overhead for in-process calls. The real key to making it easy to understand small methods is good naming. If you have a good name for a method you don’t need to look at the body.

You should be much more aggressive about decomposing methods. A guide to follow is that whenever you feel the need to comment something, write a method
instead. Such a method contains the code that was commented but is named after the intention of the code rather than how it does it. You can do this on a group of lines or on as little as a single line of code.





Using the Strategy Pattern to Change Threading at Runtime

21 08 2011

The strategy pattern involves one class delegating some behaviour to a member which meets some interface. By delegating in this way you can change behaviour at runtime by changing the member to some other type from that same inheritance hierarchy. In my OrderMatchingEngine project I found a cool (to me at least) use for this pattern. You can change the behaviour of a component from synchronous, to multithreaded via the ThreadPool to multithreaded via dedicated heavyweight threads and back again as required at runtime.

In my project each OrderBook has an OrderProcessor. There are three types that inherit from OrderProcessor. They are SynchronousOrderProcessor, ThreadPooledOrderProcessor and DedicatedThreadsOrderProcessor. With some careful locking inside the OrderProcessor Property setter and the InserOrder method you can safely switch which type of OrderProcessor is used, committing more resources when and where they are needed.

On receipt of its first order the Market kicks off a timer which fires every second and prioritises the OrderBooks by number of orders received. The top 10% of OrderBooks are assigned dedicated threads, the next 20% use the ThreadPool and the remainder are given synchronous behaviour. In this way the Market can react to peaks of activity during the day and give more performance to those OrderBooks that need it.

namespace OrderMatchingEngine.OrderBook
{
public class SynchronousOrderProcessor : OrderProcessor
    {
        public SynchronousOrderProcessor(BuyOrders buyOrders, SellOrders sellOrders, Trades trades)
            : base(buyOrders, sellOrders, trades)
        {
        }

        public override void InsertOrder(Order order)
        {
            ProcessOrder(order);
        }
    }

    public class ThreadPooledOrderProcessor : OrderProcessor
    {
        public ThreadPooledOrderProcessor(BuyOrders buyOrders, SellOrders sellOrders, Trades trades)
            : base(buyOrders, sellOrders, trades)
        {
        }

        public override void InsertOrder(Order order)
        {
            ThreadPool.QueueUserWorkItem((o) => ProcessOrder(order));
        }
    }
    public class DedicatedThreadOrderProcessor : OrderProcessor
    {
        private readonly Thread m_Thread;
        private readonly BlockingCollection m_PendingOrders = new BlockingCollection();

        public DedicatedThreadOrderProcessor(BuyOrders buyOrders, SellOrders sellOrders, Trades trades)
            : base(buyOrders, sellOrders, trades)
        {
            m_Thread = new Thread(ProcessOrders);
            m_Thread.Start();
        }

        private void ProcessOrders()
        {
            foreach (Order order in m_PendingOrders.GetConsumingEnumerable())
                ProcessOrder(order);
        }

        public void Stop()
        {
            m_PendingOrders.CompleteAdding();
        }

        public override void InsertOrder(Order order)
        {
            m_PendingOrders.Add(order);
        }
    }

    public class OrderBook
    {
        private OrderProcessor m_OrderProcessingStrategy;

        private readonly Object m_Locker = new Object();

        public Instrument Instrument { get; private set; }
        public BuyOrders BuyOrders { get; private set; }
        public SellOrders SellOrders { get; private set; }
        public Trades Trades { get; private set; }
        public Statistics Statistics { get; private set; }

        public OrderProcessor OrderProcessingStrategy
        {
            get { return m_OrderProcessingStrategy; }
            set
            {
                lock (m_Locker)
                {
                    var dedicatedThreadOrderProcessor = m_OrderProcessingStrategy as DedicatedThreadsOrderProcessor;

                    if (dedicatedThreadOrderProcessor != null)
                        dedicatedThreadOrderProcessor.Stop();

                    m_OrderProcessingStrategy = value;
                }
            }
        }

        public OrderBook(Instrument instrument, BuyOrders buyOrders, SellOrders sellOrders, Trades trades,
                         OrderProcessor orderProcessingStrategy)
        {
            if (instrument == null) throw new ArgumentNullException("instrument");
            if (buyOrders == null) throw new ArgumentNullException("buyOrders");
            if (sellOrders == null) throw new ArgumentNullException("sellOrders");
            if (trades == null) throw new ArgumentNullException("trades");
            if (orderProcessingStrategy == null) throw new ArgumentNullException("orderProcessingStrategy");
            if (!(instrument == buyOrders.Instrument && instrument == sellOrders.Instrument))
                throw new ArgumentException("instrument does not match buyOrders and sellOrders instrument");

            Instrument = instrument;
            BuyOrders = buyOrders;
            SellOrders = sellOrders;
            Trades = trades;
            OrderProcessingStrategy = orderProcessingStrategy;
            Statistics = new Statistics();
        }

        public OrderBook(Instrument instrument)
            : this(instrument, new BuyOrders(instrument), new SellOrders(instrument), new Trades(instrument))
        {
        }

        public OrderBook(Instrument instrument, BuyOrders buyOrders, SellOrders sellOrders, Trades trades)
            : this(
                instrument, buyOrders, sellOrders, trades, new SynchronousOrderProcessor(buyOrders, sellOrders, trades))
        {
        }

        public void InsertOrder(Order order)
        {
            if (order == null) throw new ArgumentNullException("order");
            if (order.Instrument != Instrument)
                throw new OrderIsNotForThisBookException();

            OrderReceived();

            //the strategy can change at runtime so lock here and in OrderProcessingStrategy property
            lock (m_Locker)
                OrderProcessingStrategy.InsertOrder(order);
        }

        private void OrderReceived()
        {
            var numOrders = Statistics[Statistics.Stat.NumOrders];
            numOrders++;
        }

        public class OrderIsNotForThisBookException : Exception
        {
        }
    }
}




BlockingCollection

19 08 2011

When you call TryTake on a ConcurrentQueue, ConcurrentBag or ConcurrentStack and the collection is empty you get false. In producer/consumer situations you often use events to wait when a collection is empty and signal when it is not. A blocking collection wraps any collection that implements IProducerConsumerCollectionand provides this wait and signal functionality for you. So when you call TryTake on a BlockingCollection the calling thread blocks until there are items present.

To use BlockingCollection:

1. Instantiate the class, optionally specifying the IProducerConsumerCollectionto wrap and the maximum size (bound) of the collection.

2. Call Add or TryAdd to add elements to the underlying collection.

3. Call Take or TryTake to remove (consume) elements from the underlying collection.

If you call the constructor without passing in a collection, the class will default to instantiating a ConcurrentQueue.

Another way to consume elements is to call GetConsumingEnumerable. This returns a (potentially) infinite sequence that yields elements as they become available. You can force the sequence to end by calling CompleteAdding: this method also prevents further elements from being enqueued.

Here is an example from my OrderMatchingEngine project:

public class DedicatedThreadOrderProcessor : OrderBook.OrderProcessor
{
    private readonly Thread m_Thread;
    private readonly BlockingCollection m_PendingOrders = new BlockingCollection();

    public DedicatedThreadOrderProcessor(BuyOrders buyOrders, SellOrders sellOrders, Trades trades)
        : base(buyOrders, sellOrders, trades)
    {
        m_Thread = new Thread(ProcessOrders);
        m_Thread.Start();
    }

    private void ProcessOrders()
    {
        foreach (var order in m_PendingOrders.GetConsumingEnumerable())
        {
            ProcessOrder(order);
        }
    }

    public void Stop()
    {
        this.m_PendingOrders.CompleteAdding();
    }

    public override void InsertOrder(Order order)
    {
        m_PendingOrders.Add(order);
    }

}




How Does the ThreadPool’s Minimum Thread Count Work?

17 08 2011

ThreadPool threads are created only on demand, increasing the minimum thread count to x does not mean that x threads are created straight away. Rather, it instructs the pool manager to create up to x threads the instant they are required.

The base strategy of the ThreadPool manager is to create the same number of threads as there are cores, if the queue remains stationary for more than half a second the pool manager responds by creating more threads – one every half-second – up to the capacity of the ThreadPool. This helps to prevent a brief burst of short-lived activity by fully allocating threads and suddenly swelling an application’s memory footprint. Where your tasks block on something e.g. a database query to return, it can be useful to avoid this half second delay.

You can tell the pool manager not to delay in the allocation of the first x threads, by calling SetMinThreads, for instance:

ThreadPool.SetMinThreads (50, 50);

The second value indicates how many threads to assign to I/O completion ports.





Thread Priority

14 08 2011

A thread’s Priority property determines how much execution time it gets relative to other active threads in the operating system. The options are:

enum ThreadPriority { Lowest, BelowNormal, Normal, AboveNormal, Highest }

This becomes relevant only when multiple threads are simultaneously active. Raising a thread’s priority can lead to problems such as resource starvation for other threads. A thread’s priority is throttled by the application’s process priority. To perform real-time work, you must also elevate the process priority using the Process class in System.Diagnostics:

using (Process p = Process.GetCurrentProcess()) 
    p.PriorityClass = ProcessPriorityClass.High;

The top ProcessPriorityClass is Realtime. Setting a process priority to Realtime instructs the OS that you’re process should never yield CPU time to another. If your program enters an accidental infinite loop, you can find that the power button is your only option! For this reason, High is usually the best choice for real-time applications.





How Big-O Analysis Works

11 08 2011

In big-O analysis, input size is assumed to be n. For example n can represent the number of elements in an array. In other problems, n may represent the number of nodes in a linked list, or the number of bits in a data type, or the number of entries in a hash table, and so on. After figuring out what n means in terms of the input, you have to determine how many times the n input items are “examined” in terms of n.  An examination might be something like adding  or comparing an input value to a constant.

When n input items are each examined once the result is n examinations. This is considered O(n), usually referred to as linear time: The time required to run the algorithm increases linearly with the number of input items.

Big-O analysis yields the asymptotic running time, the limit of the running time as n gets very large so you eliminate all but the highest-order term, the term that is largest as n gets very large. So something like O(n + 2) would actually be O(n) because the difference between n and n+2 is so tiny when n is very large.

The fastest-possible running time for any run-time analysis is O(1), commonly referred to as constant running time. An algorithm with constant running time always takes the same amount of time to execute, regardless of the input size.





Duplicated Code

9 08 2011

Duplicated code is the smelliest of code smells and the most pervasive. It can be present in explicit or subtle form. Explicit duplication is present where identical code (copy and paste style) is found. Subtle duplication is found where structures or processing steps exist that appear different but are essentially the same.

The simplest duplicated code problem is when you have the same expression in two methods of the same class. Then all you have to do is Extract Method and invoke the code from both places. More complex examples exist such as duplicate processing logic simply because types have different interfaces, duplicate code in constructors, algorithms that are the same except for an object creation step. In these cases refactorings like Chain Constructors, Introduce Polymorphic Creation with Factory Method and Unify Interfaces with Adapter can help you stay DRY (don’t repeat yourself).