NoAlloq 0.1.0

NoAlloq : LINQ for Span

The official stance for using LINQ with System.Memory is to convert a Memory with MemoryMarshal.ToEnumerable(), which does not help with Span itself.

NoAlloq aims to provide basic LINQ functionality on top of Span, without allocating any memory. Since some LINQ features (such as .Reverse() or .OrderBy()) require storing the entire sequence in memory, NoAlloq requires the user to provide their own memory backing.

You can contact the author at: victor@nicollet.net

Usage examples

All operations can be performed on top of a ReadOnlySpan<T>, including one on the stack or obtained from a string:

using NoAlloq;

int CountPrimeDivisors(int n)
{
    ReadOnlySpan<int> primes = stackalloc int[] { 2, 3, 5, 7, 11, 13, 17, 19 };
    return primes.Count(p => n % p == 0);
}

char FirstUppercaseChar(string s) =>
    s.AsSpan().FirstOrDefault(c => c.IsUpper);

Without allocation

Currently, NoAlloq supports the following methods without any allocation involved:

• .Select(Func<TIn, TOut>) but not yet .Select(Func<TIn, int, TOut>).
• .Where(Func<T, bool>) but not yet .Where(Func<T, int, bool>).
• .Take() and .Skip() as .Slice(skip, take) for consistency with Span<T>.Slice().
• .First(), .First(Predicate<T>), .FirstOrDefault() and .FirstOrDefault(Predicate<T>).
• .Last(), .Last(Predicate<T>), .LastOrDefault() and .LastOrDefault(Predicate<T>).
• .Count() and .Count(Predicate<T>), as well as .CountTrue() as a shortcut for .Count(b => b).
• .Any() and .Any(Predicate<T>), as well as .AnyTrue() as a shortcut for .Any(b => b).
• .All(Predicate<T>), as well as .AllTrue() as a shortcut for .All(b => b).
• .Single() and .Single(Predicate<T>).
• .Sum() and .Sum(Func<TIn, TOut>) for int, float and double.
• SpanEnumerable.Range(first, count) equivalent to Enumerable.Range.

Other methods which are obviously possible without allocation (such as ElementAt) will be added in the near future.

With external allocation

When an operation requires a memory allocation to store its output (or internal temporary values), NoAlloc will expect that memory as an argument. It can come from a stackalloc span (if the size is known to be small enough), from an ArrayPool, or simply from an array.

CopyInto

Span<T> SpanEnumerable.CopyInto(Span<T> span) expects a span large enough to fit all data in the enumerable (and will throw if there is not enough room).

ReadOnlySpan<string> strings = ...;

Span<int> lengths = stackalloc int[strings.Length];
strings.Select(s => s.Length).CopyInto(lengths);

TakeInto

Span<T> SpanEnumerable.TakeInto(Span<T> span) works like CopyInto, but stops at the end of the provided span instead of throwing an exception.

var primes = stackalloc int[10];
primes = SpanEnumerable.Range(0, 1000).Where(IsPrime).TakeInto(primes);

ReverseInto

Span<T> SpanEnumerable.ReverseInto(Span<T> span) works like CopyInto, but places the results in the span in reverse order. This is equivalent to calling CopyInto followed by Span<T>.Reverse().

var reversed = stackalloc int[10];
reversed = SpanEnumerable.Range(0, 10).ReverseInto(reversed);

If you can afford to modify the original span, you can also use .ReverseInPlace():

var numbers = stackalloc int[] { 5, 4, 3, 2, 1, 0 };
foreach (var n in numbers.ReverseInPlace())
  // visits 0, 1, 2, 3, 4, 5

OrderBy

To sort a sequence, it is necessary to store it in its entirety. Because of this, all .OrderBy() methods take a span where the sequence will be copied and stored. The standard LINQ methods thus become:

• .OrderBy(Span<T> backing, Func<T, TK> keySelector)
• .OrderBy(Span<T> backing, Func<T, TK> keySelector, IComparer<TK> comparer)
• .OrderByDescending(Span<T> backing, Func<T, TK> keySelector)
• .OrderByDescending(Span<T> backing, Func<T, TK> keySelector, IComparer<TK> comparer)

The backing span must be large enough to contain the entire sequence, but may be larger than the sequence (in which case NoAlloq will only use the necessary prefix).

For convenience, NoAlloq also provides variants for the case where the key selector is x => x:

• .OrderByValue(Span<T> backing)
• .OrderByValue(Span<T> backing, IComparer<T> comparer)
• .OrderByValueDescending(Span<T> backing)
• .OrderByValueDescending(Span<T> backing, IComparer<T> comparer)

Right now, .ThenBy() and .ThenByDescending() are not supported, but they should be soon enough.

In-place operations

If you only use methods which consume the input linearly (that is, computing the value for position p does not require cells at positions i < p ), you may choose to use the input span as the output, effectively performing an in-place transformation.

Span<string> strings = ...;
strings = strings.Select(s => s.ToUpper()).Where(s => s.Length < 10).CopyInto(strings);

The methods that consume the input linearly are:

• .Select()
• .Where()
• .OrderBy() and its variants: every time a value is consumed from an .OrderBy(), it frees the lowest used index in its backing.

This property of .OrderBy() means it's possible to do the following without any allocation:

string[] names = ...;
names.OrderBy(names, n => n.Length)
     .ThenBy(n => n)
     .Select(n => n.ToUpper())
     .CopyInto(names);

With internal allocation

NoAlloq provides the usual .ToArray(), .ToDictionary(), .ToList() and .ToHashSet(), which inherently must allocate memory (since the returned object must be allocated).

However, in order to give the caller control over those allocations, NoAlloq provides alternative .CopyInto() methods which expect their destination to be provided.

ReadOnlySpan<string> strings = ...;

// With ToList
List<string> list = strings.ToList();

// Equivalent: 
List<string> list2 = new List<string>();
strings.CopyInto(list2);

// With ToHashSet
HashSet<string> hash = strings.ToHashSet();

// Equivalent:
HashSet<string> hash = new HashSet<string>();
strings.CopyInto(hash);

// With ToDictionary
Dictionary<string, int> dict = strings.ToDictionary(s => s, s => s.Length);

// Equivalent:
Dictionary<string, int> dict2 = new Dictionary<string, int>();
strings.CopyInto(dict2, s => s, s => s.Length)

Issues and Limitations

Since any type capable of reading from a Span<T> must be a ref struct, the SpanEnumerable defined by NoAlloq cannot be stored as a member in a class or non-ref struct and cannot be used within the same function as await or yield return.

Moreover, since ref struct types cannot implement interfaces, there is no easy way to hide the complexity of the types used by NoAlloq. For example, by writing:

Span<User> span = ...;
var alive = span.OrderBy(span, x => x.Name).Where(x => x.IsAlive);

The type of the alive variable is:

SpanEnumerable<User, User, 
    SecondaryWhereDelegateProducer<User, User, 
        OrderingProducer<User, string, DelegateExtractor<User, string>, Comparer<string>>>> 

As such, creating a function that returns such a value, or takes such a value as argument, is rather tedious, even by using generics and constraints:

WithAliveUsers(SpanEnumerable<User, User, TProducer> aliveUsers)
    where TProducer : NoAlloq.Producers.IProducer<User, User>