Issue #22463 has been reported by watson1978 (Shizuo Fujita). ---------------------------------------- Feature #22463: Improve String#index and line splitting performance on x64-mingw-ucrt https://bugs.ruby-lang.org/issues/22463 * Author: watson1978 (Shizuo Fujita) * Status: Open ---------------------------------------- ## Summary On x64-mingw-ucrt, `memchr` comes from `ucrtbase.dll`. On the tested system, it is a byte-by-byte loop and runs at about 2.5 GB/s, the same speed as a plain byte loop. Ruby calls `memchr` for single-byte searches, so `String#index`, `String#each_line` and `IO#gets` are slower than they need to be on this platform. When only `memchr` is replaced on the same machine, `String#index("\n")` over 1 KB lines becomes 3.1x (SWAR) to 4.2x (SSE2) faster. We found this while profiling Fluentd's in_tail plugin on Windows with rbspy. `String#index`, which splits lines there, took about 6% of the samples. ## Environment * ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [x64-mingw-ucrt] (RubyInstaller 4.0.7-1) * Windows 10 (10.0.19045.6466), ucrtbase.dll 10.0.19041.3636 * AMD Ryzen 9 8945HS (virtual machine) * GCC 16.2.0 and mingw-w64-crt 14.0.0 from MSYS2 UCRT64 ## Where Ruby calls memchr * `rb_memsearch` in re.c calls `memchr` for a 1-byte pattern. For short patterns, `rb_memsearch_ss` also uses `memchr` to find the first byte. This is used by `String#index`, `String#byteindex` and `String#each_line`. * `rb_io_getline_fast` and `search_delim` in io.c call `memchr`. This is used by `IO#gets` and `IO#each_line`. ## memchr in ucrtbase.dll In ucrtbase.dll 10.0.19041.3636, `memchr` is a 28-byte function. It compares one byte per iteration and uses no vector registers (checked with `objdump -d`). We have not checked newer versions of ucrtbase.dll. Other string and memory functions that Ruby imports from the same DLL are much faster. These numbers are for 1040 bytes with the target at the end (crt_funcs_bench.c): | function | ucrtbase.dll | vcruntime140.dll | | -- | --: | --: | | `memchr` | 2.5 GB/s | 31.8 GB/s | | `strcmp` | 9.7 GB/s | not exported | | `strncmp` | 10.1 GB/s | not exported | | `strlen` | 18.1 GB/s | not exported | | `strstr` | 19.4 GB/s | 19.4 GB/s | | `strrchr` | 26.3 GB/s | 26.5 GB/s | | `strchr` | 26.4 GB/s | 26.4 GB/s | | `memcmp` | 37.1 GB/s | 36.9 GB/s | | `strnlen` | 38.1 GB/s | not exported | | `wcslen` | 62.9 GB/s | not exported | | `memmove` | 85.9 GB/s | 108.5 GB/s | | `memcpy` | 86.2 GB/s | 106.1 GB/s | | `memset` | 92.4 GB/s | 156.2 GB/s | A plain byte loop runs at about 2.5 GB/s on this machine. Only `memchr` is at that level, so we propose replacing only `memchr`. `__builtin_memchr` does not help. With non-constant arguments, GCC emits a jump to the library `memchr`. ## memchr implementations in C (same machine) The target byte is at the last position of the buffer. | implementation | 1040 bytes | 1 MB | | -- | --: | --: | | ucrtbase.dll `memchr` | 2.5 GB/s | 2.6 GB/s | | msvcrt.dll `memchr` | 2.5 GB/s | 2.6 GB/s | | plain byte loop (`gcc -O2` or `-O3`) | 2.5 GB/s | 2.6 GB/s | | SWAR, 8 bytes per step | 13.4 GB/s | 13.7 GB/s | | SSE2, 16 bytes per step | 26.8 GB/s | 27.3 GB/s | | SSE2, 64 bytes per step | 58.8 GB/s | 65.6 GB/s | | vcruntime140.dll `memchr` | 31.8 GB/s | 37.2 GB/s | Short inputs and early matches, in nanoseconds per call: | case | ucrtbase.dll | SWAR | SSE2, 16 bytes per step | | -- | --: | --: | --: | | n=1, match | 0.98 | 1.76 | 1.22 | | n=7, match at the end | 3.31 | 3.89 | 3.69 | | n=15, match at the end | 6.47 | 4.85 | 6.81 | | n=1040, match at offset 0 | 1.56 | 2.14 | 1.95 | | n=16, no match | 7.01 | 2.92 | 1.96 | | n=64, no match | 30.18 | 6.42 | 3.70 | | n=1040, no match | 410.09 | 77.81 | 39.40 | The replacements are up to 0.8 ns slower per call when the input is very short or the match is at the start. In the 16-byte-line benchmark below, each iteration takes about 80 ns, including the loop and argument handling. We observed no slowdown in that benchmark. ## Ruby-level effect (same machine, only memchr replaced) To change only `memchr`, we rewrote the `memchr` entry in the import address table of x64-ucrt-ruby400.dll at runtime with Fiddle. "SSE2" here is the 16-bytes-per-step version. Regexp search and `IO#read` do not use `memchr`, so they are shown as controls. | operation | ucrtbase.dll (as is) | SWAR | SSE2 | | -- | --: | --: | --: | | `String#index("\n")`, 64 MB of 1 KB lines | 2.11 GB/s | 6.61 GB/s | 8.93 GB/s | | `String#index("\n")`, 64 MB of 16 B lines | 0.20 GB/s | 0.22 GB/s | 0.22 GB/s | | `String#index("z")`, 64 MB, no match | 2.57 GB/s | 13.40 GB/s | 26.72 GB/s | | `String#each_line`, 64 MB of 1 KB lines | 1.36 GB/s | 2.44 GB/s | 2.60 GB/s | | `IO#each_line`, 256 MB file of 1 KB lines | 0.69 GB/s | 0.87 GB/s | 0.90 GB/s | | `String#index(/\n/)`, 64 MB of 1 KB lines (control) | 1.77 GB/s | 1.77 GB/s | 1.77 GB/s | | `IO#read` in 1 MB chunks, 256 MB file (control) | 8.12 GB/s | 7.91 GB/s | 8.13 GB/s | ## How to reproduce The attached files were built with GCC from MSYS2 UCRT64. C benchmarks: ``` gcc -O2 -Wall -o memchr_swar.exe memchr_swar.c memchr_swar.exe gcc -O2 -Wall -fno-builtin -o crt_funcs_bench.exe crt_funcs_bench.c crt_funcs_bench.exe ``` * memchr_swar.c first checks every implementation against a plain loop on 200,000 random inputs. Each throughput cell repeats calls on the same buffer until 512 MB is scanned. Each edge case runs 20,000,000 calls. Each value is a single run. * crt_funcs_bench.c loads each function from each DLL with `GetProcAddress`. Each cell scans 256 MB in total, and every result is checked. Ruby benchmark: ``` gcc -O2 -Wall -shared -o fastmemchr.dll fastmemchr.c set MEMCHR=ucrt ruby -r ./patch_memchr.rb ruby_level.rb set MEMCHR=swar ruby -r ./patch_memchr.rb ruby_level.rb set MEMCHR=sse2 ruby -r ./patch_memchr.rb ruby_level.rb ``` * patch_memchr.rb does nothing for `MEMCHR=ucrt`. Otherwise it points the `memchr` import of x64-ucrt-ruby400.dll to the function in fastmemchr.dll. It reads the import slot back to check that it now points to the new function, and it raises if no `memchr` import is found. It also checks that `String#index` and `String#each_line` still return correct results. * All strings are ASCII-8BIT. The 256 MB file is created in a new temporary directory (`Dir.mktmpdir`), which is removed at the end. The file is written and read in binary mode (`"rb"`), and it is read once before measuring to warm the page cache. * The `String#index("\n")` rows call `s.index("\n", pos + 1)` repeatedly until it returns nil, so every line is visited. The "no match" row is a single call over the whole string. * String operations use a 64 MB string. IO operations use a 256 MB file. * Each value is the best of 3 runs. ## Proposal Use our own `memchr` on x64-mingw-ucrt. We have only measured this platform, so we suggest limiting the change to it at first. * SSE2 is always available on x86-64, so an SSE2 version needs no runtime check. It is the fastest option we measured. * A SWAR version does not use SIMD intrinsics. It is slower than SSE2. The version below assumes a little-endian target and uses `__builtin_ctzll` from GCC and Clang. ```c #define ONES UINT64_C(0x0101010101010101) #define HIGHS UINT64_C(0x8080808080808080) #define HASZERO(x) (((x) - ONES) & ~(x) & HIGHS) /* little-endian only; __builtin_ctzll is a GCC/Clang builtin */ static void * swar_memchr(const void *s, int c, size_t n) { const unsigned char *p = s; uint64_t k = ONES * (unsigned char)c; while (n >= 8) { uint64_t v; memcpy(&v, p, 8); uint64_t m = HASZERO(v ^ k); if (m) return (void *)(p + (__builtin_ctzll(m) >> 3)); p += 8; n -= 8; } for (; n; p++, n--) { if (*p == (unsigned char)c) return (void *)p; } return NULL; } ``` include/ruby/win32.h already maps many CRT functions to `rb_w32_*` replacements, so this would follow an existing pattern. string.c also has a fallback `memrchr` (#20709), but that one is for platforms without the function. This proposal replaces an existing CRT function for performance, so the reason is different. Another option is to link `memchr` from vcruntime140.dll. MSYS2 ships `libvcruntime140.a`, and linking with `-lvcruntime140` worked in our test. However, vcruntime140.dll is not part of Windows, so it would have to be shipped with Ruby. We have not checked mswin builds. They link vcruntime140.dll, so they probably use its faster `memchr`. We have not measured aarch64-mingw-ucrt either. ## Attachments * memchr_swar.c: compares memchr implementations, including short inputs and early matches * crt_funcs_bench.c: compares CRT string and memory functions per DLL * fastmemchr.c: SWAR and SSE2 versions built as a DLL for patch_memchr.rb * patch_memchr.rb: replaces the `memchr` import of the Ruby DLL at runtime * ruby_level.rb: Ruby-level benchmark ---Files-------------------------------- fastmemchr.c (1.01 KB) memchr_swar.c (6.09 KB) patch_memchr.rb (2.5 KB) ruby_level.rb (1.31 KB) crt_funcs_bench.c (4.32 KB) -- https://bugs.ruby-lang.org/