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:

UTF-8 bytes ≥ 0x80 are what the guard bit rejects, so emoji pass through untouched. A tail shorter than 8 bytes is padded with “·” here; the real code sends those to a plain scalar loop instead (the SWAR word only runs once 8 bytes are available — try “RUBY💎 (short)” to see the pad).

the 64-bit register, one byte per lane

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