dotnet / dotnet/runtime

ActivityTraceId.IsLowerCaseHexAndNotAllZeros can be further optimized with SIMD

Open
#121,135 5 comments 0 reactions 0 assignees View on GitHub
area-System.Runtime help wanted tenet-performance
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

Currently `ActivityTraceId.IsLowerCaseHexAndNotAllZeros ` is implemeted like this:
```csharp
private static readonly SearchValues s_hexLowerChars = SearchValues.Create("0123456789abcdef");

internal static bool IsLowerCaseHexAndNotAllZeros(ReadOnlySpan idData)
{
// Verify lower-case hex and not all zeros https://w3c.github.io/trace-context/#field-value
return !idData.ContainsAnyExcept(s_hexLowerChars) && idData.ContainsAnyExcept('0');
}
```
This implementation is shared across 16 char spanId and 32 char traceId

If it fine to do separate SIMD implementations for 16/32 chars then happy case can be around 2 times faster (based on benchmarks on 5950x):

General implementation for 16/32 when Vector size is matched
```csharp
public static bool IsLowerCaseHexAndNotAllZeros_16_V256(ReadOnlySpan span)
{
if (span.Length != 16)
{
return false;
}

var value = Vector256.Create(MemoryMarshal.Cast(span));

var zeroAs0 = value - Vector256.Create((ushort)'0');
var aAs0 = value - Vector256.Create((ushort)'a');

var numMask = Vector256.LessThan(zeroAs0, Vector256.Create((ushort)10));
var lettersMask = Vector256.LessThan(aAs0, Vector256.Create((ushort)6));

var result = (numMask | lettersMask) == Vector256.AllBitsSet && zeroAs0 != Vector256.Zero;

return result;
}
```

General implementation when Vector size is 2 times smaller:
```csharp
public static bool IsLowerCaseHexAndNotAllZeros_16_V128(ReadOnlySpan idData)
{
if (idData.Length != 16)
{
return false;
}

ref var rData = ref Unsafe.As(ref MemoryMarshal.GetReference(idData));
var vPart1 = Vector128.LoadUnsafe(ref rData);
var vPart2 = Vector128.LoadUnsafe(ref rData, (nuint)Vector128.Count);

var value = Vector128.NarrowWithSaturation(vPart1, vPart2);

var zeroAs0 = value - Vector128.Create((byte)'0');
var aAs0 = value - Vector128.Create((byte)'a');

var numMask = Vector128.LessThan(zeroAs0, Vector128.Create((byte)10));
var lettersMask = Vector128.LessThan(aAs0, Vector128.Create((byte)6));

var result = (numMask | lettersMask) == Vector128.AllBitsSet
&& zeroAs0 != Vector128.Zero;

return result;
}
```

32 char will require 2 calls to Vector128 impl or a dedicated implementation
What do you think? Tagging @tannergooding as SIMD expert and @MihaZupan as the latest person to touch/optimize that code

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.