I find about a 12% savings in summing the ordered array using a foreach loop: 

            Rate unsorted   sorted
unsorted 48478/s       --     -10%
sorted   54097/s      12%       --

[download]

This isn't much, really, though time and time again the "sorted" version does win. For the purpose of testing, I'm making some assumptions though; the input data is 50% below the threshold, and 50% above it. However, a sorted list with these characteristics provides additional opportunities for optimization. With a binary search we can (in logarithmic time) find the point in the ordered array to begin summing, thereby eliminating the need to test each element for a value greater 128. By using that technique, and also pushing more of the work into internals, we get a hefty gain: 

              Rate  unsorted    sorted bsearched
unsorted   48233/s        --       -8%      -71%
sorted     52695/s        9%        --      -68%
bsearched 167021/s      246%      217%        --

[download]

Here's the benchmark code: 

use Benchmark qw(cmpthese);

use List::Util qw(shuffle sum);
use List::BinarySearch qw( binsearch_pos );

@sorted_data = 0 .. 255;

@unsorted_data = shuffle @sorted_data;

sub make_linear {
  my $aref = shift;
  return sub {
    my $sum;
    foreach my $x ( @{$aref} ) {
      if( $x > 128 ) {
        $sum += $x;
      }
    }
    return $sum;
  }
}


sub bsearched {
  return sum @sorted_data[
    ( binsearch_pos { $a <=> $b } 129, @sorted_data )
    .. $#sorted_data
  ];
}

print "$_\n" for
  make_linear( \@sorted_data  )->(),
  make_linear( \@unsorted_data)->(),
  bsearched();

cmpthese -10, {
  sorted    => make_linear( \@sorted_data   ),
  unsorted  => make_linear( \@unsorted_data ),
  bsearched => \&bsearched,
};

[download]

Using List::Util::sum along with an array slice moves the linear loop(s) into internals or XS. List::BinarySearch::binsearch_pos, by default, also moves most of the mechanics (except for the comparator callback) into XS. Plus, the binary search finds the first element greater than 128 in just a few iterations. The higher the ratio of disqualified elements to qualified, the better the results will be, since the binary search will quickly disqualify a higher proportion of the initial array.


Dave

In reply to Re: does perl have branch prediction by davido
in thread does perl have branch prediction by david2008

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.