[API Proposal]: M.E.C.M. MemoryCache - add ReadOnlySpan<char> get API

[mgravell]

Open questions (will make more sense after reading):

• key: span or interpolated string handler?
  • if interpolated string handler: DefaultInterpolatedStringHandler or something bespoke (for example a new [InterpolatedStringHandler] public ref struct KeyBuilder { ... })?
• does this single API review also encompass the proposed additions to DefaultInterpolatedStringHandler?
  • UPDATE: probably not; that ^^^ is now api-approved
• does this single API review also encompass the proposed additions to HybridCache?

(note: a lot of the discussion in comments below has already been incorporated into this top post down to end-of 2024)

Relevant runtimes / targets

Short version: .NET 10+ (omit new APIs in down-level multi-target builds)

Longer version: M.E.C.M. is an OOB NuGet multi-targeting package; the proposed API additions would by default be limited to .NET 10+; it may be technically possible to backport for .NET 9, but since .NET 9 is not LTS I'm not sure this is hugely advantageous, and would presumably require a few hacks such as [InternalsVisibleTo] or [UnsafeAccessor], which probably isn't ideal. It is not useful to consider backport lower than .NET 9, due to requiring TryGetAlternateLookup (a .NET 9 feature) to be useful.

Background and motivation

The existing MemoryCache API takes object keys, however: in many cases, the key is actually a string.

There is a set of existing APIs of the form:

namespace Microsoft.Extensions.Caching.Memory;

public interface IMemoryCache
{
    bool TryGetValue(object key, out object? value);
    // ...
}
public class MemoryCache
{
    public bool TryGetValue(object key, out object? result);
    // ...
}
public static class CacheExtensions
{
    public static bool TryGetValue<TItem>(this IMemoryCache cache, object key, out TItem? value);
    // ...
}

The impact of this is that when using string keys (the most common use-case), it is required to pay the cost of allocating the string key, which is usually string concatenation of some constants with contextual tokens, for example $"/foos/{region}/{id}".

Proposal: add a new API to facility allocation-free fetch:

  public class MemoryCache : IMemoryCache
  {
      // DECISION NEEDED HERE re span vs interpolated string handler
      // (this version may not be optimal)
+     [OverloadResolutionPriority(1)]
+     public bool TryGetValue(ReadOnlySpan<char> key, out object? value);
+     [OverloadResolutionPriority(1)]
+     public bool TryGetValue<TItem>(ReadOnlySpan<char> key, out TItem? value);
      // ...
  }

Observations:

• this API is specific to string-like keys; however, this is a huge majority of keys used in caching
• this API is specific to the concrete MemoryCache; no change to IMemoryCache is proposed; this is not an issue, and has been the approach used for .Count, .Keys, etc; consumers can type-test as if necessary; since it is specific to MemoryCache, no change to CacheExtensions is proposed
• implementing this API requires the .NET 9 TryGetAlternateLookup feature, that allows dictionaries to be accessed in such ways
• implementing this API requires MemoryCache to use a separate dictionary for string-based objects; this already exists (it was merged via "internal" for .NET 6, .NET 8 and .NET 9, and explicitly for .NET 10)
• corollary of the above two: we can just grab the alt lookup in the init, and use that to provide this API. If it turns out that we do not have the alt lookup available: just new a string and use that instead.
• the usage of [OverloadResolutionPriority(1)] here is to avoid ambiguity with cache.TryGetValue($"/foos/{region}/{id}", out var value) (CS0121), however; note that this still uses a string; you can see this here - in particular note the value passed is (ReadOnlySpan<char>)defaultInterpolatedStringHandler.ToStringAndClear() - i.e. "create a string, and shim it to the span"; if we want to avoid that issue so that $"/foos/{region}/{id}" uses the allocation-free approach (without Roslyn changes), we would need to use an interpolated string handler parameter; for example

  public class MemoryCache : IMemoryCache
  {
      // DECISION ALTERNATE
      // (this version may be preferable)
+     public bool TryGetValue(ref DefaultInterpolatedStringHandler key, out object? value);
+     public bool TryGetValue<TItem>(ref DefaultInterpolatedStringHandler key, out TItem? value);
      // ...
  }

Note that the compiler automatically prefers interpolated string handlers over string in relevant scenarios (except for pure constant values, although the problematic scenarios from this link do not apply in this scenario); for a fully worked version see here. A further complication is that we would want the interpolated string handler to expose some additional methods, to allow efficient access to the span contents - although since this is "runtime", IVTA may be sufficient here (untested). It may be simpler, however, to consider these two proposals inherently linked.

