.NET Daily Quiz archive - week 4

.NET Daily Quiz #016

Today we'll think about program design. Can you defined the following terms?
1. The no-throw guarantee
2. The strong exception guarantee
3. The weak exception guarantee

Which guarantee does this snippet offer, assuming RetrieveTaxRate could throw an exception?

var employees = GetAllEmployees();
var taxReport = employees.Select(e => e.RetrieveTaxRate());

What about this snippet?

var employees = GetAllEmployees();
var taxReport = employees.Select(e =>
      {
            var rate = e.RetrieveTaxRate()
            e.TotalTax += rate;
            return rate;
      });

Consider some code you have written recently. Which guarantees do you offer? Is there something you can do with your application to make stronger guarantees?

Answer:

These terms refer to the guarantees that your individual methods make with regards to their approach to exception-handling:
1. No-throw guarantees that a method will not throw an exception under any non-fatal circumstances. In my opinion (take it for what it’s worth) even a no-throw method could potentially throw OutOfMemoryExceptions and other very fatal exceptions.
2. The strong exception guarantee states that the method may throw an exception, but if it does then the containing object and any data it is working on will remain in the state it was in before the method was called. Any changes to internal data structures will be rolled back before the exception is (re-)thrown.
3. The weak exception guarantee states that an exception may be thrown, but that the object will be guaranteed to be in a useful but unknown state. The object and its internal data structures may have changed, but they will not be invalid. For example, maybe a method will be operating on a bunch of Money objects, and at some intermediate stage the Money objects will have the internal value of _dollars = -1 (an illegal value). One way of satisfying the weak exception guarantee would be to set these value to _dollars = 0 — this value is legal, but not necessarily correct.

Conversely to these guarantees we could consider the zeroeth exception guarantee — that all internal data structures cannot be guaranteed to be in a well-defined, legal state after an exception occurs. It is not possible to do meaningful work on a program that has reached this state — if an object does not make one of the 3 exception guarantees then an exception should crash the application or re-initialize it to a known good state.

The first code snippet offers a strong exception guarantee. The select statement makes no changes to the employee data. If RetrieveTaxRate throws, taxReport is never populated and nothing is changed from before the program was run.

The second code snippet offers a weak guarantee. The employees data is modified inside the select delegate (you should never do this, by the way). After the exception is thrown, each employee will have a legal TotalTax value, but not necessarily a correct one (especially if the exception handler retries the method).


.NET Daily Quiz #017

In C++ and some other languages, a common way to increase the performance of a program is to strategically inline particular functions. Is this capability available in C#? If so, how can we go about it? If not, why not?

Answer:

Since .NET 4.5 the System.Runtime.CompilerServices.MethodImplAttribute attribute has offered the AggressiveInlining flag, which will aggressively attempt to inline the function (although it’s still not guaranteed).

However like the C++ inline modifier, this should be used sparingly, if ever. For compiler-automated inlining, a method must be non-virtual, small in size (where “small” is defined by the compiler/JIT) and without complex control structures such as try/catch. I’m not sure if there are any more concrete rules behind this, I believe the JIT/compiler implementer is free to make this determination.

Bottom line, the compiler is (usually) smarter than you — but this doesn’t mean you shouldn’t understand what it’s doing.


.NET Daily Quiz #018

How well do you know your standard .NET data structures? Let's explore System.Collections.Generic, starting today with SortedDictionary<TKey,TValue>

The following questions assume a reasonable IComparer is supplied.

Do you know the underlying implementation of SortedDictionary<K,V>?
What is the computational complexity (big-O) for retrieval from an instance of this class?
What is the worst-case complexity for retrieval?

What is the computational complexity (big-O) for insertion into an instance of this class?
What is the worst-case complexity for insertion?

What is the computational complexity (big-O) for removal from an instance of this class?
What is the worst-case complexity for removal?

Do you know roughly how much memory a SortedDictionary<K,V> with n items occupies?

Answer:

The documentation for SortedDictionary<TKey,TValue> tells us it is a binary search tree. If we open SortedDictionary in Decompiler we can see the underlying data structure is a TreeSet<KeyValuePair<TKey,TValue>> which derives from SortedSet<T>, a Red-Black Tree.

Red-Black trees offer O(log n) complexity guaranteed across all retrieval, insertion and deletion operations. The worst case for any operation is a re-balance involving 2 rotations and 3 re-colorings of the tree, an O(1) amortized process.

Memory usage of SortedDictionary<T,K> is approximately 40 bytes per member (one object instance, a bool (red/black) and two references (left/right child)) plus the cost of the members and object references.
Memory is not required to be contiguous, so heap fragmentation does not get out of control with large numbers of inserts/deletes.


