Expression Tree Basics

DotNetKicks.com — Thu, 31 Jan 2008 13:19:24 GMT

You've been kicked (a good thing) - Trackback from DotNetKicks.com

Compiled Expression Dispatch Overhead

Blake Coverett — Thu, 31 Jan 2008 21:50:34 GMT

This seems a good place to point out/ask about something I noticed back in Beta2, and have verified is still true.

Curiously the dispatch overhead calling a delegate produced with Expression.Compile appears to be less than half of the overhead in calling a delegate produced either from a lambda expression or simply pointing at a static method.

This is entirely counter-intuative to me. I can provide the benchmark code if desired, but it isn't anything tricky.

re: Expression Tree Basics

Charlie Calvert — Thu, 31 Jan 2008 23:54:50 GMT

Blake,

Okay, that sounds interesting. I also have to agree that it sounds a bit counter-intuitive. Can you show us some code or tell us a bit more about what you are doing to get those results? Thanks.

- Charlie

re: Expression Tree Basics

Blake Coverett — Fri, 01 Feb 2008 01:33:48 GMT

Thanks. I'll email the whole file if you like, but the most relevant bits are short enough to include here:

static long Add(long a, int b) { return a + b; }

...

Func<long, int, long> AddSD = Add;

Func<long, int, long> AddAD = (a, b) => a + b;

Expression<Func<long, int, long>> AddExp = (a, b) => a + b;

Func<long, int, long> AddDD = AddExp.Compile();

...

stopwatch.Start();

for(var i = 0; i < data.Length; ++i) total = AddDD(total, data[i]);

stopwatch.Stop();

Console.WriteLine("Dynamic Delegate: value = {0}, ticks = {1}, {2:P}", total, stopwatch.ElapsedTicks, (double)stopwatch.ElapsedTicks / baseTicks);

...

And I get results like these:

Static Method: value = 2251799780130816, ticks = 1427409, 100.00 %

Static Delegate: value = 2251799780130816, ticks = 2554450, 178.96 %

Anonymous Delegate: value = 2251799780130816, ticks = 2451449, 171.74 %

Dynamic Delegate: value = 2251799780130816, ticks = 1768117, 123.87 %

Colour me puzzled.

re: Expression Tree Basics

Blake Coverett — Fri, 01 Feb 2008 01:35:30 GMT

I can be reached at blake at bcdev dot com, if that isn't enough to reproduce the results.

re: Expression Tree Basics

marlongrech — Sun, 03 Feb 2008 18:37:10 GMT

Great post.... LINQ ROCKS!!!!!!

Link List: Language Topics, Data Service, jQuery,F#, Spec#, Specs Reading, etc...

Guru Stop — Mon, 04 Feb 2008 15:09:01 GMT

It started an email Mohamed Hossam (AKA, Bashmohandes) sent to my company's local office here in Egypt

re: Expression Tree Basics

marlongrech — Mon, 11 Feb 2008 02:28:20 GMT

Hi,

I used the Dynamic Query API in order to embed code in XAML... Have a look...

http://marlongrech.wordpress.com/2008/02/10/embed-code-in-xaml/

Great JOB you guys!!!!!

Regards

LINQ Farm Seed: Using the Expression Tree Visualizer

Charlie Calvert's Community Blog — Wed, 13 Feb 2008 21:54:12 GMT

The Visual Studio 2008 CSharp samples include several valuable tools that LINQ developers can use to

LINQ Farm Seed: Using the Expression Tree Visualizer

Noticias externas — Wed, 13 Feb 2008 22:13:27 GMT

The Visual Studio 2008 CSharp samples include several valuable tools that LINQ developers can use to

re: Expression Tree Basics

Isaac Answers — Thu, 14 Feb 2008 14:12:41 GMT

Is It Possible To Use The Same Ideas Of LINQ In Expression Trees In Converting String To LINQ - Ex. Sql2LINQ or A Custom Language Converter To LINQ Expressions.

