Skip to content

Instantly share code, notes, and snippets.

@bgrainger

bgrainger/Lookup.cs

Last active August 8, 2024 17:18
Show Gist options
  • Save bgrainger/60745c7b869475e30e1e5abf10d44db7 to your computer and use it in GitHub Desktop.
Save bgrainger/60745c7b869475e30e1e5abf10d44db7 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Lookup.cs
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Diagnostics.CodeAnalysis;
using System.Text;
var summary = BenchmarkRunner.Run<Lookups>();
[MemoryDiagnoser]
public class Lookups
{
static readonly HashSet<string> CustomLookup = new HashSet<string>(new OurStringComparer())
{
"abcdefgh",
"bcdefghi",
"cdefghij",
"defghijk",
"efghijkl",
"fghijklm",
"ghijklmn",
"hijklmno",
};
static readonly HashSet<string> DotnetLookup = new HashSet<string>(StringComparer.Ordinal)
{
"abcdefgh",
"bcdefghi",
"cdefghij",
"defghijk",
"efghijkl",
"fghijklm",
"ghijklmn",
"hijklmno",
};
private static string ExistingKeyString => "efghijkl";
private static ReadOnlySpan<char> ExistingKeyUtf16 => "efghijkl";
private static ReadOnlySpan<byte> ExistingKeyUtf8 => "efghijkl"u8;
private static string NonExistingKeyString => "stuvwxyz";
private static ReadOnlySpan<char> NonExistingKeyUtf16 => "stuvwxyz";
private static ReadOnlySpan<byte> NonExistingKeyUtf8 => "stuvwxyz"u8;
[Benchmark(Baseline = true)]
public bool Dotnet_String_Hit() => DotnetLookup.Contains(ExistingKeyString);
[Benchmark]
public bool Dotnet_String_Miss() => DotnetLookup.Contains(NonExistingKeyString);
[Benchmark]
public bool Dotnet_Span_Hit()
{
var spanLookup = DotnetLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(ExistingKeyUtf16);
}
[Benchmark]
public bool Dotnet_Span_Miss()
{
var spanLookup = DotnetLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(NonExistingKeyUtf16);
}
[Benchmark]
public bool Dotnet_Utf8Decode_Hit()
{
Span<char> decoded = stackalloc char[ExistingKeyUtf8.Length];
decoded = decoded[..Encoding.UTF8.GetChars(ExistingKeyUtf8, decoded)];
var spanLookup = DotnetLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(decoded);
}
[Benchmark]
public bool Dotnet_Utf8Decode_Miss()
{
Span<char> decoded = stackalloc char[NonExistingKeyUtf8.Length];
decoded = decoded[..Encoding.UTF8.GetChars(NonExistingKeyUtf8, decoded)];
var spanLookup = DotnetLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(decoded);
}
[Benchmark]
public bool Custom_String_Hit() => CustomLookup.Contains(ExistingKeyString);
[Benchmark]
public bool Custom_String_Miss() => CustomLookup.Contains(NonExistingKeyString);
[Benchmark]
public bool Custom_Span_Hit()
{
var spanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(ExistingKeyUtf16);
}
[Benchmark]
public bool Custom_Span_Miss()
{
var spanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(NonExistingKeyUtf16);
}
[Benchmark]
public bool Custom_Utf8_Hit()
{
var utf8SpanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<byte>>();
return utf8SpanLookup.Contains(ExistingKeyUtf8);
}
[Benchmark]
public bool Custom_Utf8_Miss()
{
var utf8SpanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<byte>>();
return utf8SpanLookup.Contains(NonExistingKeyUtf8);
}
[Benchmark]
public bool Custom_Utf8Decode_Hit()
{
Span<char> decoded = stackalloc char[ExistingKeyUtf8.Length];
decoded = decoded[..Encoding.UTF8.GetChars(ExistingKeyUtf8, decoded)];
var spanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(decoded);
}
[Benchmark]
public bool Custom_Utf8Decode_Miss()
{
Span<char> decoded = stackalloc char[NonExistingKeyUtf8.Length];
decoded = decoded[..Encoding.UTF8.GetChars(NonExistingKeyUtf8, decoded)];
var spanLookup = CustomLookup.GetAlternateLookup<string, ReadOnlySpan<char>>();
return spanLookup.Contains(decoded);
}
}
public ref struct Utf8SpanRuneEnumerator
{
private ReadOnlySpan<byte> _remaining;
private Rune _current;
public Utf8SpanRuneEnumerator(ReadOnlySpan<byte> buffer)
{
_remaining = buffer;
_current = default;
}
public Rune Current => _current;
public Utf8SpanRuneEnumerator GetEnumerator() => this;
public bool MoveNext()
{
if (_remaining.IsEmpty)
{
_current = default;
return false;
}
Rune.DecodeFromUtf8(_remaining, out _current, out var bytesConsumed);
_remaining = _remaining.Slice(bytesConsumed);
return true;
}
}
class OurStringComparer : IEqualityComparer<string>,
IAlternateEqualityComparer<ReadOnlySpan<char>, string>,
IAlternateEqualityComparer<ReadOnlySpan<byte>, string>
{
public string Create(ReadOnlySpan<char> alternate) => new(alternate);
public bool Equals(string? x, string? y) => string.Equals(x, y);
public bool Equals(ReadOnlySpan<char> alternate, string other) =>
other?.AsSpan().SequenceEqual(alternate) ?? false;
public bool Equals(ReadOnlySpan<byte> alternate, string other)
{
var utf16Enumerator = other.EnumerateRunes();
var utf8Enumerator = new Utf8SpanRuneEnumerator(alternate);
while (utf16Enumerator.MoveNext())
{
if (!utf8Enumerator.MoveNext())
return false;
if (utf16Enumerator.Current != utf8Enumerator.Current)
return false;
}
return !utf8Enumerator.MoveNext();
}
public int GetHashCode([DisallowNull] string str) =>
str is null ? 0 : GetHashCode(str.AsSpan());
public string Create(ReadOnlySpan<byte> alternate) => Encoding.UTF8.GetString(alternate);
public int GetHashCode(ReadOnlySpan<char> alternate)
{
uint hash = 5381;
foreach (var rune in alternate.EnumerateRunes())
hash = hash * 33u + (uint)rune.Value;
return (int)hash;
}
public int GetHashCode(ReadOnlySpan<byte> alternate)
{
uint hash = 5381;
foreach (var rune in new Utf8SpanRuneEnumerator(alternate))
hash = hash * 33u + (uint)rune.Value;
return (int)hash;
}
}
Raw
Results.md 

