Sunday, November 27, 2016

The Performance Cost of Boxing in .NET

I recently had to do some performance optimizations against a sorted dictionary that yielded some interesting results...

Background: I am used to using Tuples a lot, simply because they are easy to use and normally quite efficient. Please remember that Tuples were changed from structs to classes back in .NET 4.0.

Problem: A struct decreased performance!

I had a SortedDictionary that was using a Tuple as a key, so I thought "hey, I'll just change that tuple to a struct and reduce the memory usage." ...bad news, that made performance WORSE!

Why would using a struct make performance worse? It's actually quite simple and obvious when you think about it: it was causing comparisons to repeatedly box the primitive data structure, thus allocating more memory on the heap and triggering more garbage collections.

Solution: Use a struct with an IComparer.

I then created a custom struct and used that; it was must faster, but it was still causing boxing because of the non-generic IComparable interface. So finally I added a generic IComparer and passed that into my dictionary constructor; my dictionary then ran fast and efficient, causing a total of ZERO garbage collections!

See for yourself:

The Moral of the Story

Try to be aware of what default implementations are doing, and always remember that boxing to object can add up fast. Also, pay attention to the Visual Studio Diagnostics Tools window; it can be very informative!

Here is how many lines of code it took to achieve a 5x performance increase:

private struct MyStruct
{
    public MyStruct(int i, string s) { I = i; S = s; }
    public readonly int I;
    public readonly string S;
}
 
private class MyStructComparer : IComparer<MyStruct>
{
    public int Compare(MyStruct x, MyStruct y)
    {
        var c = x.I.CompareTo(y.I);
        return c != 0 ? c : StringComparer.Ordinal.Compare(x.S, y.S);
    }
}

Test Program

I have written some detailed comments in the Main function about what each test is doing and how it will affect performance. Let's take a look...

public static class Program
{
    public static void Main(string[] args)
    {
        // This is going to use the class implementation
        // of Tuple that was changed in .NET 4.0. It is
        // be inefficient for three reasons:
        // 1) It is allocating a new class on the heap 
        //    for each and every key.
        // 2) It is using the default object comparer
        //    to check each item, causing inefficient 
        //    comparisons and...
        // 3) Causing boxing of primitive values.
        ClassTupleAsKey();
        Reset();
        // DURATION: 8,479 miliseconds
 
        // This is going to use the struct implementation
        // of Tuple that was available from .NET 2.0
        // until 4.0. It is even less efficiente than the
        // class tuple for both reasons listed above, and 
        // one new reason:
        // 4) The StructTuple itself will be boxed when
        //    being passed between comparers, causing
        //    even more garbage collections to occur!
        StructTupleAsKey();
        Reset();
        // DURATION: 8,880 miliseconds
 
        // Now we move to a custom struct implementation
        // for the dictionary key, but because we are using
        // a SortedDictionary we still need to implement
        // IComparable, which is not generic, and thus will
        // be slow for one reason:
        // 1) The struct itself will be boxed when being
        //    passed between comparers.
        MyStructAsKey();
        Reset();
        // DURATION: 2,896 miliseconds
 
        // This is pretty much as fast as we can get; no
        // heap allocations, no boxing, fast comparisons.
        MyStructAsKeyWithCompare();
        // DURATION: 1,442 miliseconds
    }
 
    private static void Reset()
    {
        GC.Collect();
        Thread.Sleep(500);
    }
 
    private static void ClassTupleAsKey()
    {
        var dictionary = new SortedDictionary<ClassTuple<int, string>, int>();
        var sw = Stopwatch.StartNew();
 
        for (var i = 0; i < 1000000; i++)
        {
            var key = new ClassTuple<int, string>(i % 1000, i.ToString());
            dictionary.Add(key, i);
        }
 
        sw.Stop();
        Console.WriteLine("ClassTupleAsKey: " + sw.ElapsedMilliseconds);
    }
 
    private static void StructTupleAsKey()
    {
        var dictionary = new SortedDictionary<StructTuple<int, string>, int>();
        var sw = Stopwatch.StartNew();
 
        for (var i = 0; i < 1000000; i++)
        {
            var key = new StructTuple<int, string>(i % 1000, i.ToString());
            dictionary.Add(key, i);
        }
 
        sw.Stop();
        Console.WriteLine("StructTupleAsKey: " + sw.ElapsedMilliseconds);
    }
 
