Aggregate vs Sum Performance in LINQ

Question

Three different implementations of finding the sum of an IEnumerable < int> source are given below along with the time taken when the source has 10,000 integers.

source.Aggregate(0, (result, element) => result + element);  

takes 3 ms

source.Sum(c => c);

takes 12 ms

source.Sum();

takes 1 ms

I am wondering why the second implementation is four times more expensive than the first one. Shouldn't it be same as the third implementation.

Whim

What are your test conditions ? – Rachaba

how did you get these times? How many time did you try the results? – Jara

I profiled it using dotTrace. I ran it once, but the three runs are independent. – Whim

try to run each test in a loop, this remove all the times taken for jitting and so on, the test will be more accurate. – Jara

The results remain same after couple of runs also. – Whim

Are you running this under x86 or x64? Can you try the other one? – Somatotype

Answer 1

Note: My computer is running .Net 4.5 RC, so it's possible that my results are affected by this.

Measuring the time it takes to execute a method just once is usually not very useful. It can be easily dominated by things like JIT compilation, which are not actual bottlenecks in real code. Because of this, I measured executing each method 100× (in Release mode without debugger attached). My results are:

• Aggregate(): 9 ms
• Sum(lambda): 12 ms
• Sum(): 6 ms

The fact that Sum() is the fastest is not surprising: it contains a simple loop without any delegate invocations, which is really fast. The difference between Sum(lambda) and Aggregate() is not nearly as prominent as what you measured, but it's still there. What could be the reason for it? Let's look at decompiled code for the two methods:

public static TAccumulate Aggregate<TSource, TAccumulate>(this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func)
{
    if (source == null)
        throw Error.ArgumentNull("source");
    if (func == null)
        throw Error.ArgumentNull("func");

    TAccumulate local = seed;
    foreach (TSource local2 in source)
        local = func(local, local2);
    return local;
}

public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector)
{
    return source.Select<TSource, int>(selector).Sum();
}

As you can see, Aggregate() uses a loop but Sum(lambda) uses Select(), which in turn uses an iterator. And using an iterator means there is some overhead: creating the iterator object and (probably more importantly) one more method invocation for each item.

Let's verify that using Select() is actually the reason by writing our own Sum(lambda) twice, once using Select(), which should behave the same as Sum(lambda) from the framework, and once without using Select():

public static int SlowSum<T>(this IEnumerable<T> source, Func<T, int> selector)
{
    return source.Select(selector).Sum();
}

public static int FastSum<T>(this IEnumerable<T> source, Func<T, int> selector)
{
    if (source == null)
        throw new ArgumentNullException("source");
    if (selector == null)
        throw new ArgumentNullException("selector");

    int num = 0;
    foreach (T item in source)
        num += selector(item);
    return num;
}

My measurements confirm what I thought:

• SlowSum(lambda): 12 ms
• FastSum(lambda): 9 ms

Somatotype

Very insightful. Thanks for the detailed response. – Whim

This is one of the best answers I've seen on SO, perfectly explained and well crafted. (+1 obviously) – Featureless

foreach will also create an iterator so I don't think this explanation is correct. – Biocatalyst

@Biocatalyst I believe what I meant is that it creates an additional iterator. With Aggregate(), there is only the iterator used by foreach. But with this implementation of Sum(lambda), there is one iterator used by Select and one used by Sum(). – Somatotype

Answer 2

Only a decade late, but...

I've worked on a Linq replacement (nuget, github), which is (mostly!) a drop in replacement for System.Linq (just by adding the nuget package and then changing using System.Linq to using Cistern.ValueLinq) but using value types and some tricks under the hood.

Anyway, as far as Sum goes, it uses SIMD instructions under the hood (still honouring overflow) where it can.

Results below are running on a machine which is old as this original stackoverflow question, so modern machines should even have better results (although for a non SIMD able IEnumerable you do are getting some overhead)

public enum ContainerTypes { Enumerable, Array, List, }

[MemoryDiagnoser]
public class Benchmarks
{
    IEnumerable<int> _data;

    [Params(ContainerTypes.Array, ContainerTypes.Enumerable, ContainerTypes.List)]
    public ContainerTypes ContainerType { get; set; } = ContainerTypes.Enumerable;

    [GlobalSetup]
    public void SetupData()
    {
        var data = System.Linq.Enumerable.Range(0, 1000);
        _data = ContainerType switch
        {
            ContainerTypes.Enumerable => data,
            ContainerTypes.Array => System.Linq.Enumerable.ToArray(data),
            ContainerTypes.List => System.Linq.Enumerable.ToList(data),
            _ => throw new Exception("Unknown ContainerType")
        };
    }

