⊕ Code: LuxxxLucy/easySWAR

TL;DR : We introduce SWAR “SIMD within a register”, the trick of doing SIMD with a 64-bit register so that it is a more portable operation as some small embedded chips do not possess SIMD capability. We provide some basic introduction and examples, together with benchmarking results. Later in the post we will provide a Rust crate, in what I think would be an easier way to program with SWAR, so that writing such functions (here we target string) would be less of a panic.

⊕ References:• Daniel Lemire, Why do we even need SIMD instructions?• Daniel Lemire, SWAR explained: parsing eight digits• Daniel Lemire, Detect control characters, quotes and backslashes efficiently using SWAR• Yagiz Nizipli, Eliminating branches in C++ loops• MLabs, The ‘A’ is for ‘Accelerated’: checking ASCII with SWAR• Greg Baker, Data parallelism

Introduction

A very common task we see is that we want to find whether a particular char exists in a string, say if you are writing small parsers for application layer protocols.

Say we want to determine whether there is a particular char, the newline \n, in a string such as this is a random string\n. The simplest way is a loop over the bytes.

bool has_newline_naive(const uint8_t *s, size_t n)
{
    for (size_t i = 0; i < n; i++) {
        if (s[i] == '\n') {
            return true;
        }
    }
    return false;
}

It looks at one byte per step and returns at the first hit. If there is no newline, or the newline is at the very end, it visits every byte.

This is a correct implementation, it is just that it is quite slow. The compiled loop is six instructions per byte.

ldrb  w8, [x0], #1        load one byte
cmp   w8, #10             compare it with '\n'
cset  w8, eq
ccmp  x9, #0, #4, ne      and test the remaining count (end of loop)
sub   x9, x9, #1
b.ne  loop

Now there are many problems with this implementation, one easy one we can spot is that it apparently suffers from branch misprediction. So we drop the early exit and use a logical operation.

bool has_newline_reduce_misprediction(const uint8_t *s, size_t n)
{
    bool found = false;
    for (size_t i = 0; i < n; i++) {
        found |= s[i] == '\n';
    }
    return found;
}

Note that we do not have early exit anymore, instead, we will have to loop over all the bytes exactly once. This would be an issue if the particular character we want to find exists early in the string or the frequency of it is high. But in many cases we are looking for a character that is usually serving as some sort of “delimiter”, so that is a reasonable trade-off. However, it is worthy to note that nowadays compilers are smart enough, so this simple case would not make a huge difference, though with a different function target it might be different.

It is here we discuss stronger performance offered by SIMD.

SIMD stands for Single Instruction, Multiple Data, a parallel computing capability that allows a single instruction to be applied on multiple data elements in one instruction cycle. This is better understood as a way of parallelism, as now we batch several units of data and process it in one shot. For example, you can compare N bytes using a single instruction in parallel; as long as N > 1, it would definitely be quicker than the naive 1 byte version.

Exactly how many bytes can be processed together though is still determined by what the hardware can offer. N can be 16, 32 or even larger.

Programming SIMD is usually done by using intrinsics. With AVX2 we can land with the following version. Note that the code has become expectedly uglier.

bool has_newline_avx2(const uint8_t *s, size_t n)
{
    if (n < 32) {
        return has_newline_naive(s, n);
    }
    __m256i newline = _mm256_set1_epi8('\n');
    size_t i = 0;
    for (; i + 128 <= n; i += 128) {
        __m256i m = _mm256_or_si256(
            _mm256_or_si256(_mm256_cmpeq_epi8(load256(s + i), newline),
                            _mm256_cmpeq_epi8(load256(s + i + 32), newline)),
            _mm256_or_si256(_mm256_cmpeq_epi8(load256(s + i + 64), newline),
                            _mm256_cmpeq_epi8(load256(s + i + 96), newline)));
        if (_mm256_movemask_epi8(m)) {
            return true;
        }
    }
    for (; i + 32 <= n; i += 32) {
        if (_mm256_movemask_epi8(_mm256_cmpeq_epi8(load256(s + i), newline))) {
            return true;
        }
    }
    return _mm256_movemask_epi8(
               _mm256_cmpeq_epi8(load256(s + n - 32), newline)) != 0;
}

