Repository navigation
Support non-string keys (eg. tuples) #173
Description
Activity
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.
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 thanITuple. The results were forITuple.I'll put together a few more benchmarks in more comments below.
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.0Method 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 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.0Method 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 - - - - 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.0Method 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 - - - - 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.
I did discover one interesting thing - if I make the second dictionary use key of
object, it performs the same asITuple. This means I'm right in that the issue is boxing. That itself isn't the interesting part but actually using typeobjectas 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 stringhello:{i}.
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:
The thing is, we can't easily use a tuple internally. If we said "all keys are tuples", we could use the
ITupleinterface 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),Guidor 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:
A
CacheStackmight need to be defined asCacheStack<TKey>andCacheStack<TKey, TContext>.Additional constraints include: