Thursday, May 14, 2009

Fast expression compilation

Recently we've faced a well-known problem: LambdaExpression.Compile is quite slow. Mainly, because of:
- Huge amount of reflection
- Excessive security checks
- Absence of any caching!

We've faced the issue while implementing compilation to executable providers for our RecordSet engine for DO4. We should compile generally any expression, such as predicate passed to FilterProvider here. Event quite simple LINQ queries using just a single .Where invocation normally require compilation of 2 expressions: one for original .Where criteria, and one - for index range definition for RangeSetProvider (we build it as expression).

Obviously, we recommend everyone to use our cached queries in DO4 - they eliminate the problem. But what if you can't cache the query - e.g. if it is built dynamically, and actual instances almost always differ?

So we've implemented LambdaExpression compilation cache. Being implemented well, it solves all the above problems.


Raw results

Simple expression compilation test:
- Expression: (int a, int b) => a + b;
- Without caching: 15,884 K compilations/s.
- With caching: 45,158 K compilations/s.

Complex expression compilation test:
- Expression: (int a, int b) => new {Result = a + b * 2 / a}.Result + DateTime.Now.Day * a * b - a + b
- Without caching: 0,945 K compilations/s.
- With caching: 25,747 K compilations/s.

As you see, the acceleration factor varies from ~ 3x to 26x! Even this result seems very good. But we decided to investigate why results of standard .NET expression compilation differs so much here and implemented one more test:

Always new expression compilation test:
- Expression: (int a, int b) => i;
- Without caching: 1,707 K compilations/s.
- With caching: 27,960 K compilations/s.

i
is an integer increasing its value by one on each compilation attempt. So it looks like there is already some kind of caching in .NET expression compilation logic. But IT FAILS even on such a simple case (difference in constant value)! Probably, they simply cache the compilation result using expression instance as key.

So "true" acceleration factor is at least 16x.


Implementation

Note: Further I'll use GenericType(of T) instead of standard C# notation with square brackets, because Blogger hates them - it simply cuts them out.

There is Xtensive.Core.Linq.ExpressionCompileExtensions class providing a set of additional .CachingCompile() methods to Expression type. Its usage is almost the same as of original .Compile method:
- Original code: var compiledLambda = lambda.Compile();
- New code: var compiledLambda = lambda.CachingCompile();

How it could work:
- Find cached version of provided expression tree in some dictionary
- Return its compiled version, if it exists; otherwise, compile & cache it.

Actually everything is much more complex:
- Expressions aren't comparable for equality. They neither override Equals, nor GetHashCode. But comparison for equalitry is required to use them as key in dictionary. We can't use default implmentation as well - Expression instances are almost always built anew rather than cached.
- Even if they would be comparable for equality, they won't really be equal because of closures: a new instance of closure is referenced by corresponding ConstantExpression on the subsequent creation of expression tree. Even if we could be able to compare such constants for equality, they would almost always differ.

So we've implemented:
- ExpressionTree class implementing IEquatable(of ExpressionTree), and properly overriding default GetHashCode & Equals. This allows us to compare expressions.
- ConstantExtractor - a visitor rewriting the original expression and removing any dependencies on constants from it. In fact, we rewrite original expression replacing each const of type T there to ((T) additionalLambdaParameter[constNumber]) there. E.g. () => 1 would be rewritten to (consts) => ((int) consts[0]), and we would cache this expression. ConstantExtractor builds the array of constant values (actual consts value) during processing of the original expression. Since this happens on any attempt to compile the expression by our caching compiler (because first of all we must build caching key - an ExpressionTree containing no constants), we always have this array of constants.
- So in the end we always have both compiled expression (processed by ConstantExtractor) and the array of constants. So we should just "bind" this array to the comiled expression. "Bind" means converting a pair of f(consts,a,b,c, ...) and extractedConsts to g(a,b,c, ...) = f(extractedConsts,a,b,c, ...). This actually done by corresponding overload of .CachingCompile method. Its typical code is:

public static Func(of T1, T2, ..., TResult) CachingCompile(of T1, T2, ..., TResult)
(this Expression(of Func(of T1, T2, TResult)) lambda)
{
var result = CachingExpressionCompiler.Instance.Compile(lambda);
return ((Func(of object[], T1, T2, ...)) result.First).Bind(result.Second);
}
.Bind is one more extension method provided by Xtensive.Core.Helpers.DelegateBindExtensions class.
All .Bind and .CachingCompile versions are generated by T4 templates - finally we've found the place where we could use them ;)