However, portability has always been an issue with SIMD. Essentially this means you need to write different code tailored at the targeted architecture so that you can get the best results. If such an implementation is not compatible, it would usually fall back to the naive implementation during compile time.

For example, the machine I use, my MacBook, has relatively limited support of SIMD, as it has only 16 byte SIMD registers. So the parallelism it can do would be N=16; in a different machine, we would be able to use stronger (wider) bytes.

Here we show the different versions of the same function in different settings for AVX2, NEON, AVX-512, and the RISC-V vector extension.

bool has_newline_simd(const uint8_t *s, size_t n)
{
    if (n < 16) {
        return has_newline_naive(s, n);
    }
    uint8x16_t newline = vdupq_n_u8('\n');
    size_t i = 0;
    for (; i + 64 <= n; i += 64) {
        uint8x16_t m =
            vorrq_u8(vorrq_u8(vceqq_u8(vld1q_u8(s + i), newline),
                              vceqq_u8(vld1q_u8(s + i + 16), newline)),
                     vorrq_u8(vceqq_u8(vld1q_u8(s + i + 32), newline),
                              vceqq_u8(vld1q_u8(s + i + 48), newline)));
        if (vmaxvq_u8(m)) {
            return true;
        }
    }
    for (; i + 16 <= n; i += 16) {
        if (vmaxvq_u8(vceqq_u8(vld1q_u8(s + i), newline))) {
            return true;
        }
    }
    return vmaxvq_u8(vceqq_u8(vld1q_u8(s + n - 16), newline)) != 0;
}

static inline __m256i load256(const uint8_t *p)
{
    return _mm256_loadu_si256((const __m256i *)p);
}

bool has_newline_avx2(const uint8_t *s, size_t n)
{
    if (n < 32) {
        return has_newline_naive(s, n);
    }
    __m256i newline = _mm256_set1_epi8('\n');
    size_t i = 0;
    for (; i + 128 <= n; i += 128) {
        __m256i m = _mm256_or_si256(
            _mm256_or_si256(_mm256_cmpeq_epi8(load256(s + i), newline),
                            _mm256_cmpeq_epi8(load256(s + i + 32), newline)),
            _mm256_or_si256(_mm256_cmpeq_epi8(load256(s + i + 64), newline),
                            _mm256_cmpeq_epi8(load256(s + i + 96), newline)));
        if (_mm256_movemask_epi8(m)) {
            return true;
        }
    }
    for (; i + 32 <= n; i += 32) {
        if (_mm256_movemask_epi8(_mm256_cmpeq_epi8(load256(s + i), newline))) {
            return true;
        }
    }
    return _mm256_movemask_epi8(
               _mm256_cmpeq_epi8(load256(s + n - 32), newline)) != 0;
}

bool has_newline_avx512(const uint8_t *s, size_t n)
{
    if (n < 64) {
        return has_newline_naive(s, n);
    }
    __m512i newline = _mm512_set1_epi8('\n');
    size_t i = 0;
    for (; i + 256 <= n; i += 256) {
        __mmask64 m =
            _mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + i), newline) |
            _mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + i + 64), newline) |
            _mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + i + 128), newline) |
            _mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + i + 192), newline);
        if (m) {
            return true;
        }
    }
    for (; i + 64 <= n; i += 64) {
        if (_mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + i), newline)) {
            return true;
        }
    }
    return _mm512_cmpeq_epi8_mask(_mm512_loadu_si512(s + n - 64), newline) != 0;
}

bool has_newline_rvv(const uint8_t *s, size_t n)
{
    for (size_t i = 0; i < n;) {
        size_t vl = __riscv_vsetvl_e8m8(n - i);
        vuint8m8_t x = __riscv_vle8_v_u8m8(s + i, vl);
        vbool1_t m = __riscv_vmseq_vx_u8m8_b1(x, '\n', vl);
        if (__riscv_vfirst_m_b1(m, vl) >= 0) {
            return true;
        }
        i += vl;
    }
    return false;
}

SWAR: SIMD within a register

SWAR, “SIMD within a register”, Leslie Lamport, Multiple byte processing with full-word instructions, Communications of the ACM 18(8), 1975. attempted to do SIMD even where no SIMD capability is supported. It utilized a simple fact that modern machines already have the 64-bit register, which can hold 8 bytes, so we can use that to do N=8 parallelism without any portability issue.

