bug#81620: [PATCH v2] cut: speed up -w in UTF-8 locales

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.02s
Thanks 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.

BTW if you know the data will only have ASCII spacing,
one can use LC_ALL=C to get the performant byte-search.
It's probably worth mentioning that in the texinfo.
I'll do that now with:

diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 90c2dfcd6..9bd842569 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -6258,6 +6258,9 @@ With @option{-f}, separate fields with a run of blank cha>
  (usually space or TAB).  With @samp{trimmed} do not consider
  leading and trailing blanks as field separators.
  @option{-w} is implied with the @option{-F} option.
+If runs of only ASCII blank characters (space or TAB) are used to separate
+fields, you can improve efficiency by only searching for those characters
+by invoking @command{cut} like @samp{LC_ALL=C cut}.


cheers,
Padraig