...Removing All Doubt

I recently needed to create a set of classes that was the combinatorial expansion of several implementation flavors of two independent sets of methods. Why I needed combinatorial expansion is not that interesting but the solution is. What I came up with is a way of supporting a form of mixin's in C#.

Lets take the methods,

void Lock();
bool Unlock();
bool Locked { get; }

If you call Lock(), Locked returns true, until you call Unlock(). Also Unlock() returns true if the object is now unlocked. There are several implementations I can think of for these methods, one uses a Boolean value and doesn't support nested calls to Lock():

void Lock() {
  _locked = true;
}

bool Unlock() {
  _locked = false;
  return true;
}

bool Locked {
  get { return _locked; }
}

Another uses an integer value to count the number of nested calls to Lock() and it remains locked until a matching number of Unlock() calls are made.

void Lock() {
  _count++;
}

void Unlock() {
  _count--;
  return _count == 0;
}

void Locked() {
  return _count > 0;
}

This isn't thread safe so we could provide a relatively thread-safe version in,

void Lock() {
    System.Threading.Interlocked.Increment(ref _count);
}

bool Unlock() {
    return System.Threading.Interlocked.Decrement(ref _count) == 0;
}

bool Locked {
    get { return _count > 0; }
}

I am sure you have already thought of at least one more. Now I have four possible implementations (including yours), which is the correct one? Unfortunately, that depends on how the locking is going to be used. If I know I will never need nested locks, only taking space for a Boolean makes sense. If I know I will need to support nested locks then the int seems like a good choice. If it is going to be used in a multi-threaded application I should probably use the thread-safe version. I now have two choices, pick one implementation or pass it the implementation as a parameter. Picking one implementation is easy, just copy of of the above implementation into the class; but how do you efficiently pass an implementation as a parameter?

From now on I will refer to each implementation as a locking policy. What I want is an efficient way to pass the locking policy to a set of classes. Most obvious way is to write a class for each policy and pass the policy as a parameter to each instance. This might look something like,

abstract class LockingPolicy {
  public abstract void Lock();
  public abstract bool Unlock();
  public abstract bool Locked { get; }
}

class LockableObject {
    private LockingPolicy _lockingPolicy;
  
    public LockableObject(LockingPolicy lockingPolicy) {
        _lockingPolicy = lockingPolicy;
    }
  
    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

Unfortunately, this has, on average, 36 bytes of overhead per instance on a 32 bit machine (more on 64).  This seems a bit much for such a policy and picking just one implementation, even one too general for the average application, starts looking like a better alternative. We must be able to do better than this.

Since passing the implementation as a parameter to the instances is expensive, why not try to pass the implementation to the class instead? In order to do that we need use a type parameter. What we want is something like,

class LockableObject<LockingPolicy> {
    private LockingPolicy _lockingPolicy = new LockingPolicy();

    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

In other words, we need to passing a class and delegate the implementation to that class. This does not look significantly better than the previous implementation, however, because we are new'ing up an instance and assigning it to an instance variable which, as before, consumes a minimum of 36 bytes per instance. But if LockingPolicy is a struct instead of a class then it will only add the size of the struct to the LockableObject instance size. In other words, we would only be taking space for either a bool or an int. The size overhead looks good, now how about the delegation? In order to call methods on LockingPolicy the LockingPolicy struct must implement an interface. It cannot be an abstract class because all structs are sealed and cannot be inherited from. The interface for the locking policy is fairly straight forward and looks like,

interface ILockingPolicy {
    void Lock();
    bool Unlock();
    bool Locked { get; }
}

An implementation of the Boolean locking policy looks like,

struct SimpleLockPolicy : ILockingPolicy {
    bool _locked;

    void ILockingPolicy.Lock() {
        _locked = true;
    }
    bool ILockingPolicy.Unlock() {
        _locked = false;
        return false;
    }
    bool ILockingPolicy.Locked {
        get { return _locked; }
    }
}

The counted locking policy looks like,

struct CountedLockPolicy : ILockingPolicy {
    private int _count;
    void ILockingPolicy.Lock() {
        _count++;
    }
    bool ILockingPolicy.Unlock() {
        _count--;
        return _count == 0;
    }
    bool ILockingPolicy.Locked {
        get { return _count > 0; }
    }
}

We now need to add a where clause to the LockableObject class so we can call the methods provided by the struct's methods. The modified LockableObject class looks like,

class LockableObject<LockingPolicy>
    where LockingPolicy : struct, ILockingPolicy 
{
    private LockingPolicy _lockingPolicy = new LockingPolicy();

    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

The LockableObject can now be instantiated like,

var lockableObject = new LockableObject<SimpleLockPolicy>();

for a lockable object that uses the Boolean implementation. To use the counted locking policy you would construct the object like,

var lockableObject = new LockableObject<CountedLockPolicy>();

The space consumption looks good but the delegation looks expensive it call through an interface which is a virtual. But since we are using structs, which are sealed, the call through the interface can be made static and then be a candidate for inlining. In fact, this is what happens in retail builds when not debugging. This is not entirely free however since there the runtime doesn't inline twice. Implementing Lock() directly instead of through delegation means the Lock() method can be inlined, removing the call entirely, the delegated version inlines the delegation but it still generates a call.

This mechanism for C# mixins is not as convenient as languages that support multiple inheritance, because we have to manually delegate to the policy, but it is just as efficient as we will see demonstrated more clearly in some of the next entries.