And finally, we use our ThreadSafeDictionary as actual cache, so any cached compiled result is never purged. Initially this may look as a serious lack, but actually it isn't: currently .NET is incapable of unloading any IL code. Even if we don't use cache, expression compilation eats some RAM, and this RAM is never released. So our "caching compiler" just eats a bit more - certainly, only if we don't hit the cache.


Conclusions

Pros and cons:
- We've got much faster expression compilation
- It's quite likely this solution significantly decreases the amount of RAM consumed by complied expressions during the application lifetime, since it significantly decrease the number of actual compilations.
- The compiled expression we return is a bit slower, because we replace constants to array accessors there and add one more delegate call (.Bind method does this). But I feel this will be acceptable in 99.9% of cases.

Possible improvements:
- Use lightweight expression adapters instead of Expression descendants as result of ConstantExtractor, such as the ones from MetaLinq. .NET expressions perform lots of checks during their construction, which aren't necessary here. We must just be able to compare such tree for equality with another one, compute its hash code, and much rarely - convert it to .NET expressions to get it compiled. I feel this should improve the performance at least twice.


Usage

- Download DO4 - it contains compiled version of Xtensive.Core.dll, as well as its source code
- Add reference to Xtensive.Core.dll to your project
- Add "using Xtensive.Core.Linq;" to C# file containing lambda.Compile()
- Replace lambda.Compile() to lambda.CachingCompile().