    private static void MyStructAsKey()
    {
        var dictionary = new SortedDictionary<MyStructA, int>();
        var sw = Stopwatch.StartNew();
 
        for (var i = 0; i < 1000000; i++)
        {
            var key = new MyStructA(i % 1000, i.ToString());
            dictionary.Add(key, i);
        }
 
        sw.Stop();
        Console.WriteLine("StructAsKey: " + sw.ElapsedMilliseconds);
    }
 
    private static void MyStructAsKeyWithCompare()
    {
        var dictionary = new SortedDictionary<MyStructB, int>(MyStructBComparer.Instance);
        var sw = Stopwatch.StartNew();
 
        for (var i = 0; i < 1000000; i++)
        {
            var key = new MyStructB(i % 1000, i.ToString());
            dictionary.Add(key, i);
        }
 
        sw.Stop();
        Console.WriteLine("StructAsKeyWithCompare: " + sw.ElapsedMilliseconds);
    }
 
    public class ClassTuple<T1, T2> : IStructuralEquatable, IStructuralComparable, IComparable
    {
        private readonly T1 _item1;
        private readonly T2 _item2;
 
        public T1 Item1 => _item1;
        public T2 Item2 => _item2;
 
        public ClassTuple(T1 item1, T2 item2)
        {
            _item1 = item1;
            _item2 = item2;
        }
 
        public override bool Equals(object obj)
        {
            return ((IStructuralEquatable) this).Equals(obj, EqualityComparer<object>.Default);
        }
 
        bool IStructuralEquatable.Equals(object other, IEqualityComparer comparer)
        {
            var objTuple = other as ClassTuple<T1, T2>;
            if (objTuple == null) return false;
            return comparer.Equals(_item1, objTuple._item1) && comparer.Equals(_item2, objTuple._item2);
        }
 
        int IComparable.CompareTo(object obj)
        {
            return ((IStructuralComparable) this).CompareTo(obj, Comparer<object>.Default);
        }
 
        int IStructuralComparable.CompareTo(object other, IComparer comparer)
        {
            if (other == null) return 1;
            var objTuple = other as ClassTuple<T1, T2>;
 
            if (objTuple == null)
                throw new ArgumentException("ArgumentException_TupleIncorrectType", nameof(other));
 
            var c = comparer.Compare(_item1, objTuple._item1);
            return c != 0 ? c : comparer.Compare(_item2, objTuple._item2);
        }
 
        public override int GetHashCode()
        {
            return ((IStructuralEquatable) this).GetHashCode(EqualityComparer<object>.Default);
        }
 
        int IStructuralEquatable.GetHashCode(IEqualityComparer comparer)
        {
            return CombineHashCodes(comparer.GetHashCode(_item1), comparer.GetHashCode(_item2));
        }
 
        private static int CombineHashCodes(int h1, int h2)
        {
            return ((h1 << 5) + h1) ^ h2;
        }
    }
 
    public struct StructTuple<T1, T2> : IStructuralEquatable, IStructuralComparable, IComparable
    {
        private readonly T1 _item1;
        private readonly T2 _item2;
 
        public T1 Item1 => _item1;
        public T2 Item2 => _item2;
 
        public StructTuple(T1 item1, T2 item2)
        {
            _item1 = item1;
            _item2 = item2;
        }
 
        public override bool Equals(object obj)
        {
            return ((IStructuralEquatable) this).Equals(obj, EqualityComparer<object>.Default);
        }
 
        bool IStructuralEquatable.Equals(object other, IEqualityComparer comparer)
        {
            if (!(other is StructTuple<T1, T2>)) return false;
            var objTuple = (StructTuple<T1, T2>) other;
            return comparer.Equals(_item1, objTuple._item1) && comparer.Equals(_item2, objTuple._item2);
        }
 
        int IComparable.CompareTo(object obj)
        {
            return ((IStructuralComparable) this).CompareTo(obj, Comparer<object>.Default);
        }
 
