
<!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><p dir="auto" style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;text-wrap-mode:wrap;word-spacing:0px;-webkit-text-stroke-width:0px;text-decoration-line:none;box-sizing:border-box;margin-bottom:16px;color:rgb(31, 35, 40);font-family:-apple-system, BlinkMacSystemFont, "Segoe UI", "Noto Sans", Helvetica, Arial, sans-serif, "Apple Color Emoji", "Segoe UI Emoji";font-size:14px;-webkit-text-size-adjust:100%;margin-top:0px !important;">When parsing strings with SIMD instructions, vectorized table lookup like vtbl (ARM NEON) are important. They are cheap (often run in 1 cycle) and powerful.<br></p><div><br></div><div>Though the details depend on the exact instruction set, the general idea is that you provide a 16-byte table, and a vector with indexes. If the indexes are in the range [0,16), then the byte is retrieved from the 16-byte table. When programming in C#, you can call them directly: e.g., Ssse3.Shuffle or AdvSimd.Arm64.VectorTableLookup. Google relies on Highway (a C++ framework) which offers TableLookupBytes for this purpose.<br></div><div><br></div><div>You can use these instructions to validate and transcode Unicode, to parse DNS records, faster regular expression parsers, base64 codecs, cryptographic hash functions and so forth. The applications are almost endless (see reference at the end). These instructions are effectively ubiquitous in 2024. On x64 systems, SSSE3 and its pshufb instruction (equivalent to ARM's vtbl) are increasingly assumed as a requirement (Windows 11, RedHat, etc.). For example, it is used in Chromium (arguably the most important Web engine) to parse HTML quickly:<br></div><div><a href="https://chromium-review.googlesource.com/c/chromium/src/+/5538407">https://chromium-review.googlesource.com/c/chromium/src/+/5538407</a><br></div><div><br></div><div>The .NET runtime uses these instructions, calling them from C#: E.g., see their base64 encoder... (System/Buffers/Text/Base64Decoder.cs) In C#, we see fast tokenizers and parsers making use of these instructions.<br></div><div><br></div><div>Unfortunately, the Vector API in Java has no equivalent.<br></div><div><br></div><div>It may seem lie rearrange and selectFrom are related, but these are not vectorized lookups. And once compiled, they generate a long flow of instructions. It provides the same functionality, but without the performance. And, of course, the performance is the whole point of using something like the Vector API.<br></div><div><br></div><div>Overall, this lack of access to an important functionality simply cuts off important algorithmic optimizations from Java.</div><div><br></div><div><br></div><div><br></div><div>- Daniel<br></div><div><br></div><div><br></div><div>---<br></div><div>References:<br></div><div><br></div><div><br></div><div>Transcoding Billions of Unicode Characters per Second with SIMD Instructions<br></div><div>Software: Practice and Experience 52 (2), 2022<br></div><div><a href="https://arxiv.org/abs/2109.10433">https://arxiv.org/abs/2109.10433</a><br></div><div><br></div><div>Validating UTF-8 In Less Than One Instruction Per Byte<br></div><div>Software: Practice and Experience 51 (5), 2021<br></div><div><a href="https://arxiv.org/abs/2010.03090">https://arxiv.org/abs/2010.03090</a><br></div><div><br></div><div>Faster Base64 Encoding and Decoding using AVX2 Instructions<br></div><div>ACM Transactions on the Web 12 (3), 2018<br></div><div><a href="https://arxiv.org/abs/1704.00605">https://arxiv.org/abs/1704.00605</a><br></div><div><br></div><div>Parsing Gigabytes of JSON per Second<br></div><div>VLDB Journal 28 (6), 2019<br></div><div><a href="https://arxiv.org/abs/1902.08318">https://arxiv.org/abs/1902.08318</a><br></div><div><br></div><div><br></div><div><br></div><div><br></div></body></html>