Cistern.ValueLinq

In the tradition of Kevin Montrose's LinqAF, a version of Linq that has minimal allocations. (Another rendition on this there is @reegeek's StructLinq).

NOTE THAT THIS A WIP; NOT ALL OPERATORS ARE SUPPORTED (ALTHOUGH THEY ALL "WORK" BECAUSE THEY ARE PATCHED TO SYSTEM.LINQ)

So given that there area already a couple of version of a value based linq, what does this one bring to the table?

• Easy conversion from System.Linq (just change the using declaration)
• Different performance profile (there are winners and losers)
• Different memory usage profile (but zero allocations on many streams)
• Performance remains on execution even when stream is returned to an IEnumerable<> (but obviously this creates an allocation)
• Fast across all source lengths (i.e. no heavy creation phase)
• If you want to get ugly, performance can be close to hand written loops (and actually beat it sometimes. Huh? Say what? Run the example! Depends on input data, so I'm assuming just "luck" of branch prediction going in my favour, but would really love someone with skills to analyse assembly to debunk or confirm this)

Anyway, here is simple example which shows:

• faster than linq (and actually System.Linq is only as fast here because it "knows" about Select().Where() as a pattern, if we were to do a Select with an index, or even a Where().Select() then the performance of Linq is much worse. ValueLinq has no such special case, although it does support some optimizations for things like Last or Count)
• "the ugly" version is faster than the handcoded version!
• the handcoded requires knowledge of the underlying data-source, otherwise wouldn't be anywhere near as fast

        [Benchmark(Baseline = true)]
        public double Handcoded()
        {
            return _ints switch
            {
                int[] asArray => AsArray(asArray),
                _ => throw new NotSupportedException(),
            };

            static int AsArray(int[] asArray)
            {
                var max = int.MinValue;
                foreach (var n in asArray)
                {
                    var x = n / 2;
                    if ((x & 1) == 0)
                    {
                        if (x > max)
                            max = x;
                    }
                }
                return max;
            }
        }

OK; Pretty simple, the linq transform of this is:

        [Benchmark]
        public int Linq() =>
            _ints
            .Select(x => x / 2)
            .Where(x => (x & 1) == 0)
            .Max();

And, the Cistern.ValueLinq looks exactly the same:

        [Benchmark]
        public double CisternValueLinq_normal() =>
            _ints
            .Select(x => x / 2)
            .Where(x => (x & 1) == 0)
            .Max();

OK, and here is an example of the 'ugly' where we use value-type lambdas to perform the actions. These are pure functions. They could copy some state around, but lead to some perverse outcomes.

        struct HalveAnInt : IFunc<int, int> { public int Invoke(int t) => t / 2; } 
        struct FilterEvenInts : IFunc<int, bool> { public bool Invoke(int t) => (t & 1) == 0; }

And then we can use them in my new Linq as follows

        [Benchmark]
        public int CisternValueLinq_ValueFuncs() =>
            _ints
            .Select(new HalveAnInt(), default(int)) // ug, sugar please + better type inference...
            .Where(new FilterEvenInts()) // ug, sugar please
            .Max();

Notice that we have to supply the output type for the where (via default(int)) due to the way that c# handles type inference of generic arguments with constraints.

Now, the following doesn't exist, but I'm imagining you could have an additional syntax something like the following, where a >=> would create a value type IFunc used in the above example, and allow a layer of type-inference to do some magic. But hey, one can but dream:

        [Benchmark]
        public double CisternValueLinq_struct_in_dream_land() =>
            _ints
            .Select(t >=> t / 2)
            .Where(t >=> (t & 1) == 0)
            .Max();

And finally a "nothing up my sleave" version that seemly switches between the value type representation and the IEnumerable<> for an example of the trivial interop with existing code. It also shows that segments created in different parts can all be just put together with an Aggregating function, and hence all the magic that ties together everything at runtime.

        [Benchmark]
        public double CisternValueLinq_struct_nothing_up_my_sleve()
        {
            IEnumerable<int> collection = GetCollection();
            IEnumerable<int> andSelect = AddSelect(collection);
            IEnumerable<int> withWhere = AddWhere(andSelect);

            var result = andSelect.Max();

            return result;

            IEnumerable<int> GetCollection() => _ints;
            IEnumerable<int> AddSelect(IEnumerable<int> stuff) => stuff.Select(x => x / 2);
            IEnumerable<int> AddWhere(IEnumerable<int> stuff) => stuff.Where(x => (x & 1) == 0);
        }