Software engineers usually try to make software that does things as quickly as possible. But occasionally we need to limit the rate at which we perform some action. For example, if we’re building a web crawler, we might rein it in so it doesn’t overwhelm a server with rapid-fire HTTP requests.

Sometimes we can get away with just slowing things down by introducing a delay. Have you ever written code like this?

for (var i = 0; i < 1000; i++)
{
    PerformAction();
    Thread.Sleep(500);
}

A delay between action executions is the simplest form of rate limiting, but it’s not very precise. The delay time is based on an estimate of how long the action will take to execute. If the action takes less time than estimated, then we might exceed the rate limit. Or if the action takes more time than estimated, then we might limit performance more than we need to. If the action is very complicated, we may not be able to easily estimate how long it will take. And how would this work if the action is being performed in parallel by multiple threads?

If we need a more precise rate control method, then we could try to limit the number of times we execute the action within distinct windows of time. We count the number of executions until we reach the limit, and then we don’t allow any more until the count is reset to zero at the end of the time window. For example, suppose we’re aiming for a rate limit of 2 per second. The algorithm would allow only two executions between 0.0 and 1.0 seconds, two more between 1.0 and 2.0 seconds, and so on. This algorithm is effective at controlling the average rate, but it allows for bursts up to two times the rate limit. Using the parameters above, it would allow action executions at 0.8, 0.9, 1.1, and 1.2 seconds, which is 4 occurrences in less than half a second!

Yet another possible method is to use a rate limiting algorithm like the Leaky Bucket. Fortunately these aren’t terribly difficult to implement. But, like the algorithm above, they’re really designed for average rate limiting. They usually allow the rate limit to be exceeded for short bursts.

So what would we want of a better rate limiting method? Well, we would want it to limit the number of occurrences N of an action within any time period of length M (i.e. no bursts allowed). It would allow our code to perform as close to the rate limit as possible without exceeding it. And it would be able to enforce the rate limit whether the action is performed in a single thread or by multiple threads in parallel.

The Rate Limited Pizzeria

Suppose we’re in charge of making pizzas at a pizzeria and we have a pizza oven that can hold 6 pizzas at once. The pizza maker assembles the pizzas and then places them in the oven to bake. After each pizza bakes for exactly 30 minutes, another person removes it from the oven, slices it, and boxes it for delivery.

Each pizza that we place in the oven uses one unit of the oven’s capacity for exactly 30 minutes. It’s not possible to place more than 6 pizzas in the oven in any 30 minute period. In more academic terms, a system with processing capacity N that processes each item in time M has a maximum processing rate of N/M.

Note that the baking time and oven capacity still limit the rate at which pizzas can be placed in the oven even if more than one pizza maker is making the pizzas. When the oven is full, the pizza makers will have to wait in line to place their pizzas in the oven.

Building the RateGate

Using the pizzeria model, if we can create a software object that behaves like the pizza oven and then require that we “place a pizza in the oven” before performing an action, then we effectively limit the rate at which we perform the action. We’ll call this object a RateGate because we’ll have to “pass through” it before we perform the action that we want to rate limit.

Code that requires rate control will configure a RateGate instance, specifying the rate limit by number of occurrences and duration of the time period. Before performing the action, the code will call RateGate.WaitToProceed() which will block the current thread until the action is allowed to occur. Calling WaitToProceed() is like trying to add a pizza to the oven; if the oven is full (i.e. we have hit our rate limit), then the caller will have to wait until a pizza is removed from the oven. For example, the following code calls PerformAction() 1,000 times at a rate of at most 2 times per second:

// Create a RateGate that allows 2 occurrences per second.
using (var rateGate = new RateGate(2, TimeSpan.FromSeconds(1)))
{
    for (var i = 0; i < 1000; i++)
    {
        rateGate.WaitToProceed();
        PerformAction();
    }
}

As you can see, the RateGate is very simple to use. Let’s take a peek inside to see how it works.

The RateGate contains a counting semaphore that acts like the pizza oven. When a thread calls WaitToProceed(), it will have to wait in line until the semaphore value is less than the count (just like waiting until the number of pizzas in the oven is less than the oven’s capacity). It can then enter the semaphore (i.e. place a pizza in the oven) and proceed with the action. For our RateGate implementation in .NET 4.0, we’ll use a SemaphoreSlim as our counting semaphore. In previous versions of .NET, we could use a regular old Semaphore.

At some point we’ll need to exit the semaphore (i.e. take a pizza out of the oven). Before exiting WaitToProceed(), we compute the time when this should occur and add it to a queue. A queue is convenient because the next semaphore exit time can always be found at the front of the queue.

How do we then exit the semaphore at the time that we computed? We can’t depend on the thread that entered the semaphore to do it; that thread has moved on to other things like performing the action that we’re rate limiting. Instead we’ll take care of this in a separate management thread. Here’s how it works:

We have to ensure that our queue is thread safe because multiple threads may try to add semaphore exit times to the queue concurrently. And the management thread may also be simultaneously removing exit times. In .NET 4.0, we’ll use a ConcurrentQueue<int>, which will handle all of the synchronization internally. In previous versions of .NET, we could use a Queue<int>, but we would have to implement our own thread synchronization.

The RateGate is obviously very time dependent, so we need to be careful how we measure time. The system clock has a resolution of around 16ms, which should be more than sufficient for general rate limiting; there’s no need to use a high resolution timer. We could try to use the current system time but we can’t depend on it to be consistent, even if we avoid daylight saving time by using UTC. The system time could still be changed by a user, or it could be adjusted automatically when synchronizing with an external time source. A better clock for our purposes is System.Environment.TickCount, which gives us the number of milliseconds since the computer started. We just have to be careful because this value is stored as a 32-bit signed integer. The value starts at zero and increases for around 24.9 days until it wraps from Int32.MaxValue (2,147,483,647) to Int32.MinValue (-2,147,483,648). Then it continues increasing until it gets back to Int32.MaxValue. It’s easy enough to account for this value wrapping by using unchecked arithmetic to compute differences between time values. The downside is that we won’t be able to handle any time periods greater than around 49.8 days. But that should be okay; we’re not really looking to limit the number of occurrences over a period that long.

