substr() with replacement slowdown on large strings

[bbrtj]

Description

substr with fourth argument (REPLACEMENT) is slower than alternative ways of doing the same thing. The difference is more pronounced as the size of the string grows.

Test program:

use strict;
use warnings;

use Benchmark::Dumb qw(cmpthese);

my $string = 'SUBSTRdata' x shift;

cmpthese( 200.01, {
    'substr_replace' => sub { my $cpy = $string; substr $cpy, 0, 6, ''; },
    'substr' => sub { my $cpy = substr $string, 6 },
    'regexp' => sub { my $cpy = $string; $cpy =~ s/^SUBSTR//; },
} );

When ran with a small number argument (like 5), both substr and substr_replace are way faster than regexp (around +200%), substr_replace being marginally slower (not unexpected).

Weird things start happening around number 10000 (100 kB string). substr_replace starts to fall off, dropping below the speed of regexp. With argument 1000000 (10 MB string) substr_replace is running at less than half the speed of regexp.

Steps to Reproduce

(see script above)

Expected behavior

I would expect substr_replace case above to keep running at more or less the speed of substr regardless of the input size.

Perl configuration

Summary of my perl5 (revision 5 version 42 subversion 0) configuration:

  Platform:
    osname=linux
    osvers=5.15.161
    archname=x86_64-linux
    uname='linux thinkpad.local 5.15.161 #1 smp preempt sun jun 16 15:55:06 cdt 2024 x86_64 intel(r) core(tm) i7-8650u cpu @ 1.90ghz genuineintel gnulinux '
    config_args='-de -Dprefix=/home/bartosz/perl5/perlbrew/perls/perl-5.42.0 -Duseshrplib -Aeval:scriptdir=/home/bartosz/perl5/perlbrew/perls/perl-5.42.0/bin'
    hint=recommended
    useposix=true
    d_sigaction=define
    useithreads=undef
    usemultiplicity=undef
    use64bitint=define
    use64bitall=define
    uselongdouble=undef
    usemymalloc=n
    default_inc_excludes_dot=define
  Compiler:
    cc='cc'
    ccflags ='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -D_FORTIFY_SOURCE=2'
    optimize='-O2'
    cppflags='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion=''
    gccversion='11.2.0'
    gccosandvers=''
    intsize=4
    longsize=8
    ptrsize=8
    doublesize=8
    byteorder=12345678
    doublekind=3
    d_longlong=define
    longlongsize=8
    d_longdbl=define
    longdblsize=16
    longdblkind=3
    ivtype='long'
    ivsize=8
    nvtype='double'
    nvsize=8
    Off_t='off_t'
    lseeksize=8
    alignbytes=8
    prototype=define
  Linker and Libraries:
    ld='cc'
    ldflags =' -fstack-protector-strong -L/usr/local/lib'
    libpth=/usr/local/lib /usr/lib /lib64 /usr/lib64 /lib /usr/local/lib64
    libs=-lpthread -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc
    perllibs=-lpthread -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.33.so
    so=so
    useshrplib=true
    libperl=libperl.so
    gnulibc_version='2.33'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs
    dlext=so
    d_dlsymun=undef
    ccdlflags='-Wl,-E -Wl,-rpath,/home/bartosz/perl5/perlbrew/perls/perl-5.42.0/lib/5.42.0/x86_64-linux/CORE'
    cccdlflags='-fPIC'
    lddlflags='-shared -O2 -L/usr/local/lib -fstack-protector-strong'


Characteristics of this binary (from libperl):
  Compile-time options:
    HAS_LONG_DOUBLE
    HAS_STRTOLD
    HAS_TIMES
    PERLIO_LAYERS
    PERL_COPY_ON_WRITE
    PERL_DONT_CREATE_GVSV
    PERL_HASH_FUNC_SIPHASH13
    PERL_HASH_USE_SBOX32
    PERL_MALLOC_WRAP
    PERL_OP_PARENT
    PERL_PRESERVE_IVUV
    PERL_USE_SAFE_PUTENV
    USE_64_BIT_ALL
    USE_64_BIT_INT
    USE_LARGE_FILES
    USE_LOCALE
    USE_LOCALE_COLLATE
    USE_LOCALE_CTYPE
    USE_LOCALE_NUMERIC
    USE_LOCALE_TIME
    USE_PERLIO
    USE_PERL_ATOF
  Built under linux
  Compiled at Jul  4 2025 15:22:25
  %ENV:
    PERLBREW_HOME="/home/bartosz/.perlbrew"
    PERLBREW_MANPATH="/home/bartosz/perl5/perlbrew/perls/perl-5.42.0/man"
    PERLBREW_PATH="/home/bartosz/perl5/perlbrew/bin:/home/bartosz/perl5/perlbrew/perls/perl-5.42.0/bin"
    PERLBREW_PERL="perl-5.42.0"
    PERLBREW_ROOT="/home/bartosz/perl5/perlbrew"
    PERLBREW_SHELLRC_VERSION="1.01"
    PERLBREW_VERSION="1.01"
  @INC:
    /home/bartosz/perl5/perlbrew/perls/perl-5.42.0/lib/site_perl/5.42.0/x86_64-linux
    /home/bartosz/perl5/perlbrew/perls/perl-5.42.0/lib/site_perl/5.42.0
    /home/bartosz/perl5/perlbrew/perls/perl-5.42.0/lib/5.42.0/x86_64-linux
    /home/bartosz/perl5/perlbrew/perls/perl-5.42.0/lib/5.42.0

[richardleach]

This might have always been the case, or might be a problem with the OP_SUBSTR_LEFT optimization, which was introduced in the 5.41.x dev cycle. (If the latter, it might boil down to the performance of the OOK mechanism.)

I'll take a look.

[richardleach]

v5.40.1 shows similar behaviour, so OP_SUBSTR_LEFT doesn't seem to have introduced a regression. Will look some more later.

[richardleach]

Possibly what's happening is a 2x string copy in the substr_replace case, courtesy of Perl_sv_backoff. This double copy is plausibly why the longer the string, the more pronounced the effect.

1. After the first iteration of my $cpy = $string;, $cpy is a COW copy of $string. [FLAGS = (POK,IsCOW,pPOK)]
2. After the first substr, $cpy is a full-buffer copy of $string, with the OOK hack applied. [FLAGS = (POK,OOK,pPOK)]
3. At the subsequent iterations of my $cpy = $string, the OOK hack is undone, incurring a full copy of the full buffer less the offset 6 chars. The contents of $string's buffer are then copied into $cpys buffer again. [ FLAGS = (POK,pPOK)]
4. Rinse & repeat steps 2 & 3.

The SvOK_off(dsv) at https://github.com/Perl/perl5/blob/blead/sv.c#L4651C15-L4651C23 triggers the de-OOKing.

That macro is defined as:

#define SvOK_off(sv)		(assert_not_ROK(sv) assert_not_glob(sv)	\
                                 SvFLAGS(sv) &=	~(SVf_OK|		\
                                                  SVf_IVisUV|SVf_UTF8),	\
                                                        SvOOK_off(sv))

