develooper Front page | perl.perl5.porters | Postings from August 2016

Re: [perl #39358] sort with custom subname and prototype ($$)segfaults intermittently

Thread Previous | Thread Next
Dave Mitchell
August 10, 2016 15:36
Re: [perl #39358] sort with custom subname and prototype ($$)segfaults intermittently
Message ID:
On Sun, Sep 26, 2010 at 02:39:49PM -0700, Father Chrysostomos via RT wrote:
> On Thu Jun 08 21:23:40 2006, wrote:
> > #!/usr/bin/perl -w
> > 
> > @scores = (
> >   '0000.0000.00039:0000.0008.0031.',
> >   '0000.0000.00032:0000.0008.0024.',
> >   '0002.0002.00033:0002.0011.0020.',
> >   '0028.0028.00190:0077.0085.0028.');
> > 
> > @match_indices = (0,1,2,3);
> > sub sort_by_index($$) {
> >     my($A,$B) = @_;
> >     return $scores[$match_indices[$A]] cmp
> >    $scores[$match_indices[$B]];
> > }
> > @match_indices = sort sort_by_index @match_indices;
> > ----------------------------------------
> This gives me:
> Bizarre copy of UNKNOWN in aelem at - line 12.
> in commit 42bd538f820268331bc55a66fa9df0673de69250
> d963bf01c4c4db296760b1148f98bf668efcaf58, three commits later (the
> intervening commits affecting only documentation), gives 
> Use of uninitialized value $match_indices[2] in array element at - line 12.
> Use of uninitialized value $match_indices[2] in array element at - line 12.
> Use of uninitialized value $match_indices[0] in array element at - line 12.
> but I can’t see how it fixes it.

Fixed now in blead by the following. The issue was as the bit below about
mergesort leaving random pointers lying about.

commit 84721d614eb7d9835d9a09505b0001c7be40a865
Author:     David Mitchell <>
AuthorDate: Wed Aug 10 15:12:56 2016 +0100
Commit:     David Mitchell <>
CommitDate: Wed Aug 10 16:34:04 2016 +0100

    Partially pessimise in-place sorting
    There's currently an optimisation that converts at compile-time
        @a = sort { .... } @a
    into (approximately)
        sort { ... } \@a
    Then at run time, rather than passing an svp pointer to the appropriate
    sort routine which points to a list of SV*'s on the stack, pp_sort()
    passes a pointer to @a's AvARRAY. This allows the array to be sorted
    in-place, which is more efficient.
    However, it has some issues. First, the @a visible to the sort routine
    will be varying, whereas logically it should still hold the original list
    of values until after the '@a = ...' assignment.
    Secondly, the mergesort algorithm cureently used internally, when in
    mid-sort, temporarily stores pointers in the array which aren't pointers
    to SVs - this means that if @a elements are accessed mid-sort, it can
    The solution to both these problems is for pp_sort() to push the elements
    of @a onto the stack at the beginning, sort the stack (like normal sorts
    do), then copy back to @a at the end. This is less efficient than before,
    but is still a lot more efficient than executing separate padav and
    aassign ops.
    Here are benchmark results in raw instruction counts etc (lower is better)
    for the sort line in this code block:
        my (@a, @b);
        @a = reverse 1..10;
        @b = sort { $a <=> $b } @a;
    A is for a non-in-place sort, i.e. @b = sort ... @a;
    B and C are for an inline sort, i.e. as above, but  @a = sort ... @a;
    where B is blead before this commit and C is this commit.
                     A       B       C
                ------  ------  ------
            Ir  5238.0  2324.0  2772.0
            Dr  1464.0   649.0   765.0
            Dw   919.0   298.0   370.0
          COND   782.0   320.0   405.0
           IND    25.0    25.0    26.0
        COND_m    14.9    13.0    17.0
         IND_m     8.0     5.0     5.0
    As can be seen, this partial pessimisation slows down in-place sorting by
    round 20%, but overall in-place is still nearly twice the speed as without
    the optimisation.
    These are the figures for a plain numeric sort (which is optimised to use
    a C comparison function); for other types of sort, the cost of the
    comparator dominates, and so the slowdown is much less marked.

"But Sidley Park is already a picture, and a most amiable picture too.
The slopes are green and gentle. The trees are companionably grouped at
intervals that show them to advantage. The rill is a serpentine ribbon
unwound from the lake peaceably contained by meadows on which the right
amount of sheep are tastefully arranged." -- Lady Croom, "Arcadia"

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About