BenchmarkDotNet v0.14.0, Windows 10 (10.0.19045.4717/22H2/2022Update)
Intel Core i7-10875H CPU 2.30GHz, 1 CPU, 16 logical and 8 physical cores
.NET SDK 9.0.100-preview.6.24328.19
  [Host]     : .NET 9.0.0 (9.0.24.32707), X64 RyuJIT AVX2
  DefaultJob : .NET 9.0.0 (9.0.24.32707), X64 RyuJIT AVX2
Method Mean Error StdDev Ratio RatioSD Allocated Alloc Ratio
Dotnet_String_Hit 17.74 ns 0.590 ns 1.741 ns 1.01 0.14 - NA
Dotnet_String_Miss 10.29 ns 0.389 ns 1.148 ns 0.59 0.09 - NA
Dotnet_Span_Hit 29.82 ns 0.644 ns 1.357 ns 1.70 0.19 - NA
Dotnet_Span_Miss 22.11 ns 0.480 ns 1.416 ns 1.26 0.15 - NA
Dotnet_Utf8Decode_Hit 44.40 ns 0.925 ns 2.143 ns 2.53 0.29 - NA
Dotnet_Utf8Decode_Miss 34.70 ns 0.761 ns 2.245 ns 1.98 0.24 - NA
Custom_String_Hit 29.51 ns 1.099 ns 3.241 ns 1.68 0.25 - NA
Custom_String_Miss 24.10 ns 0.822 ns 2.411 ns 1.37 0.20 - NA
Custom_Span_Hit 44.88 ns 0.940 ns 1.695 ns 2.55 0.28 - NA
Custom_Span_Miss 40.35 ns 0.819 ns 0.766 ns 2.30 0.24 - NA
Custom_Utf8_Hit 54.73 ns 1.125 ns 2.273 ns 3.12 0.35 - NA
Custom_Utf8_Miss 29.98 ns 0.754 ns 2.223 ns 1.71 0.22 - NA
Custom_Utf8Decode_Hit 58.93 ns 1.386 ns 4.087 ns 3.36 0.42 - NA
Custom_Utf8Decode_Miss 55.21 ns 1.140 ns 2.250 ns 3.14 0.35 - NA
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment