Replace characters in a string using Vectorization

This post is part of the series 'SIMD'. Be sure to check out the rest of the blog posts of the series!

• Faster Guid comparisons using Vectors (SIMD) in .NET
• Finding the maximum value in an array using vectorization
• Replace characters in a string using Vectorization (this post)

I continue to look at code that uses Vectorization in the .NET libraries. In this post, we'll check the method ReplacePlusWithSpace from the ASP.NET Core code. This method replaces + with (space). This is useful to unescape URLs. This method uses Vector128 and SSE2 instructions. Like in previous posts, the comments in the code are mine:

// source: https://github.com/dotnet/aspnetcore/blob/c65dac77cf6540c81860a42fff41eb11b9804367/src/Shared/QueryStringEnumerable.cs#L169

// Cache the delegate to avoid an instantiation each time, or a null check
// https://www.meziantou.net/performance-lambda-expressions-method-groups-and-delegate-caching.htm
private static readonly SpanAction<char, IntPtr> s_replacePlusWithSpace = ReplacePlusWithSpaceCore;

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe string ReplacePlusWithSpace(ReadOnlySpan<char> span)
{
    // You cannot use the ReadOnlySpan<char> as a parameter of string.Create<T>().
    // The following code doesn't compile:
    // string.Create<ReadOnlySpan<char>>(10, span, (buffer, span) => { });
    //
    // The workaround is to create a pointer from the ReadOnlySpan and use the pointer
    // in string.Create
    fixed (char* ptr = &MemoryMarshal.GetReference(span))
    {
        return string.Create(span.Length, (IntPtr)ptr, s_replacePlusWithSpace);
    }
}

private static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
{
    // Convert the destination buffer to a pointer
    fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
    {
        // Vector only support numeric types, so you cannot use char.
        // char and ushort are both 2 bytes long, so you can convert
        // the pointer from (char*) to (ushort*)
        var input = (ushort*)state.ToPointer();
        var output = (ushort*)ptr;

        var i = (nint)0;
        var n = (nint)(uint)buffer.Length;

        // Use Vector<128> to process 8 characters at a time
        if (Sse41.IsSupported && n >= Vector128<ushort>.Count)
        {
            // Create a Vector128 instance with all elements initialized to '+'
            var vecPlus = Vector128.Create((ushort)'+');

            // Create a Vector128 instance with all elements initialized to '.'
            var vecSpace = Vector128.Create((ushort)' ');

            do
            {
                // Load 8 chars from the input string
                // vec:  ['a', 'a', '+', 'a', '+', 'a', 'a', 'a']
                var vec = Sse2.LoadVector128(input + i);

                // Compare the chars with '+'. The result contains 0x0000 when the char
                // is not equals to '+', and 0xFFFF when it is equals to '+'.
                // The goal is to create a mask which indicate the characters to replace
                // with a space
                //
                // vec:     [ 'a'  ,  'a'  ,  '+'  ,  'a'  ,  '+'  ,  'a'  ,  'a'  ,  'a'  ]
                // vecPlus: [ '+'  ,  '+'  ,  '+'  ,  '+'  ,  '+'  ,  '+'  ,  '+'  ,  '+'  ]
                // mask:    [0x0000, 0x0000, 0xFFFF, 0x0000, 0xFFFF, 0x0000, 0x0000, 0x0000]
                var mask = Sse2.CompareEqual(vec, vecPlus);

                // Replace chars where mask 1 with space
                // vec:      [ 'a'  ,  'a'  ,  '+'  ,  'a'  ,  '+'  ,  'a'  ,  'a'  ,  'a'  ]
                // vecSpace: [ ' '  ,  ' '  ,  ' '  ,  ' '  ,  ' '  ,  ' '  ,  ' '  ,  ' '  ]
                // mask:     [0x0000, 0x0000, 0xFFFF, 0x0000, 0xFFFF, 0x0000, 0x0000, 0x0000]
                // res:      [ 'a'  ,  'a'  ,  ' '  ,  'a'  ,  ' '  ,  'a'  ,  'a'  ,  'a'  ]
                var res = Sse41.BlendVariable(vec, vecSpace, mask);

                // Store the res vector to the output buffer
                Sse2.Store(output + i, res);

                // Process the next 8 chars
                i += Vector128<ushort>.Count;

            } while (i <= n - Vector128<ushort>.Count);
        }

        // Processing the remaining characters (from 0 to 7 chars)
        for (; i < n; ++i)
        {
            if (input[i] != '+')
            {
                output[i] = input[i];
            }
            else
            {
                output[i] = ' ';
            }
        }
    }
}

#Replace specific instructions with Vector128 methods

The previous code uses direct instructions such as Sse41.BlendVariable. This code works, but you need to check if the hardware supports them and you need to provide a fallback implementation when hardware is not supported. .NET provides methods that use SIMD instructions when possible and fall back to a software implementation. This way you don't need to handle the complexity by yourself.

The previous code can be rewritten using the Vector128 static methods:

