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

80 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. Hello. I'm subscribed to your posts. You inspire me a lot.카지노사이트I am so grateful.

    ReplyDelete
  10. I've been looking for photos and articles on this topic over the past few days due to a school assignment, and I'm really happy to find a post with the material I was looking for! I bookmark and will come often! Thanks :D 바둑이사이트

    ReplyDelete
  11. I haven't seen anything interesting in a long time, and I'm writing on this form, so I hope to see you.토토사이트

    ReplyDelete
  12. I'm writing on this topic these days, , but I have stopped writing because there is no reference material. Then I accidentally found your article. I can refer to a variety of materials, so I think the work I was preparing will work! Thank you for your efforts. 토토커뮤니티

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

    ReplyDelete
  14. This site seems to inspire me a lot. Thank you so much for organizing and providing this quality information in an easy to understand way. 먹튀검증사이트 I think that a healthy era of big data can be maintained only when such high-quality information is continuously produced. And I, too, are working hard to organize and provide such high-quality information. It would be nice to come in once and get information. 먹튀검증

    ReplyDelete
  15. I've been looking for photos and articles on this topic over the past few days due to a school assignment, and I'm really happy to find a post with the material I was looking for! I bookmark and will come often! Thanks :D 토토사이트

    ReplyDelete
  16. I am overwhelmed by your post with such a nice topic. Usually I visit your 메이저토토사이트 and get updated through the information you include but today’s blog would be the most appreciable. Well done!

    ReplyDelete
  17. 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
  18. I am contemplating this topic. I think you can solve my problems. My site is at "카지노사이트". I hope you can help me.

    ReplyDelete
  19. 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
  20. As I am looking at your writing, I regret being unable to do outdoor activities due to Corona 19, and I miss my old daily life. If you also miss the daily life of those days, would you please visit my site once? My site is a site where I post about photos and daily life when I was free.토토커뮤니티

    ReplyDelete
  21. I learned a lot from you.토토사이트 I have a hobby similar to yours.

    ReplyDelete
  22. Hey there! I could have sworn I’ve been to this website before but after reading through some of the post I realized it’s new to me. Nonetheless, I’m definitely happy I found it and I’ll be book-marking and checking back frequently 안전놀이터추천

    ReplyDelete
  23. Of course, your article is good enough, 먹튀검증 but I thought it would be much better to see professional photos and videos together. There are articles and photos on these topics on my homepage, so please visit and share your opinions.

    ReplyDelete
  24. Of course, your article is good enough, 온라인바둑이 but I thought it would be much better to see professional photos and videos together. There are articles and photos on these topics on my homepage, so please visit and share your opinions.

    ReplyDelete
  25. Nice post love it check my site for fast Satta King we provide superfast and all time result Satta King

    ReplyDelete
  26. 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
  27. I'm writing on this topic these days, , but I have stopped writing because there is no reference material. Then I accidentally found your article. I can refer to a variety of materials, so I think the work I was preparing will work! Thank you for your efforts. 토토커뮤니티

    ReplyDelete
  28. I seriously love your site.. Very nice colors & theme. Did you create this site yourself? Please reply back as I’m trying to create my very own site and would like to learn where you got this from or exactly what the theme is named. Many thanks. 토토사이트추천

    ReplyDelete
  29. I think this site is a must if you want a distinctive design. Why can't 메이저놀이터추천 do other designs? I think it is possible.

    ReplyDelete
  30. 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
  31. I've been searching for hours on this topic and finally found your post. , I have read your post and I am very impressed. We prefer your opinion and will visit this site frequently to refer to your opinion. When would you like to visit my site? 토토사이트

    ReplyDelete
  32. I always think about what is. It seems to be a perfect article that seems to blow away such worries. 안전메이저놀이터 seems to be the best way to show something. When you have time, please write an article about what means!!

    ReplyDelete
  33. Thanks , I’ve just been looking for info about this subject for a long time and yours is the best I have found out till now. But, what in regards to the bottom line? Are you certain in regards to the source? 메이저토토사이트

    ReplyDelete
  34. Nice post love it check my site for fast Satta King we provide superfast and all time result SattaKing

    ReplyDelete
  35. 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
  36. That’s a wonderful piece of writing. Not as good as you, but I’m wearing it like this. 토토사이트

    ReplyDelete
  37. This blog is awesome. Thank you for sharing it. 먹튀검증

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

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

    ReplyDelete
  40. If you are facing any challenges in arranging any place 토토사이트

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

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

    ReplyDelete
  43. That’s a wonderful piece of writing. 토토사이트

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

    ReplyDelete
  45. It's too bad to check your article late. I wonder what it would be if we met a little faster. I want to exchange a little more, but please visit my site 라이브바카라 and leave a message!!

    ReplyDelete
  46. I'm writing on this topic these days, , but I have stopped writing because there is no reference material. Then I accidentally found your article. I can refer to a variety of materials, so I think the work I was preparing will work! Thank you for your efforts. 토토사이트

    ReplyDelete
  47. Hi ! I specialize in writing on these topics. My blog also has these types of articles and forums. Please visit once. 메이저놀이터

    ReplyDelete
  48. Of course, your article is good enough, 먹튀검증 but I thought it would be much better to see professional photos and videos together. There are articles and photos on these topics on my homepage, so please visit and share your opinions.

    ReplyDelete
  49. Write more, thats all I have to say. Literally, it seems as though you relied on the 안전놀이터주소 to make your point.

    ReplyDelete
  50. I've been looking for photos and articles on this topic over the past few days due to a school assignment, 먹튀검증업체 and I'm really happy to find a post with the material I was looking for! I bookmark and will come often! Thanks :D

    ReplyDelete
  51. Admiring the dedication you put into your site and in depth information you offer. It's awesome to come across a blog 먹튀검증사이트 every once in a while that isn't the same unwanted rehashed material. Fantastic read! I've saved your site and I'm including your RSS feeds to my Google account.

    ReplyDelete
  52. It was an awesome post to be sure. I completely delighted in understanding it in my noon. Will without a doubt come and visit this blog all the more frequently. A debt of gratitude is in order for sharing! 메이저놀이터

    ReplyDelete
  53. I just wanted to say that I was new to the blog and really enjoyed this website. More likely to bookmark your blog.사설토토사이트You certainly have a remarkable article. This is a guide for sharing websites.

    ReplyDelete
  54. What a post I've been looking for! I'm very happy to finally read this post. 토토사이트 Thank you very much. Can I refer to your post on my website? Your post touched me a lot and helped me a lot. If you have any questions, please visit my site and read what kind of posts I am posting. I am sure it will be interesting.

    ReplyDelete
  55. Really no matter if someone doesn't be aware of after that its up to other users that they will help, so here it takes place 토토사이트추천.

    ReplyDelete
  56. best site for satta king result, leak number all game record charts. We provide 100% fix number direct from Satta king gali company which includes all famous games like Satta king Desawar, Gali Satta, Ghaziabad, Faridabad, Shri Ganesh Satta, Taj Satta King, charminar and other games of Satta Market Matka is also a simple game and essentially is a form of old lottery games. Ratan Khatri was the founder of this game in the 70 century and was become popular up until the 90 century. The game is not played that much anymore mostly in the regions of North India and Pakistan. Instead, many enjoy the lottery games Satta king result more so these days.

    ReplyDelete
  57. best site for satta king result, leak number all game record charts. We provide 100% fix number.

    ReplyDelete
  58. Best site for Satta king kashipurleak number & all game record charts. We provide 100% fix number direct from Satta king kashipur company which includes all famous games like, Shri Ganesh Satta King Here is an example card. satta-king.online is the no1 satta king site where you can get the fastest Shri ganesh satta king

    ReplyDelete
  59. It was an awesome post to be sure. I completely delighted in understanding it in my noon. Will without a doubt come and visit this blog all the more frequently. A debt of gratitude is in order for sharing. 온라인포커

    ReplyDelete
  60. Really no matter if someone doesn't be aware of after that its up to other users that they will help, so here it takes place 토토사이트추천.

    ReplyDelete
  61. Your writing is perfect and complete. However, I think it will be more wonderful if your post includes additional topics that I am thinking of. I have a lot of posts on my site similar to your topic. Would you like to visit once? 먹튀커뮤니티

    ReplyDelete
  62. It's the same topic, but I was surprised that it was so different from my opinion. I hope you feel the same after seeing the writings I have written. 토토사이트

    ReplyDelete
  63. Exceptional post however , I was wanting to know if you could write a litte more on this topic? I’d be very thankful if you could elaborate a little bit further. Thanks 사설토토사이트

    ReplyDelete
  64. Of course, your article is good enough, 먹튀검증 but I thought it would be much better to see professional photos and videos together. There are articles and photos on these topics on my homepage, so please visit and share your opinions.

    ReplyDelete
  65. I've been searching for hours on this topic and finally found your post. , I have read your post and I am very impressed. We prefer your opinion and will visit this site frequently to refer to your opinion. When would you like to visit my site? 바둑이사이트

    ReplyDelete
  66. I still saw several posts while visiting, but the text was neat and easy to read.
    메이저놀이터

    ReplyDelete
  67. It's really great. Thank you for providing a quality article. There is something you might be interested in. Do you know 메이저토토 ?

    ReplyDelete
  68. Looking at this article, I miss the time when I didn't wear a mask. Kèo nhà cái Hopefully this corona will end soon. My blog is a blog that mainly posts pictures of daily life before Corona and landscapes at that time. If you want to remember that time again, please visit us.

    ReplyDelete
  69. I'm so happy to finally find a post with what I want. 안전놀이터순위 You have inspired me a lot. If you are satisfied, please visit my website and leave your feedback.

    ReplyDelete
  70. I've been looking for photos and articles on this topic over the past few days due to a school assignment, 메이저놀이터순위 and I'm really happy to find a post with the material I was looking for! I bookmark and will come often! Thanks :D

    ReplyDelete
  71. I have recently started a website, the information you provide on this website has helped me greatly. Thank you for all of your time & work. 먹튀신고

    ReplyDelete
  72. I am the one who writes on a topic similar to yours. I hope you come to my blog and take a look at the posts I've been writing. 안전놀이터추천

    ReplyDelete

Real Time Web Analytics