Fastest way of incrementing an element of a List<(Guid, int)>

Question

I have a List<(Guid, int)> (a list of value-tuples), and I want to increment the Item2 field of an element at a specified index. Based on the answers in this question, there are two ways to do it:

1. The first is to get a copy of the existing (Guid, int) at the specified index, increment the Item2 field of the copy, and replace the existing element with the copy.

2. The second is to use the CollectionsMarshal.AsSpan API (.NET 5), get the Span<(Guid, int)> representation of the backing array of the list, and update in-place the Item2 of the desirable element.

static void Increment1(List<(Guid, int)> list, int index)
{
    (Guid, int) copy = list[index];
    copy.Item2++;
    list[index] = copy;
}

static void Increment2(List<(Guid, int)> list, int index)
{
    Span<(Guid, int)> span = CollectionsMarshal.AsSpan(list);
    span[index].Item2++;
}

Which of these two approaches is the most performant? I am interested about a benchmark on the newest .NET platform (.NET 7), in release mode.

Answer 1

I'm going to treat this as a more general question about benchmarking so this answer is more generally useful. I'll use your proposed algorithms as an example though.

---

A naive approach to benchmarking in .NET would be to execute your algorithm wrapped in a StopWatch, however, except for the most crude of estimations, (talk order of magnitude levels of accuracy), this is pretty useless. So please don't do this. Use BenchmarkDotNet instead.

For simple tests such as this, it's very simple.

1. Create a console app.
2. Install the package through NuGet.
3. Create a test class
4. Create a method for each of your tests and annotate with [Benchmark]
5. Create a setup method to get your data ready and annotate it with either [GlobalSetup] or [IterationSetup] depending on whether or not you want it resetting between each test.
6. Add a single-line top-level statement to run your tests.

using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Reports;
using BenchmarkDotNet.Running;

Summary? summary = BenchmarkRunner.Run<IncrementBenchmark>();


public class IncrementBenchmark
{
    private List<(Guid, int)> _testData = new();
    
    [GlobalSetup]
    public void Setup()
    {
        _testData = new();

        for (int i = 0; i < 10000; i++)
        {
            _testData.Add((Guid.NewGuid(), Random.Shared.Next()));
        }
    }

    [Benchmark]
    public void IndexCopyBasedIncrement()
    { 
        for (int i = 0; i < _testData.Count; i++)
        {
            (Guid, int) copy = _testData[i];
            copy.Item2++;
            _testData[i] = copy;
        }
    }

    [Benchmark]
    public void SpanBasedIncrement()
    {
        Span<(Guid, int)> span = CollectionsMarshal.AsSpan(_testData);
        for (int i = 0; i < _testData.Count; i++)
        {
            span[i].Item2++;
        }
    }
}

Then run your console app and wait for the results.

In this case, the span-based implementation is an order of magnitude faster.

Method	Mean	Error	StdDev
IndexCopyBasedIncrement	70.743 us	0.3260 us	0.3049 us
SpanBasedIncrement	4.679 us	0.0419 us	0.0391 us

Given the massive improvements made in .NET 7 to LINQ, you might be able to get further improvements by replacing my loop with something that can make use of those improvements, but that's beyond the scope of this answer.