LinearVsDictionaryTest.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;

public class LinearVsDictionaryTest
{
    public static void Test()
    {
        int[] capacities = {1, 2, 4, 8, 10, 100, 1000, 10000, 100000};
        var cases = new ICase[]
        {
            new LinearCase(),
            new DictionaryCase(),
        };

        var hole = 0;

        var random = new Random(123);

        for (var w = 0; w < 100; w++) // warmup
        {
            Console.WriteLine("");
            Console.WriteLine($"round: {w}");
            
            foreach (var capacity in capacities)
            {
                var opCount = 100000000 / capacity;

                var keys = new int[opCount];
                for (var i = 0; i < keys.Length; i++)
                {
                    keys[i] = random.Next();
                }

                foreach (var aCase in cases)
                {
                    aCase.Reset(capacity);
                    for (var i = 0; i < capacity; i++)
                    {
                        aCase.Add(keys[random.Next(keys.Length)], random.Next());
                    }
                }

                var report = $"capacity: {capacity}, op count: {opCount}";
                foreach (var aCase in cases)
                {
                    var results = new int[keys.Length];
                    var watch = Stopwatch.StartNew();
                    aCase.Run(keys, results, keys.Length);
                    watch.Stop();
                    report += $", {aCase.GetType().Name}: {1000000.0 * watch.Elapsed.TotalMilliseconds / opCount}ns";
                    foreach (var result in results)
                    {
                        hole += result;
                    }
                    GC.Collect();
                }

                Console.WriteLine(report);
            }
        }

        Console.WriteLine($"Garbage: {hole}");
    }

    private interface ICase
    {
        void Reset(int capacity);

        void Add(int key, int value);

        void Run(int[] keys, int[] results, int count);
    }

    private class LinearCase : ICase
    {
        private int[] _keys;
        private int[] _values;
        private int _count;

        public void Reset(int capacity)
        {
            _keys = new int[capacity];
            _values = new int[capacity];
            _count = 0;
        }

        public void Add(int key, int value)
        {
            var i = _count++;
            _keys[i] = key;
            _values[i] = value;
        }

        public void Run(int[] keys, int[] results, int count)
        {
            for (var i = 0; i < count; i++)
            {
                results[i] = Calculate(keys[i]);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int Calculate(int key)
        {
            for (var i = 0; i < _keys.Length; i++)
            {
                if (_keys[i] == key)
                {
                    return _values[i];
                }
            }

            return -1;
        }
    }

    private class DictionaryCase : ICase
    {
        private IDictionary<int, int> _dict;

        public void Reset(int capacity)
        {
            _dict = new Dictionary<int, int>(capacity);
        }

        public void Add(int key, int value)
        {
            _dict[key] = value;
        }

        public void Run(int[] keys, int[] results, int count)
        {
            for (var i = 0; i < count; i++)
            {
                results[i] = Calculate(keys[i]);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int Calculate(int key)
        {
            if (_dict.TryGetValue(key, out var result))
            {
                return result;
            }

            return -1;
        }
    }
}