# Deep dive into .NET 11 Performance Improvements #7

In this series, I explore some of the most interesting .NET 11 performance improvements described in Stephen Toub's blog post, [Performance Improvements in .NET 11](https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-11).

Each post focuses on one example from the original article while digging a little deeper into an additional aspect that was not covered there. The series covers the following topics:

1. [Allocation free numbers](https://blog.ladeak.net/posts/net11-perf-imp-01)
1. [Virtual generic method calls](https://blog.ladeak.net/posts/net11-perf-imp-02)
1. [Vector zero equality](https://blog.ladeak.net/posts/net11-perf-imp-03)
1. [Guid creation on Linux](https://blog.ladeak.net/posts/net11-perf-imp-04)
1. [JIT generating implicit-else assembly instructions](https://blog.ladeak.net/posts/net11-perf-imp-05)
1. [Guid equality](https://blog.ladeak.net/posts/net11-perf-imp-06)
1. *Current post: [Copy-on-write locking strategy](https://blog.ladeak.net/posts/net11-perf-imp-07)*

## Copy-on-write locking strategy

One pull request pointed out a cache optimization based on the [copy-on-write strategy](https://github.com/dotnet/runtime/pull/124997/changes). In this pattern, the backing array contains items that are rarely extended. Reads can proceed without synchronization because the array is not mutated in place; instead, a new array is created when an item is added. After the new array has been copied and extended, the reference is swapped atomically. Copying the array and swapping the reference still need to be protected by a lock; otherwise, concurrent writers can overwrite one another's changes.

In a rather artificial example, `TimeParserLock` maintains a cache of integers to `DateTime`. Every time it encounters an unseen year, it creates the corresponding `DateTime` and adds it to its local cache.

> `CachedTime` is a reference type here intentionally to mimic the behavior in the PR mentioned above more closely.

```csharp
public class TimeParserLock
{
    private record class CachedTime(int Year, DateTime DateTime);

    private CachedTime[] _cache = [];
    private readonly Lock _lock = new();

    public DateTime GetDateTime(int year)
    {
        var items = _cache;
        foreach (var item in items)
        {
            if (item.Year == year)
                return item.DateTime;
        }
        return SlowPath(year);
    }

    private DateTime SlowPath(int year)
    {
        lock (_lock)
        {
            foreach (var item in _cache)
            {
                if (item.Year == year)
                    return item.DateTime;
            }
            var dateTime = new DateTime(year, 1, 1);
            _cache = [.. _cache, new(year, dateTime)];
            return dateTime;
        }
    }
}
```

Could a different strategy work when the cache size is known up front? Let's assume that all `year` values in the above example are known to have at most 30 distinct values. That constrains the backing array to 30 references. An alternative implementation can preallocate the array and update a single element atomically using `Interlocked`.

```csharp
public class TimeParserInterlocked
{
    private class CachedTime() { public int Year { get; set; } public DateTime DateTime { get; set; } }

    private readonly CachedTime?[] _cache = new CachedTime?[30]; // Items are always constrained to 30.

    public DateTime GetDateTime(int year)
    {
        Span<CachedTime?> span = _cache;
        for (int i = 0; i < span.Length; i++)
        {
            var item = span[i];
            if (item is null)
                return SlowPath(year, i);
            else if (item.Year == year)
                return item.DateTime;
        }

        return default;
    }

    private DateTime SlowPath(int year, int i)
    {
        var entry = new CachedTime() { Year = year, DateTime = new DateTime(year, 1, 1) };
        for (; i < _cache.Length; i++)
        {
            var oldValue = Interlocked.CompareExchange(ref _cache[i], entry, null);
            if (oldValue is null) // Success, new item added to the cache
                return entry.DateTime;
            else if (oldValue.Year == year)
                return oldValue.DateTime;
        }
        throw new InvalidOperationException();
    }
}
```

Notice that this implementation:

1. requires a precondition on the input
2. the copy-on-write strategy uses a double-checked locking pattern that prevents duplicate `CachedTime` objects from being created in parallel requests with the same year; however, the interlocked approach creates a new `CachedTime` in each parallel request with the same year, even though only one object is eventually added to the array
3. in the interlocked approach, reading the array requires an additional `null` check

The exact performance characteristics depend on the cost of creating the cached item, in this case `CachedTime`. Overall performance also depends on how the types are used and the bounds of the inputs:

- insertion alone is 2.5x faster (`1,114.8 ns` vs. `439.7 ns`)
- read operations become slower: on the test machine, 50 rounds of read operations offset the gains from write operations (`7.805 us` vs. `7.527 us`), and beyond that point the copy-on-write approach wins
- when concurrent threads compete, the outcome is strongly influenced by the cost of creating the underlying item

It is interesting to understand why the read operation is slower: although the C# code is very similar, the JIT compiled assembly is significantly different. For the copy-on-write case, the entire `GetDateTime` method fits in a single snippet:

```assembly
; TimeParserLock.GetDateTime(Int32)
       sub       rsp,28
       mov       rax,[rcx+8]
       mov       r8d,[rax+8]
       test      r8d,r8d
       jle       short 0000000000001B32
       add       rax,10
       nop       word ptr [rax+rax]
M01_L00:
       mov       r10,[rax]
       cmp       [r10+8],edx
       je        short 0000000000001B3E
       add       rax,8
       dec       r8d
       jne       short 0000000000001B20
M01_L01:
       call      qword ptr [4780]; TimeParserLock.SlowPath(Int32)
       nop
       add       rsp,28
       ret
M01_L02:
       mov       rax,[r10+10]
       add       rsp,28
       ret
; Total bytes of code 71
```

The inner loop is at the `M01_L00` label. `edx` contains the input year, `rax` points to the current array slot, and `r8d` is the loop counter. The code is optimized to 6 CPU instructions.

The interlocked approach compiles to a larger code size, but its inner loop looks like this:

```assembly
G_M000_IG04:                ;; offset=0x0030
       mov      rax, gword ptr [rbx+8*r8]
       test     rax, rax
       je       SHORT G_M000_IG11

G_M000_IG05:                ;; offset=0x0039
       cmp      dword ptr [rax+0x08], edx
       je       SHORT G_M000_IG09

G_M000_IG06:                ;; offset=0x003E
       inc      r8d
       cmp      r8d, esi
       jl       SHORT G_M000_IG04
```

While the instructions look similar, they cost more:

- they include an additional null check (`test` and `je`)
- the loop index increments upward, so there is a second `cmp` instruction to compare against the length of the array (value stored in `esi` register)
- and there is no strength reduction: the multiplication `rbx+8*r8` happens on each iteration, compared to a single addition (`rax,8`) in the copy-on-write approach

Some of these points may improve in future .NET releases, but removing the additional `null` check would not be possible without changing the data structure or the access pattern.

## Conclusion

This post focused on an interesting optimization technique from the [Performance Improvements in .NET 11](https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-11) article. While `Interlocked.CompareExchange` is known to be more efficient than `Lock`, the gains can be quickly offset by external factors. This post demonstrates that even with constrained inputs, performance gains are easily eroded by multiple environmental factors. The copy-on-write strategy remains a flexible and performant choice for similar problems.