Why is Linq slower?

[paululvinius]

Hi!

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

public List<ConferenceRoomOldWay(int minimumSeatingCapacity)
{
List<ConferenceRoomavailableRooms = new List<ConferenceRoom>();

foreach (ConferenceRoom room in rooms)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
availableRooms.Add(room);
}

return availableRooms;
}

public List<ConferenceRoomNewWay(int minimumSeatingCapacity)
{
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

PS.
Just did a plain and simple:

DateTime start = DateTime.Now;
for (int i = 0; i < 1000000; i++)
rooms.OldWay(8);

Console.WriteLine((DateTime.Now - start).Ticks);

....to mesaure the performance (Did repeate the test over and over).

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

Why is Linq slower?

Thanks
/Paul

[Jeroen]

Results:

Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

What am I missing here? Less ticks actually means it's faster, right?

-Jeroen

[=?Utf-8?B?UGF1bA==?=]

Sorry mixed the results:

Results:
Linq: ca. 6 300 000 ticks
Non-Linq: ca. 3 100 000

"pa**********@hotmail.com" wrote:

Hi!

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

public List<ConferenceRoomOldWay(int minimumSeatingCapacity)
{
List<ConferenceRoomavailableRooms = new List<ConferenceRoom>();

foreach (ConferenceRoom room in rooms)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
availableRooms.Add(room);
}

return availableRooms;
}

