Laszlo - SIMD Gather and Scatter Anagram

SIMD Gather and Scatter Anagram

08/25/2026 | 8 minutes to read

Introduction

One of the most difficult problems with SIMD is handling non-contiguous memory access. To address this challenge AVX-512 adds gather and scatter instructions to load and store memory in an array at non-adjacent indexes. These instructions enable a whole new set of algorithms to be vectorized using SIMD operations.

Gather is a single instruction that loads data from non-adjacent indexes of an array into a Vector register. Scatter is a single instruction that stores data at non-adjacent indexes to an array from a Vector register.

Both instructions have a source/destination register parameter, a reference to an array parameter, and another vector parameter containing the indexes for each lane to be loaded or stored.

In this blog post, I will explore one algorithm using gather and scatter instructions with .NET 10. Unfortunately, .NET 10 has not yet implemented these instructions for AVX family of instruction sets, although the API surface has already been approved. Another issue for using the AVX instruction set is that my current CPU does not support AVX-512 (or above). Fortunately, .NET implements the gather and scatter intrinsics for Scalable Vector Extension (SVE). SVE is introduced by Armv8-A architecture. As I also have a Snapdragon X Elite laptop, I thought this would be an excellent opportunity for the test. Unfortunately, while this CPU is derived from Armv8-A architecture, it does not implement SVE. Eventually, I settled on using SVE in the cloud. The Cobalt machines of Azure implement SVE, hence those are used for the performance measurements in this post.

Problem

An anagram problem involves rearranging the letters of a given word or phrase to form a new word or phrase, using all the original letters exactly once. For example, given the word "listen," we can rearrange its letters to form the word "silent." Both "listen" and "silent" are anagrams of each other because they use the same letters in a different order. This post proposes implementations for solving the anagram problem: given two string input values, are they anagrams?

The following preconditions are set for this post:

The input string only contains lower-case ASCII letters.
SVE is supported by the executing architecture.
The vector register is 128 bit long.

Solutions

In this section, I show two implementations, one regular and one using SIMD with SVE.

Regular Approach

The regular approach uses a backing array, where each element of the array corresponds to one of the lower-case characters in [a-z]. The algorithm iterates through the inputs, and for each character in the [a-z] range increases/decreases the corresponding index of the array by one. Finally, it validates that every element of the array is 0. If one backing array element is not zero, the inputs are not anagram.

Input a increases the value of the backing array.
Input b decreases the value of the backing array.

 public bool IsAnagram(ReadOnlySpan<char> a, ReadOnlySpan<char> b)
 {
    // When the length of the inputs are not equal
    // they are not anagram.
     if (a.Length != b.Length)
         return false;
     Span<int> buffer = stackalloc int[26];
     for (int i = 0; i < a.Length; i++)
     {
        // 'a' is subtrackted as an offset
         buffer[a[i] - 'a']++;
         buffer[b[i] - 'a']--;
     }

     // Is any of the element is not null
     // the inputs are not anagram.
     foreach (var item in buffer)
     {
         if (item != 0)
             return false;
     }
     return true;
 }

The value of a is subtracted from each character, so that the ASCII values can be used directly indexing into the array at an offset.

SVE Approach

With SVE, the implementation follows the same logic, but it handles Vector<int>.Count number of characters of the input at a time. Please note that this algorithm only works on CPU's supporting SVE and throws otherwise. At its core, it uses the Gather and Scatter instructions. In each iteration of the main loop, a 4-character vector is used on my machine. However, there is a conflict situation when using the Scatter instruction: given two identical characters in a current vector, the two characters need to update the same index of the backing array. For example, given an input of

[a, b, a, c]

Both the 0th and the 2nd index of this input would need to increment the same corresponding index ([0]) of the backing array:

[0, 1, 0, 2]

With Scatter one of the writes would get suppressed. A few conflict resolution strategies exist. In AVX there is an explicit instruction for detecting conflicts. The AVX instruction and the resolution strategies are detailed in an excellent blog post: AVX-512 conflict detection without resolving conflicts. In SVE, no such conflict detection instruction exists. To handle the conflict, the backing storage space can be inflated to by a factor of 4 - the number of lanes in the vector. Each lane of the vector has a dedicated section in the backing array:

- Index 0: [0-25]
- Index 1: [26-51]
- Index 2: [52-77]
- Index 3: [78-103]

So, the indexes from the above example are transformed with a single addition operation to

 [0,  1,  0,  2]
+[0, 26, 52, 78]
----------------
=[0, 27, 52, 80]

This way Scatter can avoid a more complex conflict resolution strategy, and the core of the main loops remains simple. A larger backing array demands more space in the CPU cache (416 byte) but is still acceptable.

