perl5 'OFFSET' optimization for s/^...// no longer applied

Preliminary note

In a conversation with @demerphq a while ago it was observed that s/^...// is no longer optimized with 'recent' perls. I've decided to take a look at why and the results you can find below.

Personally I don't care about the optimization, I'm however creating the issue to document what happened to it (just in case someone is). (As far as I'm concerned this can be closed as WON'T FIX)

Description

When removing characters from the beginning of a string there is an optimization. This can be seen for example with:

    #!/usr/bin/perl

    use Devel::Peek;
    my $x = join("", "a".."z", "A".."Z");
    substr($x, 0, 7, "");
    Dump($x);

    __END__

    SV = PV(0x606b60) at 0x622b70
      REFCNT = 1
      FLAGS = (PADMY,POK,OOK,pPOK)
      OFFSET = 7
      PV = 0x61b847 ( "abcdef\7" . ) "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"\0
      CUR = 45
      LEN = 47

Rather then copy'ing/moving the PV it sets the 'OFFSET' flag[^1].

That same optimization was at one point also done when using s///;

Example:

    #!/usr/bin/perl

    use Devel::Peek;
    my $x = join("", "a".."z", "A".."Z");
    $x =~ s/^.{7}//;
    Dump($x);

Output on perl v5.18.4:

    SV = PV(0x55b62051d118) at 0x55b6204b8180
      REFCNT = 1
      FLAGS = (PADMY,POK,OOK,pPOK)
      OFFSET = 7
      PV = 0x55b620450b47 ( "abcdef\7" . ) "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"\0
      CUR = 45
      LEN = 57

Output on perl v5.20.0 (same output on blead):

    SV = PV(0x55f538dd3f68) at 0x55f538dd6308
      REFCNT = 1
      FLAGS = (PADMY,POK,pPOK)
      PV = 0x55f538d789a0 "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"\0
      CUR = 45
      LEN = 48

[^1]: It appears it also modified the PV value: 'g' was replaced with '\7', I didn't investigate why)

Jul 24 '22 12:07 bram-perl

Bisecting this proved to be a bit tricky because the behaviour flip-flopped a couple of times and is influenced by two things.