        int IStructuralComparable.CompareTo(object other, IComparer comparer)
        {
            var objTuple = (StructTuple<T1, T2>) other;
            var c = comparer.Compare(_item1, objTuple._item1);
            return c != 0 ? c : comparer.Compare(_item2, objTuple._item2);
        }
 
        public override int GetHashCode()
        {
            return ((IStructuralEquatable) this).GetHashCode(EqualityComparer<object>.Default);
        }
 
        int IStructuralEquatable.GetHashCode(IEqualityComparer comparer)
        {
            return CombineHashCodes(comparer.GetHashCode(_item1), comparer.GetHashCode(_item2));
        }
 
        private static int CombineHashCodes(int h1, int h2)
        {
            return ((h1 << 5) + h1) ^ h2;
        }
    }
 
    private struct MyStructA : IComparable
    {
        public MyStructA(int i, string s)
        {
            I = i;
            S = s;
        }
 
        public readonly int I;
        public readonly string S;
 
        public int CompareTo(object obj)
        {
            var y = (MyStructA) obj;
            var c = I.CompareTo(y.I);
            return c != 0 ? c : StringComparer.Ordinal.Compare(S, y.S);
        }
    }
 
    private struct MyStructB
    {
        public MyStructB(int i, string s)
        {
            I = i;
            S = s;
        }
 
        public readonly int I;
        public readonly string S;
    }
 
    private class MyStructBComparer : IComparer<MyStructB>
    {
        public static readonly MyStructBComparer Instance = new MyStructBComparer();
 
        public int Compare(MyStructB x, MyStructB y)
        {
            var c = x.I.CompareTo(y.I);
            return c != 0 ? c : StringComparer.Ordinal.Compare(x.S, y.S);
        }
    }
}

Enjoy,
Tom