public List<ConferenceRoomNewWay(int minimumSeatingCapacity)
{
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

PS.
Just did a plain and simple:

DateTime start = DateTime.Now;
for (int i = 0; i < 1000000; i++)
rooms.OldWay(8);

Console.WriteLine((DateTime.Now - start).Ticks);

....to mesaure the performance (Did repeate the test over and over).

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

Why is Linq slower?

Thanks
/Paul

[=?Utf-8?B?UGF1bA==?=]

Sorry, just posted a reply saying that I mixed the results.

Its supposed to be vice-verca.

thanks

"Jeroen" wrote:

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

What am I missing here? Less ticks actually means it's faster, right?

-Jeroen

[Jon Skeet [C# MVP]]

On Jan 30, 3:22 pm, [e-mail] wrote:

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

It's probably due to the overhead in calling the delegate.

The question is whether it's actually significant. Is this a
performance bottleneck for you? Is the extra third of a second for a
million iterations going to hurt you?

Jon

[Willy Denoyette [MVP]]

<pa**********@hotmail.comwrote in message
news:c4**********************************@b2g2000h sg.googlegroups.com...

Hi!

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

public List<ConferenceRoomOldWay(int minimumSeatingCapacity)
{
List<ConferenceRoomavailableRooms = new List<ConferenceRoom>();

foreach (ConferenceRoom room in rooms)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
availableRooms.Add(room);
}

return availableRooms;
}

public List<ConferenceRoomNewWay(int minimumSeatingCapacity)
{
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

PS.
Just did a plain and simple:

DateTime start = DateTime.Now;
for (int i = 0; i < 1000000; i++)
rooms.OldWay(8);

Console.WriteLine((DateTime.Now - start).Ticks);

...to mesaure the performance (Did repeate the test over and over).

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

Why is Linq slower?

Thanks
/Paul

Impossible to tell, unless you post the whole code.

Willy.

[Nicholas Paldino [.NET/C# MVP]]

Paul,

In addition to the other comments, you have to remember that when you
perform the call to ToList, which will ultimately iterate through your
query, you are calling three implementations of the methods on
IEnumerable<T>.

The first is in the original implementation of IEnumerable<Ton rooms.

The second is in the call to the Where extension method, which returns
an IEnumerable<Twhich calls the original enumerator and applies the filter
(it is applied in the MoveNext implementation of the IEnumerable<T>
returned).

The last is the call to the Select extension method, which performs the
transformation (if there is one), but still calls through to the IEnumerable
returned by the Where extension method.

The more you filter/transform/sort/any other operation, the larger the
composition of IEnumerable<Timplementations that you are making. It is
going to affect performance in some way.

And of course, as Jon mentioned, every separate were clause is going to
add another anonymous method, and there is some overhead in calling a
delegate as opposed to a direct method call.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

<pa**********@hotmail.comwrote in message
news:c4**********************************@b2g2000h sg.googlegroups.com...

Hi!

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

public List<ConferenceRoomOldWay(int minimumSeatingCapacity)
{
List<ConferenceRoomavailableRooms = new List<ConferenceRoom>();

foreach (ConferenceRoom room in rooms)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
availableRooms.Add(room);
}

return availableRooms;
}

public List<ConferenceRoomNewWay(int minimumSeatingCapacity)
{
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

PS.
Just did a plain and simple:

DateTime start = DateTime.Now;
for (int i = 0; i < 1000000; i++)
rooms.OldWay(8);

Console.WriteLine((DateTime.Now - start).Ticks);

...to mesaure the performance (Did repeate the test over and over).

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

Why is Linq slower?

Thanks
/Paul

[=?Utf-8?B?UGF1bA==?=]

Interesting. Thank you guys for the info. Just started to dig into this,
after have just red some conceptual info.

Regards
Paul

"pa**********@hotmail.com" wrote:

Hi!

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one is
twice as fast.

public List<ConferenceRoomOldWay(int minimumSeatingCapacity)
{
List<ConferenceRoomavailableRooms = new List<ConferenceRoom>();

foreach (ConferenceRoom room in rooms)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
availableRooms.Add(room);
}

return availableRooms;
}

public List<ConferenceRoomNewWay(int minimumSeatingCapacity)
{
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

PS.
Just did a plain and simple:

DateTime start = DateTime.Now;
for (int i = 0; i < 1000000; i++)
rooms.OldWay(8);

Console.WriteLine((DateTime.Now - start).Ticks);

....to mesaure the performance (Did repeate the test over and over).

Results:
Non-Linq: ca. 6 300 000 ticks
Linq: ca. 3 100 000

Why is Linq slower?

Thanks
/Paul

[Frans Bouma [C# MVP]]

Jon Skeet [C# MVP] wrote:

On Jan 30, 3:22 pm, [e-mail] wrote:

Testing som Linq-expressions and tried to measure performance and
compare it to pre-Linq programming.

The folloing two methods are functional equal but the non-Linq one
is twice as fast.

It's probably due to the overhead in calling the delegate.

I tested this for a library I'm writing and accessing a property
through a lambda or accessing the property directly and accessing it
through a lambda is roughly 5 times slower. (but still fast, 8ms
(direct access) vs 40ms through the lambda, release builds, 1 million
calls)

Considering the difference in times, roughly twice the speed, it might
be that the lambda indeed is the bottleneck, though there have been
found other bottlenecks in Linq to object's code (concat is O(n^2) for
example according to a recent bugreport) so I wouldn't be surprised if
it is due to something else.

FB
--
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------

[Frans Bouma [C# MVP]]

Nicholas Paldino [.NET/C# MVP] wrote:

Paul,

In addition to the other comments, you have to remember that when you
perform the call to ToList, which will ultimately iterate through
your query, you are calling three implementations of the methods on
IEnumerable<T>.

The first is in the original implementation of IEnumerable<Ton
rooms.

no, this is done by the Where call, which is equal to
List<T>.FindAll<T>(predicate)

The second is in the call to the Where extension method, which
returns an IEnumerable<Twhich calls the original enumerator and
applies the filter (it is applied in the MoveNext implementation of
the IEnumerable<Treturned).

The last is the call to the Select extension method, which performs
the transformation (if there is one), but still calls through to the
IEnumerable returned by the Where extension method.

isn't called either :)

The query is simply rooms.FindAll<T>(filter). It would be interesting
to see if that .NET 2.0 code would run as fast as his original foreach
or as fast as the linq query :)

FB

--
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------

[=?Utf-8?B?UGF1bA==?=]

The query is simply rooms.FindAll<T>(filter). It would be interesting

to see if that .NET 2.0 code would run as fast as his original foreach
or as fast as the linq query :)

The code below actually performs slightly faster than my original foreach...

public static List<ConferenceRoomFindAllTest(int minimumSeatingCapacity)
{
return rooms.FindAll(delegate(ConferenceRoom room)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
return true;
return false;
});
}

So, the scoreboard now looks like this (with a faster computer than the one
before):
Foreach w. nested if-statement: 2 500 000 ticks
Linq: 4 500 000 ticks
FindAll: 2 400 000 ticks

(All tests have been repeated several times and the results are based on an
average "score")

Can anyone come up with a faster way? :)

[Nicholas Paldino [.NET/C# MVP]]

Frans,

Yes, you are right, Select doesn't get called, but I should have
elaborated and said the first implementation of IEnumerable<Tto return
something is the implementation of IEnumerable<Ton IList<T>, which is then
filtered through the IEnumerable<Treturned by the call to Where, etc, etc.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"Frans Bouma [C# MVP]" <pe******************@xs4all.nlwrote in message
news:xn***************@news.microsoft.com...

Nicholas Paldino [.NET/C# MVP] wrote:

>Paul,

In addition to the other comments, you have to remember that when you
perform the call to ToList, which will ultimately iterate through
your query, you are calling three implementations of the methods on
IEnumerable<T>.

The first is in the original implementation of IEnumerable<Ton
rooms.

no, this is done by the Where call, which is equal to
List<T>.FindAll<T>(predicate)

>The second is in the call to the Where extension method, which
returns an IEnumerable<Twhich calls the original enumerator and
applies the filter (it is applied in the MoveNext implementation of
the IEnumerable<Treturned).

The last is the call to the Select extension method, which performs
the transformation (if there is one), but still calls through to the
IEnumerable returned by the Where extension method.

isn't called either :)

The query is simply rooms.FindAll<T>(filter). It would be interesting
to see if that .NET 2.0 code would run as fast as his original foreach
or as fast as the linq query :)

FB

--
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------

[Jon Skeet [C# MVP]]

On Jan 31, 12:51 pm, Paul <[e-mail]:

<snip>

Can anyone come up with a faster way? :)

That's pretty tricky without having complete source code. Give us a
proper test harness and we can experiment appropriately.

Jon

[=?Utf-8?B?UGF1bA==?=]

The reason FindAll was faster probably was because it uses a for-loop instead
of a foreach-loop (I guess its because the foreach requires that extra call
for GetEnumerator() -method). So if I switch to a for-loop in my original
foreach-based code, I get around 1 800 000 ticks. So the good old reliable
for-loop might be the choice for those hardcode fps-game-programmers (for the
ones who dare to come out of the C++ closet that is). For the rest of us, I
guess it couldn't matter less :)

"Paul" wrote:

The query is simply rooms.FindAll<T>(filter). It would be interesting
to see if that .NET 2.0 code would run as fast as his original foreach
or as fast as the linq query :)

The code below actually performs slightly faster than my original foreach...

public static List<ConferenceRoomFindAllTest(int minimumSeatingCapacity)
{
return rooms.FindAll(delegate(ConferenceRoom room)
{
if (room.SeatingCapacity >= minimumSeatingCapacity)
return true;
return false;
});
}

So, the scoreboard now looks like this (with a faster computer than the one
before):
Foreach w. nested if-statement: 2 500 000 ticks
Linq: 4 500 000 ticks
FindAll: 2 400 000 ticks

(All tests have been repeated several times and the results are based on an
average "score")

Can anyone come up with a faster way? :)

[Jon Skeet [C# MVP]]

On Jan 31, 1:37 pm, Paul <[e-mail]:

The reason FindAll was faster probably was because it uses a for-loop instead
of a foreach-loop (I guess its because the foreach requires that extra call
for GetEnumerator() -method). So if I switch to a for-loop in my original
foreach-based code, I get around 1 800 000 ticks. So the good old reliable
for-loop might be the choice for those hardcode fps-game-programmers (for the
ones who dare to come out of the C++ closet that is). For the rest of us, I
guess it couldn't matter less :)

Alternatively, use foreach but don't call ToList() at the end of the
LINQ expression. That avoids making a copy to a new list at all, which
may well save rather a lot of time. Only a benchmark would tell, of
course :)

Jon

[Marc Gravell]

darn... wrong key:

where:

public static IEnumerable<ConferenceRoomLinqTest(int
minimumSeatingCapacity) {
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room);
}

public static IEnumerable<ConferenceRoomLinqListTest(int
minimumSeatingCapacity) {
return (from room in rooms
where room.SeatingCapacity >= minimumSeatingCapacity
select room).ToList();
}

[Jon]>Only a benchmark would tell, of course :)
Get out of my mind! ;-p

Marc

[Marc Gravell]

(oops - this is actually a continuation of another branch in this
topic - but you get the idea...)

[Jon Skeet [C# MVP]]

On Jan 31, 2:17 pm, "Marc Gravell" <[e-mail]:

(oops - this is actually a continuation of another branch in this
topic - but you get the idea...)

You want to bring continuations into the equation as well? Yikes!

;)

Jon

[Jon Skeet [C# MVP]]

On Jan 31, 2:29 pm, Paul <[e-mail]:

But without the ToList() the methods are not functional equal anymore. It
becomes unfair to compare them since the other methods have to go through and
test all 5 rooms 1 million times where the deferred execution one (LinkTest)
doesn't (until we eventually start iterating). Or am I missing something?

The important thing is to work out whether you really *need* a list.
Often you won't - you just need to iterate.

So yes, the benchmark for each should iterate over the filtered
results each time.

We should also test with a larger list - say 1000 elements, and
100,000 elements (with fewer iterations, of course), making sure that
a reasonable proportion (e.g. half) match the filter each time.

Jon

[Marc Gravell]

D'oh! Yes you are right.... deferred exectuion; the LINQ (without
ToList()) hasn't done anything!

OK, I've returned Count, using property on lists, and
Enumerable.Count() on the LINQ (w/o list), and added a checksum:

ForeachTest: 1,839,284 2000000
LinqTest: 3,210,923 2000000
LinqListTest: 3,919,258 2000000
FindAllTest: 1,342,625 2000000
ForTest: 0,850,867 2000000

So yes, it looks slower (approx factor of 2)... but even so, you are
talking 1s for 1M iterations, and it appears to scale linearly...

Not a great answer, I'll admit...

Marc

[Marc Gravell]

OK; I did some more tests... the problem appears to not be LINQ as
much as virtual calls...

Your test rig works directly off the List<Tvariable, so (since this
is sealed) it can jump the virtcall and go direct to the method. When
all you have is the interface (IList<T>, IEnumerable<T>, etc), then it
cannot do this.

I constructed another test rig just doing a filtered count (no LINQ)
using 10000 iterations over 10000 objects, with all permutations of:
* interface vs concrete List<T>
* foreach vs indexer
* inline test vs predicate

I haven't included the full rig code (quite long) - but I will keep it
for a little while if anybody wants to verify / etc.
Results are console, using stopwatch, with forced GC between runs,
release without debugger (last column is a checksum to prove all
equal):

ConcreteForeachInline 1439ms [39040000]
InterfaceForeachInline 2479ms [39040000]
ConcreteIndexerInline 678ms [39040000]
InterfaceIndexerInline 675ms [39040000]
ConcreteForeachPredicate 2212ms [39040000]
InterfaceForeachPredicate 3239ms [39040000]
ConcreteIndexerPredicate 1445ms [39040000]
InterfaceIndexerPredicate 1453ms [39040000]

This pretty much ties in with what we were seeing for LINQ, in
particular looking at the Foreach results (since LINQ-to-objects
primarily uses IEnumerable<T>), both for inline and predicate usage.

In reality, you are unlikely to ever face a scenario where this is the
actual bottleneck, but I'm glad I understand it a bit better. For
example, if this was critical you could write a few List<T>-specific
extension methods for Where etc, and still use LINQ without a single
change to your code (except perhaps an extra "using" statement). This
would work because of how the compiler works - but the problem would
be what to return from Where etc - if you return IEnumerable<Tyou
are back in interface-ville, but you don't necessarily want the memory
overhead of filling another List. But to demonstrate I went for the
latter option and knocked a few together:

Std LINQ Count 4234ms [39040000]
List LINQ Count 2264ms [39040000]

Std LINQ Where ToList 7797ms [39040000]
List LINQ Where ToList 3160ms [39040000]

Does that fill in a few blanks?

Marc

[Marc Gravell]

List LINQ Count 2264ms [39040000]

I should clarify that this was a predicate count; the Count() without
predicate is a lot quicker; the standard LINQ implementation has the
good-sense to test for ICollection<T>, so the unfiltered Count() works
blindingly either way; not worth re-implementing...

Marc

[Marc Gravell]

Actually, a caffeine low meant I fluffed the test slightly
(InterfaceIndexer* was using List<T>); I'll try and get my act
together!

The good news is that the revised code further demonstrates this
point, highlighting that the difference also applies with indexers:

ConcreteForeachInline 1916ms [39040000]
InterfaceForeachInline 3297ms [39040000]
ConcreteIndexerInline 888ms [39040000]
InterfaceIndexerInline 1655ms [39040000]
ConcreteForeachPredicate 3022ms [39040000]
InterfaceForeachPredicate 4355ms [39040000]
ConcreteIndexerPredicate 1908ms [39040000]
InterfaceIndexerPredicate 2692ms [39040000]

For the record, I would still recommend coding to interfaces; it makes
the code far more reusable and open to refactoring.

I've treble checked my signatures this time:

static int ConcreteForeachInline(List<Foofoos, int cutoff) {...}
static int InterfaceForeachInline(IEnumerable<Foofoos, int cutoff)
{...}
static int ConcreteIndexerInline(List<Foofoos, int cutoff) {...}
static int InterfaceIndexerInline(IList<Foofoos, int cutoff) {...}
static int ConcreteForeachPredicate(List<Foofoos, int cutoff) {...}
static int InterfaceForeachPredicate(IEnumerable<Foofoos, int
cutoff) {...}
static int ConcreteIndexerPredicate(List<Foofoos, int cutoff) {...}
static int InterfaceIndexerPredicate(IList<Foofoos, int cutoff)
{...}

Marc