Support non-string keys (eg. tuples)

[Turnerj]

What problem does the feature solve?

Currently all keys must be of type string. This works fine but can cause unnecessary allocations, especially on data retrieval, when one would combine values together to form a string - eg. $"namespace:{someInteger}:{someOtherValue}".

They could instead use a Tuple like ("namespace", someInteger, someOtherValue) which would avoid allocations and overall increase performance.

Here is a basic benchmark of two dictionaries - one with a tuple and one without:

[SimpleJob(RuntimeMoniker.NetCoreApp50), MemoryDiagnoser]
public class TestBenchmark
{
	private Dictionary<string, int> DataA {get;set;} = new();
	private Dictionary<(string, int), int> DataB {get;set;} = new();
	
	[Benchmark]
	public void String()
	{
		DataA.Clear();
		for (var i = 0; i < 10000; i++)
		{
			DataA.Add($"hello:{i}", i);
		}
	}

	[Benchmark]
	public void Tuple()
	{
		DataB.Clear();
		for (var i = 0; i < 10000; i++)
		{
			DataB.Add(("hello", i), i);
		}
	}
}

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
String	1,169.8 μs	13.60 μs	12.06 μs	152.3438	58.5938	-	695.31 KB
Tuple	525.4 μs	10.25 μs	11.40 μs	79.1016	22.4609	-	312.5 KB

The thing is, we can't easily use a tuple internally. If we said "all keys are tuples", we could use the ITuple interface however that creates issues with boxing. It would still save on allocations but not as many.

The thing is we would ideally need a generic argument for keys but defined for a CacheStack. This starts working against us again because while you might have a key like (string, int, int) in one place, you might have another being (string, int), Guid or anything else. We would hit boxing issues again if we wanted to support all variations at all times.

Many things would need to be worked out but in the mean time, this would be a good placeholder issue.

How would you use/interact with the feature? (if applicable)

Something like:

