/Relinq

Relatively Efficient Linq

Primary LanguageC#Apache License 2.0Apache-2.0

Purpose

This package is intended for situations where you want Linq functionality in situations where it's undesirable to create garbage (i.e. during gameplay).

Usage

  • Unity
    • Add "com.github.legocylon.relinq": "https://github.com/LegoCylon/Relinq.git", to the manifest.json file in your project's Packages folder.
    • After Unity imports the package, it will add a lock section with the package name (com.github.legocylon.relinq) pinning you to the latest master commit SHA for the package on github. If you want to update to a newer version, delete the lock section for this package or manually update the SHA to the version you want to use.
    • Note: If IL2CPP is enabled for your project, you'll want to set the managed code stripping level to Medium or higher since IL2CPP pessimistically generates every permutation of all generic value types (which can quickly get out of control). A higher level of stripping will limit the generic sharing permutations to what you're actually using.
    • Managed Code Stripping Project Settings
  • C#
    • Add using Relinq; to each file you want to be able to use one of the methods above.
    • At each callsite that you prefer to use Relinq rather than Linq, call .AsEnumerable() to convert enumerables into EnumerableAdapter<TEnumerator, TSource> instances. It's intentional that the name AsEnumerable conflicts with another Linq method of the same name - to help reinforce that mixing calls to both libraries is going to result in heap allocations when Linq is used by mistake.

Avoid explicitly referencing algorithm-specific enumerators where possible. They would be internal if it wasn't necessary for them to be instantiated at the callsite.

Supported Enumerables

Unsupported Enumerables

The following enumerables were omitted because their enumerators generate garbage since they're implemented as coroutines:

The following enumerables were omitted because their enumerators generate garbage since they're implemented as a stack-based tree traversals:

The following enumerables were omitted because their enumerators box and don't support indexers (which would allow implementing a non-boxing enumerator like we've done for IList and IReadOnlyList).

Supported Linq-like Algorithms

  • Aggregate
  • All
  • Any
  • Append
  • Cast
  • Concat
  • Contains
  • Count
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting, otherwise O(N).
  • DefaultIfEmpty
  • ElementAt
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • ElementAtOrDefault
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • Empty
  • First
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • FirstOrDefault
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • Last
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • LastOrDefault
    • The predicate-less overload has O(1) complexity if the enumerable supports O(1) counting and indexing, otherwise O(N).
  • Max
  • Min
  • OfType
    • Suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • Prepend
  • Range
  • Repeat
  • Select
    • The predicate-less overload suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • SelectMany
    • The predicate-less overload suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • SequenceEqual
  • Single
  • SingleOrDefault
  • Skip
  • SkipWhile
    • Suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • Take
  • TakeWhile
    • Suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • ToList
  • Where
    • Suppresses O(1) counting and indexing (due to its conditional nature) for subsequent operations on this enumerable.
  • Zip

Additional Algorithms

  • int? EnumerableAdapter<TSource>.Mismatch<TSecondEnumerator> (EnumerableAdapter<TSecondEnumerator, TSource> second)
    • Returns the nullable index of the first mismatch between the current enumerable and a second enumerable.
    • If no elements mismatch, then the nullable has no value.
    • Uses the default equality comparer for TSource.
  • int? EnumerableAdapter<TSource>.Mismatch<TSecondEnumerator> (EnumerableAdapter<TSecondEnumerator, TSource> second, IEqualityComparer<TSource> comparer)
    • Returns the nullable index of the first mismatch between the current enumerable and a second enumerable.
    • If no elements mismatch, then the nullable has no value.
    • If comparer is null, it uses the default equality comparer for TSource.
  • bool EnumerableAdapter<TSource>.None ()
    • Returns true when the enumerable is empty.
  • bool EnumerableAdapter<TSource>.None (Func<TSource, bool> predicate)
    • Returns true if all calls to the predicate (one per element in the enumerable) returns false.
  • EnumerableAdapter<RangeEnumerator<TEnumerator, TSource>, TSource> Range<TSource> (TSource start, int count, Func<TSource, int, TSource> generator)
    • A generalized implementation of the standard Range algorithm with support for any type and method of generation via the generator.
  • EnumerableAdapter<ReplaceEnumerator<TEnumerator, TSource>, TSource> EnumerableAdapter<TSource>.Replace (TSource what, TSource with)
    • Returns an enumerable which will substitute with for all instances of what in the original enumerable.
  • void EnumerableAdapter<TSource>.ToList (List<TSource> results)
    • Converts the enumerable into the provided results list instance. Existing contents are not preserved.

Unsupported Algorithms

The following algorithms were omitted because they rely on converting the enumerables to sets or dictionaries for efficient execution:

Average and Sum weren't implemented because they have a ton of overloads, were outside my original use case, and can be implemented in terms of Aggregate.

Implementation Details

The algorithms use stack memory embedded in value type structs to maintain state rather than heap memory. While this avoids generating garbage, it will require additional stack memory for most algorithms which can get expensive as they are nested. It also relies on a cardinal sin for C# - mutable value types (for the enumerators). However, since the enumerators for Dictionary, HashSet, LinkedList, and List already do that it seemed like a reasonable compromise.

The value type enumerables use duck typing to facilitate foreach support rather than implementing IEnumerable or IEnumerator. This helps to avoid accidentally creating garbage when trying to pass the enumerables around.

Although most of the algorithms themselves (with unavoidable exceptions like ToList) don't generate heap allocations, you may still generate them at the callsite if state is captured from the callsite (i.e. via a lambda closure). Consider using a local function where possible to reduce the cost of capturing.