Utilizing this idea we can have:

#define ONES 0x0101010101010101ULL /* 0x01 in every lane */
#define HIGH 0x8080808080808080ULL /* the top bit of every lane */

// High bit set in each lane of x that holds '\n'.
static inline uint64_t has_newline_swar_helper(uint64_t x)
{
    uint64_t v = x ^ (ONES * '\n');
    return (v - ONES) & ~v & HIGH;
}

bool has_newline_swar_simple(const uint8_t *s, size_t n)
{
    size_t i = 0;
    for (; i + 8 <= n; i += 8) {
        if (has_newline_swar_helper(load64(s + i))) {
            return true;
        }
    }
    return has_newline_naive(s + i, n - i);
}

A uint64_t already holds eight bytes, and we want to test all eight for \n with integer arithmetic. Lemire’s post on parsing eight digits is the best explanation of SWAR I know; here we need only one trick from it. First, load eight bytes with a memcpy into a uint64_t, which the compiler turns into a single load. We call each of the eight byte positions inside the word a lane, lane 0 being the lowest byte, lane 7 the highest; a SIMD register has lanes in the same sense, sixteen or more of them. Second, repeat a byte across the word: multiplying a byte by 0x0101010101010101 copies it into every lane. The code calls that constant ONES, and HIGH is the top bit of every lane. Third, XOR the word with ONES * '\n'. A lane that held \n becomes zero and every other lane becomes non-zero, so the question is now which lanes of the word are zero, and there is a classic answer to that.

Subtracting ONES takes one from every lane. A zero lane cannot pay, so it wraps to 0xFF and its top bit turns on, while a lane below 0x80 stays below 0x80 and keeps its top bit off. The & ~v handles the lanes that were at or above 0x80 to begin with, since those keep their top bit through the subtraction and ~v clears it. Then & HIGH throws away everything but the top bits. The result is a word whose lane is 0x80 exactly when byte was a newline, and any non-zero result means we found one. Here is the whole thing on the bytes abc\ndefg, one lane per column, lowest address on the left.

x               61 62 63 0A 64 65 66 67    "abc\ndefg"
v = x ^ ONES*10 6B 68 69 00 6E 6F 6C 6D    the newline lane is zero
v - ONES        6A 67 68 FF 6C 6E 6B 6C    the zero lane wrapped to FF
& ~v & HIGH     00 00 00 80 00 00 00 00    top bit marks the lane

Note that the wrap borrows one from the lane above, which is why 6E became 6C and not 6D. That borrow can turn on the top bit of the lane above a true match. It happens when the byte after the newline is 0x0B: after the XOR that lane is 0x01, the borrow makes it 0xFF, and ~v does not clear it. For has_newline it does not matter, since the lane above only fires when there is a real match below it, and we only ask whether any lane fired. It does matter once masks are combined with AND, and we come back to it in the section on byte sequences.

The loop is the same as the NEON one, four words per step and then one at a time. Now doing just an 8-byte check in a loop would still create too much branching, so instead of just doing 8 bytes at a time, we can further improve it to 4 * 8 (note 4 is just a heuristic).

bool has_newline_swar(const uint8_t *s, size_t n)
{
    if (n < 8) {
        return has_newline_naive(s, n);
    }
    size_t i = 0;
    for (; i + 32 <= n; i += 32) {
        uint64_t m = has_newline_swar_helper(load64(s + i)) |
                     has_newline_swar_helper(load64(s + i + 8)) |
                     has_newline_swar_helper(load64(s + i + 16)) |
                     has_newline_swar_helper(load64(s + i + 24));
        if (m) {
            return true;
        }
    }
    for (; i + 8 <= n; i += 8) {
        if (has_newline_swar_helper(load64(s + i))) {
            return true;
        }
    }
    return has_newline_swar_helper(load64(s + n - 8)) != 0;
}

Here we present the results, running the three versions on one core of an Apple M4, Apple clang 21 at -O3 with auto-vectorization off, on a 2 MiB input. Vectorization is off (-fno-vectorize -fno-slp-vectorize, and -C no-vectorize-loops -C no-vectorize-slp for Rust) because both compilers turn the four-word SWAR step into NEON automatically.

