Performance Issues with Delegates

[jehugaleahsa]

I wrote a simple method that allows me to pass a delegate to find a
value in a list. I already had a set of methods for doing comparisons:
less, greater, equal, equivalent, etc. However, find algorithms always
compare the element in the list to a given value. In other words, I
needed to bind one value for all the comparisons.

I wrote a simple Bind1st method that looks like this:

public delegate R Operation<R, T>(T value);

public delegate R Operation2<R, T>(T lhs, T rhs);

public static Operation<R, TBind1st<R, T>(Operation2<R, T>
operation, T lhs)
{
return delegate(T rhs)
{
return operation(lhs, rhs);
};
}

However, when I run my find method with the Bind1st it runs *much*
slower. I understand that the bind has to call a method each time;
however, I can't see why that would cause the performance hit I am
experiencing. I have tried putting the delegate inline with the value
hard-coded as well and it runs much better. My code performs best when
no delegates are involved at all (but this means not using my find
method).

Any suggestions for getting away from the wall?

Thanks,
Travis

[Peter Duniho]

je**********@gmail.com wrote:

I wrote a simple method that allows me to pass a delegate to find a
value in a list. I already had a set of methods for doing comparisons:
less, greater, equal, equivalent, etc. However, find algorithms always
compare the element in the list to a given value. In other words, I
needed to bind one value for all the comparisons.

I wrote a simple Bind1st method that looks like this:

public delegate R Operation<R, T>(T value);

public delegate R Operation2<R, T>(T lhs, T rhs);

public static Operation<R, TBind1st<R, T>(Operation2<R, T>
operation, T lhs)
{
return delegate(T rhs)
{
return operation(lhs, rhs);
};
}

However, when I run my find method with the Bind1st it runs *much*
slower.

First, I don't understand the code you posted. It won't compile, due to
the missing semicolon, but also the Bind1st<R, Tmethod never calls the
operation delegate. Why have that block of code at all?

Second, you haven't posted nearly enough code to really describe your
problem. What are your delegate methods doing? How do you use
Bind1st<R, Tin real code? What are the _actual_ time differences for
different implementations? That is, you need to define "much slower".

Obviously, calling a method by reference, such as using a delegate or
virtual method or similar, is going to be slower than calling a method
directly. But in practice this is almost never an issue. The act of
calling any method is so inexpensive compared to code that does anything
interesting, it's almost never an issue.

But there's not really enough context in your question to be able to
provide useful, specific advice. You should post a concise-but-complete
example of code that reliably reproduces the problem. This would
include demonstrating the time cost of the two implementations you're
comparing.

Pete

[jehugaleahsa]

Ask and you shall receive.

public static IIterator<TFind<T>(IIterator<Tfirst,
IIterator<Tpast, Predicate<Tpredicate)
{
if (first == null)
{
throw new ArgumentNullException();
}
if (past == null)
{
throw new ArgumentNullException();
}
if (predicate == null)
{
throw new ArgumentNullException();
}
first = first.Clone();
while (!first.Equals(past) && !predicate(first.Current))
{
first.Next();
}
return first;
}

public static bool Equivalent<T>(T lhs, T rhs)
{
return Object.ReferenceEquals(lhs, rhs) || lhs != null &&
lhs.Equals(rhs);
}

Algorithms.Find<T>(list.GetFirst(),
list.GetPast(),
new Predicate<T>(Functional.Bind1st<bool,
T>(Functional.Equivalent<T>, value)));

These are merely snippets. There is a library of data structures that
provided iterators; list is a doubly-linked list. If you have ever
worked in C++, this should certainly seem familiar.

Just so you know, I copied that code from a working set. It was inside
a class, so that might explain your compile error. I am not sure what
you mean by a missing semicolon; it looks fine to me.

I figured someone would ask what "much slower" meant. I am not talking
factors of N, of course. I am talking something that runs in 19
seconds taking 59 seconds, something taking 17 minutes taking 45
minutes. That is significant enough even if it isn't a factor of N.
These are real times, by the way.

