LinqAF: Allocating

This is part of a series on LinqAF, you should start with the first post.

When does LinqAF allocate?

The whole point of LinqAF is to be a low-allocation re-implementation of LINQ-to-Objects, so why does it allocate at all?

The answer is that there are a few operations that, logically, must allocate:

• Distinct
  • Needs to track what has already been yielded
• Except
  • Needs to track what cannot be yielded
• GroupJoin
  • Needs to keep track of groups as it iterates over a sequence
• Intersect
  • Needs to track what can be yielded
• Join
  • Needs to keep track of items in the first sequence to join against the second
• OrderBy(Descending) & ThenBy(Descending)
  • Needs to enumerate the whole sequence before it can begin sorting
• Reverse
  • Needs to enumerate the whole sequence to find the last item before yielding
• ToArray
  • Has to allocate the returned array
• ToList
  • Has to allocate the returned list
• ToLookup
  • Needs to build an internal dictionary to lookup groups by
• ToDictionary
  • Has to allocate the returned dictionary
• Union
  • Needs to track what has already been yielded

There are many cases (like passing known Empty enumerables) that can be optimized to not allocate, but in general these are unavoidable.

LinqAF allows for some application-specific optimizations by letting consumers register an alternative IAllocator which handles actual allocations.  For example, you could exploit the knowledge that no enumerables in a web app survive past a request and re-use allocated List<T>s.

IAllocator exposes the following methods:

• GetArray<T>(int)
• ResizeArray<T>(ref T[], int)
• GetEmptyList<T>(int?)
• GetPopulatedList<T>(IEnumerable<T>)
• GetEmptyDictionary<TKey, TValue>(int?, IEqualityComparer<TKey>)
• EnumerableBoxed<T>()
  • This is called for profiling purposes only

How does LinqAF minimize the size of necessary allocations?

It’s possible to safely reduce the number of cats pictured.

In cases where allocations must be made LinqAF can still minimize allocations by using specialized types rather than the generic ones in the BCL.

CompactSet<T> is used by Intersect, Except, Union, and Distinct in place of HashSet<T>.  It stores all elements in a single array (which can be shared in some cases, reducing duplication) and optimizes the common case where a “bucket” has a single value to avoid allocating an array.  CompactSet<T> only supports adding elements, as that is the only method needed for LINQ operators.

LookupHashtable<TKey, TElement> is used by ToLookup (which itself backs Join, GroupBy, and GroupJoin) in place of Dictionary<TKey, TElement>.  It also stores all elements in a single array, and optimizes the common case where a “bucket” has a single value.  Unlike CompactSet<T>, LookupHashtable<TKey, TElement> can be enumerated in a stable order.

OrderBy(Descending) uses a StructStack<T> in place of a Stack<T> internally to keep track of subsets needing sorting.  StructStack<T> only supports Push(T) and Pop(), as that’s all that is needed for OrderBy(Descending).

LinqAF also reduces allocation sizes by shrinking structs by omitting as many fields as possible, and by liberally applying [StructLayout(LayoutKind.Auto)] to allow the runtime to reorder fields for packing efficiency.

When does LINQ inherently allocate?

There are cases where the LINQ expression-to-method-calls transformation introduces some inherent allocations.  For example, repeat chains of from expressions like

int[] xs, ys, zs =/* initialization code */ 

var e = 
  from x in xs
  from y in ys
  from z in zs
  select x + y + z;

introduces an anonymous object to hold x, y, and z.  The compiler produces code equivalent to

int[] xs, ys, zs =/* initialization code */ 

var e = 
  xs.SelectMany(_ => ys, (x, y) => new { x, y })
    .SelectMany(_ => zs, (xy, z) => xy.x + xy.y + z);

which has an allocates four delegates, one of which itself allocates an anonymous object per invocation.

I personally always use explicit method calls rather than the expression-style of LINQ which makes any “inherent” allocations an explicit and visible part of my code.  If you prefer the expression-style, then you should be aware that there are cases where the compiler will insert allocations outside of LinqAF’s code.

What’s next?

I’ll cover the peculiar case of SelectMany and why LinqAF must have a notion of “boxing”.