if (n >= Vector128<ushort>.Count) // No need to check for hardware support
{
    var vecPlus = Vector128.Create((ushort)'+');
    var vecSpace = Vector128.Create((ushort)' ');

    do
    {
        // Equivalent of Sse2.LoadVector128(input + i);
        var vec = Vector128.Load(input + i);

        // Equivalent of Sse2.CompareEqual(vec, vecPlus);
        var mask = Vector128.Equals(vec, vecPlus);

        // Equivalent of Sse41.BlendVariable(vec, vecSpace, mask);
        var res = Vector128.ConditionalSelect(mask, vecSpace, vec);

        // Equivalent of Sse2.Store(output + i, res);
        res.Store(output + i);

        i += Vector128<ushort>.Count;

    } while (i <= n - Vector128<ushort>.Count);
}

for (; i < n; ++i)
{
    if (input[i] != '+')
    {
        output[i] = input[i];
    }
    else
    {
        output[i] = ' ';
    }
}

#Improve the method with AVX2

AVX2 provides instructions to process 16 characters at a time. The code is very similar to the SSE instruction set. Similar to Vector128, you can use Vector256 to avoid handling the complexity of providing a software implementation. Let's see if this improves the performance.

private static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
{
    fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
    {
        var input = (ushort*)state.ToPointer();
        var output = (ushort*)ptr;

        var i = (nint)0;
        var n = (nint)(uint)buffer.Length;

        // Process 16 chars per loop
        if (Vector256.IsHardwareAccelerated && n >= Vector256<ushort>.Count)
        {
            var vecPlus = Vector256.Create((ushort)'+');
            var vecSpace = Vector256.Create((ushort)' ');

            do
            {
                var vec = Vector256.Load(input + i);
                var mask = Vector256.Equals(vec, vecPlus);
                var res = Vector256.ConditionalSelect(mask, vecSpace, vec);
                res.Store(output + i);
                i += Vector256<ushort>.Count;
            } while (i <= n - Vector256<ushort>.Count);
        }

        // Process 8 chars per loop
        if (Vector128.IsHardwareAccelerated && n - i >= Vector128<ushort>.Count)
        {
            var vecPlus = Vector128.Create((ushort)'+');
            var vecSpace = Vector128.Create((ushort)' ');

            do
            {
                var vec = Vector128.Load(input + i);
                var mask = Vector128.Equals(vec, vecPlus);
                var res = Vector128.ConditionalSelect(mask, vecSpace, vec);
                res.Store(output + i);
                i += Vector128<ushort>.Count;
            } while (i <= n - Vector128<ushort>.Count);
        }

        // Processing the remaining characters (from 0 to 7 chars)
        for (; i < n; ++i)
        {
            if (input[i] != '+')
            {
                output[i] = input[i];
            }
            else
            {
                output[i] = ' ';
            }
        }
    }
}

#Benchmark

Let's compare all the previous implementations, plus string.Replace. While string.Replace cannot be used in this case as the source is a ReadOnlySpan<char> and not a string, it gives a good indication of the performance of this method.

[ReturnValueValidator]
public class ReplacePlusWithSpaceBenchmark
{
    [ParamsSource(nameof(ValueSource))]
    public string Value { get; set; } = null!;

    public IEnumerable<string> ValueSource
    {
        get
        {
            for (int i = 0; i < 128; i += 6)
            {
                yield return string.Create(i, state: (object?)null, (span, state) =>
                {
                    for (var i = 0; i < span.Length; i++)
                    {
                        span[i] = i % 5 == 0 ? '+' : 'a';
                    }
                });
            }
        }
    }

    [Benchmark()]
    public string Basic() => BasicHelper.ReplacePlusWithSpace(Value);

    [Benchmark]
    public string StringReplace() => Value.Replace('+', ' ');

    [Benchmark(Baseline = true)]
    public string Current() => Vector128Helper_Sse.ReplacePlusWithSpace(Value);

    [Benchmark]
    public string Vector128() => Vector128Helper.ReplacePlusWithSpace(Value);

    [Benchmark]
    public string Vector256() => Vector256Helper.ReplacePlusWithSpace(Value);
}

public static class BasicHelper
{
    private static readonly SpanAction<char, IntPtr> s_replacePlusWithSpace = ReplacePlusWithSpaceCore;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe string ReplacePlusWithSpace(ReadOnlySpan<char> span)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(span))
        {
            return string.Create(span.Length, (IntPtr)ptr, s_replacePlusWithSpace);
        }
    }

    private static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
        {
            var input = (ushort*)state.ToPointer();
            var output = (ushort*)ptr;
            var i = (nint)0;
            var n = (nint)(uint)buffer.Length;
            for (; i < n; ++i)
            {
                if (input[i] != '+')
                {
                    output[i] = input[i];
                }
                else
                {
                    output[i] = ' ';
                }
            }
        }
    }
}

