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, T> Bind1st<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]

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, T> Bind1st<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, T> method 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, T> in 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<T> Find<T>(IIterator<T> first,
IIterator<T> past, Predicate<T> predicate)
{
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]]

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.

 

[Peter Duniho]

Ask and you shall receive.

I asked for "concise-but-complete".

[...]
These are merely snippets.

"Snippets" != "complete".

[...]
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.

My fault. I misread the code and wasn't paying close enough attention
to the return type of Bind1st. It is fine.

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.

Yes, but under what circumstances? What is the code actually doing?

I don't think that the use of delegates should in and of itself cause a
three-fold increase in time cost. But it's certainly possible that when
used inappropriately or in some relatively degenerate situation (ie, the
call itself makes up the bulk of the time cost) you might see that.

Without a concise-but-complete example of code, there's not really any
way to comment usefully.

Pete

 

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

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, T> Bind1st<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.

 

[jehugaleahsa]

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

impact.

No. I verified it in release mode as well.

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.

In order to give a more full example, I am afraid I would have to
include one of the data structures. I was just hoping for a simple
explaination for why using a delegate that creates a delegate would
have an efficiency problem. Sorry for not being able to explain the
situation more clearly.

Yes, but under what circumstances? What is the code actually doing?

The code is searching through a linked list data structure. That
should mean something to someone who knows about data structure
analysis. The limited snippet that includes the Find<T> method that
does a linear search that starts from the first element and goes to
element that matches the predicate.

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.

I think Göran Andersson understands the problem. I will just think of
another way of avoiding the problem.

Thanks for your responses,
Travis

 

[Jon Skeet [C# MVP]]

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 [C# MVP]]

No. I verified it in release mode as well.

Hmm. Odd.

In order to give a more full example, I am afraid I would have to
include one of the data structures. I was just hoping for a simple
explaination for why using a delegate that creates a delegate would
have an efficiency problem. Sorry for not being able to explain the
situation more clearly.

I don't see why you'd need one of your real data structures. Why not
just use a simple one (e.g. a "Person" type)? In particular, if you try
to come up with a simple example and find that you don't get the same
performance difference, that gives information in itself.

The code is searching through a linked list data structure. That
should mean something to someone who knows about data structure
analysis. The limited snippet that includes the Find<T> method that
does a linear search that starts from the first element and goes to
element that matches the predicate.

That still isn't really enough information: are you creating the
predicate millions of times, searching through a short list each time,
or creating one predicate and searching through a massive list? This
kind of thing can have a significant impact, and is why a complete
example is really important.

I think Göran Andersson understands the problem. I will just think of
another way of avoiding the problem.

Göran has given one *possible* explanation, which I don't happen to
believe is correct. We need to be able to verify it ourselves to make
much more progress.

 

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

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, T> Bind<R, T>(Operation2<R, T> operation, T
left) {
return delegate(T right) { return operation(left, right); };
}

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

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

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

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

}

}

 

[Jon Skeet [C# MVP]]

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...