ciphersofreason-blog

[ciphersofreason-blog]

Thread safety and the swap-reference pattern

True immutability for deep object hierarchies can only be achieved with deep copy, a requirement that is at best time consuming to achieve and at worst, not possible (when using third-party libraries, for example).  A commonly-known mechanism for achieving thread safety in your application is the use of the lock keyword.  I'm not going to spend too much time on this, I'm sure you know what it is.  While the pattern is familiar and therefore fairly easy to use, there are other mechanisms for achieving thread safety.  

Why bother, I hear you ask?  I admit, it is applicable and flexible to cover a variety of scenarios.  However, there are scenarios wherein alternative strategies could be considered, strategies that are faster and fairly easy to implement.  One such strategy is the swap-reference pattern.

Scenario:

Let us say I have a simple set of cached data that I populate at the start of the application.  The data changes infrequently, with a forced refresh on a schedule (e.g. daily):

public interface IReferenceCache<T> where T: class { //Get the latest version. T Get(); //Return the previous version. T Put(T t); } /// <summary> /// NOT THREADSAFE!!! /// </summary> /// <typeparam name="T">Any reference type.</typeparam> public class ReferenceCache<T>: IReferenceCache<T> where T:class { private T _objRef; public T Get() { return _objRef; } public T Put(T t) { T previous = _objRef; _objRef = t; return previous; } } public class CacheManager { private readonly IReferenceCache<MutableObject> _simpleObjectCache; private readonly IReferenceCache<List<MutableObject>> _listObjectCache; private readonly IReferenceCache< Dictionary<string, MutableObject>> _dictionaryCache; public CacheManager() { _simpleObjectCache = new ReferenceCache<MutableObject>(); _listObjectCache = new ReferenceCache<List<MutableObject>>(); _dictionaryCache = new ReferenceCache< Dictionary<string, MutableObject>>(); } public void RefreshDaily() { //Get latest versions of the List or Dictionary, //from some report repository, //and do a put. The put is a reference swap. _simpleObjectCache.Put(GetLatestVersion()); _listObjectCache.Put(GetLatestVersionList()); _dictionaryCache.Put(GetLatestVersionMap()); } public MutableObject SimpleObject { get { return _simpleObjectCache.Get(); } } public List<MutableObject> ListObject { get { return _listObjectCache.Get(); } } public Dictionary<String, MutableObject> Map { get { return _dictionaryCache.Get(); } } ... }  

Granted, the example is a bit contrived and one could argue I should be using MemoryCache or insert_your_favourite_cache_here, but this isn't entirely uncommon, so bear with me on this one. The ReferenceCache class is in no way thread safe. Here's how I would change it to make it thread safe:

/// <summary> /// Represents a simple cache that provides ready access to /// an instance of a reference type. /// The access and modification of reference are threadsafe. /// However, it gives no guarantees about the threadsafety /// of a reference type. /// </summary> /// <typeparam name="T">Any reference type</typeparam> public class ReferenceCache<T>: IReferenceCache<T> where T: class { private T _objRef; public T Put(T t) { //All we're doing here is swapping the //reference in a thread-safe manner. //This does not mean that all mutations //on the actual object is threadsafe. //More on that later... return Interlocked.Exchange(ref _objRef, t); } public T Get() { //If the accessor holds on to a //reference received by this method, //that will not get updated when a put //is performed on this cache. return Interlocked.CompareExchange( ref _objRef, default(T), default(T)); } }

Interlocked methods are easy to use, are faster than many other synchronization mechanisms and more importantly, lends itself to be used in such scenarios. Admittedly, there are scenarios where the lock keyword is a better fit, particularly from the perspective of making your code readable. However, as you can see in this scenario, Interlocked is less intrusive and provides all the benefits listed earlier.

The ubiquitous lock should not be so prevalent anymore.

[ciphersofreason-blog]

Immutability and the builder pattern

Building on my previous post on thread safety, I wanted to cover certain strategies to ensure shared data is not exposed to the vagaries of thread scheduling or interleaving.

One simple way of making shared data thread-safe is to make it immutable.   I don't really need to expound the benefits of immutability when it comes to multi-threaded programs.  This seems a favourite topic for many and you will find many authors have tackled this subject.

http://www.javapractices.com/topic/TopicAction.do?Id=29

http://blogs.msdn.com/b/ericlippert/archive/tags/immutability/

Jon Skeet, of Stack Overflow fame, observed a pattern used in Protocol Buffers (or more specifically, his port of Protocol Buffers), that I find quite interesting:

http://msmvps.com/blogs/jon_skeet/archive/2008/08/20/lessons-learned-from-protocol-buffers-part-1-messages-builders-and-immutability.aspx

So, without further ado, here's an example of building an immutable object using the builder pattern:

internal sealed class ImmutableSharedData { //Should use the Builder to build an instance of ImmutableSharedData private ImmutableSharedData() { } public String StringValue { get; private set; } public double PrimitiveValue { get; private set; } public DateTime StructValue { get; private set; } public MutableStruct MutableStructValue { get; private set; } public sealed class Builder { public ImmutableSharedData Build() { return new ImmutableSharedData() { StringValue = SetStringValue, PrimitiveValue = SetPrimitiveValue, StructValue = SetImmutableStructValue, MutableStructValue = SetMutableStructValue }; } public String SetStringValue { private get; set; } public double SetPrimitiveValue { private get; set; } public DateTime SetImmutableStructValue { private get; set; } public MutableStruct SetMutableStructValue { private get; set; } } public override string ToString() { return String.Format( "String: {0}, Primitive: {1}, " + "ImmutableStruct: {2}, MutableStruct: {3}", StringValue, PrimitiveValue, StructValue, MutableStructValue ); } } class ImmutableSharedDataUser { public ImmutableSharedData SharedData { get; private set; } public ImmutableSharedDataUser(ImmutableSharedData sharedData) { SharedData = sharedData; } public static void Main(string[] args) { var sharedData = new ImmutableSharedData.Builder() { SetPrimitiveValue = 2.25, SetStringValue = "Something", SetImmutableStructValue = DateTime.Today.AddDays(1), //Following value type semantics, the value is set //to a copy of the original struct SetMutableStructValue = new MutableStruct() }.Build(); var user = new ImmutableSharedDataUser(sharedData); Console.WriteLine(user.SharedData.ToString()); //A struct follows value-type semantics. //If a struct is a property of another object, accessing //the property creates a copy and actions will be performed //on the copy. As result, the value of the original mutable //struct remains unchanged. user.SharedData.MutableStructValue.Mutate(); Console.WriteLine(user.SharedData.ToString()); Console.Read(); } }

Conclusion:  When creating custom types, it is worth considering whether that can be made immutable or not.  If shared state has to contain reference types that are mutable, then indeed, we may have to consider alternate strategies for ensuring thread safety (of course, we have the ICloneable and deep-copy malarkey, but we have to strike a balance between functionality and perfection).  However, immutable objects are a viable alternative in many scenarios.  As we will see later, when combined with the swap-reference pattern, this is truly a good strategy for ensuring state is thread-safe for the entire lifecyle of an application.

[ciphersofreason-blog]

What is thread safety?

Thread safety is a phrase that is overused, ill-understood and very, very hard to define.  That hasn't, however, stopped us from attempting to explain this abstract concept in oh so many ways.  I'm not about to break this long-standing tradition.

Thread safety is best understood from the perspective of any shared data in a program that multiple threads have the ability to mutate.  Let us assume that the program expects the shared data to be correct at all times.  The definition of this correctness is largely contextual:  Some programs might expect the shared state to always reflect the latest mutation performed on it.  Other programs might expect it to reflect the cumulative effect of all mutations performed on it, or even that the mutations are performed in sequential order.  

Whatever the definition of correctness, the shared data is said to be thread-safe if it adheres to this principle of correctness regardless of the scheduling of those threads or interleaving of mutations performed on it. 

My, isn't that wordy?  I don't know which is worse:  realising the need for it by experiencing a threading issue or trying to define it.  What do you think?

[ciphersofreason-blog]

Atomic Boolean in C#

The Framework Class Library (FCL) offers many synchronous, non-blocking, mechanisms of updating state, some of which include Thread.VolatileRead and Thread.VolatileWrite as well as the Interlocked methods. However, there does not seem to be an AtomicBoolean equivalent in C# (as that seen in Java). Here's a fast, interlocked-based implementation:

/// <summary> /// Provides non-blocking, thread-safe access to a boolean valueB. /// </summary> public class AtomicBoolean { #region Member Variables private const int VALUE_TRUE = 1; private const int VALUE_FALSE = 0; private int _currentValue; #endregion #region Constructor public AtomicBoolean(bool initialValue) { _currentValue = BoolToInt(initialValue); } #endregion #region Private Methods private int BoolToInt(bool value) { return value ? VALUE_TRUE : VALUE_FALSE; } private bool IntToBool(int value) { return value == VALUE_TRUE; } #endregion #region Public Properties and Methods public bool Value { get { return IntToBool(Interlocked.Add( ref _currentValue, 0)); } } /// <summary> /// Sets the boolean value. /// </summary> /// <param name="newValue"></param> /// <returns>The original value.</returns> public bool SetValue(bool newValue) { return IntToBool( Interlocked.Exchange(ref _currentValue, BoolToInt(newValue))); } /// <summary> /// Compares with expected value and if same, assigns the new value. /// </summary> /// <param name="expectedValue"></param> /// <param name="newValue"></param> /// <returns>True if able to compare and set, otherwise false.</returns> public bool CompareAndSet(bool expectedValue, bool newValue) { int expectedVal = BoolToInt(expectedValue); int newVal = BoolToInt(newValue); return Interlocked.CompareExchange( ref _currentValue, newVal, expectedVal) == expectedVal; } #endregion }