Tern

simd

The simd module works on 16 bytes at once. A bytes16 is a value like an int (no allocation), and each operation is one instruction on ARM (NEON), x86 (SSE2/SSSE3) and wasm (SIMD128), or a short loop where there's none: for scanning text, parsing, byte tables and checksums. std re finds where a match may start with it.

import simd

# the first digit in s, 16 bytes a step
fn first_digit(s: str) int:
    zero = simd.splat(48)
    nine = simd.splat(9)
    i = 0
    while i < len(s):
        v = simd.load_upto(s, i)           # (the last few bytes: zeros after them, not digits)
        k = simd.first_lane(simd.le(v - zero, nine))   # '0'..'9' -> 0..9
        if k < 16:
            return i + k
        i += 16
    return -1

fn main():
    print(first_digit("order number: 4711, shipped"), first_digit("none here"))
    v = simd.load("Hello, bytes16!!", 0)
    print(simd.bits(simd.eq(v, simd.splat(108))))           # lanes holding 'l'
    hex = simd.of("0123456789abcdef")                        # a 16-entry table
    print(simd.to_str(simd.lookup(hex, simd.load("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f", 0))))
Output
14 -1
12
0123456789abcdef

Functions and operators

simd.load(s: str, i: int) bytes16      s[i..i+16] (a runtime error past the end)
simd.load_upto(s: str, i: int) bytes16 the same with zeros past the end (i up to len(s)): a
                                       string's last few bytes, or a short string, in one load
simd.of(t: str) bytes16                a 16-byte string as a bytes16 (a table for lookup)
simd.splat(b: int) bytes16             every lane b (0 to 255)
simd.to_str(v: bytes16) str            the 16 bytes as a string
a & b, a | b, a ^ b, ~a                lane by lane
a + b, a - b                           lane by lane, wrapping (250 + 10 is 4)
a << n, a >> n                         every lane shifted by n (0 to 7), zeros shifted in
a == b, a != b                         all 16 lanes equal (a bool)
simd.eq(a, b) bytes16                  255 in the lanes where a == b, else 0
simd.lt(a, b), simd.le(a, b)           ... where a < b / a <= b (as bytes: 0 to 255)
simd.min(a, b), simd.max(a, b)         lane by lane
simd.lookup(t, i) bytes16              lane k is t's lane i[k] (0 if i[k] >= 16)
simd.bits(v) int                       bit k set when lane k isn't 0 (16 bits)
simd.first_lane(v) int                 the first lane that isn't 0 (16 if none)
simd.any(v) bool                       a lane isn't 0
simd.lane(v, k) int                    lane k (0 to 15)
simd.popcount(v) bytes16               lane k is the number of bits set in lane k (0 to 8)
simd.sum(v) int                        the 16 lanes added up
simd.first(m) int                      the lowest set bit of m (64 if none)

simd.lookup is the building block of byte-classification tricks: split each byte into its low and high nibble (v & simd.splat(15), v >> 4), look each up in a table of 16, and AND the two; that is how re checks three bytes of a few literal strings at 16 positions in a handful of instructions (Teddy). A bytes16 can be a struct field or an array element and compares with ==; it can't be a map key or go to JSON.

Four f32s at once: f32x4

An f32x4 holds four f32s (§ 32-bit floats in the reference) and works on them in one instruction: dot products, distances and sums over [f32] vectors. Like a bytes16 it is a value (no allocation); + - * / work lane by lane, with another f32x4 or with an f32 (which goes to every lane).

import simd

# a dot product, 8 lanes a step (two sums, so each add needn't wait for the one before)
fn dot(a: [f32], b: [f32]) f32:
    s0 = simd.splat_f32(0.0)
    s1 = simd.splat_f32(0.0)
    i = 0
    while i + 8 <= len(a):
        s0 = simd.fma(simd.load_f32(a, i), simd.load_f32(b, i), s0)
        s1 = simd.fma(simd.load_f32(a, i + 4), simd.load_f32(b, i + 4), s1)
        i += 8
    s = simd.sum_f32(s0 + s1)
    while i < len(a):                      # the last few one at a time
        s += a[i] * b[i]
        i += 1
    return s

fn main():
    a: [f32] = []
    b: [f32] = []
    for i in 0..10:
        a.push(f32(i))
        b.push(0.5)
    print(dot(a, b))
    v = simd.f32x4(1.0, 4.0, 9.0, 16.0)
    print(simd.sqrt_f32(v) * 2.0, simd.lane_f32(v, 3), simd.max_f32(v, simd.splat_f32(5.0)))
    simd.store_f32(&a, 0, v)
    print(a[..5])
Output
22.5
f32x4[2.0, 4.0, 6.0, 8.0] 16.0 f32x4[5.0, 5.0, 9.0, 16.0]
[1.0, 4.0, 9.0, 16.0, 4.0]
simd.load_f32(xs: [f32], i: int) f32x4     xs[i..i+4] (a runtime error past the end)
simd.store_f32(xs: mut [f32], i, v)        xs[i..i+4] = v's lanes
simd.splat_f32(x: f32) f32x4               every lane x
simd.f32x4(a, b, c, d: f32) f32x4          these four
a + b, a - b, a * b, a / b, -a             lane by lane (b may be an f32)
a == b, a != b                             all four lanes equal (a bool)
simd.fma(a, b, c) f32x4                    a * b + c, rounded once (one instruction on arm64 and x86 with FMA)
simd.sum_f32(v) f32                        the four lanes added up
simd.min_f32(a, b), simd.max_f32(a, b)     lane by lane
simd.abs_f32(v), simd.sqrt_f32(v)          lane by lane
simd.lane_f32(v, k) f32                    lane k (0 to 3)

The lanes are added in a different order than a loop over the elements would, so a sum can differ from one in the last bits.

Loads in a loop shaped like the dot product's (while i + k <= n: or while i < n:, ending in i += step, and loading xs[base + i + c] where the loop never changes i otherwise, nor n, xs, or base) cost no bounds check: before the loop one test shows every index it can reach is in range, and then it runs without them. (If the test fails it runs with them, so an out-of-range load stops the program on the same line as always.) simd.load on a string works the same way. A tiled matrix multiply written like this runs at the speed of C's. An f32x4 can be a struct field or an array element and compares with ==; it can't be a map key or go to JSON.