That covers the general idea behind the RateGate. Please check out the source code (.NET 4.0) for additional details. There are plenty of code comments that explain the “why” and “how”.

Rate Limiting a Loop

As a simple example, let’s use the code above that limits calls to PerformAction() to two per second. We’ll simulate PerformAction() by sleeping for 250ms and we’ll record its start and end times. The results with and without rate limiting are below. Notice the delay introduced by the RateGate that keeps the rate below the limit.

Executing 10 times with no rate limiting:
Iteration   Start   Finish
       1       0      249
       2     250      500
       3     500      750
       4     751     1000
       5    1000     1250
       6    1250     1500
       7    1501     1750
       8    1750     2015
       9    2016     2265
      10    2266     2515

Executing 10 times with a rate limit of 2 per second:
Iteration   Start   Finish
       1      17      266
       2     266      516
       3    1012     1262
       4    1273     1523
       5    2022     2272
       6    2287     2537
       7    3036     3286
       8    3301     3551
       9    4050     4300
      10    4315     4565

Rate Limiting LINQ

Another relatively simple application would be using a RateGate to limit the rate at which a LINQ query is processed through an IEnumerable extension method:

public static IEnumerable<T> LimitRate<T>(this IEnumerable<T> sequence, int items, TimeSpan timePeriod)
{
    using (var rateGate = new RateGate(items, timePeriod))
    {
        foreach (var item in sequence)
        {
            rateGate.WaitToProceed();
            yield return item;
        }
    }
}

We can then use this extension method to limit the rate at which a sequence is enumerated:

var stopwatch = new Stopwatch();
var sequence = Enumerable.Range(1, 20);
stopwatch.Start();
// Limit the rate of processing the sequence to 5 items per second.
foreach (var number in sequence.LimitRate(5, TimeSpan.FromSeconds(1)))
    Console.WriteLine("{0,4} {1,6}", number, stopwatch.ElapsedMilliseconds);

Enumerating sequence with rate limit of 5 items per second:
   1     14
   2     33
   3     34
   4     34
   5     34
   6   1026
   7   1029
   8   1029
   9   1029
  10   1029
  11   2040
  12   2040
  13   2040
  14   2040
  15   2040
  16   3058
  17   3058
  18   3058
  19   3058
  20   3059

Be careful, though, if using this extension method in a PLINQ query. PLINQ can use a chunking strategy in which it pulls a chunk of items from the sequence before distributing the items for parallel processing. In the code below, suppose PLINQ starts by pulling a chunk of 50 items from the sequence. That part of the processing will be rate limited, taking around 10 seconds to complete. Then PLINQ will start calling PerformAction() for the items that it pulled from the sequence. The calls to PerformAction() will likely be executed in multiple threads, and without any rate limiting at all!

// Warning: Might not work as expected!
using (var rateGate = new RateGate(5, TimeSpan.FromSeconds(1)))
{
    Enumerable.Range(1, 1000)
        .LimitRate(rateGate)
        .AsParallel()
        .ForAll(x => PerformAction(x));
}

Rate Limiting and Concurrency

As a final example, let’s use a RateGate to rate limit across multiple threads. We’ll use the Task Parallel Library to execute the rate limited action:

// Create a RateGate that allows 2 occurrences per second.
using (var rateGate = new RateGate(2, TimeSpan.FromSeconds(1)))
{
    Parallel.For(0, 10, i =>
                            {
                                rateGate.WaitToProceed();
                                PerformAction();
                            });
}

The TPL performs the processing out of sequence and introduces some delays, but the RateGate still limits the rate at which the items are processed.

Executing 10 times with no rate limiting:
Iteration   Start   Finish
       1      50      299
       6      61      311
       2      66      316
       3     300      550
       7     317      567
       5     317      567
       4     550      800
       8     567      817
       9     568      817
      10     817     1067

Executing 10 times with a rate limit of 2 per second:
Iteration   Start   Finish
       6       5      255
       1       7      257
       2    1980     2229
       7    1980     2230
       3    2987     3237
      10    2987     3237
       5    4001     4251
       4    4001     4251
       8    5015     5265
       9    5266     5515

Download the Code

I hope you find the RateGate interesting and/or useful! You can grab the .NET 4.0 source code here. Please leave a comment if you have suggestions for improvements or if you find a neat use for it. Cheers!

Why Multicast?

SQL Server Integration Services (SSIS) includes a very useful data transformation called “Multicast”. If you’re not familiar with SSIS, it allows you to build (among other things) Data Flow Tasks in which data rows “flow” from one or more sources, through one or more transformations, to one or more destinations. For example, you could copy rows from one source table to two destination tables by building a Data Flow Task that looks something like this:

The Multicast Transform creates copies of each row it receives from the upstream component and distributes one copy to each downstream component. Multicasting is very important in SSIS because it allows us to avoid executing expensive upstream components multiple times in order to feed the same rows to multiple downstream components.

What if we have a similar situation in .NET? Say we have an IEnumerable<float> and we want to compute the minimum, maximum, and average of all values in the sequence. We could use the Min, Max, and Average standard query operators like this:

var min = sequence.Min();
var max = sequence.Max();
var average = sequence.Average();

But this code will make three separate passes through the sequence to compute the three aggregates. If enumerating the sequence were expensive, then we might not want to do it three times. Wouldn’t it be great if we had some way to get the same results with only one pass?

Jon Skeet and Marc Gravell have developed one solution that they call “Push” LINQ. In “Push” LINQ, you configure multiple aggregators for use with a single DataProducer object and then tell the DataProducer to “push” the elements of the sequence to all of the aggregators. Jon Skeet has also figured out a different solution using the Reactive Extensions for .NET. These are fine solutions, but they require custom-built query operators; you can’t just use standard query operators.

