On 19/08/2026 19:42, Pádraig Brady wrote:
On 14/08/2026 15:08, Iván Rodriguez wrote:Sorry for the noise. I forgot the cover note with v2.Thanks for the rev, you're right. v1 called memchr2() over the whole remaining line on every field lookup. With only multi-byte separators (no SP/TAB) that rescans the suffix each time and is quadratic in the field count. That matches your -f999999 case; -f1 hid it. I also tried bounding memchr2() to each ASCII run (up to the next high bit), and caching the last multi-byte blank sequence as you suggested. Both still leave a quadratic hole on long pure-ASCII lines: computing the ASCII run end walks to EOL on every field. Caching what counts as a separator cheapens the local classification, but does not remove that rescan. So v2 uses a single forward pass for UTF-8 -w: check SP/TAB byte-wise, and mcel_scan/c32issep for high bytes. Each field lookup only examines bytes up to the next delimiter, so the whole line stays O(n). Unibyte locales still use memchr2. Best-of-3 wall times on this host (LC_ALL=C.UTF-8): # your recipe: (a+U+2003)*40000 + b, cut -w -f999999 v1 (suffix memchr2) 0.66s bounded ASCII-run 0.00s v2 (linear) 0.00s master (mb_any) 0.00s # pure ASCII many fields: (a+SP)*500000 + z, cut -w -f250000 v1 0.00s bounded ASCII-run 8.47s v2 (linear) 0.00s master 0.00s # mostly-ASCII ~21MiB, cut -w -f1 master 0.06s v2 0.02sThanks for the update. I had a very quick look again at this. The -f1 win above is mainly due to the existing byte-search routine short circuiting the rest of the line once field selection is exhausted. I.e. it wins with low fields, relative to the length of the line. The changes made to parsing ASCII blanks, and then multi-byte blanks are really a reimplementation of the existing mcel_isblank() (and a little slower in testing). Fundamentally, matching an externally defined set of multi-byte spaces requires per character processing. Munging the two approaches seems a bit awkward. Another approach could be to apply the same short-circuiting optimization to cut_fields_mb_any(), which might be a simpler approach. I originally discounted doing that because I didn't think the use case warranted a narrow optimization like that. But I'll reconsider, and think about this a bit more.
The attached 3 patches optimize the existing cut_fields_mb_any() giving -f1 -w 4x throughput improvement with typical inputs: -- src/cut-before | command | sl | llw | asw | mbw | | --------------- | -------- | -------- | -------- | -------- | | UTF8 -f1 -w | 96.2 ms | 1.916 s | 190.6 ms | 906.5 ms | | UTF8 -f10 -w | 104.6 ms | 1.921 s | 187.7 ms | 845.6 ms | | UTF8 -f100 -w | 104.4 ms | 1.916 s | 187.4 ms | 846.4 ms | -- src/cut-after | command | sl | llw | asw | mbw | | --------------- | -------- | -------- | -------- | -------- | | UTF8 -f1 -w | 88.7 ms | 112.4 ms | 43.5 ms | 146.3 ms | | UTF8 -f10 -w | 95.2 ms | 114.4 ms | 193.5 ms | 848.4 ms | | UTF8 -f100 -w | 94.8 ms | 130.6 ms | 194.4 ms | 848.1 ms | I'll push these later. thanks, Padraig
From 481138141d826efa5b355e76064dab4611c9ab11 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= <[email protected]> Date: Wed, 2 Sep 2026 16:41:48 +0100 Subject: [PATCH 1/3] cut: -w: avoid per character function calls Adding a couple of inlining hints to the compiler gives a 30% boost in raw character processing performance in cut_fields_mb_any(). $ yes $(yes eeeaae | head -n10K | paste -s -d,) | head -n10K > ll.in $ time LC_ALL=C.UTF-8 src/cut-before -f1 -w ll.in >/dev/null real 0m2.279s $ time LC_ALL=C.UTF-8 src/cut-after -f1 -w ll.in >/dev/null real 0m1.619s * src/cut.c (scan_mb_blank_field): Tag as inline. (scan_mb_delim_field): Likewise. --- src/cut.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/cut.c b/src/cut.c index f4973a2c7..c279c8fe7 100644 --- a/src/cut.c +++ b/src/cut.c @@ -497,7 +497,7 @@ append_field_1_bytes (mbbuf_t *mbbuf, mcel_t g, idx_t *n_bytes) append_field_1_chunk (mbbuf_char_offset (mbbuf, g), g.len, n_bytes); } -static enum field_terminator +static inline enum field_terminator scan_mb_blank_field (mbbuf_t *mbbuf, struct mbfield_parser *parser, bool *have_pending_line, bool write_field, idx_t *n_bytes) @@ -534,7 +534,7 @@ scan_mb_blank_field (mbbuf_t *mbbuf, struct mbfield_parser *parser, } } -static enum field_terminator +static inline enum field_terminator scan_mb_delim_field (mbbuf_t *mbbuf, bool *have_pending_line, bool write_field, idx_t *n_bytes) { -- 2.55.0
From 45161357566cbd8c2a13dc9568e50c33073e7bd9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= <[email protected]> Date: Sat, 22 Aug 2026 15:57:53 +0100 Subject: [PATCH 2/3] cut: -w: optimize extracting the start of a line MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit There were no significant performance changes from the test cases in commit a325c9978, but adding additional whitespace delimited cases shows significant improvement. Below, with -f1, typical space delimited input shows 4x more throughput, while the long line test shows 17x more. Performance was tested with GCC 16 on an i7-5600U with CFLAGS='-march=native -O3 -flto' with the following setup: $ yes | head -n10M > sl.in $ yes $(yes eeeaae | head -n10K | paste -s -d' ') | head -n10K > llw.in $ yes $(yes eeeaae | head -n9 | paste -s -d' ') | head -n1M > asw.in $ yes $(yes éééááé | head -n9 | paste -s -d$'\xe2\x80\x83') | head -n1M > mbw.in for type in sl llw asw mbw; do cat $type.in >/dev/null; for imp in '-before' '-after'; do echo ============ "${imp:-base}" $type ==============; for d in -w; do fields='-f1 -f10 -f100' test "$d" = "-b" && { fields='-b1 -b10 -b100'; d=''; } test "$d" = "-c" && { fields='-c1 -c10 -c100'; d=''; } for f in $fields; do for loc in C.UTF-8; do # Skip -b for UTF-8 as no different test "$loc" = C.UTF-8 && echo "$f" | grep -q -- -b \ && continue # Skip multi-byte delimiter for C and not allowed test "$loc" = C && test $(echo -n "$d" | wc -c) -ge 4 \ && continue bin=src/cut${imp} LC_ALL=$loc $bin $f $d /dev/null 2>/dev/null && hyperfine --warmup=2 -m2 -M6 \ "LC_ALL=$loc $bin $f $d $type.in >/dev/null" || printf 'Benchmark 1: %s\n unsupported\n\n' \ "LC_ALL=$loc $bin $f $d $type.in >/dev/null" done; done; done; done; done After a little post-processing of the results, we get: -- src/cut-before | command | sl | llw | asw | mbw | | --------------- | -------- | -------- | -------- | -------- | | UTF8 -f1 -w | 96.2 ms | 1.916 s | 190.6 ms | 906.5 ms | | UTF8 -f10 -w | 104.6 ms | 1.921 s | 187.7 ms | 845.6 ms | | UTF8 -f100 -w | 104.4 ms | 1.916 s | 187.4 ms | 846.4 ms | -- src/cut-after | command | sl | llw | asw | mbw | | --------------- | -------- | -------- | -------- | -------- | | UTF8 -f1 -w | 88.7 ms | 112.4 ms | 43.5 ms | 146.3 ms | | UTF8 -f10 -w | 95.2 ms | 114.4 ms | 193.5 ms | 848.4 ms | | UTF8 -f100 -w | 94.8 ms | 130.6 ms | 194.4 ms | 848.1 ms | * src/cut.c (scan_mb_line_end): A new function to skip to EOL once we have exhausted the field selection. (cut_fields_mb_any): Only skip after recognizing a field delimiter. * tests/cut/cut.pl: Add test cases. * tests/cut/mb-non-utf8.sh: Likewise. * NEWS: Mention the improvement. --- NEWS | 3 ++ src/cut.c | 84 +++++++++++++++++++++++++++++----------- tests/cut/cut.pl | 13 +++++++ tests/cut/mb-non-utf8.sh | 7 ++++ 4 files changed, 85 insertions(+), 22 deletions(-) diff --git a/NEWS b/NEWS index cc9bcf248..966683dc7 100644 --- a/NEWS +++ b/NEWS @@ -131,6 +131,9 @@ GNU coreutils NEWS -*- outline -*- 'who /var/log/wtmp' and 'users /var/log/wtmp' use the wtmpdb database instead of the file /var/log/wtmp. This makes them Y2038-safe. + 'cut -w' operates more efficiently when extracting the start of a line + in multi-byte locales, giving up to 4x more throughput with typical input. + 'df', 'du', 'ls', 'od', 'pr', and 'sort' now escape invalid arguments in error messages for options expecting an integer. diff --git a/src/cut.c b/src/cut.c index c279c8fe7..b5a5eb7cf 100644 --- a/src/cut.c +++ b/src/cut.c @@ -570,6 +570,41 @@ scan_mb_field (mbbuf_t *mbbuf, struct mbfield_parser *parser, n_bytes)); } +/* Skip input through the next line delimiter without decoding characters. + PARSER may have saved a character beyond a whitespace delimiter. */ + +static enum field_terminator +scan_mb_line_end (mbbuf_t *mbbuf, struct mbfield_parser *parser, + bool *have_pending_line) +{ + if (parser->have_saved) + { + parser->have_saved = false; + if (parser->saved_g.ch == MBBUF_EOF) + return FIELD_EOF; + + *have_pending_line = true; + if (parser->saved_g.ch == line_delim) + return FIELD_LINE_DELIMITER; + } + + while (true) + { + idx_t available = mbbuf_topup (mbbuf); + if (available == 0) + return FIELD_EOF; + + char *buffer = mbbuf->buffer + mbbuf->offset; + char *line_end = search_bytes (buffer, line_delim, available); + idx_t n = line_end ? line_end - buffer + 1 : available; + mbbuf_advance (mbbuf, n); + *have_pending_line = true; + + if (line_end) + return FIELD_LINE_DELIMITER; + } +} + /* Return a pointer to the next field delimiter in BUF, searching LEN bytes. Return NULL if none is found. DELIM_BYTES must be a single byte or represent a valid UTF-8 character. BUF can contain invalid/NUL bytes, @@ -960,12 +995,12 @@ cut_fields_mb_any (FILE *stream, bool whitespace_mode) while (true) { + enum field_terminator terminator; if (field_idx == 1 && buffer_first_field) { idx_t n_bytes = 0; - enum field_terminator terminator - = scan_mb_field (&mbbuf, &parser, &have_pending_line, false, - &n_bytes); + terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, + false, &n_bytes); if (terminator == FIELD_EOF && n_bytes == 0) return; @@ -990,31 +1025,36 @@ cut_fields_mb_any (FILE *stream, bool whitespace_mode) write_bytes (field_1_buffer, n_bytes); found_any_selected_field = true; } - next_item (&field_idx); } - - enum field_terminator terminator; - bool write_field = begin_field_output (field_idx, buffer_first_field, - &found_any_selected_field); - - terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, - write_field, NULL); + else + { + bool write_field + = begin_field_output (field_idx, buffer_first_field, + &found_any_selected_field); + terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, + write_field, NULL); + } if (terminator == FIELD_DELIMITER) - next_item (&field_idx); - else { - if (terminator == FIELD_EOF && !have_pending_line) - break; - if (found_any_selected_field - || !(suppress_non_delimited && field_idx == 1)) - write_line_delim (); - if (terminator == FIELD_EOF) - break; + next_item (&field_idx); + if (! field_selection_exhausted (field_idx)) + continue; - reset_field_line (&field_idx, &found_any_selected_field, - &have_pending_line, &parser); + terminator = scan_mb_line_end (&mbbuf, &parser, + &have_pending_line); } + + if (terminator == FIELD_EOF && !have_pending_line) + break; + if (found_any_selected_field + || !(suppress_non_delimited && field_idx == 1)) + write_line_delim (); + if (terminator == FIELD_EOF) + break; + + reset_field_line (&field_idx, &found_any_selected_field, + &have_pending_line, &parser); } } diff --git a/tests/cut/cut.pl b/tests/cut/cut.pl index 7e4a7ef80..c0c962ea0 100755 --- a/tests/cut/cut.pl +++ b/tests/cut/cut.pl @@ -425,6 +425,19 @@ if ($mb_locale ne 'C') {OUT=>"\xc3\xa9\t\xc3\xbc\n"}, {ENV => "LC_ALL=$mb_locale"}], + # Stop decoding fields once the finite selection is exhausted. + ['mb-w-exhausted-1', '-w', '-f1', + {IN=>"a\xe2\x80\x83ignored\nb\xe2\x80\x83ignored"}, + {OUT=>"a\nb\n"}, {ENV => "LC_ALL=$mb_locale"}], + ['mb-w-exhausted-2', '-w', '-f1', {IN=>"a \nb "}, + {OUT=>"a\nb\n"}, {ENV => "LC_ALL=$mb_locale"}], + ['mb-w-exhausted-initial', '-s', '-w', '--complement', '-f1-', + {IN=>"a\xe2\x80\x83ignored\nplain"}, {OUT=>"\n"}, + {ENV => "LC_ALL=$mb_locale"}], + ['mb-delim-exhausted', '-d', "\xa9", '-f1', + {IN=>"A\xc3\xa9B\xa9ignored\nC\xa9ignored"}, + {OUT=>"A\xc3\xa9B\nC\n"}, {ENV => "LC_ALL=$mb_locale"}], + # -b -n with output delimiter ['mb-bn-odelim', qw(-b1,3 -n), '--output-d=:', {IN=>"\xc3\xa9x\n"}, {OUT=>"x\n"}, diff --git a/tests/cut/mb-non-utf8.sh b/tests/cut/mb-non-utf8.sh index 896018a12..c381cdce5 100755 --- a/tests/cut/mb-non-utf8.sh +++ b/tests/cut/mb-non-utf8.sh @@ -35,6 +35,13 @@ for delim in ',' ':' "$delim_gb18030" "$delim_ff"; do test "$num_out" = "2_3" || fail=1 done +# Check skipping to the line end after a finite field selection. +printf '1%s2%s3\n4%s5' "$delim_gb18030" "$delim_gb18030" \ + "$delim_gb18030" \ + | cut -d "$delim_gb18030" -f1 > out || fail=1 +printf '1\n4\n' > exp || framework_failure_ +compare exp out || fail=1 + # A valid 2-byte GB18030 character. printf '%sx\n' "$delim_gb18030" | cut -c1 > out || fail=1 printf '%s\n' "$delim_gb18030" > exp || framework_failure_ -- 2.55.0
From a860041a1ac8d3d999781ffe469dffc9c6312c48 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= <[email protected]> Date: Sat, 22 Aug 2026 19:42:12 +0100 Subject: [PATCH 3/3] cut: simplify multi-byte field processing Simplify cut_fields_mb_any() used with: -w in a multi-byte locale, including UTF-8 --w=trimmed in any locale, including C -f -d CHAR in non utf-8 multi-byte locale -f -d CHAR in utf-8 with certain invalid CHARs This is a net reducation of 24 lines, and is performance neutral. (cut_fields_mb_any): Use persistent first field and output state. This allows using the existing field output helpers and avoiding separate first field and line completion handling. (cut_fields_bytesearch): Handle blanks explicitly. (finish_current_line): Remove redundant condition. --- src/cut.c | 76 +++++++++++++++++++------------------------------------ 1 file changed, 26 insertions(+), 50 deletions(-) diff --git a/src/cut.c b/src/cut.c index b5a5eb7cf..cc85a6927 100644 --- a/src/cut.c +++ b/src/cut.c @@ -771,8 +771,7 @@ handle_field_1 (uintmax_t field_idx, bool buffer_first_field, static inline void handle_field_delimiter (uintmax_t *field_idx, bool buffer_first_field, idx_t *field_1_n_bytes, - bool *found_any_selected_field, bool *write_field, - bool blank_delimited, bool *skip_blank_run) + bool *found_any_selected_field, bool *write_field) { if (handle_field_1 (*field_idx, buffer_first_field, field_1_n_bytes)) *found_any_selected_field = true; @@ -780,8 +779,6 @@ handle_field_delimiter (uintmax_t *field_idx, bool buffer_first_field, next_item (field_idx); *write_field = begin_field_output (*field_idx, buffer_first_field, found_any_selected_field); - if (blank_delimited) - *skip_blank_run = true; } static inline bool @@ -805,7 +802,7 @@ finish_current_line (uintmax_t field_idx, bool buffer_first_field, } *field_1_n_bytes = 0; } - else if (field_idx != 1 || found_any_selected_field) + else maybe_write_line_delim (found_any_selected_field, field_idx); } @@ -987,57 +984,31 @@ cut_fields_mb_any (FILE *stream, bool whitespace_mode) bool found_any_selected_field = false; bool buffer_first_field; bool have_pending_line = false; + bool write_field; + idx_t field_1_n_bytes = 0; current_rp = frp; mbbuf_init (&mbbuf, bytes_in, sizeof bytes_in, stream); buffer_first_field = (suppress_non_delimited ^ !print_kth (1)); + write_field = begin_field_output (field_idx, buffer_first_field, + &found_any_selected_field); while (true) { enum field_terminator terminator; - if (field_idx == 1 && buffer_first_field) - { - idx_t n_bytes = 0; - terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, - false, &n_bytes); - if (terminator == FIELD_EOF && n_bytes == 0) - return; - - if (terminator != FIELD_DELIMITER) - { - if (!suppress_non_delimited) - { - write_bytes (field_1_buffer, n_bytes); - write_line_delim (); - } - - if (terminator == FIELD_EOF) - break; - - reset_field_line (&field_idx, &found_any_selected_field, - &have_pending_line, &parser); - continue; - } - - if (print_kth (1)) - { - write_bytes (field_1_buffer, n_bytes); - found_any_selected_field = true; - } - } + if (!buffer_first_field || field_idx != 1) + terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, + write_field, NULL); else - { - bool write_field - = begin_field_output (field_idx, buffer_first_field, - &found_any_selected_field); - terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, - write_field, NULL); - } + terminator = scan_mb_field (&mbbuf, &parser, &have_pending_line, + false, &field_1_n_bytes); if (terminator == FIELD_DELIMITER) { - next_item (&field_idx); + handle_field_delimiter (&field_idx, buffer_first_field, + &field_1_n_bytes, + &found_any_selected_field, &write_field); if (! field_selection_exhausted (field_idx)) continue; @@ -1047,14 +1018,17 @@ cut_fields_mb_any (FILE *stream, bool whitespace_mode) if (terminator == FIELD_EOF && !have_pending_line) break; - if (found_any_selected_field - || !(suppress_non_delimited && field_idx == 1)) - write_line_delim (); + + finish_current_line (field_idx, buffer_first_field, + &field_1_n_bytes, found_any_selected_field, + terminator == FIELD_LINE_DELIMITER); if (terminator == FIELD_EOF) break; reset_field_line (&field_idx, &found_any_selected_field, &have_pending_line, &parser); + write_field = begin_field_output (field_idx, buffer_first_field, + &found_any_selected_field); } } @@ -1114,8 +1088,9 @@ cut_fields_bytesearch (FILE *stream) handle_field_delimiter (&field_idx, buffer_first_field, &field_1_n_bytes, - &found_any_selected_field, &write_field, - whitespace_delimited, &skip_blank_run); + &found_any_selected_field, &write_field); + if (whitespace_delimited) + skip_blank_run = true; } if (n_avail == 0) @@ -1227,8 +1202,9 @@ cut_fields_bytesearch (FILE *stream) processed += whitespace_delimited ? 1 : delim_mcel.len; handle_field_delimiter (&field_idx, buffer_first_field, &field_1_n_bytes, - &found_any_selected_field, &write_field, - whitespace_delimited, &skip_blank_run); + &found_any_selected_field, &write_field); + if (whitespace_delimited) + skip_blank_run = true; } else { -- 2.55.0