It Seems So Powerful!

Great Article.

Feb 17th Links: ASP.NET, ASP.NET AJAX, Visual Studio, .NET

ASP.NET AJAX Team Blogs — Sun, 17 Feb 2008 22:20:18 GMT

Here is the latest in my link-listing series .  Also check out my ASP.NET Tips, Tricks and Tutorials

Feb 17th Links: ASP.NET, ASP.NET AJAX, Visual Studio, .NET

BusinessRx Reading List — Sun, 17 Feb 2008 22:29:42 GMT

Here is the latest in my link-listing series .  Also check out my ASP.NET Tips, Tricks and Tutorials

re: Expression Tree Basics

Mark Wisecarver — Mon, 18 Feb 2008 16:12:48 GMT

This is awesome Charlie, thanks a bunch bro.

btw, the trail ahead looks groovy.

re: Expression Tree Basics

nu — Wed, 23 Apr 2008 00:33:13 GMT

Charlie, any chance you'll be responding to Blake Coverett's question about the counter-intuitiveness of his profiling results?

Great article though! Thank you.

re: Expression Tree Basics

Magnus Lof — Sat, 03 May 2008 01:05:12 GMT

Isaac, take a look at the LINQ Dynamic Query Library. Here's a nice blog post on it by Scott Guthrie:

http://weblogs.asp.net/scottgu/archive/2008/01/07/dynamic-linq-part-1-using-the-linq-dynamic-query-library.aspx

Eye On .NET

Hisham Elbreky — Sat, 03 May 2008 12:23:56 GMT

Eye On .NET is periodical listing series for .NET(Blogs, Articles, Media, Events and Announcing) I hope

re: Expression Tree Basics

Craig Lebowitz — Wed, 11 Jun 2008 00:22:41 GMT

Nice post, your clear writing makes this easy to understand

re: Expression Tree Basics

Sonali Noolkar — Thu, 19 Jun 2008 08:33:40 GMT

I have just started exploring Expression tree.

The article is nice to get good understanding of the concept.

re: Expression Tree Basics

Bert Loedeman — Fri, 20 Jun 2008 11:50:34 GMT

Hi Charlie,

Since it helped me a lot, I refer to your blog post at http://dotbert.blogspot.com/2008/06/lambda-expression-trees.html.

Greetings, Bert

re: Expression Tree Basics

elena — Tue, 01 Jul 2008 18:40:56 GMT

you're right, but of course there is also a counter-argument, which is that one should only expose interfaces on a "need-to-know" basis, and "just seeing what is going on" does not constitute a need to know.

re: Compiled Expression Dispatch Overhead

Somchai — Mon, 14 Jul 2008 23:11:23 GMT

On the performance of the Express Tree, if we are going to take the evalation of the Func and/or Expression Tree into the consideration, by refactor the code as follows:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

using System.Threading;

using System.Linq.Expressions;

namespace Performance

