simple-or-set-merge-microoptimisation.cs

// BenchmarkDotNet=v0.13.2, OS=macOS Monterey 12.4 (21F79) [Darwin 21.5.0]
// Apple M1, 1 CPU, 8 logical and 8 physical cores
// .NET SDK=6.0.300
//   [Host]     : .NET 6.0.5 (6.0.522.21309), Arm64 RyuJIT AdvSIMD
//   DefaultJob : .NET 6.0.5 (6.0.522.21309), Arm64 RyuJIT AdvSIMD


// |           Method | Actors | ElementSpace |       Mean |     Error |    StdDev |     Gen0 | Allocated |
// |----------------- |------- |------------- |-----------:|----------:|----------:|---------:|----------:|
// |            Merge |      1 |           50 |   6.667 us | 0.0872 us | 0.0773 us |   4.9896 |   10440 B |
// | MergeWithoutLinq |      1 |           50 |   3.606 us | 0.0351 us | 0.0311 us |        - |         - |
// |            Merge |      1 |         1000 | 118.464 us | 1.6132 us | 1.3471 us |  89.8438 |  187912 B |
// | MergeWithoutLinq |      1 |         1000 |  69.986 us | 0.4235 us | 0.3754 us |        - |         - |
// |            Merge |      1 |       100000 | 272.375 us | 3.4582 us | 3.0656 us | 224.1211 |  469840 B |
// | MergeWithoutLinq |      1 |       100000 | 144.412 us | 0.2941 us | 0.2607 us |        - |         - |
// |            Merge |     16 |           50 |  36.401 us | 0.1904 us | 0.1688 us |   9.8267 |   20584 B |
// | MergeWithoutLinq |     16 |           50 |  33.093 us | 0.0676 us | 0.0599 us |        - |         - |
// |            Merge |     16 |         1000 | 201.258 us | 2.4991 us | 2.2154 us |  97.4121 |  203992 B |
// | MergeWithoutLinq |     16 |         1000 | 142.320 us | 0.3552 us | 0.3149 us |        - |         - |
// |            Merge |     16 |       100000 | 301.174 us | 0.2420 us | 0.1889 us | 224.6094 |  470192 B |
// | MergeWithoutLinq |     16 |       100000 | 175.094 us | 0.4416 us | 0.3914 us |        - |         - |
// |            Merge |     64 |           50 |  55.026 us | 0.2476 us | 0.1933 us |  12.5122 |   26216 B |
// | MergeWithoutLinq |     64 |           50 |  51.578 us | 0.0662 us | 0.0620 us |        - |         - |
// |            Merge |     64 |         1000 | 194.061 us | 0.7827 us | 0.6111 us |  97.9004 |  205040 B |
// | MergeWithoutLinq |     64 |         1000 | 135.237 us | 0.2795 us | 0.2477 us |        - |         - |
// |            Merge |     64 |       100000 | 293.958 us | 0.3415 us | 0.2851 us | 224.6094 |  470192 B |
// | MergeWithoutLinq |     64 |       100000 | 177.670 us | 0.4122 us | 0.3442 us |        - |         - |

// #######################################################################################

