[ruby-core:125637] [Ruby Feature#22094] Speed up Array#join with a byte-copy fast path
Issue #22094 has been reported by yaroslavmarkin (Yaroslav Markin). ---------------------------------------- Feature #22094: Speed up Array#join with a byte-copy fast path https://bugs.ruby-lang.org/issues/22094 * Author: yaroslavmarkin (Yaroslav Markin) * Status: Open ---------------------------------------- ## Original idea What if we treat `Array#join(" ")`, `Array#join("\n")` and `Array#join(";")` as hot paths (as many, if not _most_ uses of `Array#join` in the wild), and see if there is anything to optimize for a single-character ASCII joiner? ## Detailed `rb_ary_join` now works in three steps. ### 1. Measure (one pass) Walk the array once to compute the total length (as before) and, at the same time, track a single flag `ascii_only`—true while every element's code range is `ENC_CODERANGE_7BIT` (and the separator is 7-bit). This is one extra flag read per element. If an element is not a `String`, fall back immediately to the existing `ary_join_0` / `ary_join_1` append path (handles `to_str`, `to_s`, nested arrays, etc.). Everything after this point knows all elements are Strings. ### 2. Decide if the result can be byte-copied A raw copy is correct only when concatenating the bytes needs no encoding negotiation. Two cases qualify: - **All content is 7-bit ASCII** (`ascii_only`). 7-bit bytes are identical under any ASCII-compatible encoding, so the result is simply 7-bit in element 0's encoding. This also covers 7-bit strings in non-UTF-8 encodings such as Shift_JIS/EUC-JP. - **Every element shares one fast-path encoding** (UTF-8 / US-ASCII / ASCII-8BIT — all ASCII-compatible with a 1-byte terminator) **and the separator is compatible** (same encoding, or 7-bit). This is checked in a short second pass that also merges the elements' code ranges. It is reached only when the array is *not* all-7-bit, so the common all-ASCII case never pays for it. This case covers all-UTF-8 text. The merged result code range is: `7BIT` if every part is 7-bit, `VALID` if some part is clean multibyte, or left `UNKNOWN` (recomputed lazily) if any part is itself `UNKNOWN`/`BROKEN`. Same-encoding concatenation makes this merge exact. Anything else—mixed encodings, multibyte Shift_JIS/EUC-JP, an incompatible separator—is not copyable and uses the existing append path. ### 3. Copy Allocate the result once, set its encoding to element 0's, then `memcpy` each separator and element into the buffer through a single cursor. Set the length once and stamp the precomputed code range (or leave it `UNKNOWN`). The output is byte-, encoding-, and code-range-identical to the previous implementation. ## Benchmarks `benchmark/array_join.yml` and `benchmark/array_join_regression.yml`, run with `benchmark-driver --repeat-count 4`; ratio = new i/s ÷ trunk i/s. MacBook Pro M1 (arm64), macOS. `" "` and `"\n"` separators measured identically; one shown. YJIT on shows the same ratios. ### All-String arrays (the target) | array length \ element bytes | 1 | 8 | 40 | |---|---|---|---| | 100 | 2.77x | 2.41x | 1.98x | | 1,000 | 2.91x | 2.52x | 2.21x | | 100,000 | 2.94x | 2.57x | 2.20x | ### Other shapes | case | ratio | |---|---| | no separator (`join`) | 2.48x | | multi-char separator (`", "`) | 2.63x | | frozen string elements | 2.58x | | all-UTF-8 multibyte text | 2.07x | | UTF-8 multibyte separator | 2.18x | | 7-bit Shift_JIS elements | ~5x (trunk uses the slow negotiating path) | | large elements, 256 B / 1 KB / 4 KB | 2.32x / 1.38x / 1.12x | ### Fallback cases (must not regress) | case | ratio | |---|---| | non-String elements (`[1,2,3]`) | 1.00x | | UTF-16 elements | 0.99x | | nested arrays | 1.00x | | Strings then a trailing non-String | 0.98x | ### YJIT on (spot check, all-String, separator `" "`) | case | ratio | |---|---| | n=1,000, 1 B | 2.93x | | n=1,000, 8 B | 2.54x | | n=100,000, 8 B | 2.61x | --- - Patch attached. - Assisted-by: Opus 4.8. ---Files-------------------------------- 0001-Speed-up-Array-join-with-a-byte-copy-fast-path.patch (13.1 KB) -- https://bugs.ruby-lang.org/
Issue #22094 has been updated by byroot (Jean Boussier). Given this is just a performance optimization with no behavior change, there is no need for Matz approval. You'd be better off opening a Pull Request at https://github.com/ruby/ruby/pulls/. ---------------------------------------- Feature #22094: Speed up Array#join with a byte-copy fast path https://bugs.ruby-lang.org/issues/22094#change-117550 * Author: yaroslavmarkin (Yaroslav Markin) * Status: Open ---------------------------------------- ## Original idea What if we treat `Array#join(" ")`, `Array#join("\n")` and `Array#join(";")` as hot paths (as many, if not _most_ uses of `Array#join` in the wild), and see if there is anything to optimize for a single-character ASCII joiner? ## Detailed `rb_ary_join` now works in three steps. ### 1. Measure (one pass) Walk the array once to compute the total length (as before) and, at the same time, track a single flag `ascii_only`—true while every element's code range is `ENC_CODERANGE_7BIT` (and the separator is 7-bit). This is one extra flag read per element. If an element is not a `String`, fall back immediately to the existing `ary_join_0` / `ary_join_1` append path (handles `to_str`, `to_s`, nested arrays, etc.). Everything after this point knows all elements are Strings. ### 2. Decide if the result can be byte-copied A raw copy is correct only when concatenating the bytes needs no encoding negotiation. Two cases qualify: - **All content is 7-bit ASCII** (`ascii_only`). 7-bit bytes are identical under any ASCII-compatible encoding, so the result is simply 7-bit in element 0's encoding. This also covers 7-bit strings in non-UTF-8 encodings such as Shift_JIS/EUC-JP. - **Every element shares one fast-path encoding** (UTF-8 / US-ASCII / ASCII-8BIT — all ASCII-compatible with a 1-byte terminator) **and the separator is compatible** (same encoding, or 7-bit). This is checked in a short second pass that also merges the elements' code ranges. It is reached only when the array is *not* all-7-bit, so the common all-ASCII case never pays for it. This case covers all-UTF-8 text. The merged result code range is: `7BIT` if every part is 7-bit, `VALID` if some part is clean multibyte, or left `UNKNOWN` (recomputed lazily) if any part is itself `UNKNOWN`/`BROKEN`. Same-encoding concatenation makes this merge exact. Anything else—mixed encodings, multibyte Shift_JIS/EUC-JP, an incompatible separator—is not copyable and uses the existing append path. ### 3. Copy Allocate the result once, set its encoding to element 0's, then `memcpy` each separator and element into the buffer through a single cursor. Set the length once and stamp the precomputed code range (or leave it `UNKNOWN`). The output is byte-, encoding-, and code-range-identical to the previous implementation. ## Benchmarks `benchmark/array_join.yml` and `benchmark/array_join_regression.yml`, run with `benchmark-driver --repeat-count 4`; ratio = new i/s ÷ trunk i/s. MacBook Pro M1 (arm64), macOS. `" "` and `"\n"` separators measured identically; one shown. YJIT on shows the same ratios. ### All-String arrays (the target) | array length \ element bytes | 1 | 8 | 40 | |---|---|---|---| | 100 | 2.77x | 2.41x | 1.98x | | 1,000 | 2.91x | 2.52x | 2.21x | | 100,000 | 2.94x | 2.57x | 2.20x | ### Other shapes | case | ratio | |---|---| | no separator (`join`) | 2.48x | | multi-char separator (`", "`) | 2.63x | | frozen string elements | 2.58x | | all-UTF-8 multibyte text | 2.07x | | UTF-8 multibyte separator | 2.18x | | 7-bit Shift_JIS elements | ~5x (trunk uses the slow negotiating path) | | large elements, 256 B / 1 KB / 4 KB | 2.32x / 1.38x / 1.12x | ### Fallback cases (must not regress) | case | ratio | |---|---| | non-String elements (`[1,2,3]`) | 1.00x | | UTF-16 elements | 0.99x | | nested arrays | 1.00x | | Strings then a trailing non-String | 0.98x | ### YJIT on (spot check, all-String, separator `" "`) | case | ratio | |---|---| | n=1,000, 1 B | 2.93x | | n=1,000, 8 B | 2.54x | | n=100,000, 8 B | 2.61x | --- - Patch attached. - Assisted-by: Opus 4.8. ---Files-------------------------------- 0001-Speed-up-Array-join-with-a-byte-copy-fast-path.patch (13.1 KB) -- https://bugs.ruby-lang.org/
Issue #22094 has been updated by hsbt (Hiroshi SHIBATA). FYI: https://github.com/ruby/ruby/pull/17240 ---------------------------------------- Feature #22094: Speed up Array#join with a byte-copy fast path https://bugs.ruby-lang.org/issues/22094#change-117552 * Author: yaroslavmarkin (Yaroslav Markin) * Status: Open ---------------------------------------- ## Original idea What if we treat `Array#join(" ")`, `Array#join("\n")` and `Array#join(";")` as hot paths (as many, if not _most_ uses of `Array#join` in the wild), and see if there is anything to optimize for a single-character ASCII joiner? ## Detailed `rb_ary_join` now works in three steps. ### 1. Measure (one pass) Walk the array once to compute the total length (as before) and, at the same time, track a single flag `ascii_only`—true while every element's code range is `ENC_CODERANGE_7BIT` (and the separator is 7-bit). This is one extra flag read per element. If an element is not a `String`, fall back immediately to the existing `ary_join_0` / `ary_join_1` append path (handles `to_str`, `to_s`, nested arrays, etc.). Everything after this point knows all elements are Strings. ### 2. Decide if the result can be byte-copied A raw copy is correct only when concatenating the bytes needs no encoding negotiation. Two cases qualify: - **All content is 7-bit ASCII** (`ascii_only`). 7-bit bytes are identical under any ASCII-compatible encoding, so the result is simply 7-bit in element 0's encoding. This also covers 7-bit strings in non-UTF-8 encodings such as Shift_JIS/EUC-JP. - **Every element shares one fast-path encoding** (UTF-8 / US-ASCII / ASCII-8BIT — all ASCII-compatible with a 1-byte terminator) **and the separator is compatible** (same encoding, or 7-bit). This is checked in a short second pass that also merges the elements' code ranges. It is reached only when the array is *not* all-7-bit, so the common all-ASCII case never pays for it. This case covers all-UTF-8 text. The merged result code range is: `7BIT` if every part is 7-bit, `VALID` if some part is clean multibyte, or left `UNKNOWN` (recomputed lazily) if any part is itself `UNKNOWN`/`BROKEN`. Same-encoding concatenation makes this merge exact. Anything else—mixed encodings, multibyte Shift_JIS/EUC-JP, an incompatible separator—is not copyable and uses the existing append path. ### 3. Copy Allocate the result once, set its encoding to element 0's, then `memcpy` each separator and element into the buffer through a single cursor. Set the length once and stamp the precomputed code range (or leave it `UNKNOWN`). The output is byte-, encoding-, and code-range-identical to the previous implementation. ## Benchmarks `benchmark/array_join.yml` and `benchmark/array_join_regression.yml`, run with `benchmark-driver --repeat-count 4`; ratio = new i/s ÷ trunk i/s. MacBook Pro M1 (arm64), macOS. `" "` and `"\n"` separators measured identically; one shown. YJIT on shows the same ratios. ### All-String arrays (the target) | array length \ element bytes | 1 | 8 | 40 | |---|---|---|---| | 100 | 2.77x | 2.41x | 1.98x | | 1,000 | 2.91x | 2.52x | 2.21x | | 100,000 | 2.94x | 2.57x | 2.20x | ### Other shapes | case | ratio | |---|---| | no separator (`join`) | 2.48x | | multi-char separator (`", "`) | 2.63x | | frozen string elements | 2.58x | | all-UTF-8 multibyte text | 2.07x | | UTF-8 multibyte separator | 2.18x | | 7-bit Shift_JIS elements | ~5x (trunk uses the slow negotiating path) | | large elements, 256 B / 1 KB / 4 KB | 2.32x / 1.38x / 1.12x | ### Fallback cases (must not regress) | case | ratio | |---|---| | non-String elements (`[1,2,3]`) | 1.00x | | UTF-16 elements | 0.99x | | nested arrays | 1.00x | | Strings then a trailing non-String | 0.98x | ### YJIT on (spot check, all-String, separator `" "`) | case | ratio | |---|---| | n=1,000, 1 B | 2.93x | | n=1,000, 8 B | 2.54x | | n=100,000, 8 B | 2.61x | --- - Patch attached. - Assisted-by: Opus 4.8. ---Files-------------------------------- 0001-Speed-up-Array-join-with-a-byte-copy-fast-path.patch (13.1 KB) -- https://bugs.ruby-lang.org/
Issue #22094 has been updated by byroot (Jean Boussier). Ah thanks, I'll try to find some time to review it. ---------------------------------------- Feature #22094: Speed up Array#join with a byte-copy fast path https://bugs.ruby-lang.org/issues/22094#change-117556 * Author: yaroslavmarkin (Yaroslav Markin) * Status: Open ---------------------------------------- ## Original idea What if we treat `Array#join(" ")`, `Array#join("\n")` and `Array#join(";")` as hot paths (as many, if not _most_ uses of `Array#join` in the wild), and see if there is anything to optimize for a single-character ASCII joiner? ## Detailed `rb_ary_join` now works in three steps. ### 1. Measure (one pass) Walk the array once to compute the total length (as before) and, at the same time, track a single flag `ascii_only`—true while every element's code range is `ENC_CODERANGE_7BIT` (and the separator is 7-bit). This is one extra flag read per element. If an element is not a `String`, fall back immediately to the existing `ary_join_0` / `ary_join_1` append path (handles `to_str`, `to_s`, nested arrays, etc.). Everything after this point knows all elements are Strings. ### 2. Decide if the result can be byte-copied A raw copy is correct only when concatenating the bytes needs no encoding negotiation. Two cases qualify: - **All content is 7-bit ASCII** (`ascii_only`). 7-bit bytes are identical under any ASCII-compatible encoding, so the result is simply 7-bit in element 0's encoding. This also covers 7-bit strings in non-UTF-8 encodings such as Shift_JIS/EUC-JP. - **Every element shares one fast-path encoding** (UTF-8 / US-ASCII / ASCII-8BIT — all ASCII-compatible with a 1-byte terminator) **and the separator is compatible** (same encoding, or 7-bit). This is checked in a short second pass that also merges the elements' code ranges. It is reached only when the array is *not* all-7-bit, so the common all-ASCII case never pays for it. This case covers all-UTF-8 text. The merged result code range is: `7BIT` if every part is 7-bit, `VALID` if some part is clean multibyte, or left `UNKNOWN` (recomputed lazily) if any part is itself `UNKNOWN`/`BROKEN`. Same-encoding concatenation makes this merge exact. Anything else—mixed encodings, multibyte Shift_JIS/EUC-JP, an incompatible separator—is not copyable and uses the existing append path. ### 3. Copy Allocate the result once, set its encoding to element 0's, then `memcpy` each separator and element into the buffer through a single cursor. Set the length once and stamp the precomputed code range (or leave it `UNKNOWN`). The output is byte-, encoding-, and code-range-identical to the previous implementation. ## Benchmarks `benchmark/array_join.yml` and `benchmark/array_join_regression.yml`, run with `benchmark-driver --repeat-count 4`; ratio = new i/s ÷ trunk i/s. MacBook Pro M1 (arm64), macOS. `" "` and `"\n"` separators measured identically; one shown. YJIT on shows the same ratios. ### All-String arrays (the target) | array length \ element bytes | 1 | 8 | 40 | |---|---|---|---| | 100 | 2.77x | 2.41x | 1.98x | | 1,000 | 2.91x | 2.52x | 2.21x | | 100,000 | 2.94x | 2.57x | 2.20x | ### Other shapes | case | ratio | |---|---| | no separator (`join`) | 2.48x | | multi-char separator (`", "`) | 2.63x | | frozen string elements | 2.58x | | all-UTF-8 multibyte text | 2.07x | | UTF-8 multibyte separator | 2.18x | | 7-bit Shift_JIS elements | ~5x (trunk uses the slow negotiating path) | | large elements, 256 B / 1 KB / 4 KB | 2.32x / 1.38x / 1.12x | ### Fallback cases (must not regress) | case | ratio | |---|---| | non-String elements (`[1,2,3]`) | 1.00x | | UTF-16 elements | 0.99x | | nested arrays | 1.00x | | Strings then a trailing non-String | 0.98x | ### YJIT on (spot check, all-String, separator `" "`) | case | ratio | |---|---| | n=1,000, 1 B | 2.93x | | n=1,000, 8 B | 2.54x | | n=100,000, 8 B | 2.61x | --- - Patch attached. - Assisted-by: Opus 4.8. ---Files-------------------------------- 0001-Speed-up-Array-join-with-a-byte-copy-fast-path.patch (13.1 KB) -- https://bugs.ruby-lang.org/
participants (3)
-
byroot (Jean Boussier) -
hsbt (Hiroshi SHIBATA)
-
yaroslavmarkin (Yaroslav Markin)