{

class Program

{

static long Add(long a, int b) { return a + b; }

static void Main(string[] args)

{

int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,

11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ,

21, 22, 23, 24, 25, 26, 27, 28, 29, 30 ,

31, 32, 33, 34, 35, 36, 37, 38, 39, 40 ,

41, 42, 43, 44, 45, 46, 47, 48, 49, 50 ,

51, 52, 53, 54, 55, 56, 57, 58, 59, 60 ,

61, 62, 63, 64, 65, 66, 67, 68, 69, 70 ,

71, 72, 73, 74, 75, 76, 77, 78, 79, 80 ,

81, 82, 83, 84, 85, 86, 87, 88, 89, 90 ,

91, 92, 93, 94, 95, 96, 97, 98, 99, 100,

101, 102, 103, 104, 105, 106, 107, 108, 109, 110 ,

111, 112, 113, 114, 115, 116, 117, 118, 119, 120 ,

121, 122, 123, 124, 125, 126, 127, 128, 129, 130 ,

131, 132, 133, 134, 135, 136, 137, 138, 139, 140 ,

141, 142, 143, 144, 145, 146, 147, 148, 149, 150 ,

151, 152, 153, 154, 155, 156, 157, 158, 159, 160 ,

161, 162, 163, 164, 165, 166, 167, 168, 169, 170 ,

171, 172, 173, 174, 175, 176, 177, 178, 179, 180 ,

181, 182, 183, 184, 185, 186, 187, 188, 189, 190 ,

191, 192, 193, 194, 195, 196, 197, 198, 199, 200

};

long normFactor = RunStaticMethod(data);

RunStaticDelegate(data, normFactor);

RunAnonymousDelegate(data, normFactor);

RunDynamicDelegate(data, normFactor);

Console.ReadLine();

}

static long RunStaticMethod(int[] data)

{

long total = 0;

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

// Call the Static Method directly

for (var i = 0; i < data.Length; ++i) total = Add(total, data[i]);

stopwatch.Stop();

double baseTicks = stopwatch.ElapsedTicks;

Console.WriteLine("Static Method : value = {0}, ticks = {1}, {2:P}", total, stopwatch.ElapsedTicks, (double)stopwatch.ElapsedTicks / baseTicks);

return stopwatch.ElapsedTicks;

}

static void RunStaticDelegate(int[] data, long normalizedFactor)

{

long total = 0;

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

//Static Delegate

Func<long, int, long> AddSD = Add;

//stopwatch.Start();

for (var i = 0; i < data.Length; ++i) total = AddSD(total, data[i]);

stopwatch.Stop();

double baseTicks = normalizedFactor;

Console.WriteLine("Static Delegate : value = {0}, ticks = {1}, {2:P}", total, stopwatch.ElapsedTicks, (double)stopwatch.ElapsedTicks / baseTicks);

}

static void RunAnonymousDelegate(int[] data, long normalizedFactor)

{

long total = 0;

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

// Anonymous Delegate

Func<long, int, long> AddAD = (a, b) => a + b;

//stopwatch.Start();

for (var i = 0; i < data.Length; ++i) total = AddAD(total, data[i]);

stopwatch.Stop();

double baseTicks = normalizedFactor;

Console.WriteLine("Anonymous Delegate : value = {0}, ticks = {1}, {2:P}", total, stopwatch.ElapsedTicks, (double)stopwatch.ElapsedTicks / baseTicks);

}

static void RunDynamicDelegate(int[] data, long normalizedFactor)

{

long total = 0;

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

// The following two statements are used together

Expression<Func<long, int, long>> AddExp = (a, b) => a + b;

Func<long, int, long> AddDD = AddExp.Compile();

//stopwatch.Start();

for (var i = 0; i < data.Length; ++i) total = AddDD(total, data[i]); //Speedy DD

stopwatch.Stop();

double baseTicks = normalizedFactor;

Console.WriteLine("Dynamic Delegate : value = {0}, ticks = {1}, {2:P}", total, stopwatch.ElapsedTicks, (double)stopwatch.ElapsedTicks / baseTicks);

}

The outcome indicates that the Expression Tree is slowest. The point is that the code will get executed sooner or later. Perhaps, we should take that time into our consideration.

And here is the comparison:

============================

When Stopwatch is triggered AFTER the Func and/or Expression Tree evaluation:

Static Method : value = 20100, ticks = 434069, 100.00 %

Static Delegate : value = 20100, ticks = 11713, 2.70 %

Anonymous Delegate : value = 20100, ticks = 410176, 94.50 %

Dynamic Delegate : value = 20100, ticks = 9426, 2.17 %

.VS.

When Stopwatch is triggered BEFORE the Func and/or Expression Tree evaluation:

Static Method : value = 20100, ticks = 434928, 100.00 %

Static Delegate : value = 20100, ticks = 13183, 3.03 %

Anonymous Delegate : value = 20100, ticks = 620347, 142.63 %

Dynamic Delegate : value = 20100, ticks = 14994281, 3,447.53 %

StaticStringDictionary - Fast Switching with LINQ revisited

Code Beside — Thu, 28 Aug 2008 23:58:43 GMT

StaticStringDictionary - Fast Switching with LINQ revisited

re: Expression Tree Basics

Erik — Fri, 29 Aug 2008 01:19:19 GMT

The comment above's results are still a bit skewed. In your testing scenario we see Static Method takes a good deal longer to execute than static delegate. This is also a bit counter-intuitive. The expectation is the two should run nearly in the same time.

In fact this is observed if you run the test consecutively (call the function blocks twice. You see there is the initial translation of the IL to machine language time being added to whoever is unfortunate enough to be measured first.

If you rerun the tests with the first two calls swapped, suddenly the Delegate takes a great deal longer. Running them back-to-back twice reflects very few (but always more) ticks longer for the static delegate to execute over static method. This is observed regardless of order.

I'm sure an examination of the IL would show an extra instruction somewhere - the two don't appear to compile to the same instructions to get executed. Someone with time could verify this.

To see this, call your function as you do here, then before ending, call all four again but simply move the static delegate above static method. Examine the tick counts. The delegate always takes longer than method.

re: Expression Tree Basics

Blake Coverett — Sat, 27 Sep 2008 05:35:10 GMT

Somchai misses the point of my question and benchmark entirely. Apart from

Yes, creating delegates and compiling/JIT'ing expression trees has an overhead, but that's not what I found unexpected. The odd thing is the speed of dispatch of the resulting calls after they are JIT'd. Unfortunately I haven't heard anything back from Charlie on this.

[MSTD09] Programmation dynamique avec .net

Atteint de JavaScriptite Aiguë [Cyril Durand] — Sun, 15 Feb 2009 23:58:40 GMT

Lors des techdays 2009, je suis allé voir la session “ Programmation dynamique ” de Mitsu Furuta et Simon

re: Expression Tree Basics

Charles Prakash Dasari — Tue, 17 Feb 2009 00:21:56 GMT

This is a great post. Thanks for a good learning.

re: Expression Tree Basics

Dylan Borg — Sun, 14 Jun 2009 15:45:44 GMT

Thanks for this entry. It really explains part of the DLR to me in a better way.

C# 4.0 Part 4 - Understanding Expression Tree

שלמה גולדברג — Sun, 21 Jun 2009 12:48:36 GMT

אז בפוסט הקודם ראינו שלמעשה אין ב - Runtime טיפוס dynamic, וכל מה שאנחנו משימים לתוך dynamic עובר להיות

re: Expression Tree Basics

sbndqa — Thu, 06 Aug 2009 02:15:31 GMT

npoBIS <a href="http://rdrsmmanfghc.com/">rdrsmmanfghc</a>, [url=http://zlpfeeucnkcr.com/]zlpfeeucnkcr[/url], [link=http://ibhrffvvyfvr.com/]ibhrffvvyfvr[/link], http://jqmmkzbtfuuv.com/

re: Expression Tree Basics

webcliff — Fri, 04 Sep 2009 18:19:27 GMT

Expression Tree Explained in plain language.

One of the best blog post I have ever read.

re: Expression Tree Basics

ID10T — Thu, 17 Sep 2009 21:26:37 GMT

Thank you for this! You have made the complex very simple to understand, which is a rare thing!

re: Expression Tree Basics

Sam — Sun, 04 Oct 2009 10:44:34 GMT

Hi, Is it possible convert string to Expression?For the code is:

public void testExp(Func<T,object> func)

{...}

...

string exp="x=>x.name";

testExp(SOME_FUNCTION(exp));

Dose there exist the function(SOME_FUNCTION) I used above?

re: Expression Tree Basics

Shobz — Fri, 27 Nov 2009 00:13:28 GMT

Very Good blog clarifying the basic concepts really well