    [Benchmark(Baseline = true)] public int System_Linq_Sum() => System.Linq.Enumerable.Sum(_data);
    [Benchmark] public int System_Linq_Sum_Predicate() => System.Linq.Enumerable.Sum(_data, c => c);
    [Benchmark] public int System_Linq_Aggregate() => System.Linq.Enumerable.Aggregate(_data, 0, (result, element) => result + element);
    [Benchmark] public int Cistern_ValueLinq_Sum() => Cistern.ValueLinq.Enumerable.Sum(_data);
    [Benchmark] public int Cistern_ValueLinq_Sum_Predicate() => Cistern.ValueLinq.Enumerable.Sum(_data, c => c);
    [Benchmark] public int Cistern_ValueLinq_Aggregate() => Cistern.ValueLinq.Enumerable.Aggregate(_data, 0, (result, element) => result + element);

    static void Main(string[] args) => BenchmarkRunner.Run<Benchmarks>();
}

Method	ContainerType	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen 0	Gen 1	Gen 2	Allocated
System_Linq_Sum	Enumerable	6.025 us	0.1155 us	0.1501 us	6.041 us	1.00	0.00	0.0076	-	-	40 B
System_Linq_Sum_Predicate	Enumerable	8.731 us	0.1727 us	0.3681 us	8.742 us	1.45	0.08	-	-	-	40 B
System_Linq_Aggregate	Enumerable	8.534 us	0.1683 us	0.3514 us	8.657 us	1.42	0.07	-	-	-	40 B
Cistern_ValueLinq_Sum	Enumerable	6.907 us	0.1369 us	0.3061 us	6.911 us	1.15	0.07	0.0076	-	-	40 B
Cistern_ValueLinq_Sum_Predicate	Enumerable	9.769 us	0.1907 us	0.1784 us	9.823 us	1.62	0.04	-	-	-	40 B
Cistern_ValueLinq_Aggregate	Enumerable	9.295 us	0.1847 us	0.4962 us	9.396 us	1.52	0.08	-	-	-	40 B
System_Linq_Sum	Array	6.731 us	0.1343 us	0.3653 us	6.814 us	1.00	0.00	0.0076	-	-	32 B
System_Linq_Sum_Predicate	Array	9.432 us	0.1873 us	0.5065 us	9.685 us	1.41	0.11	-	-	-	32 B
System_Linq_Aggregate	Array	9.494 us	0.1890 us	0.4707 us	9.759 us	1.41	0.11	-	-	-	32 B
Cistern_ValueLinq_Sum	Array	1.404 us	0.0279 us	0.0710 us	1.436 us	0.21	0.02	-	-	-	-
Cistern_ValueLinq_Sum_Predicate	Array	4.064 us	0.0811 us	0.0996 us	4.087 us	0.61	0.04	-	-	-	-
Cistern_ValueLinq_Aggregate	Array	3.549 us	0.0709 us	0.1496 us	3.584 us	0.53	0.04	-	-	-	-
System_Linq_Sum	List	11.779 us	0.2344 us	0.3048 us	11.854 us	1.00	0.00	-	-	-	40 B
System_Linq_Sum_Predicate	List	14.227 us	0.2842 us	0.6919 us	14.601 us	1.22	0.05	-	-	-	40 B
System_Linq_Aggregate	List	13.852 us	0.2761 us	0.7418 us	14.249 us	1.17	0.06	-	-	-	40 B
Cistern_ValueLinq_Sum	List	1.437 us	0.0288 us	0.0835 us	1.471 us	0.12	0.01	-	-	-	-
Cistern_ValueLinq_Sum_Predicate	List	3.672 us	0.0732 us	0.1941 us	3.771 us	0.32	0.02	-	-	-	-
Cistern_ValueLinq_Aggregate	List	3.597 us	0.0718 us	0.1880 us	3.698 us	0.31	0.02	-	-	-	-

Cleavable

Are you using the Vector.IsHardwareAccelerated property, to avoid using SIMD when not available? – Yeeyegg

It is used github.com/manofstick/Cistern.ValueLinq/blob/… are you saying that it doesn't work properly? – Cleavable

No, AFAIK it works correctly. I am just wondering whether you query this property in order to fall back to normal LINQ operators, in case the current machine does not support SIMD. Because in that case the SIMD operations are simulated, and the performance suffers. – Yeeyegg