Whilst Perl's built-in sort now has an optimisation that comes into play if the source array and the target array are the same, this is only usable if the array is declared at the same scope as you wish to sort (without trickery). You cannot (yet?) pass an array ref to sort, which means that you're forced to copy the array in your sub, even when you pass an array ref in.

To emphasis the difference, this benchmark uses two pure perl implementations of qsort algorithm; identical, except that qsortr() sorts the array in-place via a reference, whilst qsortv() passes the array to be sort in and out by value (as a list).

Even for very small arrays, using pass-by-value for this recursive algorithm highlights the cost of indiscriminate copying of lists. With larger numbers it becomes extreme 

P:\test>396406 -N=10 -I=-1
            Rate by_value  xby_ref
by_value 10925/s       --     -69%
xby_ref  35072/s     221%       --

P:\test>396406 -N=1000 -I=-3
           Rate by_value  xby_ref
by_value 2.09/s       --     -99%
xby_ref   219/s   10340%       --

[download]

Benchmark:

#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];

our $N ||= 4000;
our $I ||= -3;

sub qsortr {
    my( $ref, $lo, $hi ) = @_;
    
    my $pivot = $ref->[ ( $lo + $hi ) / 2 ];
    my( $lb, $rb ) = ( $lo, $hi );
    while( 1 ) {
        $lb++ while $ref->[ $lb ] < $pivot; 
        $rb-- while $ref->[ $rb ] > $pivot;
        $lb++ while $lb != $rb and $ref->[ $lb ] == $ref->[ $rb ];
        last if $lb == $rb;
        @{ $ref }[ $lb, $rb ] = @{ $ref }[ $rb, $lb ];
    }
    qsortr( $ref, $lo, $lb ) if $lo < --$lb;
    qsortr( $ref, $rb, $hi ) if $hi > ++$rb;
}

sub qsortv {
    my( $lo, $hi, @data ) = @_;
    
    my $pivot = $data[ ( $lo + $hi ) / 2 ];
    my( $lb, $rb ) = ( $lo, $hi );
    while( 1 ) {
        $lb++ while $data[ $lb ] < $pivot; 
        $rb-- while $data[ $rb ] > $pivot;
        $lb++ while $lb != $rb and $data[ $lb ] == $data[ $rb ];
        last if $lb == $rb;
        @data[ $lb, $rb ] = @data[ $rb, $lb ];
    }
    @data = qsortv( $lo, $lb, @data ) if $lo < --$lb;
    @data = qsortv( $rb, $hi, @data ) if $hi > ++$rb;
    return @data;
}

our @data = map{ int rand( 1000 ) } 1 .. $N;

cmpthese $I, {
    by_value => q[
        my @copy = qsortv( 0, $#data, @data );
        $I == 1 and print "V: @copy";
    ],
    
    xby_ref => q[
        qsortr( \@data, 0, $#data );
        $I == 1 and print "R: @data";
    ],
};

__END__
P:\test>396406 -N=10 -I=1
V: 26 97 100 300 387 391 598 665 853 962
            (warning: too few iterations for a reliable count)

R: 26 97 100 300 387 391 598 665 853 962
            (warning: too few iterations for a reliable count)

                       Rate  xby_ref by_value
xby_ref  1000000000000000/s       --       0%
by_value 1000000000000000/s       0%       --

P:\test>396406 -N=4000 -I=10
            (warning: too few iterations for a reliable count)

            s/iter by_value  xby_ref
by_value      8.79       --    -100%
xby_ref  2.81e-002   31167%       --

[download]
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

In reply to Re: Show that using references is faster by BrowserUk
in thread Show that using references is faster by Keystroke

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.