A JRuby pull request, live in your browser
SWAR String#tr: Find and Replace 8 Bytes at Once
str.tr('-', '_') is everywhere in Ruby code.
JRuby #10000
makes it up to 2× faster by checking eight bytes per step in one plain 64-bit
long: no vector instructions, no lookup table.
Type a string, pick the characters, and step through it.
Every step on this page is computed by Ruby (loading WebAssembly…)
One plain ASCII character on each side. Accents and emoji in the string just pass through.
The string as JRuby walks it. Click a word to step through its 8 lanes below:
Eight steps, one register. Click a step, or use the ← → keys.
the 64-bit register: 8 lanes, one instruction
What the steps show
The question is the same for every byte: is this the character I'm looking for? Instead of asking
it eight times, JRuby asks it once for a whole 8-byte word. Copy the character into all eight lanes, XOR
it with the word, and every matching byte turns into 0x00. The rest of the steps are just a way
to find those zero bytes without a loop, and then swap them for the replacement in one more XOR.
Why XOR, twice
XOR with the same value twice gets you back where you started, and XOR with zero changes nothing. So
'-' ^ '_' = 0x2D ^ 0x5F = 0x72 is the "flip" that turns one into the other.
Put 0x72 in the lanes that matched, 0x00 everywhere else, XOR it into the word, and only the
hyphens change.
Why the zero test is exact
The classic trick, (x - 0x01…) & ~x & 0x80…, can report a false match when a borrow runs
from one lane into the next. That's fine for "is there a zero somewhere?", but here every lane gets
rewritten, so a false match would corrupt a byte. JRuby uses the exact form instead:
- Mask to 7 bits, then add 0x7F. The biggest sum is 0x7F + 0x7F = 0xFE, so nothing carries into the next lane. Bit 7 ends up set when the low 7 bits had anything in them.
- OR in the original
x. That catches bytes whose only set bit was bit 7, which the mask threw away. - OR in 0x7F and invert. Every lane becomes
0x00, except the ones that were exactly zero, which become0x80.
The last few bytes
A string is rarely a multiple of 8. Instead of finishing byte by byte, JRuby loads the last 8 bytes again,
overlapping the previous word, and masks off the lanes it has already done. Strings shorter than 8 bytes are
packed into a long by hand, and the empty lanes are masked too. Those lanes hold zeros, and zero would
match if you searched for the NUL character.
Only copy when something changes
A JRuby string can share its bytes with other strings. The fast path only makes its own copy the first time a
word actually changes, so tr! on a string with nothing to replace never copies anything and returns
nil.
How fast?
For the benchmark in jruby/jruby#9990, strings of
8 to 64 bytes went from 145–230 ns to 90–130 ns. A 16 MB string with nothing to replace went from
7.0 ms to 3.6 ms. CRuby head takes 12.8 ms for the same thing. Several characters at once
(tr('abc', 'xyz')) use the same idea with one pass per character, which only pays off on strings
up to 64 bytes. Past that, the normal lookup table is faster again.
Further reading
- jruby/jruby #10000: the change this page animates (
trTransAsciiLiteralsinRubyString.java). - ruby/ruby #18647: CRuby's SIMD version, for the new
tr(Hash)API. - Needles in a haystack (Kloudfuse): the same zero-byte test, used for log search in Java.
- SWAR in Java: a tiny introduction to the idea.
- SWAR: 8 Bytes at a Time: the companion page, where SWAR does case-mapping for CRuby's
capitalize!. - Knuth, TAOCP Vol. 4A, §7.1.3, and Warren, Hacker's Delight, ch. 6: where these bit tricks come from.
The Ruby that ran this page
The lane values came from the function below: real Ruby, in your browser, via
ruby.wasm, following the Java code line by line.
If WebAssembly can't load, a JavaScript BigInt version does the same math; the badge
up top says which one you got.
Show the in-browser Ruby source