What if the function becomes complicated?

So far the task we do is that we want to find whether a particular byte exists in the string. But real use cases would be more complicated.

In Daniel Lemire’s blog Daniel Lemire, Detect control characters, quotes and backslashes efficiently using SWAR, 2025. about JSON parsing, the task is defined as determining whether a string is valid, where:

• the string should not contain a control character (below 32)
• the string should not contain a quote (34)
• the string should not contain a backslash (92)

The code would be like this:

// High bit set in each lane of x below 0x20, equal to '"', or equal to '\\'.
// Falk Hüffner's form: XOR with 2 maps 34 onto 32, so one subtraction of 33
// wraps both "below 32" and "equal to 34".
static inline uint64_t has_json_escapable_swar_helper(uint64_t x)
{
    uint64_t is_ascii = ~x & HIGH;
    uint64_t lt32_or_eq34 = (x ^ (ONES * 2)) - (ONES * 33);
    uint64_t eq92 = (x ^ (ONES * '\\')) - ONES;
    return (lt32_or_eq34 | eq92) & is_ascii;
}

This has become much more complicated and makes it, let us say, not intuitive to write other functions.

Here I decide to write a Rust lib easySWAR that provides good interface that can make writing these kinds of functions easier.

easySWAR uses a proc-macro swar! to generate the code as a sort of preprocessing. Several predicates such as eq, lt, range, non_ascii, and seq, combined with |, &, and !, can be combined to write complicated functions easily yet still make it compile into same effects.

The aforementioned JSON check function would look like this:

fn json_macro(s: &[u8]) -> bool {
    swar!(lt(0x20) | eq(b'"') | eq(b'\\')).contains(s)
}

You can see from the results that, though the 8-byte SWAR is not as good as the proper SIMD, it still produces impressive results.

We can even make more complicated functions. For example, a good task that comes to my mind is searching for a substring, such as \r\n or \r\n.\r\n, which are frequently used as delimiters in application layer protocols. In C, the \r\n.\r\n search would be like this.

#define STEP_BYTES 12

static inline uint64_t load64(const uint8_t *p)
{
    uint64_t x;
    memcpy(&x, p, 8);
    return x;
}

// High bit set in exactly the lanes of x equal to c. Adding 0x7F to the low
// seven bits of a lane never carries into the next lane, so the masks of
// two words can be ANDed.
static inline uint64_t eq_lanes(uint64_t x, uint8_t c)
{
    uint64_t v = x ^ (ONES * c);
    return ~(((v & LOW7) + LOW7) | v) & HIGH;
}

// High bit set in each lane where "\r\n.\r\n" starts, for the 8 bytes at p.
static inline uint64_t has_end_of_message_swar_helper(const uint8_t *p)
{
    return eq_lanes(load64(p), '\r') & eq_lanes(load64(p + 1), '\n') &
           eq_lanes(load64(p + 2), '.') & eq_lanes(load64(p + 3), '\r') &
           eq_lanes(load64(p + 4), '\n');
}

bool has_end_of_message_swar(const uint8_t *s, size_t n)
{
    if (n < STEP_BYTES) {
        return has_end_of_message_naive(s, n);
    }
    size_t i = 0;
    for (; i + 24 + STEP_BYTES <= n; i += 32) {
        uint64_t m = has_end_of_message_swar_helper(s + i) |
                     has_end_of_message_swar_helper(s + i + 8) |
                     has_end_of_message_swar_helper(s + i + 16) |
                     has_end_of_message_swar_helper(s + i + 24);
        if (m) {
            return true;
        }
    }
    for (; i + STEP_BYTES <= n; i += 8) {
        if (has_end_of_message_swar_helper(s + i)) {
            return true;
        }
    }
    return has_end_of_message_swar_helper(s + n - STEP_BYTES) != 0;
}

Using easySWAR it would be possible to write simply as:

fn end_of_message_search(s: &[u8]) -> bool {
    swar!(seq(b"\r\n.\r\n")).contains(s)
}

Wrap up

SWAR is a small trick, that provides SIMD-like performance using the 64-bit register as the vehicle.