61 comments:

  1. RE:
    Simple expression compilation test:
    - Expression: (int a, int b) => a + b;
    - Without caching: 15,884 K compilations/s.
    - With caching: 45,158 K compilations/s.

    Of course caching would help if we compile the same expression millions times, but what about one time compilation ? I guess it is even slower...

    ReplyDelete
    Replies
    1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a .Net developer learn from Dot Net Training in Chennai. or learn thru ASP.NET Essential Training Online . Nowadays Dot Net has tons of job opportunities on various vertical industry.
      or Javascript Training in Chennai. Nowadays JavaScript has tons of job opportunities on various vertical industry.

      Delete
  2. Yes, it is, although not dramatically: as you may find here, all the "additional job" we do is expression comparison. As it's shown, it takes ~ 30% of pure compilation time at max, and it happens anyway. So if there will be really unique expressions, they'll be compiled 30% slower.

    What's more important: how frequently do you produce really unique expressions, that are compiled just once, taking into account the way we compare them - our comparer is constant-insensitive?

    Moreover, each of such unique expressions will eat some RAM after the compilation (.NET doesn't unload the code), so such a process can't live infinitely. If you're caring about its perfromance, I admit such compilations must happen e.g. 1000 times per second. So it will die in ~ 1 day (8Gb ~= 100bytes*1000*60*60*24).

    ReplyDelete
  3. Hi Alex,

    I know this post is too old, but I didn't find any other open-sourced solution like this one (or better).

    The download link is broken.
    Do you still have the source code?
    It would be great if we have a github repo and nuget package for it. What do you think?

    Thanks!

    ReplyDelete
  4. I’m really impressed with your article, MBA Dissertation Writing Service such great & usefull knowledge you mentioned here

    ReplyDelete
  5. This is really a great stuff for sharing. Keep it up. Medical Assignment Help Thanks for sharing.

    ReplyDelete
  6. When you must switch to the World Wide Web to search for some Assignment Help . Our high expert's professionals who have extensive experience in writing assignment will not only make you avail with the quality assignment, but you will also get plagiarism free assignment within the given time.

    ReplyDelete
  7. We Provide assignment help for students especially in usa getting brilliant quality reviews writing USA, essays and dissertations.We at Top Quality Assignment believe that there is no shortcut to success and to attain success, hard work, dedication, and commitment must be present.AllassignmentHelp.co.uk Reviews best in writing unique Assignment.

    ReplyDelete
  8. Thank You So Much For providing the important and Knowledgeable information.
    I am Olivia Crew, SEO Expert in a reputed company livewebtutors. All of your information is very useful to me. I am working as an academic consultant in Australia and offer Excellent Assignment Help Services to college students.
    visit here:- my assignment help

    ReplyDelete
  9. Extremely informative blog. Thanks for your efforts in this blog. Visit for
    SEO Service in Delhi

    ReplyDelete
  10. I am very happy to read this. This is the kind of manual that needs to be given and not the random misinformation that’s at the other blogs. Appreciate your sharing this best posting. Make My Assignment

    ReplyDelete
  11. Great site and a great topic as well I really get amazed to read this. It’s really good. I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. brass jhula chain

    ReplyDelete
  12. Java Assignment help
    Therefore, students take Java Assignment help from the online assignment writing services. They are cost-efficient, as well as fast in their service. A student who is new to these assignment writing can get a proper idea on the format which should be followed. However, there is one more thing to ponder.

    ReplyDelete
  13. It is the big concern how to maintain the overall glory of accessing the scholar degree. It does not matter you are studying in which subject domain. During the learning process of you choose subject stream, all students cannot give equal attention to complete it on time. For gaining the best output, they would have to take the online Assignment Help with our academic expert. In order to know more information, you have to surf our web portal.

    ReplyDelete
  14. Your blogs are amazing and I am glad to read them. Thanks for sharing the tips and samples of our assignments. They are useful in knowing the key points that can increase the value of an assignment. And a special thanks to the My Assignment Help Australia for helping the students 24/7. You can email us at Info@Myassignmenthelpau.Com or Phone Number: +61-2-8005-8227

    ReplyDelete
  15. Hire the best assignment help Adelaide in Australia and let our assignment helpers assist you score high grades in the final term.

    ReplyDelete
  16. I admire people who keep sharing valuable stories through great writing. I'm glad to have read this blog. Thanks and hope to read more soon. Check out Lawrence Todd Maxwell's page to learn more about real estate.

    ReplyDelete
  17. I loved the article, keep updating interesting articles. I will be a regular reader… I am offering assignment help to students over the globe at a low price.
    "Essay writing
    "
    "Essay Writer
    "
    "Article rewriter
    "
    "Essay writing service
    "
    "Essay writing help
    "
    "Write My Essay
    "
    "Write My Article
    "
    "Essay Helps
    "
    "Write my essay cheap
    "
    "Do my essay cheap
    "

    ReplyDelete
  18. Many of the people are depressed about the problems of essay writing. Well, don’t worry about that because we are providing this service at a very reasonable price.
    "Assignment Help
    "
    "Assignment Helper
    "
    "Essay writing
    "
    "Essay writing service
    "
    "Dissertation help
    "
    "Thesis writing help
    "
    "Write My Essay
    "
    "Computer Science Assignment Help
    "
    "Assignment Help Soth Africa
    "
    "Assignment Writing Service
    "

    ReplyDelete
  19. I found this one pretty fascinating and it should go into my collection. Very good work! I am Impressed. We appreciate that please keep going to write
    more content. We are the assignment helper, we provide services all over the globe. We are best in these services:-

    "Assignment help NZ
    "
    "Assignment help NZ
    "
    "Assignment help UK
    "
    "Assignment help US
    "
    "Assignment help Australia
    "
    "Assignment help Canada
    "
    "Assignment helper
    "
    "Assignment help
    "
    "Writing Assignment Help
    "
    "Help For Assignment
    "
    "Write my assignment help
    "

    ReplyDelete
  20. Many of the people are depressed about the problems of essay writing. Well, don’t worry about that because we are providing this service at a very reasonable price.

    "Assignment Help
    "
    "Assignment Helper
    "
    "Essay writing
    "
    "Essay writing service
    "
    "Dissertation help
    "
    "Thesis writing help
    "
    "Write My Essay
    "
    "Do My Essay
    "
    "Hire Cheap Essay Writer
    "
    "College Essay Help
    "

    ReplyDelete
  21. I am searching for some good site for learning. bitmex

    ReplyDelete
  22. For some students, understanding Physics and doing the given homework is easy while for some it is a hard nut to crack. So getting physics homework help is the only sound way out to get rid of the troubles of doing the papers and avoid the mistakes.
    If you have ever taken help from the professional proofreading services for your assignments, then, you must have received an error-free copy from them. Do you want to know how do the expert proofreaders make the papers flawless so that you don’t lose any point? Read this blog to know about this.

    ReplyDelete
  23. I loved the article, keep updating interesting articles. I will be a regular reader… I am offering assignment help to students over the globe at a low price.
    "Assignment Help
    "
    "Assignment Helper
    "
    "Essay writing
    "
    "Essay writing service
    "
    "Dissertation help
    "
    "Thesis writing help
    "
    "Write My Essay
    "
    "Do My Essay
    "
    "Hire Cheap Essay Writer
    "
    "College Essay Help
    "

    ReplyDelete
  24. I found this one pretty fascinating and it should go into my collection. Very good work! I am Impressed. We appreciate that please keep going to write
    more content. We are the assignment helper, we provide services all over the globe. We are best in these services:-
    "Assignment Help
    "
    "Assignment Helper
    "
    "Essay writing
    "
    "Essay writing service
    "
    "Dissertation help
    "
    "Thesis writing help
    "
    "Write My Essay
    "
    "Computer Science Assignment Help
    "
    "Assignment Help Soth Africa
    "
    "Assignment Writing Service
    "

    ReplyDelete
  25. Thanks for sharing this information. I have shared this link with others keep posting such information. to provide best in class law assignment help online at very affordable prices.
    "Essay writing
    "
    "Essay Writer
    "
    "Article rewriter
    "
    "Essay writing service
    "
    "Essay writing help
    "
    "Write My Essay
    "
    "Write My Article
    "
    "Essay Helps
    "
    "Write my essay cheap
    "
    "Do my essay cheap
    "

    ReplyDelete
  26. Many of the people are depressed about the problems of essay writing. Well, don’t worry about that because we are providing this service at a very reasonable price.
    Digital Markrting Blog
    SEO Blog
    Social Media Blog
    Email Marketeting Blog
    Online marketing Blog

    ReplyDelete
  27. I found this one pretty fascinating and it should go into my collection. Very good work! I am Impressed. We appreciate that please keep going to write
    more content. We are the assignment helper, we provide services all over the globe. We are best in these services:-

    "Assignment help NZ
    "
    "Assignment help NZ
    "
    "Assignment help UK
    "
    "Assignment help US
    "
    "Assignment help Australia
    "
    "Assignment help Canada
    "
    "Assignment helper
    "
    "Assignment help
    "
    "Writing Assignment Help
    "
    "Help For Assignment
    "
    "Write my assignment help
    "

    ReplyDelete
  28. I am searching for some good site for learning. Sto

    ReplyDelete
  29. Our online programming help services ensure students receive needed assistance to fulfill their desired academic goals.

    ReplyDelete
  30. I am Olivia Crew as an “Academic Writer” in Livewebtutors. The above post has given reliable and genuine information about Assignment Help Australia, New Zealand, USA, UK etc. Looking forward to avail their eminent services.
    visit now:- assignment help

    ReplyDelete
  31. A lot of valuable information can be derived from the post. Certainly, this compelling post will encourage readers to choose Assignment Help Australia services. You can email us at info@firstassignmenthelp.com.

    ReplyDelete
  32. That’s a great idea you have, and yes this would make use of the information you have provided us through this blog. I often avail the services of GOASSIGNMENTHELP . They have given me unlimited free assistance for all assignment help

    ReplyDelete
  33. It is very important for the students to take help from the Online Essay Editors to complete your tasks in an effective manner. this will further contribute in scoring well in your exams.

    ReplyDelete
  34. Thanks for this informative content. It’s really good. Actually, I want to share some thoughts and reviews about an Australian assignment help company in Australia and the brand name is SAMPLE ASSIGNMENT. Here, I am working as an Academic Expert. To look at our online academic assistants who provide reference assignment including Accounting, Management, Finance, IT, Economics, Computer Science, Nursing, Marketing; all Academic subjects to University Students all over the Australia or even worldwide, Here is a big online assignment help providers who help students to get HD grades according to assessment guidelines and instructions. Those who are searching fo assignment help Melbourne, Perth, Brisbane, Adelaide etc. get a touch with Sample Assignment - the No.1 Assignment provider. Any student really wants to buy an assignment at the cheapest price goes to our branded website and has a look and opts our amazing and informative services, you can avail of our convenient online assignment help and samples available on our website for free. You can download it if you want. Are you ready to get 100 out of 100 in your university assessment? We assign the best writer according to the subject for your academic problems and provide support in assignment writing services. Our Customer Care Executives are available 24*7 hours to assist you in the best possible manner. Phone calls and emails are the best methods used by online assignment maker.

    ReplyDelete