List Extensions

ListExtensions.cs

/*
// * Summary *

BenchmarkDotNet=v0.13.0, OS=Windows 10.0.19042.1052 (20H2/October2020Update)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
.NET SDK=6.0.100-preview.4.21255.9
  [Host]     : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT
  DefaultJob : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT


|            Method |        Mean |     Error |    StdDev |
|------------------ |------------:|----------:|----------:|
|        WrapperArr |    58.19 ns |  0.954 ns |  0.796 ns |
|       WrapperList |    56.58 ns |  1.151 ns |  0.898 ns |
|  WrapperImmutable |   149.55 ns |  2.326 ns |  2.176 ns |
|       ExplicitArr |   171.86 ns |  2.950 ns |  2.615 ns |
|      ExplicitList | 1,925.37 ns | 30.796 ns | 27.300 ns |
| ExplicitImmutable | 2,468.93 ns | 37.708 ns | 35.272 ns |
|        GeneralArr |   123.16 ns |  2.436 ns |  2.607 ns |
|       GeneralList |   118.84 ns |  2.306 ns |  2.368 ns |
|  GeneralImmutable |   517.53 ns | 10.105 ns |  9.452 ns |

// * Hints *
Outliers
  Program.WrapperArr: Default       -> 2 outliers were removed (67.58 ns, 68.52 ns)
  Program.WrapperList: Default      -> 3 outliers were removed (63.15 ns..71.78 ns)
  Program.WrapperImmutable: Default -> 1 outlier  was  detected (146.24 ns)
  Program.ExplicitArr: Default      -> 1 outlier  was  removed (203.42 ns)
  Program.ExplicitList: Default     -> 1 outlier  was  removed, 2 outliers were detected (1.86 us, 1.99 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 ns   : 1 Nanosecond (0.000000001 sec)

// ***** BenchmarkRunner: End *****
// ** Remained 0 benchmark(s) to run **
Run time: 00:02:24 (144.17 sec), executed benchmarks: 9

Global total time: 00:02:28 (148.55 sec), executed benchmarks: 9
*/

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

#nullable enable

namespace MyBenchmarks {

    public class ListExtensions<T> {
        public readonly IList<T> List;

        public delegate int FBinarySearch(int index, int count, T value, IComparer<T>? comparer);
        public readonly FBinarySearch BinarySearch;

        public delegate void FRemoveRange(int index, int count);
        public readonly FRemoveRange RemoveRange;

        public ListExtensions(IList<T> list) {
            List = list;

            FBinarySearch? binarySearch = null;
            if (list is Array arr) {
                binarySearch = (index, count, value, cmp) => Array.BinarySearch(arr, index, count, value, cmp is null ? null : Comparer<T>.Create(cmp.Compare));
            }
            else {
                var func = list.GetType().GetMethod("BinarySearch", new Type[] { typeof(int), typeof(int), typeof(T), typeof(IComparer<T>) });
                if (func != null)
                    binarySearch = (FBinarySearch?)Delegate.CreateDelegate(typeof(FBinarySearch), list, func, throwOnBindFailure: false);
            }
            if (binarySearch == null)
                binarySearch = (index, count, value, cmp) => GeneralBinarySearch(list, index, count, value, cmp);
            BinarySearch = binarySearch;

            FRemoveRange? removeRange = null;
            {
                var func = list.GetType().GetMethod("RemoveRange", new Type[] { typeof(int), typeof(int) });
                if (func != null)
                    removeRange = (FRemoveRange?)Delegate.CreateDelegate(typeof(FRemoveRange), list, func, throwOnBindFailure: false);
            }
            if (removeRange == null)
                removeRange = (index, count) => GeneralRemoveRange(list, index, count);
            RemoveRange = removeRange;
        }

        public static int GeneralBinarySearch(IList<T> list, int index, int lenght, T value, IComparer<T>? comparer = null) {
            comparer ??= Comparer<T>.Default;
            int lower = index;
            int upper = index + lenght - 1;
            while (lower <= upper) {
                int middle = lower + (upper - lower) / 2;
                int comparisonResult = comparer.Compare(value, list[middle]);
                if (comparisonResult == 0)
                    return middle;
                else if (comparisonResult < 0)
                    upper = middle - 1;
                else
                    lower = middle + 1;
            }
            return ~lower;
        }

        public static void GeneralRemoveRange(IList<T> list, int index, int count) {
            while (count-- > 0)
                list.RemoveAt(index + count);
        }
    }

    public class Program {
        const int NumElements = 100000;
        readonly Random _rand = new();
        readonly int[] _arr = new int[NumElements];
        readonly List<int> _list;
        readonly ImmutableList<int> _imm;
        readonly ListExtensions<int> _extArr, _extList, _extImm;
        readonly int _lookupValue;

        public Program() {
            for (int i = 0; i < NumElements; ++i)
                _arr[i] = _rand.Next();
            Array.Sort(_arr);
            _list = _arr.ToList();
            _imm = _arr.ToImmutableList();
            
            _extArr = new ListExtensions<int>(_arr);
            _extList = new ListExtensions<int>(_list);
            _extImm = new ListExtensions<int>(_imm);

            _lookupValue = _arr[1];
        }

        [Benchmark] public int WrapperArr() => _extArr.BinarySearch(0, NumElements, _lookupValue, null);
        [Benchmark] public int WrapperList() => _extList.BinarySearch(0, NumElements, _lookupValue, null);
        [Benchmark] public int WrapperImmutable() => _extImm.BinarySearch(0, NumElements, _lookupValue, null);

        [Benchmark] public int ExplicitArr() => new ListExtensions<int>(_arr).BinarySearch(0, NumElements, _lookupValue, null);
        [Benchmark] public int ExplicitList() => new ListExtensions<int>(_list).BinarySearch(0, NumElements, _lookupValue, null);
        [Benchmark] public int ExplicitImmutable() => new ListExtensions<int>(_imm).BinarySearch(0, NumElements, _lookupValue, null);

        [Benchmark] public int GeneralArr() => ListExtensions<int>.GeneralBinarySearch(_arr, 0, NumElements, _lookupValue, null);
        [Benchmark] public int GeneralList() => ListExtensions<int>.GeneralBinarySearch(_list, 0, NumElements, _lookupValue, null);
        [Benchmark] public int GeneralImmutable() => ListExtensions<int>.GeneralBinarySearch(_imm, 0, NumElements, _lookupValue, null);


        public static void Main() =>
            BenchmarkRunner.Run<Program>();
    }
}