Building Multicast in .NET 4.0

It would be nice to have an IEnumerable<T> extension method that applies multiple aggregators but enumerates the sequence only once. Maybe we could pass the aggregators to this method using lambda expressions and get the results back in a Tuple. Then we could write code like this:

var tuple = sequence.Multicast(a => a.Min(), b => b.Max(), c => c.Average());
var min = tuple.Item1;
var max = tuple.Item2;
var average = tuple.Item3;

The syntax is a bit clumsy, but it’s workable given the potential performance benefits. Let’s try to create this extension method for just two aggregators:

public static Tuple<T1, T2> Multicast<T, T1, T2>(
    this IEnumerable<T> sequence, 
    Func<IEnumerable<T>, T1> aggregator1, 
    Func<IEnumerable<T>, T2> aggregator2)

First we have to figure out how the two aggregators can pull from the IEnumerable<T> sequence at the same time. How about running each aggregator in its own thread? We don’t want to create a lot of threads, but one for each aggregator doesn’t seem too bad. We’ll spin up a separate thread for each aggregator and then use a System.Threading.CountdownEvent object to block the main thread until the aggregator threads end.

public static Tuple<T1, T2> Multicast<T, T1, T2>(
    this IEnumerable<T> sequence, 
    Func<IEnumerable<T>, T1> aggregator1, 
    Func<IEnumerable<T>, T2> aggregator2)
{
    // Assign default values for the results.
    var result1 = default(T1);
    var result2 = default(T2);
            
    // Invoke each of the aggregators.
    InvokeAll(new Action[] { () => result1 = aggregator1.Invoke(sequence),
                             () => result2 = aggregator2.Invoke(sequence)
                           });

    // Return the aggregator results in a Tuple.
    return new Tuple<T1, T2>(result1, result2);
}

private static void InvokeAll(Action[] actions)
{
    var actionCount = actions.Length;

    // Create the CountdownEvent that will let us wait until all of the
    // action threads end.
    var countdownEvent = new CountdownEvent(actionCount);
            
    // Start the action threads.
    for (var i = 0; i < actionCount; i++)
    {
        // Grab a reference to the current action so we're not accessing a
        // modified closure in the thread delegate below.
        var action = actions[i];

        new Thread(() =>
            {
                // Invoke the action.
                action.Invoke();
                // Signal the CountdownEvent that we're done.
                countdownEvent.Signal();
            }).Start();
    }

    // Wait for the actions threads to end.
    countdownEvent.Wait();
}

Within its own thread, each aggregator will call GetEnumerator() on the the IEnumerable<T> sequence and will receive its own instance of the enumerator. Because each aggregator has its own enumerator instance, we’re still going to be traversing the sequence twice, but now we’re doing so in parallel. Hmmm, that’s not much of an improvement. In fact, it’s could be worse than enumerating the sequence in series. We can take another step in the right direction if both aggregators were to receive the same enumerator instance when they call GetEnumerator(). We can use a custom IEnumerable<T> that wraps the original sequence and have it always give out the same enumerator singleton. Easy enough.

Now suppose that both aggregators get the same enumerator instance when they call GetEnumerator(). Then they’re going to start iterating the sequence using MoveNext(). We could have some concurrency problems. In one case, the aggregators make alternating calls to MoveNext() and the get_Current() accessor. As a result, each aggregator processes only a subset of the elements of the sequence:

In another case, both aggregators call MoveNext() and then both call get_Current(). The two aggregators will receive the same sequence element, but another element will have been skipped entirely:

We need to ensure that the aggregators each process all of the elements in the sequence, and we can do that by having them iterate the sequence in lockstep. That is, we wait until both aggregators call MoveNext() before actually moving to the next element of the sequence. To accomplish this, we’ll need a custom IEnumerator<T>, and we’ll need to somehow make the threads wait until all of the aggregators have called MoveNext(). This is where the new System.Threading.Barrier class in .NET 4.0 comes in.

A Barrier object allows multiple threads to process an algorithm concurrently, but in phases. First we tell Barrier how many threads we have. When each thread completes processing for the current phase, it calls Barrier.SignalAndWait() which blocks the thread until all of the threads have called SignalAndWait(). In our situation, a phase will consist of each aggregate calling MoveNext(), then calling get_Current(), and then processing the item.

We will build an enumerator, LockstepEnumerator<T>, that will use a Barrier object internally. When LockstepEnumerator<T>.MoveNext() is called, it will call Barrier.SignalAndWait(). The Barrier object will wait until all enumerator threads have signaled and then invoke a post-phase delegate which calls MoveNext() on the underlying enumerator. Then LockstepEnumerator<T>.MoveNext() will return the result of the underlying MoveNext() call.

public class LockstepEnumerator<T> : IEnumerator<T>
{
    private readonly IEnumerator<T> _Enumerator;
    private readonly Barrier _Barrier;
    private bool _MoveNextResult;

    public LockstepEnumerator(IEnumerator<T> enumerator, int degree)
    {
        // Check the arguments.
        if (enumerator == null)
            throw new ArgumentNullException("enumerator");
        if (degree <= 0)
            throw new ArgumentOutOfRangeException("degree", "Degree must be a positive integer.");

        _Enumerator = enumerator;

        // Create a Barrier with the given degree as the participant count 
        // and give it a post-phase action that will call MoveNext() on 
        // the enumerator.
        _Barrier = new Barrier(degree, x => _MoveNextResult = _Enumerator.MoveNext());
    }