[Jon Skeet [C# MVP]]

je**********@gmail.com <je**********@gmail.comwrote:

<snip>

I figured someone would ask what "much slower" meant. I am not talking
factors of N, of course. I am talking something that runs in 19
seconds taking 59 seconds, something taking 17 minutes taking 45
minutes. That is significant enough even if it isn't a factor of N.
These are real times, by the way.

Are you running inside the debugger? That could well have a significant
impact.

If you could post a short but *complete* program which demonstrates the
problem, including the performance issue, we're much more likely to
have a chance of sorting it out.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

je**********@gmail.com wrote:

I wrote a simple method that allows me to pass a delegate to find a
value in a list. I already had a set of methods for doing comparisons:
less, greater, equal, equivalent, etc. However, find algorithms always
compare the element in the list to a given value. In other words, I
needed to bind one value for all the comparisons.

I wrote a simple Bind1st method that looks like this:

public delegate R Operation<R, T>(T value);

public delegate R Operation2<R, T>(T lhs, T rhs);

public static Operation<R, TBind1st<R, T>(Operation2<R, T>
operation, T lhs)
{
return delegate(T rhs)
{
return operation(lhs, rhs);
};
}

However, when I run my find method with the Bind1st it runs *much*
slower. I understand that the bind has to call a method each time;
however, I can't see why that would cause the performance hit I am
experiencing. I have tried putting the delegate inline with the value
hard-coded as well and it runs much better. My code performs best when
no delegates are involved at all (but this means not using my find
method).

Any suggestions for getting away from the wall?

Thanks,
Travis

As the delegate that you create in the method is using one of the
parameters from the method, the delegate is not just a pointer to a
method any more. Instead the compiler has to package the delegate along
with the value of the parameter.

I don't know exactly how this is done, but it's certainly more
complicated than just using a pointer, so there is the reason for the
difference in performance.

--
Göran Andersson
_____
http://www.guffa.com

[Jon Skeet [C# MVP]]

Göran Andersson <gu***@guffa.comwrote:

As the delegate that you create in the method is using one of the
parameters from the method, the delegate is not just a pointer to a
method any more. Instead the compiler has to package the delegate along
with the value of the parameter.

I don't know exactly how this is done, but it's certainly more
complicated than just using a pointer, so there is the reason for the
difference in performance.

It's not that complicated - it's just creating an instance of a type
which has been created behind the scenes.

Object creation is very fast for simple cases - I don't think it's
likely to account for this slowdown.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

Jon Skeet [C# MVP] wrote:

je**********@gmail.com <je**********@gmail.comwrote:

<snip>

>I figured someone would ask what "much slower" meant. I am not talking
factors of N, of course. I am talking something that runs in 19
seconds taking 59 seconds, something taking 17 minutes taking 45
minutes. That is significant enough even if it isn't a factor of N.
These are real times, by the way.

Are you running inside the debugger? That could well have a significant
impact.

If you could post a short but *complete* program which demonstrates the
problem, including the performance issue, we're much more likely to
have a chance of sorting it out.

Here's a short but complete program.

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace UnitTest {

class Program {

private static void Main(string[] args) {
TestDelegates();
}

#region Clock

private static Stopwatch clock = new Stopwatch();

private static void Start() {
clock.Reset();
clock.Start();
}

private static void Stop() {
Stop("Time: {0:N3} seconds.");
}

private static void Stop(string format) {
clock.Stop();
Console.WriteLine(format, clock.Elapsed.TotalSeconds);
}

#endregion

public delegate R Operation<R, T>(T value);
public delegate R Operation2<R, T>(T left, T right);

public static Operation<R, TBind<R, T>(Operation2<R, Toperation, T
left) {
return delegate(T right) { return operation(left, right); };
}

public static bool StringEqual(string left, string right) {
return left == right;
}

public static List<TFind<T>(List<Tsource, T value,
Operation2<bool, Toperation) {
List<Tresult = new List<T>();
foreach (T t in source) {
if (operation(t, value)) {
result.Add(t);
}
}
return result;
}

public static List<TFind<T>(List<Tsource, Operation<bool, T>
operation) {
List<Tresult = new List<T>();
foreach (T t in source) {
if (operation(t)) {
result.Add(t);
}
}
return result;
}

private static void TestDelegates() {
int iterations = 1000000;
List<stringsource = new List<string>(new string[] { "a", "b", "c",
"d", "e", "f", "g" } );
Start();
for (int i = 0; i < iterations; i++) {
List<stringresult = Find<string>(source, "c", StringEqual);
}
Stop();
Start();
for (int i = 0; i < iterations; i++) {
List<stringresult = Find<string>(source, Bind<bool,
string>(StringEqual, "c"));
}
Stop();
}

}

}
--
Göran Andersson
_____
http://www.guffa.com

[Jon Skeet [C# MVP]]

Göran Andersson <gu***@guffa.comwrote:

Are you running inside the debugger? That could well have a significant
impact.

If you could post a short but *complete* program which demonstrates the
problem, including the performance issue, we're much more likely to
have a chance of sorting it out.

Here's a short but complete program.

Right. Thanks for that :)

It looks like the delegate creation is indeed the issue here - moving
the call to Bind outside the loop makes the performance basically the
same for both cases.

So, really we need to ask the OP if they can do the same thing...

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too