cacheStack.GetOrSetAsync(("namespace", 14), (old, ctx) => /* do whatever */, new CacheSettings(TimeSpan.FromMinutes(30)))`

A CacheStack might need to be defined as CacheStack<TKey> and CacheStack<TKey, TContext>.

Additional constraints include:

• How do external cache calls handle the different keys?
• How do the layers handle it?

[prat0088]

That's an interesting benchmark and

I know these are more C# than CacheTower, but I'm curious:

• What would a third benchmark show that adds the strings from a pre-constructed that was built in the Benchmark setup section? The string in loop two is a static const, possibly leading to further optimization.
• How do Tuples compare for lookup speed? Since it's a value type, presumably it is on par with other value types.

[Turnerj]

I actually have a mistake in that benchmark. I was trying a few different things out and wrote the optimized benchmark with the non-optimized results. It actually allocates far less if I have the dictionary use the key (string, int) rather than ITuple. The results were for ITuple.

I'll put together a few more benchmarks in more comments below.

[Turnerj]

Strings vs Tuple Benchmark: Writing

[SimpleJob(RuntimeMoniker.NetCoreApp50), MemoryDiagnoser]
public class TestBenchmark
{
	private Dictionary<string, int> DataA {get;set;} = new();
	private Dictionary<(string, int), int> DataB {get;set;} = new();
	
	private string BaseString;
	
	[GlobalSetup]
	public void Setup()
	{
		BaseString = "hello";
	}
	
	[Benchmark]
	public void NoTuple()
	{
		DataA.Clear();
		for (var i = 0; i < 10000; i++)
		{
			DataA.Add($"hello:{i}", i);
		}
	}

	[Benchmark]
	public void Tuple()
	{
		DataB.Clear();
		for (var i = 0; i < 10000; i++)
		{
			DataB.Add((BaseString, i), i);
		}
	}
}

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.1052 (2004/?/20H1)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.301
  [Host] : .NET Core 5.0.7 (CoreCLR 5.0.721.25508, CoreFX 5.0.721.25508), X64 RyuJIT
Job=.NET Core 5.0  Runtime=.NET Core 5.0  

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
NoTuple	1,167.1 μs	9.17 μs	8.13 μs	150.3906	56.6406	-	712002 B
Tuple	347.9 μs	5.17 μs	4.84 μs	-	-	-	1 B

[Turnerj]

Strings vs Tuple Benchmark: Reading

[SimpleJob(RuntimeMoniker.NetCoreApp50), MemoryDiagnoser]
public class TestBenchmark
{
	private Dictionary<string, int> DataA {get;set;} = new();
	private Dictionary<(string, int), int> DataB {get;set;} = new();
	
	private string BaseString;
	private int BaseInt;
	
	[GlobalSetup]
	public void Setup()
	{
		BaseString = "hello";
		BaseInt = 6485;

		for (var i = 0; i < 10000; i++)
		{
			DataA.Add($"hello:{i}", i);
		}
		for (var i = 0; i < 10000; i++)
		{
			DataB.Add((BaseString, i), i);
		}
	}

	[Benchmark]
	public int NoTuple()
	{
		return DataA[$"hello:{BaseInt}"];
	}

	[Benchmark]
	public int Tuple()
	{
		return DataB[(BaseString, BaseInt)];
	}
}

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.1052 (2004/?/20H1)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.301
  [Host] : .NET Core 5.0.7 (CoreCLR 5.0.721.25508, CoreFX 5.0.721.25508), X64 RyuJIT
Job=.NET Core 5.0  Runtime=.NET Core 5.0 

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
NoTuple	108.76 ns	1.260 ns	1.052 ns	0.0229	-	-	72 B
Tuple	54.11 ns	0.353 ns	0.330 ns	-	-	-	-

[Turnerj]

String vs Tuple Benchmark: Lookup Only

[SimpleJob(RuntimeMoniker.NetCoreApp50), MemoryDiagnoser]
public class TestBenchmark
{
	private Dictionary<string, int> DataA {get;set;} = new();
	private Dictionary<(string, int), int> DataB {get;set;} = new();
	
	private string BaseString;
	private int BaseInt;
	
	private string NoTupleKey;
	private (string, int) TupleKey; 
	
	[GlobalSetup]
	public void Setup()
	{
		BaseString = "hello";
		BaseInt = 6485;
		
		NoTupleKey = $"hello:{BaseInt}";
		TupleKey = (BaseString, BaseInt);

		for (var i = 0; i < 10000; i++)
		{
			DataA.Add($"hello:{i}", i);
		}
		for (var i = 0; i < 10000; i++)
		{
			DataB.Add((BaseString, i), i);
		}
	}

	[Benchmark]
	public int NoTuple()
	{
		return DataA[NoTupleKey];
	}

	[Benchmark]
	public int Tuple()
	{
		return DataB[TupleKey];
	}
}

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.1052 (2004/?/20H1)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.301
  [Host] : .NET Core 5.0.7 (CoreCLR 5.0.721.25508, CoreFX 5.0.721.25508), X64 RyuJIT
Job=.NET Core 5.0  Runtime=.NET Core 5.0  

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
NoTuple	19.71 ns	0.141 ns	0.125 ns	-	-	-	-
Tuple	48.32 ns	0.397 ns	0.372 ns	-	-	-	-

[Turnerj]

So the lookup itself is quite a bit slower in the test vs strings however that time is counteracted by the saving of creating the string vs creating the tuple.

[Turnerj]

I did discover one interesting thing - if I make the second dictionary use key of object, it performs the same as ITuple. This means I'm right in that the issue is boxing. That itself isn't the interesting part but actually using type object as the key allows both strings and tuples without much complicated logic.

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
String	1.239 ms	0.0080 ms	0.0074 ms	148.4375	64.4531	-	695.31 KB
Object	1.365 ms	0.0197 ms	0.0184 ms	152.3438	58.5938	-	695.31 KB

It performs slightly worse when it is a object-type vs string when the key is actually a string but the allocations are the same. But still with the same object-type as the key but using a tuple instead, we get the results I have in the issue description:

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
String	1,260.5 μs	10.06 μs	8.40 μs	148.4375	58.5938	-	695.31 KB
Tuple	534.0 μs	3.16 μs	2.80 μs	79.1016	21.4844	-	312.5 KB

So if a Dictionary<object, int> gets a tuple, we still are ahead due to the overhead of creating that example string hello:{i}.