Skip Menu |
Report information
Id: 128340
Status: resolved
Priority: 0/
Queue: perl5

Owner: Nobody
Requestors: zefram [at] fysh.org
Cc:
AdminCc:

Operating System: Linux
PatchStatus: (no value)
Severity: low
Type: core
Perl Version: 5.24.0
Fixed In: 5.25.4



CC: zefram [...] fysh.org
To: perlbug [...] perl.org
Date: Tue, 07 Jun 2016 20:59:21 +0100
From: zefram [...] fysh.org
Subject: in-place sort incorrectly preserves element lvalue identity
Download (untitled) / with headers
text/plain 4.4k
This is a bug report for perl from zefram@fysh.org, generated with the help of perlbug 1.40 running under perl 5.24.0. ----------------------------------------------------------------- [Please describe your issue here] [perl #127759] led me to spot another problem with in-place sort optimisation: $ perl -le '@c=(55,44,33); $d = \$c[2]; @c = @e = sort { $a <=> $b } @c; $$d = "z"; print @c' 334455 $ perl -le '@c=(55,44,33); $d = \$c[2]; @c = sort { $a <=> $b } @c; $$d = "z"; print @c' z4455 The latter case triggers the in-place sort optimisation, while the former is semantically equivalent (except for clobbering @e) but does not get the optimisation. The former is behaving correctly, in that the array ends up with fresh element scalars not aliased to the old ones, so the mutation via reference doesn't affect the new array content. But with the in-place optimisation, it turns out that the original element scalars are merely being rearranged. The copying to fresh scalars that is part of list assignment semantics is not happening. It is incorrect to apply the in-place optimisation if any of the array's element scalars might be aliased somewhere else. I considered saying "has SvREFCNT != 1" there, but I'm concerned about uncounted references hiding in @_ or elsewhere on the stack. [Please do not change anything below this line] ----------------------------------------------------------------- --- Flags: category=core severity=low --- Site configuration information for perl 5.24.0: Configured by zefram at Mon May 9 19:42:55 BST 2016. Summary of my perl5 (revision 5 version 24 subversion 0) configuration: Platform: osname=linux, osvers=3.16.0-4-amd64, archname=x86_64-linux-thread-multi uname='linux barba.rous.org 3.16.0-4-amd64 #1 smp debian 3.16.7-ckt11-1+deb8u6 (2015-11-09) x86_64 gnulinux ' config_args='-des -Dprefix=/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52 -Duselargefiles -Dusethreads -Uafs -Ud_csh -Uusesfio -Uusenm -Duseshrplib -Dusedevel -Uversiononly -Ui_db' hint=recommended, useposix=true, d_sigaction=define useithreads=define, usemultiplicity=define use64bitint=define, use64bitall=define, uselongdouble=undef usemymalloc=n, bincompat5005=undef Compiler: cc='cc', ccflags ='-D_REENTRANT -D_GNU_SOURCE -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='-D_REENTRANT -D_GNU_SOURCE -fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include' ccversion='', gccversion='4.9.2', 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/gcc/x86_64-linux-gnu/4.9/include-fixed /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib libs=-lpthread -lnsl -ldb -ldl -lm -lcrypt -lutil -lc perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc libc=libc-2.19.so, so=so, useshrplib=true, libperl=libperl.so gnulibc_version='2.19' Dynamic Linking: dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E -Wl,-rpath,/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0/x86_64-linux-thread-multi/CORE' cccdlflags='-fPIC', lddlflags='-shared -O2 -L/usr/local/lib -fstack-protector-strong' --- @INC for perl 5.24.0: /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/site_perl/5.24.0/x86_64-linux-thread-multi /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/site_perl/5.24.0 /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0/x86_64-linux-thread-multi /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0 . --- Environment for perl 5.24.0: HOME=/home/zefram LANG (unset) LANGUAGE (unset) LD_LIBRARY_PATH (unset) LOGDIR (unset) PATH=/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/bin:/home/zefram/usr/perl/util:/home/zefram/pub/x86_64-unknown-linux-gnu/bin:/home/zefram/pub/common/bin:/usr/bin:/bin:/usr/local/bin:/usr/games PERL_BADLANG (unset) SHELL=/usr/bin/zsh
Date: Tue, 7 Jun 2016 21:39:47 +0100
To: perl5-porters [...] perl.org
From: Zefram <zefram [...] fysh.org>
Subject: Re: [perl #128340] in-place sort incorrectly preserves element lvalue identity
Download (untitled) / with headers
text/plain 884b
I wrote: Show quoted text
>It is incorrect to apply the in-place optimisation if any of the array's >element scalars might be aliased somewhere else.
If we can detect which ones are (or might be) aliased, it's not necessary to drop the optimisation entirely when there are some. It would suffice to add a step that dealiases the aliased ones, after the actual sorting. In my proposal for [perl #127759] that does one copy of the AvARRAY, the dealiasing would be applied to the sorted version of the AvARRAY, just before it gets installed into the AV. Show quoted text
> I'm concerned about uncounted references >hiding in @_ or elsewhere on the stack.
If the stack is a problem, it may still be acceptable to just look at SvREFCNT != 1. The remaining broken cases would be classed as yet another stack-not-refcounted bug. I live in hope that some day we'll address those. -zefram
Subject: Re: [perl #128340] in-place sort incorrectly preserves element lvalue identity
To: Zefram <zefram [...] fysh.org>
From: Dave Mitchell <davem [...] iabyn.com>
CC: perl5-porters [...] perl.org
Date: Wed, 10 Aug 2016 16:39:50 +0100
Download (untitled) / with headers
text/plain 2.4k
On Tue, Jun 07, 2016 at 09:39:47PM +0100, Zefram wrote: Show quoted text
> I wrote:
> >It is incorrect to apply the in-place optimisation if any of the array's > >element scalars might be aliased somewhere else.
> > If we can detect which ones are (or might be) aliased, it's not necessary > to drop the optimisation entirely when there are some. It would suffice > to add a step that dealiases the aliased ones, after the actual sorting. > In my proposal for [perl #127759] that does one copy of the AvARRAY, > the dealiasing would be applied to the sorted version of the AvARRAY, > just before it gets installed into the AV. >
> > I'm concerned about uncounted references > >hiding in @_ or elsewhere on the stack.
> > If the stack is a problem, it may still be acceptable to just look > at SvREFCNT != 1. The remaining broken cases would be classed as yet > another stack-not-refcounted bug. I live in hope that some day we'll > address those.
Now done with: commit 45c198c1bc981a507ab719edbd292922a896a397 Author: David Mitchell <davem@iabyn.com> AuthorDate: Wed Aug 10 16:19:55 2016 +0100 Commit: David Mitchell <davem@iabyn.com> CommitDate: Wed Aug 10 16:34:04 2016 +0100 in-place sort preserved element lvalue identity RT #128340 The in-place sorting optimisation @a = sort @a, was preserving the elements of @a rather than (logically) making copies. So make a copy of any element whose refcount is greater than 1. This may not be the perfect condition, but keeps performance for the common cases. Note that several of the tests in t/op/sort.t actually relied on this behaviour to test whether the sort was being in-placed, so I've added tests for in-placing to t/perf/opcount.t instead. See the previous commit for a general discussion of performance; to the A, B, C in that commit message, here's a fourth column added: D is like C but with this commit added: A B C D ------ ------ ------ ------ Ir 5238.0 2324.0 2772.0 2801.0 Dr 1464.0 649.0 765.0 765.0 Dw 919.0 298.0 370.0 380.0 COND 782.0 320.0 405.0 405.0 IND 25.0 25.0 26.0 26.0 COND_m 14.9 13.0 17.0 17.1 IND_m 8.0 5.0 5.0 5.0 so it has little effect on performance. -- I thought I was wrong once, but I was mistaken.
Download (untitled) / with headers
text/plain 313b
Thank you for filing this report. You have helped make Perl better. With the release today of Perl 5.26.0, this and 210 other issues have been resolved. Perl 5.26.0 may be downloaded via: https://metacpan.org/release/XSAWYERX/perl-5.26.0 If you find that the problem persists, feel free to reopen this ticket.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org