A secondary win here is that pre-existing inline usage of interpolated strings, i.e. cache.TryGetValue($"/foos/{region}/{id}", ...) will, when recompiled, pick up the lower-allocation API without any code changes. However, the real intended "win" here is via secondary APIs such as HybridCache (below).

Question: if using interpolated string handlers should we use DefaultInterpolatedStringHandler? or a bespoke KeyBuilder that encapsulates a DefaultInterpolatedStringHandler ? (there are some complications in the latter due to the compiler considering exposing the span that far as unsafe).

---

Use-cases:

We want allocation-free fetch from complex APIs like HybridCache, which use IMemoryCache (and usually, although we'd need to type-test) therefore: MemoryCache. By adding this API, along with some "format" APIs in new HybridCache APIs, we allow the scenario where composite keys can be passed as (for example) value-tuples, with a formatter that writes not a string but a Span<char>, used for reads. The impact here is reduced allocations for the key in the hot "cache hit" path. Obviously cache misses still need to pay the cost, but we can't have everything.

Usage example:

HybridCache currently has a GetOrCreateAsync<T> API that takes a string key parameter.

We would add a GetOrCreateAsync<T> overload that takes an alloc-based char-based key (with the same considerations as above), passing the key along, allowing local-cache "hit" scenarios (which should be a common event) to be allocation free end-to-end. I presume this would be a separate API proposal, but will have very similar considerations to the above. Likely conclusion:

namespace Microsoft.Extensions.Caching.Hybrid;

public abstract class HybridCache
{
    public abstract ValueTask<T> GetOrCreateAsync<TState, T>(string key, TState state, Func<TState, CancellationToken, ValueTask<T>> factory,
        HybridCacheEntryOptions? options = null, IEnumerable<string>? tags = null, CancellationToken cancellationToken = default);
    public ValueTask<T> GetOrCreateAsync<T>(string key, Func<CancellationToken, ValueTask<T>> factory,
        HybridCacheEntryOptions? options = null, IEnumerable<string>? tags = null, CancellationToken cancellationToken = default)
        => GetOrCreateAsync(key, factory, WrappedCallbackCache<T>.Instance, options, tags, cancellationToken);

+    public virtual ValueTask<T> GetOrCreateAsync<TState, T>(ref DefaultInterpolatedStringHandler key, TState state, Func<TState, CancellationToken, ValueTask<T>> factory,
+        HybridCacheEntryOptions? options = null, IEnumerable<string>? tags = null, CancellationToken cancellationToken = default)
+      => GetOrCreateAsync(key.ToStringAndClear(), factory, WrappedCallbackCache<T>.Instance, options, tags, cancellationToken);
+    public ValueTask<T> GetOrCreateAsync<T>(ref DefaultInterpolatedStringHandler key, Func<CancellationToken, ValueTask<T>> factory,
+        HybridCacheEntryOptions? options = null, IEnumerable<string>? tags = null, CancellationToken cancellationToken = default)
+        => GetOrCreateAsync(ref key, factory, WrappedCallbackCache<T>.Instance, options, tags, cancellationToken);
    // ...
}

i.e. a new virtual method that takes ref DefaultInterpolatedStringHandler key, that concrete implementations should override to perform allocation-free local-cache lookups, otherwise defaulting to existing string usage (if they do not override).

Question: is the above sufficient to consider part of this API proposal, or should a separate API process be followed for the HybridCache addition?

API Proposal

covered above

API Usage

covered above

Alternative Designs

span vs interpolated string handler covered above

Risks

No response

[mgravell]

Random scratch ideas for how HybridCache could implement the someFormatterThing efficiently, using interceptors to replace a formattable string with a custom formatter: https://gist.github.com/mgravell/69ec4c1a23fbaf7bce0277f86d8ad1d4 by turning $"this {key.id:000} is {key.region} magic" into something that emits:

var scratch = new Writer<TWriter>(ref writer);
scratch.WriteString("this ");
scratch.WriteSpanFormattable(key.id, "000", provider);
scratch.WriteString(" is ");
scratch.WriteString(key.region);
scratch.WriteString(" magic");
scratch.Flush();

(but everything still works if that magic isn't available)

[stephentoub]

Random scratch ideas for how HybridCache could implement the someFormatterThing efficiently

Why not use an interpolated string handler?

[mgravell]

@stephentoub because I didn't know that was a thing; if that is a good fit here, great! Huge thanks! Linking for the long tail (and to check we're on the same page): https://learn.microsoft.com/dotnet/csharp/advanced-topics/performance/interpolated-string-handler

[stephentoub]

Yup. I only briefly skimmed what you wrote, but on quick perusal it looks like a good fit.
https://devblogs.microsoft.com/dotnet/string-interpolation-in-c-10-and-net-6/

[mgravell]

@stephentoub yes, looks like an ideal fit; in fact, wait one moment for a follow-up API suggestion... because right now I can get everything I want via:

var key = (id: 42, region: "abc");
var cache = new Cache();
cache.Get<int>($"abc {key.id:000} in {key.region}");

...

class Cache
{
    public T Get<T>(ref DefaultInterpolatedStringHandler key) // real code has "miss" callback etc
    {
        // this is just to show it is working; obvs we don't actually ToString usually
        Console.WriteLine($"Fetching: {GetText(ref handler).ToString()}");
        Clear(ref handler);

        return default!; // result doesn't matter here
    }

    [UnsafeAccessor(UnsafeAccessorKind.Method, Name = "Clear")]
    private static extern void Clear(ref DefaultInterpolatedStringHandler value);

    [UnsafeAccessor(UnsafeAccessorKind.Method, Name = "get_Text")]
    private static extern ReadOnlySpan<char> GetText(ref DefaultInterpolatedStringHandler value);
}

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-extensions-caching
See info in area-owners.md if you want to be subscribed.

[stephentoub]

// this is just to show it is working; obvs we don't actually ToString usually

ReadOnlySpan<char> should work fine as an interpolated string argument on core... did it not?

in fact, wait one moment for a follow-up API suggestion... because right now I can get everything I want via:

MemoryCache builds for netstandard and netfx as well, and DefaultInterpolatedStringHandler isn't available there. Are you proposing these new APIs only for .NET Core builds?

[NickCraver]

I am trying to envision what the tuple/record/etc. case look like to avoid the case of the handler as well we initially were thinking here - does this approach mean we would need to figure this our per cache type, or do we want to think through this in a more holistic way given the underlying split of string/everything-else split that's happened beneath in several places now?

I guess the other argument to be made for usability is records being a good fit - perhaps it's worth seeing what is the ideal key scenario across all these cache types with usability vs. hashing and imagine what that might look like equally on say MemoryCache and HybridCache as well?

I have been thinking of this in terms of how we can access caches directly today with more efficient lookups, but not most of the caching APIs, for example:

void Main()
{
    Util.AutoScrollResults = true;
    BenchmarkRunner.Run<LookupBenchmarks>();
}

[MemoryDiagnoser]
public class LookupBenchmarks
{
    private ConcurrentDictionary<(UserType UT, RequestType RT, string RequestID), object> _tupleCache = new();
    private ConcurrentDictionary<RequestKey, object> _recordCache = new();

    [Benchmark]
    public object TupleLookup() => _tupleCache.TryGetValue((UserType.A, RequestType.B, "myKey"), out var val) ? val : default;
    [Benchmark]
    public object RecordLookup() => _recordCache.TryGetValue(new(UserType.A, RequestType.B, "myKey"), out var val) ? val : default;
}

public enum UserType { A, B }
public enum RequestType { A, B, C }
public readonly record struct RequestKey(UserType UT, RequestType RT, string RequestID);

Method	Mean	Error	StdDev	Allocated
TupleLookup	7.600 ns	0.1020 ns	0.0954 ns	-
RecordLookup	3.681 ns	0.0600 ns	0.0561 ns	-

...but I realize everything today is a string on the common caching APIs, so maybe that's the only viable path without API explosion. If they all could take things like a readonly record struct though...possibilities.

[mgravell]

@NickCraver The interpolated string handler suggested replaces the need to even worry about that - and has the advantage of working with the L1 we have today (if we make the change proposed here) rather than some speculative L1 we might wish to have in the future (RCache etc with TKey generic key usage). So your usage just becomes regular HybridCache:

HybridCache cache = ... // Probably injected

var data = cache.GetOrCreateAsync($"/foos/{region}/{id}/bars", ...callback...);

That work? Note this would be based on the alt-lookup if CD<string,object> which means: .NET 9+ if I hack in unsafe-accessor, and .NET 10+ to use the new API if we get it.