Sampo Development LLC

A Ruby pull request, live in your browser

SWAR: 8 Bytes at a Time

A pull request to Ruby proposes an eight-bytes-per-step fast path for String#capitalize!: one ordinary 64-bit register, no vector instructions. The technique is SWAR (SIMD Within A Register), from Lamport, 1975. Type a string and step through it.

Every step on this page is computed by Ruby (loading WebAssembly…)

Try:

The strip below shows the whole string split the way the code splits it: byte 0 (scalar upcase), then full 8-byte SWAR words, then any leftover under 8 bytes (scalar). UTF-8 bytes ≥ 0x80 (emoji, accents) are rejected by the guard and pass through untouched.

Click a SWAR word to step through its 8 lanes below:

the 64-bit register: 8 lanes, one instruction

Select a step above to walk through the pipeline.

What the steps show

capitalize! upcases byte 0 with a plain scalar step (the dashed card), then runs the SWAR loop over the next eight bytes at once. Steps 2–6 above are that loop's helper, swar_in_range(v, 'A', 'Z') from string.c: park the guard bit, two adds to test every lane against 'A' and 'Z', a non-ASCII check, then AND the three verdicts into one mask. The caller does the rest: step 1 loads the register, and steps 7–8 shift that mask onto the case bit and XOR it in, flipping every uppercase lane. One question (is this byte an ASCII uppercase letter?), answered for eight bytes at once, in bit 7 of each lane.

Hex, quickly

A byte is two hex digits, 4 bits each. Upper and lower case differ in exactly bit 5 (0x20): 'R' 0x52 ^ 0x20 = 0x72 'r'. One bit, whole alphabet; the C code asserts it at compile time (ASCII_CASE_BIT == ('Z'^'z')).

Why it's safe

Eight independent bytes share one adder: a carry from lane 3 could corrupt lane 4. Three properties prevent it:

  1. The guard bit stops carries. Lanes are masked to ≤ 0x7F and the constant is ≤ 0x3F, so the worst sum (0xBE) stays inside the byte. The carry lands in bit 7, the answer flag (Lamport 1975; Knuth TAOCP 4A §7.1.3).
  2. The shift can't smear. Each lane holds 0x80 or 0x00; bit 7 shifted by 2 is bit 5, same byte.
  3. XOR touches only masked lanes. 0x20 in letter lanes, 0x00 everywhere else. Non-letters pass bit-for-bit; rewriting an unchanged byte with its own value is a no-op.

Non-ASCII gets caught twice: a byte like 0xC3 masks to a fake letter, so the final mask also requires the original bit 7 clear (~v & 0x80…).

Endianness

Every step stays inside its own lane, so register byte order is irrelevant: little-endian, big-endian (s390x), same result. Only SWAR that moves data between lanes has to care.

Why bother, isn't this the compiler's job?

For the copying case (downcase), yes: unconditional stores auto-vectorize to 16-byte NEON. The in-place case must store only what changed, and there compilers give up: clang emits slow masked stores, GCC goes byte-at-a-time. SWAR does one 8-byte load, test, store. Measured: parity below 64 bytes, roughly 2× (clang) and 3× (GCC) on multi-kilobyte strings.

Further reading

  • The String#capitalize! SWAR pull request: the change this page animates.
  • Lamport, CACM 18(8), 1975: the original; the guard bit is his “separator bit”.
  • Knuth, TAOCP Vol. 4A, §7.1.3: broadword computation.
  • ruby/ruby #17403: the merged capitalize ASCII fast path this builds on.
  • ruby/ruby #17415: the related upcase/downcase work.

The Ruby that ran this page

The lane values came from the function below: real Ruby, in your browser, via ruby.wasm, mirroring the C helper line for line. If the WebAssembly download fails, a JavaScript BigInt engine takes over; the badge up top says which one you got.

Show the in-browser Ruby source