public sealed class ObservedRemoveSet<TActorId, TItem>
    : IObservedRemoveSet<ObservedRemoveSet<TActorId, TItem>, TActorId, TItem>
    where TItem : notnull
    where TActorId : notnull
{
    private readonly Dictionary<TItem, Dictionary<TActorId, int>> _items = new();
    private readonly Dictionary<TActorId, int> _versionVector = new();
    
    private static readonly ArrayPool<TActorId> ActorsArrayPool = ArrayPool<TActorId>.Create();
    private static readonly ArrayPool<TItem> ItemArrayPool = ArrayPool<TItem>.Create();
    private static readonly ArrayPool<KeyValuePair<TActorId, int>> DotsArrayPool = ArrayPool<KeyValuePair<TActorId, int>>.Create();

    public ICollection<TItem> Items => _items.Keys;
    public int Count => _items.Count;

    public void Add(TItem item, TActorId actorId)
    {
        var counter = _versionVector.GetValueOrDefault(actorId);
        _versionVector[actorId] = counter++;

        if (_items.TryGetValue(item, out var dots))
        {
            dots[actorId] = counter;
            ++_versionVector[actorId];
        }
        else
        {
            _items[item] = new Dictionary<TActorId, int> { [actorId] = counter };
            ++_versionVector[actorId];
        }
    }

    public bool Contains(TItem item) => _items.ContainsKey(item);

    public bool Remove(TItem item) => _items.Remove(item);

    public void Merge(ObservedRemoveSet<TActorId, TItem> other)
    {
        RemoveLocalDotsThatOtherObservedRemovalOf(other);
        AddDotsThatAreNewToMe(other);

        // merge version vectors
        foreach (var (actorId, version) in other._versionVector)
        {
            _versionVector[actorId] = Math.Max(_versionVector.GetValueOrDefault(actorId), version);
        }
    }

    private void RemoveLocalDotsThatOtherObservedRemovalOf(ObservedRemoveSet<TActorId, TItem> other)
    {
        // remove all item and dots that exist locally, but other observed their removal
        var itemsToRemove = ItemArrayPool.Rent(_items.Count);
        
        // number of dots in our item is guaranteed to be not greater then our version vector length 
        var dotsToRemove = ActorsArrayPool.Rent(_versionVector.Count);
        try
        {
            var i = 0;
            foreach (var (ourItem, ourDots) in _items)
            {
                var length = CopyDotsToRemoveToArray(other, ourDots, ourItem, dotsToRemove);

                if (length == ourDots.Count)
                {
                    itemsToRemove[i] = ourItem;
                    ++i;
                    continue;
                }

                for (var k = length - 1; k >= 0; --k)
                {
                    ourDots.Remove(dotsToRemove[k]);
                }
            }

            for (var k = i - 1; k >= 0; --k)
            {
                _items.Remove(itemsToRemove[k]);
            }
        }
        finally
        {
            ActorsArrayPool.Return(dotsToRemove);
            ItemArrayPool.Return(itemsToRemove);
        }
    }

    private static int CopyDotsToRemoveToArray(ObservedRemoveSet<TActorId, TItem> other,
        Dictionary<TActorId, int> ourDots,
        TItem ourItem,
        TActorId[] dotsToRemove)
    {
        var j = 0;
        foreach (var (actorId, ourVersion) in ourDots)
        {
            // we remove dot if it was observed in other (i.e. versionVector is higher)
            // AND if it is also removed from other._version
            if (ourVersion <= other._versionVector.GetValueOrDefault(actorId)
                && (!other._items.TryGetValue(ourItem, out var otherDots)
                    || !otherDots.ContainsKey(actorId)))
            {
                dotsToRemove[j] = actorId;
                ++j;
            }
        }

        return j;
    }

    private void AddDotsThatAreNewToMe(ObservedRemoveSet<TActorId, TItem> other)
    {
        // number of dots within an items of other is guaranteed to not be greater then other version vector length
        var newDotsToUs = DotsArrayPool.Rent(other._versionVector.Count);
        try
        {
            // add all items and dots that exist in other, but new to us (approx. M'' in paper notation)
            foreach (var (otherItem, otherDots) in other._items)
            {
                var length = CopyDotsThatAreNewForUsToArray(otherDots, newDotsToUs);

                if (length == 0) continue;

                if (_items.TryGetValue(otherItem, out var ourDots))
                {
                    AddNewDots(ourDots, newDotsToUs, length);
                }
                else
                {
                    var newValue = new Dictionary<TActorId, int>(length);
                    AddNewDots(newValue, newDotsToUs, length);
                    _items[otherItem] = newValue;
                }
            }
        }
        finally
        {
            DotsArrayPool.Return(newDotsToUs);
        }
    }

    private static void AddNewDots(Dictionary<TActorId, int> ourDots,
        KeyValuePair<TActorId, int>[] newDotsToUs,
        int length)
    {
        for (var k = length - 1; k >= 0; --k)
        {
            var (newActor, newVersion) = newDotsToUs[k];
            // if key (actor) already exists, it must have a lower version, which means we simply overwrite it
            ourDots[newActor] = newVersion;
        }
    }

    private int CopyDotsThatAreNewForUsToArray(Dictionary<TActorId, int> otherDots,
        KeyValuePair<TActorId, int>[] newDotsToUs)
    {
        var i = 0;
        foreach (var otherDot in otherDots)
        {
            if (otherDot.Value > _versionVector.GetValueOrDefault(otherDot.Key))
            {
                newDotsToUs[i] = otherDot;
                ++i;
            }
        }

        return i;
    }
}

// #######################################################################################
// #######################################################################################
// #######################################################################################

[MemoryDiagnoser]
public class ObserveRemoveSetBenchmarks
{
    [Params(1, 16, 64)]
    public int Actors { get; set; }
    
    [Params(50, 1000, 100000)]
    public int ElementSpace { get; set; }

    private readonly CrdtArticle.First.ObservedRemoveSet<Guid, int> _setLeft = new();
    private readonly CrdtArticle.First.ObservedRemoveSet<Guid, int> _setRight = new(); 
    
    private readonly CrdtArticle.Second.ObservedRemoveSet<Guid, int> _setLeftNoLinq = new();
    private readonly CrdtArticle.Second.ObservedRemoveSet<Guid, int> _setRightNoLinq = new();

    private readonly Random _random = new(1);
    
    [GlobalSetup]
    public void Setup()
    {
        var actorsLeft = GetActors(Actors);
        var actorsRight = GetActors(Actors);
        const int operations = 1000; 
        
        for (var j = 0; j < operations; ++j)
        {
            MakeRandomOperation(_setLeft, _setLeftNoLinq, actorsLeft);
            MakeRandomOperation(_setRight, _setRightNoLinq, actorsRight);
        }
        
        _setLeft.Merge(_setRight);
        _setRight.Merge(_setLeft);
        
        _setLeftNoLinq.Merge(_setRightNoLinq);
        _setRightNoLinq.Merge(_setLeftNoLinq);
        
        for (var j = 0; j < operations; ++j)
        {
            MakeRandomOperation(_setLeft, _setLeftNoLinq, actorsLeft);
            MakeRandomOperation(_setRight, _setRightNoLinq, actorsRight);
        }
    }

    [Benchmark]
    public void Merge() => _setLeft.Merge(_setRight);

    [Benchmark]
    public void MergeWithoutLinq() => _setLeftNoLinq.Merge(_setRightNoLinq);


    private void MakeRandomOperation(ObservedRemoveSet<Guid, int> set,
        CrdtArticle.Second.ObservedRemoveSet<Guid, int> setNoLinq,
        Guid[] actors)
    {
        switch (_random.NextDouble(), set.Count)
        {
            case (< 0.25, > 0):
                var valueToRemove = set.Items.First();
                set.Remove(valueToRemove);
                setNoLinq.Remove(valueToRemove);
                break;
            default:
                var valueToAdd = _random.Next(0, ElementSpace);
                var actor = actors[_random.Next(0, actors.Length)];
                set.Add(valueToAdd, actor);
                setNoLinq.Add(valueToAdd, actor);
                break;
        }
    }
    
    private static Guid[] GetActors(int nActors)
    {
        var actors = new Guid[nActors];
        for (var i = 0; i < nActors; ++i)
        {
            actors[i] = Guid.NewGuid();
        }

        return actors;
    }
}