LinqAF: All the operations

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

What operations does LinqAF support?

baby-cats-955895_640

So many operations.  And cats.

All the ones the LINQ does, and LinqAF sports numerous optimizations that additional type information makes possible.

Concretely:

There are also three static methods on Enumerable that expose special enumerables which sport many optimizations.  They are:

  • Empty
    • Aggregate() with no seed always throws
    • Aggregate() always returns seed, or seed passed to resultSelector, depending on overload
    • Any() is always false
    • AsEnumerable() always results in an empty IEnumerable
    • Average() over non-nullable types always throws an exception
    • Average() overnullable types always returns null
    • DefaultIfEmpty() can be optimized into a “OneItem” enumerable
    • Cast() always results in an empty enumerable of the destination type
    • Concat() calls return the non-empty parameter
    • Contains() always returns false
    • Count() is always 0
    • Distinct() always returns an empty enumerable
    • ElementAt() always throws an exception
    • ElementAtOrDefault() always returns default
    • First() always throws an exception
    • FirstOrDefault() always returns default
    • GroupJoin() results in an empty enumerable
    • Join() results in an empty enumerable
    • Last() always throws an exception
    • LastOrDefault() always returns default
    • LongCount() is always 0
    • Min() and Max() over non-nullable types always throw exceptions
    • Min() and Max() over nullable types always return null
    • OfType() always results in an empty enumerable of the destination type
    • OrderBy() and OrderByDescending() result in a special EmptyOrdered enumerable
    • Reverse() results in an empty enumerable
    • Select() results in an empty enumerable
    • SelectMany() results in an empty enumerable
    • SequenceEqual() always has the same result for many types (DefaultIfEmpty => false, another Empty => true)
    • SequenceEqual() devolves to a Count or Length check on things like List<T> or Dictionary<T,V>
    • Single() always throws an exception
    • SingleOrDefault() always returns default
    • Skip() and SkipWhile() result in an empty enumerable
    • Sum() is always 0
    • Take() and TakeWhile() result in an empty enumerable
    • ToArray(), ToList(), and ToDictionary() results can all be pre-sized to 0
    • ToLookup() can return a global, known empty, Lookup
    • Where() results in an empty enumerable
    • Zip() results in an empty enumerable
  • Range
    • Any() without a predicate just check the inner count
    • Count() and LongCount() just return the inner count
    • Distinct() with no comparer returns itself
    • ElementAt() and ElementAtOrDefault() are simple math ops
    • Contains() is a range check
    • First() and FirstOrDefault() return the starting element, if count > 0
    • Last() and LastOrDefault() are simple math ops
    • Max() is equivalent to Last()
    • Min() is equivalent to First()
    • Reverse() can return be optimized into a “ReverseRange” enumerable
    • SequenceEqual() against another range enumerable can just compare start and count
    • SequenceEqual() against a repeat enumerable is only true if count is 0 or 1
    • Single() and SingleOrDefault() just check against count and return start
    • Skip() advances start and reduces count
    • Take() reduces count
    • ToArray(), ToDictionary(), and ToList() can be pre-sized appropriately
  • Repeat
    • Any() without a predicate just check the inner count
    • Contains() just check against the inner object
    • Count() and LongCount() just return the inner count
    • Distinct() without a comparer returns a repeat enumerable with 0 or 1 items as appropriate
    • ElementAt() and ElementAtOrDefault() return the inner item
    • First() and FirstOrDefault() return the inner item
    • Last() and LastOrDefault() return the inner item
    • Max() and Min() return the inner item
    • SequenceEqual() against an empty enumerable is just a check against the inner count
    • SequenceEqual() against a range enumerable is only true if count is 0 or 1
    • SequenceEqual() against another repeat enumerable just checks for equality between the inner item and the inner count
    • Single() and SingleOrDefault() just check the inner count and return the inner item
    • Skip() is equivalent to reducing the inner count
    • Take() is equivalent to replacing the inner count
    • ToList() and ToArray() can be pre-sized appropriately

As mentioned in the above lists, LinqAF introduces a few new “kinds” of enumerables as optimizations.  Some of these actually exist behind the scenes in LINQ-to-Objects, but the IEnumerable<T> interface conceals that.  These new enumerables are:

  • EmptyOrdered
    • Representing an empty sequence that has been ordered
    • All the optimizations on Empty apply, except that Concat() calls with EmptyOrdered as a parameter cannot return EmptyOrdered – they return Empty if they would otherwise return EmptyOrdered
  • OneItemDefault
    • Represents a sequence that is known to only yield one value, and that value is default(T)
    • All() only checks against the single item
    • Any() without a predicate is always true
    • Contains() checks against the single item
    • Count() and LongCount() are always 1
    • Count() and LongCount() with predicates are 0 or 1, depending on the single item
    • DefaultIfEmpty() returns itself
    • ElementAt() throws if index is not 0, and always returns default(T) if it is
    • ElementAtOrDefault() always returns default(T)
    • First(), FirstOrDefault(), Last(), LastOrDefault(), Single(), and SingleOrDefault() all return default(T)
    • Reverse() returns itself
    • ToArray(), ToList(), and ToDictionary() can a be pre-sized to 1 item
    • OrderBy() and OrderByDescending() result in a special OneItemDefaultOrdered enumerable
  • OneItemSpecific
    • Represents a sequence that is known to only yield one value, but that value is determined at runtime
    • Has all the same optimizations as OneItemDefault, except the specified value is returned where appropriate and OrderBy() and OrderByDescending() result in a special OneItemSpecificOrdered enumerable
  • OneItem(Default|Specific)Ordered
    • Represents one of the OneItem enumerables that have been ordered
    • All the optimization on their paired OneItem enumerable apply, except that Concat() calls cannot return a OneItem(Default|Specific)Ordered – they return the paired unordered enumerable if they otherwise would
  • ReverseRange
    • Represents a Range that has been reversed – that is, it counts down from a value
    • All the optimizations on Range apply, except that calling Reverse() on a  ReverseRange results in a Range
  • SelectSelect
    • Represents repeated calls to Select() – this allows a single enumerator to handle the entire chain of calls
    • Select() results in yet another SelectSelect
    • Where() results in a SelectWhere
  • SelectWhere
    • Represents any number of  Select() calls followed by any number of Where() calls – this allows a single enumerator to handle the entire chain of calls
    • Where() results in a SelectWhere
  • WhereSelect
    • Represents any number of Where() calls followed by any number of Select() calls – this allows a single enumerator to handle the entire chain of calls
    • Select() results in a WhereSelect
  • WhereWhere
    • Represents repeated calls to Where() – this allows a single enumerator to handle the entire chain of calls
    • Select() results in a WhereSelect
    • Where() results in a WhereWhere

These gigantic lists are a pretty good demonstration of how many cases additional compile time typing lets us optimizes.

What’s next?

I’ll cover when LinqAF does allocate, why it does, and how you can provide your own allocator scheme to minimize the impact of those allocations.