public static class Vector128Helper_Sse
{
    private static readonly SpanAction<char, IntPtr> s_replacePlusWithSpace = ReplacePlusWithSpaceCore;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe string ReplacePlusWithSpace(ReadOnlySpan<char> span)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(span))
        {
            return string.Create(span.Length, (IntPtr)ptr, s_replacePlusWithSpace);
        }
    }

    private static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
        {
            var input = (ushort*)state.ToPointer();
            var output = (ushort*)ptr;

            var i = (nint)0;
            var n = (nint)(uint)buffer.Length;

            if (Sse41.IsSupported && n >= Vector128<ushort>.Count)
            {
                var vecPlus = Vector128.Create((ushort)'+');
                var vecSpace = Vector128.Create((ushort)' ');

                do
                {
                    var vec = Sse2.LoadVector128(input + i);
                    var mask = Sse2.CompareEqual(vec, vecPlus);
                    var res = Sse41.BlendVariable(vec, vecSpace, mask);
                    Sse2.Store(output + i, res);
                    i += Vector128<ushort>.Count;

                } while (i <= n - Vector128<ushort>.Count);
            }

            for (; i < n; ++i)
            {
                if (input[i] != '+')
                {
                    output[i] = input[i];
                }
                else
                {
                    output[i] = ' ';
                }
            }
        }
    }
}

public static class Vector128Helper
{
    private static readonly SpanAction<char, IntPtr> s_replacePlusWithSpace = ReplacePlusWithSpaceCore;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe string ReplacePlusWithSpace(ReadOnlySpan<char> span)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(span))
        {
            return string.Create(span.Length, (IntPtr)ptr, s_replacePlusWithSpace);
        }
    }

    public static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
        {
            var input = (ushort*)state.ToPointer();
            var output = (ushort*)ptr;
            var i = (nint)0;
            var n = (nint)(uint)buffer.Length;

            if (n >= Vector128<ushort>.Count)
            {
                var vecPlus = Vector128.Create((ushort)'+');
                var vecSpace = Vector128.Create((ushort)' ');

                do
                {
                    var vec = Vector128.Load(input + i);
                    var mask = Vector128.Equals(vec, vecPlus);
                    var res = Vector128.ConditionalSelect(mask, vecSpace, vec);
                    res.Store(output + i);
                    i += Vector128<ushort>.Count;

                } while (i <= n - Vector128<ushort>.Count);
            }

            for (; i < n; ++i)
            {
                if (input[i] != '+')
                {
                    output[i] = input[i];
                }
                else
                {
                    output[i] = ' ';
                }
            }
        }
    }
}

public static class Vector256Helper
{
    private static readonly SpanAction<char, IntPtr> s_replacePlusWithSpace = ReplacePlusWithSpaceCore;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe string ReplacePlusWithSpace(ReadOnlySpan<char> span)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(span))
        {
            return string.Create(span.Length, (IntPtr)ptr, s_replacePlusWithSpace);
        }
    }

    private static unsafe void ReplacePlusWithSpaceCore(Span<char> buffer, IntPtr state)
    {
        fixed (char* ptr = &MemoryMarshal.GetReference(buffer))
        {
            var input = (ushort*)state.ToPointer();
            var output = (ushort*)ptr;

            var i = (nint)0;
            var n = (nint)(uint)buffer.Length;

            if (Vector256.IsHardwareAccelerated && n >= Vector256<ushort>.Count)
            {
                var vecPlus = Vector256.Create((ushort)'+');
                var vecSpace = Vector256.Create((ushort)' ');

                do
                {
                    var vec = Vector256.Load(input + i);
                    var mask = Vector256.Equals(vec, vecPlus);
                    var res = Vector256.ConditionalSelect(mask, vecSpace, vec);
                    res.Store(output + i);
                    i += Vector256<ushort>.Count;
                } while (i <= n - Vector256<ushort>.Count);
            }

            if (Vector128.IsHardwareAccelerated && n - i >= Vector128<ushort>.Count)
            {
                var vecPlus = Vector128.Create((ushort)'+');
                var vecSpace = Vector128.Create((ushort)' ');

                do
                {
                    var vec = Vector128.Load(input + i);
                    var mask = Vector128.Equals(vec, vecPlus);
                    var res = Vector128.ConditionalSelect(mask, vecSpace, vec);
                    res.Store(output + i);
                    i += Vector128<ushort>.Count;
                } while (i <= n - Vector128<ushort>.Count);
            }

            for (; i < n; ++i)
            {
                if (input[i] != '+')
                {
                    output[i] = input[i];
                }
                else
                {
                    output[i] = ' ';
                }
            }
        }
    }
}

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 5800X, 1 CPU, 16 logical and 8 physical cores
.NET SDK=7.0.100-preview.5.22307.18
  [Host]    : .NET 7.0.0 (7.0.22.30112), X64 RyuJIT
  RyuJitX64 : .NET 7.0.0 (7.0.22.31201), X64 RyuJIT

Job=RyuJitX64  Jit=RyuJit  Platform=X64
Toolchain=.NET 7.0.100-preview.6.22316.8

#Additional resources

• Use Vector instead of direct Intrinsics

Do you have a question or a suggestion about this post? Contact me!