Results from bisecting:

    * blead                                     = Optimization not in use
    * ...
    * 13b0f67d12a6400f01bbc27945223ca68a12a7ef  = Optimization not in use  (re-enable Copy-on-Write by default.)
    * 13d1b68a2ea5e2239b9c86d7059e575e9dfd82c7  = Optimization in use      (typo fixes for Unicode UCD)
    * ...
    * 9f351b45f43b0ed78a9b796af692ef90a6d23879  = Optimization in use      ('Disable by default the new Copy-on-Write for 5.18')
    * 126fc07f46caef8f4f9866ac6a1ebaa9456995f4  = Optimization not in use  (Synchronise Env with CPAN)
    * ...
    * cd298ce42eb3c82a651608c3fbd658ec616b0297  = Optimization not in use  ([Merge] New COW mechanism)
    |\
    | * f5a0fd1e07ceb4866d2eee4eb9283498cd3ef1be = Optimization not in use    (Don't share TARGs between recursive ops)
    | * e1b145039d15f6202e21cd23abb95117153eb816 = Optimization not in use    (subst.t: Test something I nearly broke)
    | * d78f32f607952d58a998c5b7554572320dc57b2a = Optimization not in use    (Update docs to concur with $`,$&,$' changes)
    | * 20961b6483f3653e3bf928a60cca828e2b13e098 = Optimization not in use    (Increase $English::VERSION to 1.06)
    | * 3b5bc0ddfbcdd17ef47d61fbce7a265b219a5889 = Optimization not in use    (English.pm: Update -no_match_vars docs)
    | * 00f6437b30bbbd24904cbecfa1c00ab91f7315e5 = Optimization not in use    (Test perl #4289)
    | * aaee23ae9c2dfc4e671dcc6a11a59f9baf00f533 = Optimization not in use    (test_bootstrap.t: Skip PL_sawampersand tests)
    | * c9669de21442b78c25b8a9d8500a806a25fb9194 = Optimization not in use    (Fix up Peek.t to account for preceding commits)
    | * 5b50f57e3c9dd69e1372943621f74736a63b65e5 = Optimization not in use    (perl.h: Mention PERL_SAWAMPERSAND in perl -V output)
    | * 1a904fc88069e249a4bd0ef196a3f1a7f549e0fe = Optimization not in use    (Disable PL_sawampersand)
    | * 07d01d6ec25527bf0236de2205ea412d40353058 = Optimization in use        (Enable PERL_NEW_COPY_ON_WRITE by default)
    | * f7a8268cd8b5af71e2d24a595ca88e48464a3e94 = Optimization in use        (Allow COW with magical and blessed scalars (among others))
    | * 9fd2152b911b1c311a72e55728050bfa2fc67ca6 = Optimization in use        (Min string length for COW)
    | * db2c6cb33ec067c880a2cb3c4efdb33f7e3e3d0f = Optimization in use        (New COW mechanism)
    |/
    *
    * 08bf00be470db7b367e14733226d4fddc004c796  = Optimization in use      (Fix comment referencing pp_iterinit (should be pp_enteriter))
    * ...

The optimization no longer happens when:

Copy-on-Write is enabled
PL_sawampersand is disabled

This means it's possible to get the optimization back by using:

./Configure -Accflags=-DPERL_SAWAMPERSAND, or
./Configure -Accflags=-DPERL_NO_COW[^1]

Commit 1a904fc88069e249a4bd0ef196a3f1a7f549e0fe does shed some light on the reason why:

    commit 1a904fc88069e249a4bd0ef196a3f1a7f549e0fe
    Author: Father Chrysostomos <[email protected]>
    Date:   Sun Nov 25 12:57:04 2012 -0800

        Disable PL_sawampersand

        PL_sawampersand actually causes bugs (e.g., perl #4289), because the
        behaviour changes.  eval '$&' after a match will produce different
        results depending on whether $& was seen before the match.

        Using copy-on-write for the pre-match copy (preceding patches do that)
        alleviates the slowdown caused by mentioning $&.  The copy doesn't
        happen unless the string is modified after the match.  It's now a
        post- match copy.  So we no longer need to do things differently
        depending on whether $& has been seen.

        PL_sawampersand is now #defined to be equal to what it would be if
        every program began with $',$&,$`.

        I left the PL_sawampersand code in place, in case this commit proves
        immature.  Running Configure with -Accflags=PERL_SAWAMPERSAND will
        renable the PL_sawampersand mechanism.

It's now using copy-on-write for the pre-match copy. Which means a copy needs to made when s/// modifies the string which prevents the optimization.

[^1]: Compiling blead with -DPERL_NO_COW currently fails, see #19987

Jul 24 '22 12:07 bram-perl

One final thing I observed is some inconsistency in the optimization between -DPERL_SAWAMPERSAND[^1] and -DPERL_NO_COW[^1]:

perl compiled with -Accflags=-DPERL_NO_COW:

    $ ./perl -Ilib -MDevel::Peek -e 'my $x = "abcdefgijklmnopqrstuvwxyz";$x =~ s/.{3}//;Dump($x)'
    SV = PV(0x946d60) at 0x9662b0
      REFCNT = 1
      FLAGS = (POK,OOK,pPOK)
      OFFSET = 3
      PV = 0x9645b3 ( "ab\3" . ) "defgijklmnopqrstuvwxyz"\0
      CUR = 22
      LEN = 23

-> optimized;

perl compiled with -Accflags=-DPERL_SAWAMPERSAND:

    $ ./perl -Ilib -MDevel::Peek -e 'my $x = "abcdefgijklmnopqrstuvwxyz";$x =~ s/.{3}//;Dump($x)'
    SV = PV(0x947d70) at 0x9672a0
      REFCNT = 1
      FLAGS = (POK,pPOK)
      PV = 0x9655a0 "defgijklmnopqrstuvwxyz"\0
      CUR = 22
      LEN = 32

-> not optimized;

It appears -DPERL_SAWAMPERSAND is a bit more selective in when/what it optimizes?:

Adding $x .= "";:

    $ ./perl -Ilib -MDevel::Peek -e 'my $x = "abcdefgijklmnopqrstuvwxyz"; $x .= ""; $x =~ s/.{3}//;Dump($x)'
    SV = PV(0x947d60) at 0x9672d0
      REFCNT = 1
      FLAGS = (POK,OOK,pPOK)
      OFFSET = 3
      PV = 0x9655d3 ( "ab\3" . ) "defgijklmnopqrstuvwxyz"\0
      CUR = 22
      LEN = 24

-> optimized

Using x 1:

    $ ./perl -Ilib -MDevel::Peek -e 'my $x = "abcdefgijklmnopqrstuvwxyz" x 1; $x =~ s/.{3}//;Dump($x)'
    SV = PV(0x947d60) at 0x967220
      REFCNT = 1
      FLAGS = (POK,OOK,pPOK)
      OFFSET = 3
      PV = 0x965523 ( "ab\3" . ) "defgijklmnopqrstuvwxyz"\0
      CUR = 22
      LEN = 24

-> optimized

(I did not investigate on what's causing this difference.)

[^1]: using 914bb57489325d34ddbb7c0557c53df7baa84d86~1 since that's the last commit where -DPERL_NO_COW works

Jul 24 '22 12:07 bram-perl

See also https://github.com/Perl/perl5/issues/17253

Jul 24 '22 12:07 dur-randir

It appears it also modified the PV value: 'g' was replaced with '\7', I didn't investigate why

This is the OOK hack. When chopping data off the front of a non-COWed string we set the OOK flag, change the pv to point at the new beginning of the string, and then set the byte before it to the length of the stuff that is "hidden". When we free the pointer we see the OOK flag, check the byte before, subtract that many bytes from the pointer and then call free on that, which should be the original beginning of the buffer.

This is another place where COW isn't the universal panacea that people thought it was. Obviously this optimisation is "cute" in the sense that it only works for for up to 255 characters, but in practice it made a difference in various places.

Im not entirely sure I get this to be honest. Why would we COW the string we are modifying in a s///? That doesn't seem to make any sense at all. As soon we do the modification we trigger a copy anyway, so we might as not bother with COW stuff.

Jan 21 '23 18:01 demerphq

On Sat, Jan 21, 2023 at 10:23:40AM -0800, Yves Orton wrote:

Im not entirely sure I get this to be honest. Why would we COW the string we are modifying in a s///? That doesn't seem to make any sense at all. As soon we do the modification we trigger a copy anyway, so we might as not bother with COW stuff.

I think the issue is more that the string to be substituted against was already COW, and in some fashion it already being COW prevents the OOK optimisation being used. E.g.:

# This assignment to $s causes $s to use a COWed string buffer shared
# between it and whatever was on the RHS:
my $s = ...;

# Oh dear, $s is COW so can't OOK it:

$s =~ s/^.{7}//;

but I haven't looked at the source to confirm.

-- Indomitable in retreat, invincible in advance, insufferable in victory -- Churchill on Montgomery

Jan 24 '23 18:01 iabyn

perl5 perl5 copied to clipboard

'OFFSET' optimization for s/^...// no longer applied

perl5
perl5 copied to clipboard