ObjectIdGenerator Performance

benchmark.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Linq;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Runtime.Serialization;

namespace ConsoleApp4
{
    // naive implementation using System.Collections.Dictionary
    public class DictionaryObjectIdGenerator
    {
        private long _count = 0L;
        private Dictionary<object, long> _dict = new Dictionary<object, long>(new ReferenceEqualityComparer());

        public long GetId(object obj, out bool firstTime)
        {
            if (_dict.TryGetValue(obj, out long id))
            {
                firstTime = false;
                return id;
            }

            firstTime = true;
            return _dict[obj] = _count++;
        }

        private class ReferenceEqualityComparer : IEqualityComparer<object>
        {
            public new bool Equals(object x, object y) => object.ReferenceEquals(x, y);

            public int GetHashCode(object obj) => RuntimeHelpers.GetHashCode(obj);
        }
    }

    [MemoryDiagnoser]
    public class Benchmark
    {
        private object[] _objects;

        [Params(10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000)]
        public int N;

        [GlobalSetup]
        public void Setup()
        {
            var random = new Random(Seed: N);
            var pool = Enumerable
                .Range(1, (int)Math.Round(Math.Sqrt(N)))
                .Select(_ => new object())
                .ToArray();

            _objects = Enumerable
                .Range(1, N)
                .Select(i => pool[random.Next(pool.Length)])
                .ToArray();
        }

        [Benchmark]
        public void ObjectIdGenerator()
        {
            var idGen = new ObjectIDGenerator();

            for (int i = 0; i < N; i++)
            {
                idGen.GetId(_objects[i], out bool _);
            }
        }

        [Benchmark]
        public void DictObjectIdGenerator()
        {
            var idGen = new DictionaryObjectIdGenerator();

            for (int i = 0; i < N; i++)
            {
                idGen.GetId(_objects[i], out bool _);
            }
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Benchmark>();
        }
    }
}

Results.md

Method	N	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
ObjectIdGenerator	10	261.0 ns	3.92 ns	3.28 ns	0.0176	-	-	280 B
DictObjectIdGenerator	10	415.4 ns	7.92 ns	8.81 ns	0.0167	-	-	264 B
ObjectIdGenerator	100	2,237.4 ns	38.87 ns	32.45 ns	0.0458	-	-	776 B
DictObjectIdGenerator	100	3,697.2 ns	72.95 ns	71.64 ns	0.0648	-	-	1040 B
ObjectIdGenerator	1000	27,641.9 ns	465.12 ns	412.32 ns	0.0916	-	-	1912 B
DictObjectIdGenerator	1000	35,959.2 ns	580.88 ns	543.35 ns	0.1221	-	-	2128 B
ObjectIdGenerator	10000	280,995.4 ns	3,813.34 ns	3,567.00 ns	0.4883	-	-	10074 B
DictObjectIdGenerator	10000	314,475.7 ns	4,308.54 ns	4,030.21 ns	0.4883	-	-	10240 B
ObjectIdGenerator	100000	3,079,294.0 ns	57,311.47 ns	50,805.13 ns	-	-	-	22731 B
DictObjectIdGenerator	100000	3,283,738.9 ns	63,732.66 ns	70,838.68 ns	-	-	-	22360 B
ObjectIdGenerator	1000000	29,516,906.0 ns	539,270.72 ns	478,049.45 ns	-	-	-	109362 B
DictObjectIdGenerator	1000000	32,816,996.0 ns	691,539.16 ns	646,866.16 ns	-	-	-	102264 B
ObjectIdGenerator	10000000	348,584,250.0 ns	4,216,428.58 ns	3,737,754.11 ns	-	-	-	232856 B
DictObjectIdGenerator	10000000	377,302,846.4 ns	7,480,302.37 ns	10,728,026.14 ns	-	-	-	215688 B
ObjectIdGenerator	100000000	4,004,379,426.7 ns	35,888,393.04 ns	33,570,025.12 ns	-	-	-	1030904 B
DictObjectIdGenerator	100000000	5,520,828,720.0 ns	64,372,279.52 ns	60,213,870.21 ns	-	-	-	942056 B
ObjectIdGenerator	1000000000	50,706,753,792.9 ns	155,480,165.59 ns	137,829,117.01 ns	-	-	-	2152168 B
DictObjectIdGenerator	1000000000	67,422,329,728.6 ns	226,110,855.55 ns	200,441,383.95 ns	-	-	-	1963384 B