    public T Current
    {
        get { return _Enumerator.Current; }
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    public void Dispose()
    {
        _Barrier.Dispose();
        _Enumerator.Dispose();
    }

    public bool MoveNext()
    {
        // Signal the Barrier and block the current thread.
        _Barrier.SignalAndWait();

        // The Barrier's post-phase action will have executed before 
        // SignalAndWait unblocks, so return the result of that action 
        // calling MoveNext() on the underlying sequence.
        return _MoveNextResult;
    }

    public void Reset()
    {
        // Doesn't make sense to allow reset with multiple threads 
        // using this enumerator.
        throw new NotSupportedException();
    }    
}

The entire sequence for one phase looks like this:

We still need a custom IEnumerable<T> that will hand out a singleton instance of LockstepEnumerator<T> when GetEnumerator() is called. We’ll call it LockstepEnumerable<T>, and have it wrap the original IEnumerable<T>.

public class LockstepEnumerable<T> : IEnumerable<T>
{
    // Lazy that will create the enumerator when requested.
    private readonly Lazy<IEnumerator<T>> _Enumerator;

    public LockstepEnumerable(IEnumerable<T> sequence, int degree)
    {
        // Check the arguments.
        if (sequence == null)
            throw new ArgumentNullException("sequence");
        if (degree <= 0)
            throw new ArgumentOutOfRangeException("degree", "Degree must be a positive integer");
            
        // Create the Lazy that will create the LockstepEnumerator wrapping 
        // the sequence enumerator.
        _Enumerator = new Lazy<IEnumerator<T>>(() => new LockstepEnumerator<T>(sequence.GetEnumerator(), degree));
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _Enumerator.Value;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Finally, we have to modify our Multicast extension method so that it wraps the sequence in a LockstepEnumerable<T>:

public static Tuple<T1, T2> Multicast<T, T1, T2>(
    this IEnumerable<T> sequence, Func<IEnumerable<T>, T1> aggregator1, 
    Func<IEnumerable<T>, T2> aggregator2)
{
    // Assign default values for the results.
    var result1 = default(T1);
    var result2 = default(T2);

    var multicastSequence = new LockstepEnumerable<T>(sequence, 2);

    InvokeAll(new Action[] { 
                () => result1 = aggregator1.Invoke(multicastSequence),
                () => result2 = aggregator2.Invoke(multicastSequence)
            });

    return Tuple.Create(result1, result2);
}

And, voilà! We can multicast.

Multicast Performance

Let’s see our Multicast method in action. To demonstrate its performance characteristics, I started with two sequences: an “expensive” sequence and a “normal” sequence, each containing 1,000 integers. I simulated “expensive” by making the thread sleep for 10ms each time MoveNext() is called. I applied the Min, Max, and Average aggregates to these sequences both with and without Multicast. The mean results for several trials are:

The results for the “expensive” sequence clearly show the advantages of our Multicast method when applying multiple aggregators. In this scenario, the time saved by making only one pass through the sequence far outweighs the time spent in the aggregators and the overhead of parallel execution. For the “normal” sequence, the opposite is true; it’s far more efficient to make three passes than to incur the overhead of multicasting.

This Multicast extension method isn’t a silver bullet. It’s really only good for situations where (1) you’re applying aggregate query operators to an expensive sequence, (2) you don’t want to persist the sequence or it would be too expensive to do so, and (3) you don’t mind spinning up threads. For those situations, though, the performance improvement can be very significant.

You can download a VS.NET project containing code for the Multicast extension method and performance tests here. The code includes overloads of the Multicast method supporting up to seven aggregators.

This is the third and final post in a series covering rounding in .NET. In Part 1, we learned that the Math.Round method’s default rounding algorithm probably isn’t what we would expect, which led to a few more questions about rounding in general. In Part 2, we covered all kinds of different rounding methods and how they can be implemented in C#. Here in Part 3, we’ll wrap things up by looking at some specific rounding scenarios and determining which algorithms are most appropriate in those situations.

As before, to remove a bit of complexity, we’ll assume that “rounding” means “rounding to an integer”. Once you can round to an integer, it’s easy to round to arbitrary precision.

Rounding Individual Values

The rounding operation simply exchanges a number with an approximation of its value. The difference between that approximation and the original value is called rounding error. Rounding error can be difficult to nail down because it depends on both the fraction part of the number and the rounding method used. Fortunately it’s fairly straightforward to establish a range and an average for the rounding error when rounding a single value. Then you can often use those results to establish ranges and averages for rounding multiple values.

The table below contains the rounding error ranges and averages for the rounding methods we’ve been working with. You’ll notice that I’ve included specific cases for positive and negative numbers for the Round Toward Zero and Round Away from Zero methods. If you know something about the numbers you’re rounding, then you can often be more specific about rounding error. For example, suppose you know that a value is the result of dividing an integer by 2 and therefore has a fraction part of 0.0 or 0.5. Then Round Ceiling will always leave the value unchanged or will increase it by exactly 0.5.

We can reach some useful general conclusions just by examining the rounding error ranges for the various rounding methods. For example, if you’re looking to minimize the overall rounding error for an arbitrary number, then Round to Nearest is the best choice and you probably want to steer clear of Round Dither. And Round Ceiling will increase the value of an arbitrary number by 0.5 on average and will never decrease the value, so count on it shifting your values toward positive infinity.

Cumulative Rounding Error

One of the most famous examples of rounding error is an index that was created in 1982 for the Vancouver Stock Exchange (VSE). The index was assigned a value of 1,000.000 at its inception, but after 22 months the value of the index had fallen to 524.881 with no general downturn in economic activity. Something was wrong. The index value was updated after each stock trade. Rather than recompute the entire index value at each update, the developers who implemented the calculation decided to adjust the value based on the difference in price of the traded stock. After adjusting the index value, they would truncate the result to three decimal places. This truncation caused the index value to lose up to 0.001 points (average 0.0005 points) each time a stock was traded, on average 2,800 times per day. And the rounding error accumulated with every trade. After discovering the error and recomputing the index value (probably using some variation of Round to Nearest), the “true” value was found to be 1098.892.

What happened with the VSE index is an example of cumulative rounding error. When rounding is performed after each step of a long running computation, the result has a cumulative error that is the sum of the rounding error at each step.

Let’s run a simulation of the VSE index with various rounding algorithms. We’ll start with a value of 1,000.000. At each step, we’ll adjust the index value by a delta taken from a random Gaussian distribution with mean 0.000 and standard deviation 0.08333, which should reasonably simulate small stock price fluctuations. Then we’ll run this simulation for 1,232,000 steps (2,800 trades per day x 20 days per month x 22 months). The results are plotted below:

The black line represents several overlapping data sets: no rounding, all of the Round to Nearest methods, and Round Dither. There was some variation among the results for these methods, but they performed similarly. The blue line represents Round Ceiling and Round Away from Zero. The green line represents Round Floor and Round Toward Zero. Clearly Round Ceiling, Round Floor, Round Away from Zero, and Round Toward Zero would be poor choices for this scenario. Round Floor and Round Toward Zero are both equivalent to truncation for the values involved in this simulation, and the results are consistent with what happened in real life.

If we were to extend the simulation beyond 22 months, the Round Ceiling and Round Away from Zero values will continue to grow and the Round Floor values will continue toward negative infinity. Once the cumulative result becomes negative, however, Round Toward Zero will tend to drive the value to zero rather than making it more negative.

Because they have an overall mean rounding error of 0.0, Round to Nearest and Round Dither would be reasonable choices for this scenario. Round to Nearest with any tie-breaking rule would probably be the best choice because its rounding error range is smaller. Again, if your data set has properties you can count on, like every pre-rounding value has a fraction part of 0.0 or 0.5, then you’ll need to pay more attention to this choice.

Sample Sets

If we round every value in a set, then we may end up altering characteristics of the set as a whole. We see this in statistical sample sets, where rounding the samples can change the values of statistical measures of the set.

Say we’re looking at the arithmetic mean of a sample set. If we adjust each value by some δ, then the arithmetic mean (μ) will also change by exactly δ:

Suppose we round each value in an arbitrary sample set using Round to Nearest. Each value would change by some δ in the range (-0.5, 0.5), which makes the error range for the arithmetic mean (-0.5, 0.5) as well.

Let’s see an example. We’ll start with a random Gaussian distribution of 1 million values in the interval [0,100], each with a precision of 1/10. We’ll apply each of rounding methods to that set. Take a look at this histogram showing some of the results:

The rounding methods that are not included are duplicates. Rounding caused values to shift, and that caused variation in the number of samples in each interval. How did it affect our statistical measures?

Round Ceiling, Round Floor, Round Away from Zero, and Round Toward Zero are probably unacceptable choices for this scenario. They each changed the mean value of our sample set by nearly 1%, which could have significant impact on any statistical results gleaned from the rounded set.

The Round to Nearest methods performed reasonably well, but there’s an inherent bias in half of the tie-breaking rules that shows up in the rounded results. Approximately 10% of the values in our random sample set had a fraction part of 0.5 and thus were subject to the tie-breaking rule. Round Half Away from Zero, Round Half Toward Zero, Round Half Toward Positive Infinity, and Round Half Toward Negative Infinity all had a significantly larger effect on the sample set than the other tie-breaking rules.

Round Dither had essentially no effect on the arithmetic mean of the set, but it changed the standard deviation more than any other method.

For the sample set rounding scenario, four rounding methods appear to be superior: Round to Nearest with Round Half to Even, Round to Nearest with Round Half to Odd, Round to Nearest with Round Half Randomly, and Round to Nearest with Round Half Alternatingly. That makes sense because Round to Nearest has the smallest general rounding error range and these tie-breaking rules are designed to eliminate bias.

Quantization

Quantization is the process of approximating a continuous range of values (or a very large set of possible discrete values) by a relatively small (usually finite) set of discrete values. This essentially amounts to rounding each sample value to one of the discrete range values. Perhaps the most common use for quantization is in performing analog-to-digital conversion for signals. Audio signals, for instance. The problem is that this process can often change psychometric characteristics of the original signal. Listeners are sensitive to distortion in the signal, so we have to be careful that quantization doesn’t introduce distortion that they will find unacceptable. We need to apply a method of rounding that preserves the essential characteristics of the signal. Let’s look at an example of a smooth analog signal quantized using Round to Nearest:

The approximation looks reasonable, but the stair-step result would sound significantly different than the smoothly increasing curve if this were an audio signal. All of the other rounding methods produce the same kind of stair-step result. Take a look at the results with Round Dither, though:

This doesn’t look all that different from the Round to Nearest stair steps, and it seems like this would be a poor choice with all of those jumps between values. But to the human ear, this is going to sound a lot closer to the original analog signal. For analog signal quantization, Round Dither is the clear choice.

Conclusion

We’ve covered a great deal in this series, but there are other rounding methods and lots of other scenarios to consider. Ultimately you just need to be very careful with rounding. When you round a number, you change its value, and that can have significant effects in your system that can sometimes be difficult to predict.

The best advice is to avoid rounding, or at least round as little as possible. Perform rounding as late as you can in a calculation, and preferably round only the final result. Keep an eye on the context of your problem; look at what values you are rounding and think about the results of rounding those values. Figure out how rounding error will affect your system. And if you care about accuracy, be sure to check your results carefully and impose correctness control (like unit tests) around all critical rounded calculations.

If you’re interested in the code for the example scenarios (which uses the C# rounding implementations from Part 2), you can download the project here. The random Gaussian distributions were easy to generate thanks to Math.NET Iridium, part of the excellent Math.NET Project.

• Part 1: The Mystery of Math.Round
  The Math.Round method isn’t as straightforward as one might expect.
• Part 2: Exotic Rounding Algorithms
  A menagerie of lesser-known rounding methods, with implementations in C#.
• Part 3: Rounding in Action
  Why some rounding algorithms are better than others in certain situations.

This is the second in a series of three blog posts covering rounding in .NET. In Part 1, we learned that the Math.Round method’s default rounding algorithm probably isn’t what we would expect, which led to many more questions about rounding in general. In Part 2, we’ll try to answer some of those questions by taking a look at some different rounding methods and how they can be implemented in C#.

For the rest of this discussion, let’s assume that “rounding” means “rounding to an integer”. Once you know how to round to an integer, you can round to any precision by multiplying by a factor, rounding to an integer, and then multiplying by the inverse of the factor.

We’ll break the rounding methods into four groups: Round to Nearest (with its many tie breaking rules), Round Ceiling/Floor, Round Toward Zero/Away from Zero, and Round Dither.

Round to Nearest

The most common rounding algorithm, Round to Nearest simply tries to round to the nearest integer value. If the fraction part of the number is less than 0.5, then the result is the next lower integer value. If the fraction part of the number is greater than 0.5, then the result is the next greater integer value. But what if the fraction part of the number is 0.5, equidistant from the two surrounding integers? In that case, we have to apply some kind of tie breaking rule, and there are at least eight rules from which to choose!

The most commonly used tie breaking rule, and rounding method in general, is Round Half Away from Zero, also known as Conventional Rounding or Symmetric Arithmetic Rounding. Rounding a fraction part of 0.5 results in the nearest integer that is further from zero. For example, suppose we’re rounding 1.5. The nearest integers are 1.0 and 2.0, so the result would be 2.0 because it’s further from zero. Similarly, -1.5 would round to -2.0.

One way to round a positive number with Round Half Away from Zero is to add 0.5 and then truncate the result. To round a negative number, subtract 0.5 and truncate:

public static int RoundToNearestRoundHalfAwayFromZero(decimal value)
{
    // Add or subtract 0.5 depending on whether the value is positive 
    // or negative, and truncate the result.
    return (int)(value + 0.5m * Math.Sign(value));
}

The opposite of Round Half Away from Zero is Round Half Toward Zero. This tie breaking rule rounds a fraction part of 0.5 to the nearest integer that is closer to zero. For example, 1.5 would round to 1.0 and -1.5 would round to -1.0.

To round a positive number using this rule, subtract 0.5 and find the next greater integer. To round a negative number, add 0.5 and find the next lower integer:

public static int RoundToNearestRoundHalfTowardZero(decimal value)
{
    // If value is non-negative, subtract 0.5 and take the next 
    // greater integer. If value is negative, add 0.5 and take the 
    // next lower integer.
    if (value >= 0)
        return (int)Math.Ceiling(value - 0.5m);
    else
        return (int)Math.Floor(value + 0.5m);
}

Instead of rounding toward or away from zero, we could round toward positive or negative infinity instead. The Round Half Toward Positive Infinity tie breaking rule specifies that we round a fraction part of 0.5 to the next greater integer. For example, 1.5 would round to 2.0 and -1.5 would round to -1.0.

To round to nearest while always rounding a fraction part of 0.5 to the next greater integer, we simply add 0.5 to the number and then find the next lower integer:

public static int RoundToNearestRoundHalfTowardPositiveInfinity(decimal value)
{
    // Add 0.5 and take the next lower integer.
    return (int)Math.Floor(value + 0.5m);
}

The opposite of Round Half Toward Positive Infinity would be the Round Half Toward Negative Infinity rule, which instead rounds a fraction part of 0.5 to the next lower integer. For example, 1.5 rounds to 1.0 and -1.5 rounds to -2.0.

To round to nearest while taking a fraction part of 0.5 to the next lower integer, we subtract 0.5 from the number and find the next greater integer:

public static int RoundToNearestRoundHalfTowardNegativeInfinity(decimal value)
{
    // Subtract 0.5 and take the next greater integer.
    return (int)Math.Ceiling(value - 0.5m);
}

Another very common tie breaking rule (and, as we discovered in Part 1, the default for .NET’s Math.Round method) is Round Half to Even or Banker’s Rounding. As the name suggests, we round a fraction part of 0.5 to the nearest even integer. For example, 1.5 and 2.5 both round to 2.0 and -1.5 and -2.5 both round to -2.0.

One way to implement Round Half to Even is by first applying Round Half Toward Positive Infinity. If the result is even, we’re done. Otherwise, we subtract one. If we apply this algorithm to the value 2.5, we first round to 3.0 and then, because 3.0 is not even, we subtract one giving 2.0:

public static int RoundToNearestRoundHalfToEven(decimal value)
{
    // First round half toward positive infinity. Then if the fraction
    // part of the original value is 0.5 and the result of rounding is
    // odd, then subtract one.
    var temp = (int)Math.Floor(value + 0.5m);
    if (value - Math.Floor(value) == 0.5m && temp % 2 != 0)
        temp -= 1;
    return temp;
}

Why round to the nearest even integer, though? The Round Half to Odd rule rounds a fraction part of 0.5 to the nearest odd integer instead. For example, 1.5 rounds to 1.0, 2.5 rounds to 3.0, -1.5 rounds to -1.0, and -2.5 rounds to -3.0. The C# implementation is nearly identical to Round Half to Even:

public static int RoundToNearestRoundHalfToOdd(decimal value)
{
    // First round half toward positive infinity. Then if the fraction
    // part of the original value is 0.5 and the result of rounding is 
    // even, then subtract one.
    var temp = (int)Math.Floor(value + 0.5m);
    if (value - Math.Floor(value) == 0.5m && temp % 2 == 0)
        temp -= 1;
    return temp;
}

All of the above tie breaking rules have some inherent bias. In order to eliminate the bias, the Round Half Randomly rule, also known as Stochastic Rounding, rounds a fraction part of 0.5 to either the next greater or the next lower integer randomly, with equal probability. This method effectively eliminates the bias, but the results are not reproducible (unless a pseudo-random number generator with the same seed value is used as the source of randomness).

To implement Round Half Randomly, we use a random number source to generate a value of either zero or one with equal probability. If the value is zero, we apply the Round Half Toward Positive Infinity rule. If the value is one, we apply the Round Half Toward Negative Infinity Rule:

private static readonly Random _Random = new Random();

public static int RoundToNearestRoundHalfRandomly(decimal value)
{
    // Randomly use round to nearest with either the round half toward
    // positive infinity or round half toward negative infinity rule.
    if (_Random.Next(0, 2) == 0)
        return (int)Math.Floor(value + 0.5m);
    else
        return (int)Math.Ceiling(value - 0.5m);
}

Note that the above code is not thread-safe. In particular, there is a race condition in the Random.Next method that can cause the random sequence to become constantly zero after some point. There are several ways to address this, but perhaps the easiest is to avoid having a System.Random instance that persists between method calls. We could change the method so that it rounds each value in a sequence instead of a single value:

public static IEnumerable<int> RoundToNearestRoundHalfRandomly(this IEnumerable<decimal> values)
{
    var random = new Random();

    foreach (var value in values)
    {
        // Randomly use round to nearest with either the round half toward
        // positive infinity or round half toward negative infinity rule.
        if (random.Next(0, 2) == 0)
            yield return (int) Math.Floor(value + 0.5m);
        else
            yield return (int) Math.Ceiling(value - 0.5m);
    }
}

Like Round Half Randomly, the Round Half Alternatingly rule also eliminates bias, but the results are more predictable. We alternate between rounding a fraction part of 0.5 to the next lower and the next greater integer. So, for example, if we had the sequence {1.5, 1.5, 1.5, 1.5}, the result would be {1.0, 2.0, 1.0, 2.0}.

To implement Round Half Alternatingly, we start with a source of alternating sequence of zeros and ones. I’ve chosen to implement this using an enumerator that provides an infinite alternating sequence:

private static IEnumerator<int> GetAlternatingEnumerator()
{
    for (; ; ) {
        yield return 0;
        yield return 1;
    }
}

Then we can implement the actual rounding method:

private static readonly IEnumerator<int> _AlternatingSequence = GetAlternatingEnumerator();

public static int RoundToNearestRoundHalfAlternatingly(decimal value)
{
    // Use round to nearest with either the round half toward 
    // positive infinity or the round half toward negative infinity 
    // rule based on the current value of the alternating sequence.
    _AlternatingSequence.MoveNext();
    if (_AlternatingSequence.Current == 0)
        return (int) Math.Floor(value + 0.5m);
    else
        return (int)Math.Ceiling(value - 0.5m);
}

Again, there are some thread safety issues because we have to maintain state of the alternating sequence between successive calls to our rounding method. Each thread making calls to this method may not get truly alternating rounding if calls from multiple threads are interleaved. The results would be unpredictable, and could be biased. To get around this, we can again use a method that rounds each value in a sequence rather than just a single value:

public static IEnumerable<int> RoundToNearestRoundHalfAlternatingly(this IEnumerable<decimal> values)
{
    var alternatingEnumerator = GetAlternatingEnumerator();

    foreach (var value in values)
    {    
        // Use round to nearest with either the round half toward positive
        // infinity or the round half toward negative infinity rule based
        // on the current value of the alternating sequence.
        alternatingEnumerator.MoveNext();
        if (alternatingEnumerator.Current == 0)
            yield return (int)Math.Floor(value + 0.5m);
        else
            yield return (int)Math.Ceiling(value - 0.5m);
    }
}

Round Ceiling and Round Floor

Sometimes we want to round numbers so that the results are always greater or always lower. At those times, we want to use the Round Ceiling and Round Floor methods. Round Ceiling always rounds a number with a fraction part to the next greater integer. Round Floor always rounds to the next lower integer. These methods are easily implemented using the Math.Ceiling and Math.Floor methods in .NET:

public static int RoundCeiling (decimal value)
{
    return (int)Math.Ceiling(value);
}

public static int RoundFloor (decimal value)
{
    return (int)Math.Floor(value);
}

Round Toward Zero and Round Away from Zero

We can pull our values toward zero or push them away from zero, respectively, using the Round Toward Zero and Round Away from Zero rounding methods. As their names suggest, Round Toward Zero rounds every number with a fraction part to the surrounding integer that’s closer to zero. Round Away from Zero does just the opposite. Round Toward Zero is equivalent to simple truncation, and we can implement the Round Away from Zero method by using either the Round Ceiling or the Round Floor method depending on whether the number is positive or negative.

public static int RoundTowardZero(decimal value)
{
    // To round toward zero, we can simply truncate by casting to Int32.
    return (int) value;
}

public static int RoundAwayFromZero(decimal value)
{
    return value >= 0 ? (int)Math.Ceiling(value) : (int)Math.Floor(value);
}

Round Dither

Some instances, such as rounding values in a slowly changing sequence, may call for an approach that maintains the essence of the original sequence and does not result in long sub-sequences that are constant. The Round Dither method achieves this by rounding numbers with fraction parts using either the Round Ceiling or Round Floor method randomly with a probability that is equal to one minus the fraction part. For example, if we round 1.28 to the nearest integer, then it would be rounded to 1.0 with probability 0.72 or rounded to 2.0 with probability 0.28.

To implement Round Dither in C#, we start with a random number source that can generate fractions between 0 and 1. To round a number, we generate a random fraction, and compare it with the fraction part of the number to be rounded. If the random fraction is less than the fraction part of the number, then we use Round Ceiling. Otherwise, we use Round Floor.

private static readonly Random _Random = new Random();

public static int RoundDither(decimal value)
{
    // If the next random fraction is less than the fraction part of the 
    // number to be rounded, then use Round Ceiling. Otherwise, use 
    // Round Floor.
    if ((decimal)_Random.NextDouble() < Math.Abs(value - (int)value))
        return (int)Math.Ceiling(value);
    else
        return (int)Math.Floor(value);
}

As was the case with the implementation of the Round Half Randomly tie-breaking rule above, this code is not thread-safe. Again, one way that we can address this is by creating a method that rounds each value in a sequence rather than just a single value:

public static IEnumerable<int> RoundDither(this IEnumerable<decimal> values)
{
    var random = new Random();

    foreach (var value in values)
    {
        // If the next random fraction is less than the fraction part of the 
        // number to be rounded, then use Round Ceiling. Otherwise, use 
        // Round Floor.
        if ((decimal)random.NextDouble() < Math.Abs(value - (int)value))
            yield return (int)Math.Ceiling(value);
        else
            yield return (int)Math.Floor(value);
    }
}

Combined Rounding Results

Before we wrap up, let’s take a look at how the example numbers from Part 1 would be rounded using some of the methods we’ve seen:

All of the above code is available in a single Rounding static utility class here. Note that these aren’t the only possible implementations, or even the most efficient. If you come up with alternate implementations, please post them in the comments.

In Part 2, we have covered most (probably not all) of the algorithms for rounding. Why do we need all of them, though? Can’t we just pick one? In Part 3, we’ll learn why it’s important to use an appropriate algorithm and how you can choose.

• Part 1: The Mystery of Math.Round
  The Math.Round method isn’t as straightforward as one might expect.
• Part 2: Exotic Rounding Algorithms
  A menagerie of lesser-known rounding methods, with implementations in C#.
• Part 3: Rounding in Action
  Why some rounding algorithms are better than others in certain situations.

Rounding seems like a fairly trivial mathematical operation, but I recently discovered that it isn’t as straightforward as I thought. If you round numbers in .NET, then there’s a good possibility that you won’t get the results you expect. This is the first post in a new blog series that will cover how Math.Round rounds, some lesser known algorithms (with C# implementations), and how to choose an appropriate algorithm.

Not long ago, I implemented some statistical calculations in C#, and the results weren’t coming out quite right. I ultimately tracked the problem to where I was rounding using the System.Math.Round method. Take a look at this example:

var values = new[] { 3.5, 2.8, 2.5, 2.2, -2.2, -2.5, -2.8, -3.5 };

foreach (var value in values)
{
    var roundedValue = Math.Round(value);
    Console.WriteLine("{0,4:N1} rounds to {1,4:N1}", value, roundedValue);
}

 3.5 rounds to  4.0
 2.8 rounds to  3.0
 2.5 rounds to  2.0
 2.2 rounds to  2.0
-2.2 rounds to -2.0
-2.5 rounds to -2.0
-2.8 rounds to -3.0
-3.5 rounds to -4.0

Huh?… 2.5 rounds to 2.0? Shouldn’t that be 3.0?

I checked the code, checked again, and stared at the screen. “Rounding is so simple,” I thought, “how could .NET get it wrong?” I figured that I should dig into this a bit further, so I opened the .NET Framework Class Library documentation.

The System.Math.Round method has eight overloads. First there are the basic round-to-integer methods:

decimal Round(decimal)
double Round(double)

Then there are two similar methods that allow rounding to a specified number of decimal places:

decimal Round(decimal, Int32)
double Round(double, Int32)

Each of the above four methods are duplicated with an additional MidpointRounding parameter:

decimal Round(decimal, MidpointRounding)
double Round(double, MidpointRounding)
decimal Round(decimal, Int32, MidpointRounding)
double Round(double, Int32, MidpointRounding)

According to the docs, Math.Round always performs a type of rounding called “round to nearest”, and the MidpointRounding parameter specifies a tie-breaking rule. This rule specifies how Math.Round should operate on a number that is exactly halfway between two possible rounded values. There are two possible rules: AwayFromZero and ToEven.

MidpointRounding.AwayFromZero specifies that a value halfway between two possible rounded values should always be rounded up. So, for example, 2.5 would round to 3.0. That sounds right. That’s the method that I learned in school. It’s technically known as “symmetric arithmetic rounding” or “round-to-nearest with round-half-away-from-zero tie breaking” (phew).

MidpointRounding.ToEven specifies that a value halfway between two possible rounded values should be rounded toward the nearest even number. So 2.5 would round to 2.0! This method is technically known as “round-to-nearest with round-half-to-even tie breaking” (phew) or “banker’s rounding”.

The four Math.Round overloads without a MidpointRounding parameter default to ToEven rounding, which explains the example above. The .NET team adopted ToEven as the default based on the IEEE Standard for Floating-Point Arithmetic (IEEE 754). With a slight modification to the original code to specify symmetric arithmetic rounding, the results are what I originally expected:

var values = new[] { 3.5, 2.8, 2.5, 2.2, -2.2, -2.5, -2.8, -3.5 };

foreach (var value in values)
{
    var roundedValue = Math.Round(value, MidpointRounding.AwayFromZero);
    Console.WriteLine("{0,4:N1} rounds to {1,4:N1}", value, roundedValue);
}

 3.5 rounds to  4.0
 2.8 rounds to  3.0
 2.5 rounds to  3.0
 2.2 rounds to  2.0
-2.2 rounds to -2.0
-2.5 rounds to -3.0
-2.8 rounds to -3.0
-3.5 rounds to -4.0

That solves the original mystery, but there are more questions to answer: Are there any rounding algorithms beyond the two that Math.Round supports? Why would anyone want to use these different algorithms anyway? Why does IEEE Standard 754, section 4 recommend round half to even tie breaking? In Part 2, we’ll look at other types of rounding and how they can be implemented in C#. In Part 3, we’ll learn how to choose an appropriate algorithm.

• Part 1: The Mystery of Math.Round
  The Math.Round method isn’t as straightforward as one might expect.
• Part 2: Exotic Rounding Algorithms
  A menagerie of lesser-known rounding methods, with implementations in C#.
• Part 3: Rounding in Action
  Why some rounding algorithms are better than others in certain situations.