With SvOOK_off(sv) being:

#define SvOOK_off(sv)		((void)(SvOOK(sv) && (sv_backoff(sv),0)))

Maybe it's possible for Perl_sv_backoff to only copy the existing buffer contents if SVf_OK is true. I'll give it a go to find out.

[richardleach]

PS This expectation can't be achieved without major work on the interpreter:

Expected behavior

I would expect substr_replace case above to keep running at more or less the speed of substr regardless of the input size.

As currently written, the substr_replace case will do a complete copy of $string on each iteration, whereas the substr case only copies 6 chars on each iteration. The best that we can do currently is try to ensure that substr_replace is only doing one copy, not two!

If the interpreter supported multiple views into a COW string (probably replacing the OOK hack completely) the expected behaviour could be supported, but that's not something we currently have. (The expectation that all strings have a terminating null byte seems a considerable complicating factor to that idea.)

[richardleach]

Maybe it's possible for Perl_sv_backoff to only copy the existing buffer contents if SVf_OK is true.

This might be a good idea in general for the likes of Perl_sv_setsv_flags, but doesn't immediately help this ticket 'cos Perl_sv_backoff is being called here by Perl_leave_scope. Will look at that callsite next.

[bbrtj]

Thanks. I think at the very minimum, substr_replace should never be slower than regexp - is this true if we fix the double copying bug?

[richardleach]

Thanks. I think at the very minimum, substr_replace should never be slower than regexp - is this true if we fix the double copying bug?

Should be. With longer strings, the (1x) copy will dominate both cases and they should end up with similar throughput.