Feature #22463: Improve String#index and line splitting performance on x64-mingw-ucrt

• Status: Open
• Assignee: -
• Target version: -

[watson1978 (Shizuo Fujita)]

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.

#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

[nobu (Nobuyoshi Nakada)]

Why doesn't mingw provide such optimization?

[watson1978 (Shizuo Fujita)]

For desktop UCRT builds, mingw-w64 currently imports memchr rather than providing its own implementation. Its libucrt.a imports the function through api-ms-win-crt-private-l1-1-0.dll, which resolves to ucrtbase.dll on the tested system.

mingw-w64 does already have a musl-derived memchr that scans a machine word at a time. It was added for libucrtapp.a, because UWP apps cannot depend on the private CRT DLL. The motivation and implementation are described in this commit. In my benchmark, that implementation reaches 12.8 GB/s for a 1040-byte buffer, compared with 2.5 GB/s for the UCRT implementation.

I have not found an explanation for why this implementation is not also used in desktop UCRT builds. I can raise this with mingw-w64 and propose using it there.

An upstream fix would also help other applications. Ruby binaries would need to be rebuilt with an updated toolchain to pick it up. Should I pursue the mingw-w64 change first? Or would a Ruby-side replacement also be worth considering?