The core of the algorithm remains the same:

var currentV = Sve.LoadVectorUInt16ZeroExtendToUInt32(Vector<uint>.One, &aa[i]);
currentV -= offset;
Vector<int> countV = Sve.GatherVector(Vector<int>.One, buffer, currentV);
countV += Vector<int>.One;
Sve.Scatter(Vector<int>.One, buffer, currentV, countV)

Loads the input into a vector.
Calculates the indexes for each character in the backing array.
Loads the values of the backing array at the calculated indexes.
Increments the values by one for input a and decrements it by one for input b.
Stores the values in the backing array.

The complete method:

public unsafe bool IsAnagramSimd(Span<char> a, Span<char> b)
{
    // Assert that Vector<uint>.Count is 4.
    // Assert that characters are `(c >= 'a' && c <= 'z')`
    if (a.Length != b.Length)
        return false;
    int* buffer = stackalloc int[26 * 4];
    var offset = new Vector<uint>('a') - new Vector<uint>([0u, 26u, 52u, 78u]);
    fixed (char* ptrA = a)
    {
        fixed (char* ptrB = b)
        {
            ushort* aa = (ushort*)ptrA;
            ushort* bb = (ushort*)ptrB;
            int i = 0;
            for (; i < a.Length - 4; i += 4)
            {
                var currentV = Sve.LoadVectorUInt16ZeroExtendToUInt32(Vector<uint>.One, &aa[i]);
                currentV -= offset;
                Vector<int> countV = Sve.GatherVector(Vector<int>.One, buffer, currentV);
                countV += Vector<int>.One;
                Sve.Scatter(Vector<int>.One, buffer, currentV, countV);

                currentV = Sve.LoadVectorUInt16ZeroExtendToUInt32(Vector<uint>.One, &bb[i]);
                currentV -= offset;
                countV = Sve.GatherVector(Vector<int>.One, buffer, currentV);
                countV -= Vector<int>.One;
                Sve.Scatter(Vector<int>.One, buffer, currentV, countV);
            }

            for (; i < a.Length; i++)
            {
                buffer[a[i] - 'a']++;
                buffer[b[i] - 'a']--;
            }
        }
    }

    for (int i = 0; i < 26; i++)
    {
        // Merging the sum of identical characters in the vector space.
        var sum = buffer[i] + buffer[i + 26] + buffer[i + 52] + buffer[i + 78];
        if (sum != 0)
            return false;
    }

    return true;
}

Remarks:

The input parameter is Span<char> instead of being a ReadOnlySpan<char>, as it needs pinning (with fixed keyword), so the GC won't move the object
The backing array is stack allocated (implicitly pinned).
The Gather, Scatter, and LoadVectorUInt16ZeroExtendToUInt32 intrinsics work with pointer types, hence the method has an unsafe modifier and the csproj file allows for unsafe code.
LoadVectorUInt16ZeroExtendToUInt32 loads and expands the UTF-16 characters into uint.
When the remaining part of the input is less than the vector size, a manual loop completes the process. Notice that SVE offers a mask for each instruction, which could be also used.
The offset is subtracted from the current vector, so that it can be a Vector<uint> (0 or a postive integer).
The final loop merges the inflated space of the backing array, so that the values of identical characters are added.

Performance Comparison

The SIMD version of the method handles 4 chars at a time (as 4 int values fit in a vector on the current implementation of SVE in .NET 10). That gives a theoretical limit of 4 for the speed-up compared to the regular approach. In practice it is rare to observe such performance improvements, because the vectorized solution also needs to load the data in vector registers. However, less branching typically means less branch miss-predictions. In this case the gain is about x1.5, which is respectable, however it also comes with the tradeoff of using unsafe code.

BenchmarkDotNet v0.15.4, Windows 11 (10.0.26200.6584) (Hyper-V)
Cobalt 100 3.40GHz, 1 CPU, 2 logical and 2 physical cores
.NET SDK 10.0.100-rc.1.25451.107
  [Host]     : .NET 10.0.0 (10.0.0-rc.1.25451.107, 10.0.25.45207), Arm64 RyuJIT armv8.0-a
  DefaultJob : .NET 10.0.0 (10.0.0-rc.1.25451.107, 10.0.25.45207), Arm64 RyuJIT armv8.0-a


| Method        | Input               | Mean       | Error    | StdDev   |
|-------------- |-------------------- |-----------:|---------:|---------:|
| IsAnagram     | anag(...)gram [280] |   433.6 ns |  0.73 ns |  0.65 ns |
| IsAnagramSimd | anag(...)gram [280] |   360.0 ns |  0.61 ns |  0.54 ns |

SVE SIMD performance vector

Hello, I am Laszlo

Software-Engineer, .NET developer