.NET Daily Quiz #019

What is the output of this application, and why? Hint: this isn't really another tricky threading question, think in terms of the IEnumerator state machine generated by the compiler.

using System;
using System.Collections.Generic;
using System.Threading;
class Program
{
    private static IEnumerator _enumerator;
    private static bool _moved = false;
    static void Main(string[] args)
    {
        _enumerator = GetStrings();
        var t1 = new Thread(MoveEnumerator);
        var t2 = new Thread(MoveEnumerator);
        t1.Start();
            Thread.Sleep(100);
        t2.Start();
        while (!_moved)
        {
        }
        Thread.Sleep(500);
        Console.WriteLine(_enumerator.Current);
        Console.ReadLine();
    }
    static IEnumerator GetStrings()
    {
        Thread.Sleep(1000);
        yield return "hello";
        yield return "world!";
    }
    static void MoveEnumerator()
    {
        _moved = _enumerator.MoveNext();
   }
}

Answer:

The reason we see the first item in the Enumerator block and not the second, despite having called MoveNext twice is explained by the rules of the state machine that the C# compiler generates for Enumerator blocks.

The following is a very brief, simplified version of the Enumerator state machine. For full details, check out the C# spec, 10.14.4 (bold for emphasis on the solution to this quiz).

- If enumerator state is before, MoveNext is called
- Change enumerator state to running
- Execute enumerator until interruption (either block finishes, exception is encountered or iterator block yields control)
- If enumerator state is running, result of MoveNext is unspecified
- If enumerator state is suspended, MoveNext is called
- Change state to running
- Resume execution of iterator from yielded position until interruption
- If enumerator state is after, MoveNext is called, return false

In the iterator block:
- When yield return is encountered
- Evaluate return expression
- Suspend execution of iterator
- Change state of iterator to suspended
- MoveNext returns true
- When yield break is encountered
- Execute finally blocks as necessary
- Change state of enumerator to after
- MoveNext returns false
- When iterator block is completed
- Change state of enumerator to after
- MoveNext returns false
- When an exception is encountered
- Execute finally blocks as necessary
- Change state of enumerator to after
- MoveNext returns false

The key here (in bold) is executing MoveNext while the state is running: according to the spec the result is unspecified. In this case it appears that the call is simply ignored by the iterator and MoveNext is returning false by the second call (which actually returns first).


.NET Daily Quiz #020

Users of my library are reporting resource leaks. What can I do to fix it?

namespace MyLibrary
{
    public interface IDoThings
    {
        void Things();
    }
    public class WorkDoer where T : IDoThings, new()
    {
        public void Thinger()
        {
            var t = new T();
            t.Things();
        }
    }
    public class WorkDoerWithMember where T : IDoThings, new()
    {
        T _t;
        public void MemberThinger()
        {
            if (_t == null) _t = new T();
            _t.Things();
        }
    }
}

Answer:

The supplied type parameter for either of our classes could implement IDisposable and this is a possibility we haven't considered in our class design. To work around this we need to defensively dispose of resources in the appropriate place.

For the class WorkDoer, T is only used locally in a method, so we can simply do it this way:

public class WorkDoer where T : new(), IDoThings
{
      public void Thinger()
      {
            var t = new T();
            using (t as IDisposable)
            {
                  t.Things();
            }
      }
}

Believe it or not this works correctly for both types that implement IDisposable and types that don't (which kind of surprised me).

Our second class uses T as a member so it's a bit more hairy. We need to ensure our class implements IDisposable itself and disposes or resources correctly, whether T implements IDisposable or not.

public sealed class WorkDoerWithMember where T : new(), IDoThings, IDisposable
{
      T _t;
      public void MemberThinger()
      {
            if (_t == null) _t = new T();
            _t.Things();
      }
      public void Dispose()
      {
            var d = _t as IDisposable;
            if (d != null)
            {
                  d.Dispose();
            }
      }
}

Note that I have marked the class as sealed. This ensures that subclasses can't reuse my Dispose method - to get around this, simply implement the full Dispose pattern (I skipped that for brevity). Also note that Dispose could be called more than once on our T object. We can't just set _t to null because our class supports value types. All IDisposable implementers must be able to handle multiple calls to Dispose, as per MSDN guidelines:

"If an object's Dispose method is called more than once, the object must ignore all calls after the first one. The object must not throw an exception if its Dispose method is called multiple times."

Consider better ways to design these classes, particularly in light of yesterday's dependency inversion session.