92 comments:

  1. What happens if you implement IComparable (generic) instead of IComparable (non-generic)?

    ReplyDelete
    Replies
    1. Implementing the generic IComparer makes all the difference! When it the IComparer is not generic it will have to box the struct for every comparison, leading to the performance problems described in the blog post.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. I created another test case using a struct that implemented the generic IComparable interface, i.e. (using [] braces instead of <> due to HTML stripping):

      private struct ComparableStruct: IComparable[ComparableStruct]
      {
      public int CompareTo(ComparableStruct other)
      {
      int c = I.CompareTo(other.I);
      return c != 0 ? c : StringComparer.Ordinal.Compare(S, other.S);
      }
      }

      The results on my PC (i7 3770K @ 3.5GHz) showed that there was no boxing and it was only slightly slower than the struct with an IComparer (~1000 ms vs ~900 ms). It's also simpler to implement and easier to use since you don't have to remember to use the non-default Comparer every time you create a container...

      Delete
    4. Yes, you are absolutely correct; the IComparable will solve the problem as well! I apologize, when I read the question I thought that Mackenzie was referring to the non generic version of IComparer. Bottom line: prevent the cast to object!

      Delete
  2. It should be generated by the compiler

    ReplyDelete
    Replies
    1. The default Comparer implementation will often provide the desired functionality, however it will come at the performance cost of boxing the values for comparison.

      Delete
  3. I am impressed. I don't think Ive met anyone who knows as much about this subject as you do. You are truly well informed and very intelligent. You wrote something that people could understand and made the subject intriguing for everyone. Really, great blog you have got here. starslot789

    ReplyDelete
  4. muay thai equipment Offers the best quality Muay Thai equipment with Maximum satisfaction.

    ReplyDelete
  5. My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more! Mike Tyson vs Roy Jones live stream

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder for 토토사이트, what about the other side? !!!!!!Thanks

    ReplyDelete
  9. I am contemplating this topic. I think you can solve my problems. My site is at "카지노사이트". I hope you can help me.

    ReplyDelete
  10. Your work is great and I value you and jumping for some more educational posts. Much obliged to you for sharing incredible data to us. 토토사이트

    ReplyDelete
  11. Thank you for very good information. May I ask for more information?? This is too helpful information for me. I think you are probably interested in 먹튀검증업체 as well. The above information is on my blog, so please feel free to visit

    ReplyDelete
  12. That’s a wonderful piece of writing. Not as good as you, but I’m wearing it like this. 토토사이트

    ReplyDelete
  13. how to write an essay for college admission 파워볼사이트

    ReplyDelete
  14. I like the theme. A debt of gratitude is in order for such an astounding your web. 안전공원

    ReplyDelete
  15. These look great. We will be wrapping our up in about 3 weeks. 해외스포츠중계

    ReplyDelete
  16. Awesome! Exactly what I need! Can't wait to purchase the Kinder one 바카라사이트

    ReplyDelete
  17. 당신의 글은 정말 사랑스러워 보여요, 여기 당신이 좋아할 만한 사이트 링크가 있어요.
    사설토토사이트

    ReplyDelete
  18. I read a good article. In the future, 먹튀 I will visit often and see a lot of content. I will visit often in the future^^

    ReplyDelete
  19. I do trust all of the ideas you have introduced on your post. They’re very convincing and can definitely work. Nonetheless, the posts are too brief for newbies. Could you please extend them a bit from subsequent time? Thank you for the post.
    카지노사이트

    ReplyDelete
  20. Hi, Neat post. There's a problem together with your site in web explorer, would check this?
    IE still is the market chief and a good part of other people will miss your excellent writing
    due to this problem.
    오피

    ReplyDelete
  21. Hiring a pro house maintaining company commonly costs so much money it is considered being a additional expense month after month. Your home cleaning moves available your housemaid As i. e. you will want to depend on her behalf for anything relating to cleaning. Though, you may result in feeling like while driving know all sorts of things related to your residence. You may are aware that your privacy is that it is impeded once cleaning maids remain, and oftentimes, you need to deliberately continue a determine your performs and words collectors maid is just about. You may possibly face various safety inquiries when any specific outsider enters your home. Though, maintaining companies be certain their service personnel for credibility, cases in robbery always occur within clients' websites. cleaning company in dubai

    ReplyDelete
  22. Thank You So Much For providing the important information. We are offering a luxurious and Delicious erotic Nuru massage and escort service. Call Girls in India.

    ReplyDelete
  23. I finally found what I was looking for! I'm so happy. 안전한놀이터 Your article is what I've been looking for for a long time. I'm happy to find you like this. Could you visit my website if you have time? I'm sure you'll find a post of interest that you'll find interesting.


    ReplyDelete
  24. Hello, I'm happy to see some great articles on your site. Would you like to come to my site later? My site also has posts, comments and communities similar to yours. Please visit and take a look 토토사이트


    ReplyDelete
  25. Your ideas inspired me very much. 메이저토토사이트모음 It's amazing. I want to learn your writing skills. In fact, I also have a website. If you are okay, please visit once and leave your opinion. Thank you.


    ReplyDelete
  26. Hello, I read the post well. 메이저토토 It's a really interesting topic and it has helped me a lot. In fact, I also run a website with similar content to your posting. Please visit once


    ReplyDelete
  27. A basic yet effective way to judge any take my math class for me is to go through the review section. It says a lot about service providers. Focus on the negative reviews especially (even if they are low in numbers). This way you will be subconsciously ready for negative outcomes as well.
    Suppose a service provider has more positive reviews in comparison to the negative ones, you can go ahead, but keep the negative ones in mind too. Tell them that you are not expecting a set of things you read in the reviews. And let them work. This way you can easily get assignment help online without being cheated on.

    ReplyDelete
  28. Nice.You made some good points there. I did a Google search about the topic and found most people will believe your blog 카지노사이트

    ReplyDelete
  29. Your article reflects the issues people care about. The article provides timely information that reflects multi-dimensional views from multiple perspectives. 토토사이트


    ReplyDelete
  30. I like what you guys are usually up too. This kind of clever work and coverage! Keep up the very good works guys I’ve incorporated you guys to blogroll.
    먹튀검증

    ReplyDelete
  31. Nice..The clearness on your post is simply spectacular and that i could assume you are a professional on this subject 룰렛

    ReplyDelete
  32. Your information was very useful. I m very pleased to read this article.카지노사이트

    ReplyDelete
  33. Did you ever listen, "take my online class for me?" Are you looking for an easy, inexpensive professional service to complete your class online, homework, exams, and other similar classes? We recognize that you have invested an enormous amount for your online classes and that in your online class and you do not want a bad grade. If you are an online student, get support from us online and get your load off. They have tutors who have attended many courses with online pupils, including their math homework, tasks, quizzes, experiments, and online exams who are looking to take my online class.

    ReplyDelete
  34. Pretty great post. I just stumbled upon your weblog and wished to say that I have really enjoyed browsing your weblog posts. In any case I’ll be subscribing to your rss feed and I am hoping you write again very soon! Feel free to visit my website; 일본야동

    ReplyDelete
  35. I will be very happy to discover this kind of post very useful personally, since it consists of great deal of info. I usually prefer to read the top quality content material and also this factor I discovered in your soul submit. Thanks for sharing. Feel free to visit my website; 일본야동

    ReplyDelete
  36. This is a very useful and important information, it was so useful to me and other readers, thank you for always feeding the readers with interesting and useful information, your blog is indeed doing very well, weldone, meanwhile you can checkout has fce post utme form out

    ReplyDelete
  37. One of the main reasons why students do not want to write organic chemistry assignment on their own is the lack of adequate knowledge of that particular subject, language barrier and difficulty in constructing the given content into desired assignment. Keeping the financial limitations of student in mind there are my homework done online service available to do needful for students.

    ReplyDelete
  38. Hi, I do think this is a great site. I stumbledupon it ;) I may revisit yet again since i have book marked it.

    Money and freedom is the best way to change, may you
    be rich and continue to help other people.


    https://www.betmantoto.pro

    ReplyDelete
  39. I've been troubled for several days with this topic. 슬롯사이트, But by chance looking at your post solved my problem! I will leave my blog, so when would you like to visit it?


    ReplyDelete
  40. Thanks to you for your effort...RPD Water Care Solutions is a pioneer in offering clients with high-quality goods and excellent service at low pricing. Sewage Treatment Plant

    ReplyDelete
  41. You are busy in your life activities and thinking about Pay Someone To Do My Online Class For Me and cannot handle the online class or exam which is scheduled up? You want someone to get an A for you in your complete online course for you? No worry! We have come to the place where our experts always do the job with perfection. Your satisfaction is our ultimate goal.

    ReplyDelete
  42. it’s awesome and I found this one informative. Tanishq Adv

    ReplyDelete
  43. My name is Alexander Barnes. GotoAssignmentHelp best CPM homework helpKeyword
    service providers in Australia countries. best services provide homework help, case study help. team paper helps assay help, any other countries Australia service provide. Assignment writing has always been a cause of concern for the students across the world. And it is same with the students of Australia. During the course of the academic career, the students of Australia face tough time to prepare assignments. GotoAssignmentHelp 24/7 hr service provide. if you are looking for an online assignment helper service. The GotoAssignmentHelp team will take care of your assignments one you book your order at our website. For more information, hire our Online Do my homework
    now.

    ReplyDelete
  44. Thank you for sharing your knowledge. I really admire your efforts and I will be waiting for your next post thank you once again. https://disqus.com/by/tanishqadv/about/

    ReplyDelete
  45. I am thankful you to visit here...RPD Water Care Solutions is a pioneer in offering clients with high-quality goods and excellent service at low pricing. Sewage treatment Plant manufacturer in Jaipur

    ReplyDelete
  46. https://sites.google.com/view/sewage-water-treatment-plant/swimming-pool-plant ///// RPD Water treatment STP Waste Water Solution and Manufacturer Company in Jaipur. Get preeminent Sewage water treatment plant from Us to improve Your industrial processes.

    ReplyDelete
  47. I Went ALL IN On 메이저사이트추천 For A HUGE Comeback! (PROFIT!)

    ReplyDelete
  48. EXCLUSIVE: Crown 메이저토토사이트추천 exposed. Sex trafficking, drugs, money laundering

    ReplyDelete
  49. I wrote about a similar issue, I give you the link to my site.bank guarantee

    ReplyDelete
  50. Hi! this is nice article you shared with great information. Thanks for giving such a wonderful informative information. I hope you will publish again such type of post. Also, please check out about MetaMask Log In | MetaMask | Metamask Chrome Extension

    ReplyDelete
  51. Thanks for the informative article. I hope you will provide more articles like this.
    Metamask wallet | Coinbase Login | Coinbase Login

    ReplyDelete

  52. Great Article. I really like your blog. Keep sharing more.
    Coinbase Pro Login | Coinbase Login

    ReplyDelete
  53. I read this post your post so nice and very informative post thanks for sharing this post!
    spookyswap | Quickswap

    ReplyDelete
  54. I'm looking for a lot of data on this topic. The article I've been looking for in the meantime is the perfect article. Please visit my site for more complete articles with him! แทงมวย

    ReplyDelete
  55. I have read your article, it is very informative and helpful for me.I admire the valuable information you offer in your articles. Thanks for posting it.. r1fight

    ReplyDelete
  56. I wrote about a similar issue, I give you the link to my site. single girl attitude quotes in hindi

    ReplyDelete
  57. Hello my fellow friends and bloggers. It felt really great going through all your article ! Really felt the effort and hardwork you have put . if you are intrested in Satta King you can check out my website. It is quick accurate and easy to use south delhi satta king

    ReplyDelete
  58. Excellent read, Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. hanumanchalisalyrics

    ReplyDelete
  59. Marry James is a writing Expert with 15+ years of experience. Marry is also associated with MyAssignmenthelp.com, where she regularly helps students write their essays/assignments. In addition, Marry also likes to read and has read more than 100 books now. Students prefer his services as a tutor and as a counsellor and guides students on academic issues. She offers HTML assignment help to students who need help with their papers. Marry is a programmer too, so she has detailed knowledge about the subject.

    Other Service
    write my essay for me
    Top Essay Writing Service
    English Essay Writing Help
    Physics homework help
    college essays help
    Essay Editing Service
    Fraction Calculator
    Persuasive Essay Help
    write my research paper
    plagiarism checker
    Book Review Writing
    Title Generator
    plagiarism checker
    Nursing Resume
    free tools
    Harvard referencing generator
    Summary Generator
    fnsacc311 assessment answers
    hltaid004 assessment answers

    ReplyDelete
  60. I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article.
    Satta King Faridabad

    ReplyDelete
  61. I am understand everything about this post i hope you are write awesome articale like that.
    Mass Backlinks

    ReplyDelete
  62. I am really enjoying reading your well written articles. I think you spend numerous effort and time updating your blog. Bollywood Stars Biography

    ReplyDelete
  63. Thanks for sharing your experience and valuable advice or enjoyed to reading this post. Christ University Admission Date 2022

    ReplyDelete
  64. Pancake Swap allows users to earn an additional yield by staking supported liquidity provider (LP) tokens in one of its numerous yield farms. By participating in a yield farm, users earn a CAKE yield on their LP tokens. This is on top of the yields generated through transaction fees.

    ReplyDelete
  65. Atomic Wallet allows users to earn an additional yield by staking supported liquidity provider (LP) tokens in one of its numerous yield farms. By participating in a yield farm, users earn a CAKE yield on their LP tokens. This is on top of the yields generated through transaction fees.

    ReplyDelete
  66. Having an understanding of statistics enables you to utilize the appropriate procedures to collect the data, to carry out the appropriate analysis, and to present the results in an effective manner. The application of statistics is an essential step in the process of making scientific discoveries, as well as judgments and forecasts that are founded on data. The level of expertise of the tutors who assist students with their assignments is of the utmost significance to every single student who uses these services. When it comes to matters pertaining to payment, no one will ever be willing to make a concession on anything. The quality of the “my homework done online service”always meets or exceeds expectations. They are able to better control and maintain the quality standard as a direct result of the ratings.

    ReplyDelete
  67. post... thanks For Sharing !!Great information for new guy like Bhagwat Geeta in Hindi PDF

    ReplyDelete
  68. post... thanks For Sharing !!Great information for new guy like Bhagwat Geeta in Hindi PDF

    ReplyDelete
  69. This is a Very well Written Post. Your Point of View Caught My Eye and It Was Very Interesting. Thanks for This Great Job

    Jaunpur Female Companion
    Jhansi Female Companion
    Kanpur Female Companion

    ReplyDelete

Real Time Web Analytics