Skip to content

Linq-like extension functions for Arrays, Span<T>, and List<T> that are faster and allocate less.

License

Notifications You must be signed in to change notification settings

jackmott/LinqFaster

Repository files navigation

Build Status

LinqFaster

Logo

A set of Linq-Like extension methods for arrays[], Span<T>, and List<T> that are faster and allocate less. LinqFaster is designed to work well alongside Linq, rather than replace it completely. Extension method names mirror Linq names with an extra character, e.g. SelectF. If you have code that is often doing small Linq operations and immediatelly calling ToArray() or ToList(), or you are often using Min,Max,Sum,Average,or Aggregate, LinqFaster may provide massive cpu and memory usage reductions. See the documentation section below for more details.

LinqFaster now includes all relevant Linq extension methods, and many SIMD and Parallel enhanced extension methods are available as well in separate projects and nuget packages. The projects have no dependencies on each other so you can pick and choose at will.

The base LinqFaster project is now compatible with Unity3D

Sample Benchmarks

64bit Win 10, 2 Core I7 Mobile

Method TEST_SIZE Mean Allocated
OrderByLinq 100000 24,436.0135 us 1.2 MB
OrderByFast 100000 5,612.7712 us 802.1 kB
MinLinq 100000 548.9181 us 48 B
MinFast 100000 69.2122 us 0 B
MinFastSIMD 100000 14.5291 us 0 B
SumLinq 100000 541.3823 us 48 B
SumFast 100000 53.8166 us 0 B
SumFastSIMD 100000 9.7636 us 0 B
SumFastSIMDParallel 100000 3.7074 us 1.11 kB

More detailed info and benchmarks available in the benchmarks file which will be continually updated.

Features

  • SIMD enhanced array operations
  • ⬇️ Execution time
  • ⬇️ GC churn
  • ⬆️ Battery life
  • ⬇️ Sever farm costs
  • ⬇️ Co2 output
  • ⬇️ Electricity bill
  • ⬆️ L1 cache hits
  • ⬆️ FPS!

Documentation

As well, all functions are properly documented so as to be explorable via intellisense.

LinqFaster

	using JM.LinqFaster;
	
	
	//Create an array of ints with values -500 to 500
	var myArray = LinqFaster.RangeArrayF(-500, 1000);
	//Create a List<T> with 1000 elements all set to 5.0
	var myList = LinqFaster.RepeatListF(5.0, 1000);

	//Compute sum, average, max,min
	var sum = myArray.SumF();
	var average = myArray.AverageF();
	var min = myArray.MinF();
	var max = myArray.MaxF();
	
	// Compute the sum of a slice of your array using Span<T>
	// LinqFaster includes a handy extension method to make slices easier
	var sliceSum = myArray.Slice(10,20).SumF();

	//As above but on a transformation
	var sum2 = myArray.SumF(x => x*x);
	var average2 = myArray.AverageF(x => x*x);
	var min2 = myArray.MinF(x => x*x);
	var max2 = myArray.MaxF(x => x*x);

	//Do a where and a select or select and where in a single pass
	var newArray = myArray.WhereSelectF(x => x % 2 == 0,x=>x*x);
	var newArray2 = myArray.SelectWhereF(x => x * x,x => x % 2 == 0);

	//Compute the sum of only the even values in a single pass
	var filteredSum = myArray.WhereAggregateF(x => x % 2 == 0, (acc, x) => acc + x);

	//New in-place methods are provided where appropriate
	myArray.SelectInPlaceF(x => x * x);
	myArray.ReverseInPlaceF();

LinqFaster.SIMD

See MSDN documentation on System.Numerics.Vectors for more detail on SIMD in C#.

using JM.LinqFaster.SIMD;

// SIMD extension methods are only available for arrays
// SIMD functions all have an S at the end, for clarity
// and to avoid naming collisions.

var myArray = LinqFaster.RangeS(-500, 500);

