LinqOptimizer

An automatic query optimizer-compiler for Sequential and Parallel LINQ. LinqOptimizer compiles declarative LINQ queries into fast loop-based imperative code. The compiled code has fewer virtual calls and heap allocations, better data locality and speedups of up to 15x (Check the Performance page).

The main idea is that we lift query sources into the world of Expression trees and after various transformations-optimizations we compile them into IL for efficient execution.

var query = (from num in nums.AsQueryExpr() // lift
             where num % 2 == 0
             select num * num).Sum();

Console.WriteLine("Result: {0}", query.Run()); // compile and execute

For F# we support functional pipelines and support for F# style LINQ queries is in development.

1: 
2: 
3: 
4: 
5: 
6: 
7:

let query = nums
            |> Query.ofSeq
            |> Query.filter (fun num -> num % 2 = 0)
            |> Query.map (fun num -> num * num)
            |> Query.sum

printfn "Result: %d" <| Query.run query // compile and execute

Get LinqOptimizer via NuGet

LinqOptimizer can be installed from NuGet:

PM> Install-Package LinqOptimizer.CSharp
PM> Install-Package LinqOptimizer.FSharp

Optimizations

Lambda inlining
Loop fusion
Nested loop generation
Anonymous Types-Tuples elimination
Specialized strategies and algorithms

The expression

var query = (from num in nums.AsQueryExpr()
             where num % 2 == 0
             select num * num).Sum();

will compile to

int sum = 0;
for (int index = 0; index < nums.Length; index++)
{
   int num = nums[index];
   if (num % 2 == 0)
      sum += num * num;
}

and for the parallel case

var query = (from num in nums.AsParallelQueryExpr()
             where num % 2 == 0
             select num * num).Sum();

will compile to a reduce-combine style strategy

Parallel.ReduceCombine(nums, 0, 
                          (acc, num) => { 
                                       if (num % 2 == 0)  
                                         return acc + num * num; 
                                       else
                                         return acc; 
                          }, (left, right) => left + right);

Future work

Many missing operators
New specialized operators
Even more optimizations

References

LinqOptimizer draws heavy inspiration from

Contributing and copyright

The project is hosted on GitHub where you can report issues, fork the project and submit pull requests.

The library is available under the Apache License. For more information see the License file in the GitHub repository.

val query : obj

Full name: index.query

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn