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

73 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. Such A nice post... thanks For Sharing !!Great information for new guy like Hanuman Chalisa Lyrics

    ReplyDelete
  4. This is also a very good post which I really enjoyed reading. It is not everyday that I have the possibility to see something like this.satta king

    ReplyDelete
  5. 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
  6. muay thai equipment Offers the best quality Muay Thai equipment with Maximum satisfaction.

    ReplyDelete
  7. 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
  8. This comment has been removed by the author.

    ReplyDelete
  9. The gear can be separated into a few classifications; every class further has a wide scope of items in it. Alongside the classes, the boxing hardware can likewise be ordered dependent on its motivation of utility. Allboxingodds.com

    ReplyDelete
  10. This is really very nice post you shared, i like the post, thanks for sharing.. Oregon Business Registry

    ReplyDelete
  11. I think it could be more general if you get a football sports activity.
    토토사이트

    ReplyDelete
  12. Wide range of Punching Bags for fitness and training, made of durable & premium quality long-lasting material. All sizes are available. Deliver to worldwide. Free UK Delivery. punching bag

    ReplyDelete
  13. I am genuinely thankful to the holder of this web page who has shared this wonderful paragraph at at this place. 토토사이트

    ReplyDelete
  14. Please continue this great work and I look forward to more of your awesome blog posts인증업체

    ReplyDelete
  15. A debt of gratitude is in order for sharing the information, keep doing awesome... I truly delighted in investigating your site. great asset... 먹튀검증

    ReplyDelete
  16. It is the intent to provide valuable information and best practices, including an understanding of the regulatory process. 스포츠티비

    ReplyDelete
  17. I wanted to leave a little comment to support you and wish you a good continuation. 토토사이트 Wishing you the best of luck for all your blogging efforts.

    ReplyDelete
  18. I have been searching to find a comfort or effective procedure to complete this process and I think this is the most suitable way to do it effectively. 먹튀사이트

    ReplyDelete

  19. While looking for articles on these topics, I came across this article on the site here. As I read your article, I felt like an expert in this field. I have several articles on these topics posted on my site. Could you please visit my homepage? 온라인홀덤

    ReplyDelete
  20. Hello ! I am the one who writes posts on these topics토토사이트 I would like to write an article based on your article. When can I ask for a review?

    ReplyDelete
  21. When did you start writing articles related to ? To write a post by reinterpreting the 안전놀이터 I used to know is amazing. I want to talk more closely about , can you give me a message?

    ReplyDelete
  22. Great post! I am actually getting ready to across this information, is very helpful my friend. Also great blog here with all of the valuable information you have. Keep up the good work you are doing here. 토토사이트

    ReplyDelete
  23. Are you the one who studies this subject?? I have a headache with this subject.카지노사이트Looking at your writing was very helpful.

    ReplyDelete
  24. Amazing article..!! Thank you so much for this informative post. I found some interesting points and lots of information from your blog. Thanks 토토사이트

    ReplyDelete
  25. The assignment submission period was over and I was nervous, 메이저놀이터 and I am very happy to see your post just in time and it was a great help. Thank you ! Leave your blog address below. Please visit me anytime.

    ReplyDelete
  26. Pretty nice post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your blog posts. In any case I will be subscribing to your rss feed and I hope you write again soon 안전놀이터

    ReplyDelete
  27. Thank you again for all the knowledge you distribute,Good post. I was very interested in the 안전놀이터, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards, 사설토토사이트

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

    ReplyDelete
  29. Hello
    Thank you for giving me useful information.
    Please keep posting good information in the future
    I will visit you often. Thank you.
    I am also running the site. 안전놀이터 This is a related site, so please visit once.
    Have a niceday!

    ReplyDelete
  30. First of all, thank you for letting me see this information. I think this article can give me a lot of inspiration. I would appreciate 바둑이사이트 if you could post more good contents in the future.

    ReplyDelete
  31. Personally I think overjoyed I discovered the blogs. 토토사이트

    ReplyDelete
  32. Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained 먹튀검증

    ReplyDelete
  33. An automated guided vehicle or automatic guided vehicle (AGV) is a portable robot that follows along with marked magnets or lasers for navigation. 먹튀폴리스

    ReplyDelete
  34. I am really so much happy to find the international day of peace topics and reviews. Everything needed to update best stories on this 먹튀검증커뮤니티

    ReplyDelete
  35. It was a very good post indeed. I thoroughly enjoyed reading it in my lunch time. Will surely come and visit this blog more often. Thanks for sharing. 메이저놀이터

    ReplyDelete
  36. It is a completely interesting blog publish.I often visit your posts for my project's help about Diwali Bumper Lottery and your super writing capabilities genuinely go away me taken aback.Thank you a lot for this publish 안전놀이터

    ReplyDelete
  37. You're the best to share us about this redesign. Trust you won't get tired on making posts as useful as this 안전놀이터

    ReplyDelete
  38. You're the best to share us about this redesign. Trust you won't get tired on making posts as useful as this 안전놀이터

    ReplyDelete
  39. I have been exploring for a little bit for any high-quality articles or blog posts in this kind of space . Exploring in Yahoo I ultimately stumbled upon this site. Reading this information So i’m satisfied to show that I’ve a very just right uncanny feeling I found out just what I needed. I such a lot indisputably will make certain to do not forget this web site and give it a glance a continuing 먹튀폴리스

    ReplyDelete
  40. Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards 토토사이트

    ReplyDelete
  41. Thanks for sharing these informations. I really like your blog post very much. You have really shared a informative and interesting blog post . 먹튀폴리스

    ReplyDelete
  42. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work. 토토사이트

    ReplyDelete
  43. Major thankies for the post.Really thank you! Really Great. 파워볼사이트

    ReplyDelete
  44. Admiring the time and effort you put into your blog and detailed information you offer!.. 먹튀검증업체

    ReplyDelete
  45. Extremely pleasant article, I appreciated perusing your post, exceptionally decent share, I need to twit this to my adherents. 먹튀폴리스꽁머니

    ReplyDelete
  46. Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. 먹튀사이트

    ReplyDelete
  47. I found your documents very interesting. You have a amazing skills of writing a brief content. Thanks for talking about this, it is really a useful for me. I am going to preserve this. 먹튀폴리스

    ReplyDelete
  48. You have observed very interesting points ! ps decent internet site . 토토커뮤니티 꽁머니

    ReplyDelete
  49. Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!! 먹튀사이트

    ReplyDelete
  50. Good day,your writing style is great and i love it, 메이저사이트 추천

    ReplyDelete
  51. I really appreciate the kind of topics you post here. Thanks for sharing  information that is actually helpful. Good day! Want to know the steps to resolve 안전놀이터추천

    ReplyDelete
  52. Hello
    Thank you for giving me useful information.
    Please keep posting good information in the future
    I will visit you often. Thank you.
    I am also running the site. 메이저놀이터 This is a related site, so please visit once.
    Have a niceday!

    ReplyDelete
  53. 토토검증사이트추천
    The website is looking bit flashy and it catches the visitors eyes. Design is pretty simple and a good user friendly interface

    ReplyDelete
  54. this article for the well-researched content and excellent wording. I got so involved in this material that
    I couldn’t stop reading. I am impressed with your work and skill. Thank you so much 사설검증사이트

    ReplyDelete
  55. Your explanation is organized very easy to understand!!! I understood at once. Could you please post about 바카라사이트?? Please!!

    ReplyDelete
  56. I actually enjoy the posting. It usually is wonderful to evaluate any one demonstrate around thoughts in the cardiac coupled with lucidity in this significant dilemma can be immediately found. 슈어벳

    ReplyDelete
  57. It's always a pleasure to read your magnificent articles on this site. You are among the top writers of this generation, and there's nothing you can do that will change my opinion on that. My friends will soon realize how good you are. 토토사이트

    ReplyDelete
  58. Thanks for a marvelous posting! I definitely enjoyed reading it, you’re a great author. I will ensure that I bookmark your blog and will come back sometime soon. I want to encourage that you continue your great work, have a nice day 이기자벳

    ReplyDelete
  59. We stumbled over here by a different website and thought I might check things out. I like what I see so now i am following you. Look forward to finding out about your web page again. 안전놀이터

    ReplyDelete
  60. I wanted to leave a little comment to support you and wish you a good continuation. 토토사이트 Wishing you the best of luck for all your blogging efforts.

    ReplyDelete
  61. Thank you and thank you so much. I'll share you useful information.토토사이트

    ReplyDelete
  62. Sweet blog! I found it while browsing on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get
    there! Thank you
    Also visit my site:강남출장안마

    ReplyDelete
  63. When I read your article on this topic, the first thought seems profound and difficult. There is also a bulletin board for discussion of articles and photos similar to this topic on my site, but I would like to visit once when I have time to discuss this topic. 온라인홀덤

    ReplyDelete
  64. First of all, thank you for your post. 먹튀검증 Your posts are neatly organized with the information I want, so there are plenty of resources to reference. I bookmark this site and will find your posts frequently in the future. Thanks again ^^

    ReplyDelete

Real Time Web Analytics