// Some operations work identically to their scalar
// counterparts,but faster, as long as the machine has 
// SIMD hardware.

var sum = myArray.SumS();
bool b = myArray.ContainsS(5);
var max = myArray.MaxS();

// Floating point math is not commutative, so the results
// of operations such as Sum and Average may differ slightly.
// Accuracy is usually better.

Console.WriteLine(myFloats.SumS() == myFloats.SumF()); // --> False!

// When using selectors, you must provide one that operates on
// Vector<T>. Optionally, you may provide a second selector
// that operates on T to handle elements that are left over, 
// when your array is not evenly divisible by the Vector width.

// When there will be no leftovers
var sum = myArray.SumS( x => x*x );   // Vector<T> has overrides for *, + etc

// When there will be leftovers
var sum = myArray.SumS(x=>x*x, x=>x*x); 

// As with the regular LinqFaster project, SIMD includes
// in place versions when appropriate:

myArray.SelectInPlaceS( v => v + new Vector(1));

LinqFaster.Parallel

using JM.LinqFaster.Parallel;

// Parallel extension methods are all named with a P 
// at the end.

var sum = myList.SumP();

// Floating point math is not commutative, so the results
// of operations such as Sum and Average may differ slightly.
// Accuracy is usually better.

Console.WriteLine(myFloats.SumP() == myFloats.SumF()); // --> False!

// In some cases, unordered versions of a function are provided for
// better performance

myList.SelectUnorderedP(x => x*x);  

// All parallel functions have an optional batch size, which
// defines how many elements are operated on per task/thread.
// This can be tuned for performance.

myArray.Select(x=>x*x,myArray.Length/10);  //split the array into 10 ranges
myArray.Select(x=>x*x,10000); // split the array into ranges of 10,000 elements each

// Parallel functions cause some allocations, and requires care in their use, as they 
// may not be faster than scalar or SIMD versions depending on the workload and
// hardware available.

LinqFaster.SIMD.Parallel

See MSDN documentation on System.Numerics.Vectors for more detail on SIMD in C#.

using LingFaster.SIMD.Parallel

// These functions combine SIMD acceleration and multithreading.
// They are all named with an SP at the end, and are available
// only for arrays.

var sum = myArray.SumSP();

// Floating point math is not commutative, so the results
// of operations such as Sum and Average may differ slightly.
// Accuracy is usually better.

Console.WriteLine(myFloats.SumSP() == myFloats.SumF()); // --> False!

// All SIMD parallel functions have an optional batch size, which
// defines how many elements are operated on per task/thread.
// This can be tuned for performance.

myArray.AverageSP(myArray.Length/10);  //split the array into 10 ranges
myArray.SelectSP(x=>x*x,10000); // split the array into ranges of 10,000 elements each


// SIMD operations are already very fast, so combining them with 
// multiple threads will only be worthwhile for large arrays and/or
// for very expensive operations.

Limitations

These are purely imperative implementations of the same higher order functions that Linq provides, but unlike Linq they are not lazily evaluated. This means that when chaining functions together such as:

var a = data.Where(predicate).Select(transform).Aggregate(foo);
//or
var b = data.Select(selector).Sum();

Linq would not do any work until the calls to Sum() or Aggregate(), and thus iterate over the collection only once and allocate very little. LinqFaster used this way would iterate over the collection each time and allocate much more. Sometimes the net result will still be faster overall but the better approach is to use the combined LinqFaster operations such as SelectWhere, WhereSelect, and WhereAggregate. For example the expressions above would become:

var a = data.WhereAggregate(predicate,transform,foo);
// and
var b = data.Sum(selector);

This gets you the best of both worlds. The speed of memory locality and no allocations at all. In short, think about how you are transforming your data. In some cases normal Linq may be the better choice.

While most of the functions strive to provide indentical results to Linq, the OrderBy methods are not a stable sort, while in Linq they are.