When you think about Roslyn source code, you should think about performance-oriented design. I would like to share some performance techniques and coding practices I have been learning from Roslyn source code, so I decided to blog about it.
Let’s start with *amazing* ObjectPool. The ObjectPool is a type used in the Roslyn C# compiler to reuse frequently used objects which would normally get instantiated up and garbage collected very often. This reduces the amount and size of garbage collection operations which have to happen.
/// <summary>
/// Generic implementation of object pooling pattern with predefined pool size limit. The main
/// purpose is that limited number of frequently used objects can be kept in the pool for
/// further recycling.
///
/// Notes:
/// 1) it is not the goal to keep all returned objects. Pool is not meant for storage. If there
/// is no space in the pool, extra returned objects will be dropped.
///
/// 2) it is implied that if object was obtained from a pool, the caller will return it back in
/// a relatively short time. Keeping checked out objects for long durations is ok, but
/// reduces usefulness of pooling. Just new up your own.
///
/// Not returning objects to the pool in not detrimental to the pool's work, but is a bad practice.
/// Rationale:
/// If there is no intent for reusing the object, do not use pool - just use "new".
/// </summary>
Nice code comments, right? I just love this “not so formal” commenting style that provides useful information about what’s going on.
internal class ObjectPool<T> where T : class
{
[DebuggerDisplay("{Value,nq}")]
private struct Element
{
internal T Value;
}
/// <remarks>
/// Not using System.Func{T} because this file is linked into the (debugger) Formatter,
/// which does not have that type (since it compiles against .NET 2.0).
/// </remarks>
internal delegate T Factory();
// Storage for the pool objects. The first item is stored in a dedicated field because we
// expect to be able to satisfy most requests from it.
private T _firstItem;
private readonly Element[] _items;
Roslyn wraps T inside a struct! The idea here is to avoid performance problems when setting array items that are reference types. There is no need to check at runtime if the type of the object is compatible with the type of the array (Please note that arrays are variant on the CLR).
internal ObjectPool(Factory factory)
: this(factory, Environment.ProcessorCount * 2)
{ }
internal ObjectPool(Factory factory, int size)
{
Debug.Assert(size >= 1);
_factory = factory;
_items = new Element[size - 1];
}
private T CreateInstance()
{
var inst = _factory();
return inst;
}
ObjectPool is an internal type. So, it is natural to have “lightweight validations.” By default, the Debug.Assert method works only in debug builds. We will have no validations in release builds!
/// <summary>
/// Produces an instance.
/// </summary>
/// <remarks>
/// Search strategy is a simple linear probing which is chosen for it cache-friendliness.
/// Note that Free will try to store recycled objects close to the start thus statistically
/// reducing how far we will typically search.
/// </remarks>
internal T Allocate()
{
// PERF: Examine the first element. If that fails, AllocateSlow will look at the remaining elements.
// Note that the initial read is optimistically not synchronized. That is intentional.
// We will interlock only when we have a candidate. in a worst case we may miss some
// recently returned objects. Not a big deal.
T inst = _firstItem;
if (inst == null || inst != Interlocked.CompareExchange(ref _firstItem, null, inst))
{
inst = AllocateSlow();
}
return inst;
}
private T AllocateSlow()
{
var items = _items;
for (int i = 0; i < items.Length; i++)
{
// Note that the initial read is optimistically not synchronized. That is intentional.
// We will interlock only when we have a candidate. in a worst case we may miss some
// recently returned objects. Not a big deal.
T inst = items[i].Value;
if (inst != null)
{
if (inst == Interlocked.CompareExchange(ref items[i].Value, null, inst))
{
return inst;
}
}
}
return CreateInstance();
}
Working with values stored directly in fields is faster than with arrays. Because of that, we have a dedicated field here which should be enough most of the time.
Interlocked is used only at the last responsible moment.
/// <summary>
/// Returns objects to the pool.
/// </summary>
/// <remarks>
/// Search strategy is a simple linear probing which is chosen for it cache-friendliness.
/// Note that Free will try to store recycled objects close to the start thus statistically
/// reducing how far we will typically search in Allocate.
/// </remarks>
internal void Free(T obj)
{
Validate(obj);
ForgetTrackedObject(obj);
if (_firstItem == null)
{
// Intentionally not using interlocked here.
// In a worst case scenario two objects may be stored into same slot.
// It is very unlikely to happen and will only mean that one of the objects will get collected.
_firstItem = obj;
}
else
{
FreeSlow(obj);
}
}
private void FreeSlow(T obj)
{
var items = _items;
for (int i = 0; i < items.Length; i++)
{
if (items[i].Value == null)
{
// Intentionally not using interlocked here.
// In a worst case scenario two objects may be stored into same slot.
// It is very unlikely to happen and will only mean that one of the objects will get collected.
items[i].Value = obj;
break;
}
}
}No concurrency checks! If something gets lost, that is ok! Like the comments are saying, it is improbable to happen. So, it is cheaper to create a new instance if needed than trying to avoid concurrent access.
Note that Free will try to store recycled objects close to the start of the array – this makes the allocating process even faster.
Using it!
ObjectPool is a low-level concept implementation. Here is a very interesting use case.
/// <summary>
/// The usage is:
/// var inst = PooledStringBuilder.GetInstance();
/// var sb = inst.builder;
/// ... Do Stuff...
/// ... sb.ToString() ...
/// inst.Free();
/// </summary>
internal class PooledStringBuilder
{
public readonly StringBuilder Builder = new StringBuilder();
private readonly ObjectPool<PooledStringBuilder> _pool;
private PooledStringBuilder(ObjectPool<PooledStringBuilder> pool)
{
Debug.Assert(pool != null);
_pool = pool;
}
public int Length
{
get { return this.Builder.Length; }
}
public void Free()
{
var builder = this.Builder;
// do not store builders that are too large.
if (builder.Capacity <= 1024)
{
builder.Clear();
_pool.Free(this);
}
else
{
_pool.ForgetTrackedObject(this);
}
}
[System.Obsolete("Consider calling ToStringAndFree instead.")]
public new string ToString()
{
return this.Builder.ToString();
}
public string ToStringAndFree()
{
string result = this.Builder.ToString();
this.Free();
return result;
}
public string ToStringAndFree(int startIndex, int length)
{
string result = this.Builder.ToString(startIndex, length);
this.Free();
return result;
}
// global pool
private static readonly ObjectPool<PooledStringBuilder> s_poolInstance = CreatePool();
// if someone needs to create a private pool;
/// <summary>
/// If someone need to create a private pool
/// </summary>
/// <param name="size">The size of the pool.</param>
/// <returns></returns>
public static ObjectPool<PooledStringBuilder> CreatePool(int size = 32)
{
ObjectPool<PooledStringBuilder> pool = null;
pool = new ObjectPool<PooledStringBuilder>(() => new PooledStringBuilder(pool), size);
return pool;
}
public static PooledStringBuilder GetInstance()
{
var builder = s_poolInstance.Allocate();
Debug.Assert(builder.Builder.Length == 0);
return builder;
}
public static implicit operator StringBuilder(PooledStringBuilder obj)
{
return obj.Builder;
}
}Roslyn uses StringBuilder intensively. ObjectPool saves a lot of work creating new instances and collecting garbage.
