{"id":5514,"date":"2018-08-26T13:00:37","date_gmt":"2018-08-26T13:00:37","guid":{"rendered":"http:\/\/writeasync.net\/?p=5514"},"modified":"2018-08-25T15:33:19","modified_gmt":"2018-08-25T15:33:19","slug":"microbenchmarks-with-benchmarkdotnet","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5514","title":{"rendered":"Microbenchmarks with BenchmarkDotNet"},"content":{"rendered":"

They say<\/a> that the fastest prime number algorithm for small inputs (up to 216<\/sup>) is a lookup table<\/a>. But this got me thinking — would it be faster to use HashSet.Contains<\/a> or a List.BinarySearch<\/a>? The answer to this type of performance<\/a> comparison<\/a> question<\/a> has been debated often, usually with no clear conclusion. What is a programmer to do?<\/p>\n

This calls for a microbenchmark<\/a>! Designing and collecting a proper benchmark is difficult to do properly and accurately, but we are in luck — BenchmarkDotNet<\/a> has done all the hard work for us. BenchmarkDotNet is a simple benchmark library which happens to be a favorite of the CoreFX team, being used to justify major performance improvements to the framework itself<\/a>.<\/p>\n

Let’s use BenchmarkDotNet to answer the specific question above. First, we need a list of primes up to 65535. WolframAlpha has us covered here<\/a>; using the “Plaintext” link, we can even get the list in a convenient-for-code-copy-paste form with braces and commas!<\/p>\n

Now we need to create a class with the code we want to benchmark, using a few attributes:<\/p>\n

\r\nnamespace BenchmarkSample\r\n{\r\n    using System.Collections.Generic;\r\n    using BenchmarkDotNet.Attributes;\r\n\r\n    [CoreJob]\r\n    public class PrimeLookup\r\n    {\r\n        private static readonly List<ushort> PrimeList = new List<ushort> { 2, 3, 5, \/* ... *\/, 65519, 65521 };\r\n\r\n        private static HashSet<ushort> PrimeSet = new HashSet<ushort>(PrimeList);\r\n\r\n        [Benchmark]\r\n        public ushort GetCountBinarySearch()\r\n        {\r\n            ushort count = 0;\r\n            for (int i = 0; i < ushort.MaxValue; ++i)\r\n            {\r\n                if (GetOneBinarySearch((ushort)i))\r\n                {\r\n                    ++count;\r\n                }\r\n            }\r\n\r\n            return count;\r\n        }\r\n\r\n        [Benchmark]\r\n        public ushort GetCountHashSet()\r\n        {\r\n            ushort count = 0;\r\n            for (int i = 0; i < ushort.MaxValue; ++i)\r\n            {\r\n                if (GetOneHashSet((ushort)i))\r\n                {\r\n                    ++count;\r\n                }\r\n            }\r\n\r\n            return count;\r\n        }\r\n\r\n        private static bool GetOneBinarySearch(ushort n) => PrimeList.BinarySearch(n) >= 0;\r\n\r\n        private static bool GetOneHashSet(ushort n) => PrimeSet.Contains(n);\r\n    }\r\n}\r\n<\/pre>\n
You can see that we have two basic algorithms being measured here. The first GetCountBinarySearch<\/code> counts the number of primes from 0 to 65535 using a lookup table via List.BinarySearch<\/code>. The second does the same but with a HashSet.Contains<\/code> lookup instead. The [CoreJob] attribute indicates that we are only interested in measuring performance with .NET Core (rather than the full .NET Framework, which one can specify with [ClrJob]). You might wonder why the code doesn’t use more static members; this is because the benchmark class cannot be sealed or static and must be default-constructible with benchmark methods as instance methods. (BenchmarkDotNet internally generates code for the benchmark which uses inheritance and instances of your class.)<\/p>\n
Before we actually measure, we need to write some tests. It doesn’t make much sense to benchmark an incorrect algorithm. This should do it:<\/p>\n
\r\nnamespace BenchmarkSample.Test\r\n{\r\n    using Microsoft.VisualStudio.TestTools.UnitTesting;\r\n\r\n    [TestClass]\r\n    public sealed class PrimeLookupTest\r\n    {\r\n        [TestMethod]\r\n        public void CountHashSet()\r\n        {\r\n            Assert.AreEqual(6542, new PrimeLookup().GetCountHashSet());\r\n        }\r\n\r\n        [TestMethod]\r\n        public void CountBinarySearch()\r\n        {\r\n            Assert.AreEqual(6542, new PrimeLookup().GetCountBinarySearch());\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
The tests pass, so let’s write the entry point to launch the benchmark:<\/p>\n
\r\nnamespace BenchmarkSample\r\n{\r\n    using BenchmarkDotNet.Running;\r\n\r\n    internal static class Program\r\n    {\r\n        private static void Main()\r\n        {\r\n            BenchmarkRunner.Run<PrimeLookup>();\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
That’s it! The attributes have already specified what we want to do and there are smart defaults for the common case.<\/p>\n
Now we just need to set the build to Release mode (very important!<\/a>) and run this experiment. You’ll see it generate a project, compile it, and then launch a benchmark session to gather statistics (automatically doing warmup iterations, etc.). The last chunk of output gives us the summary:<\/p>\n
\r\n\/\/ * Summary *\r\n\r\nBenchmarkDotNet=v0.11.0, OS=Windows 10.0.17134.228 (1803\/April2018Update\/Redstone4)\r\nIntel Core i7-3960X CPU 3.30GHz (Ivy Bridge), 1 CPU, 12 logical and 6 physical cores\r\nFrequency=3224539 Hz, Resolution=310.1218 ns, Timer=TSC\r\n.NET Core SDK=2.1.201\r\n  [Host] : .NET Core 2.0.7 (CoreCLR 4.6.26328.01, CoreFX 4.6.26403.03), 64bit RyuJIT\r\n  Core   : .NET Core 2.0.7 (CoreCLR 4.6.26328.01, CoreFX 4.6.26403.03), 64bit RyuJIT\r\n\r\nJob=Core  Runtime=Core\r\n\r\n               Method |     Mean |     Error |    StdDev |\r\n--------------------- |---------:|----------:|----------:|\r\n GetCountBinarySearch | 3.405 ms | 0.0528 ms | 0.0494 ms |\r\n      GetCountHashSet | 1.394 ms | 0.0146 ms | 0.0137 ms |\r\n<\/pre>\n
HashSet has emerged as the clear winner, at least in this experiment with ~6000 numeric items. Remember that this is a micro<\/em>benchmark and we cannot extrapolate the results too far.<\/p>\n
Why not give BenchmarkDotNet a try? It could definitely help make your .NET performance discussions less about gut feeling<\/a> and more data-driven.<\/p>\n","protected":false},"excerpt":{"rendered":"
They say that the fastest prime number algorithm for small inputs (up to 216) is a lookup table. But this got me thinking — would it be faster to use HashSet.Contains or a List.BinarySearch? The answer to this type of… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[104],"tags":[],"class_list":["post-5514","post","type-post","status-publish","format-standard","hentry","category-performance"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5514","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5514"}],"version-history":[{"count":1,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5514\/revisions"}],"predecessor-version":[{"id":5515,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5514\/revisions\/5515"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5514"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}