[Melbourne-pm] grep vs first vs foreach

[Paul Fenwick]

G'day Everyone,

At Perl Mongers the other night there was a discussion regarding the fastest
way to determine if an element exists in a list.  Without building a hash,
three proposed were given:

	* Use List::Util's first()
	* Use Perl's in-built grep() in scalar context.
	* Use a foreach loop.

Interestingly enough, after some testing I've discovered the foreach loop
wins in terms of speed. first() suffers from a high cost of entering a
subroutine for each list element, whereas grep() will search *all* items to
return the total number of matches.  Our foreach loop, on the other hand,
can end immediately when the item is found.

Using a 'return' from inside the grep() block allows short-cutting which
improves its speed significantly, although foreach still wins if the item is
found early in our list.  A pure grep() is actually fastest in our failure
case (where the item cannot be found).

I don't know if grep() is smart enough to return immediately upon finding an
item if called in a boolean context.  If not, then this seems like an
obvious optimisation that could be implemented.

Raw data and original code below:

---cut here---

First item:

                 Rate        grep       first grep-return     foreach
grep            455/s          --        -99%        -99%       -100%
first         44823/s       9741%          --        -29%        -97%
grep-return   63232/s      13782%         41%          --        -95%
foreach     1365750/s     299745%       2947%       2060%          --


Middle item:

             Rate        grep       first     foreach grep-return
grep        419/s          --        -25%        -40%        -46%
first       559/s         34%          --        -20%        -28%
foreach     700/s         67%         25%          --         -9%
grep-return 772/s         84%         38%         10%          --


Non-existent item:

             Rate       first     foreach grep-return        grep
first       297/s          --        -18%        -27%        -35%
foreach     362/s         22%          --        -11%        -21%
grep-return 409/s         38%         13%          --        -10%
grep        455/s         53%         26%         11%          --

---cut here---

Cheerio,

	Paul

#!/usr/bin/perl -w
use strict;
use List::Util qw(first);
use Benchmark qw(cmpthese);

my @list = (1..10_000);

compare(1,"First item");
compare(5000,"Middle item");
compare(-1,"Non-existent item");

sub compare {
        my ($element,$msg) = @_;

        print "\n\n$msg:\n\n";

        cmpthese(0,
                {
                        'grep' => sub {
                                grep {$_ eq $element } @list;
                        },
                        'grep-return' => sub {
                                grep {return 1 if $_ eq $element } @list;
                        },
                        'foreach' => sub {
                                foreach (@list) {
                                        last if $_ eq $element;
                                }
                        },
                        'first' => sub {
                                first { $_ eq $element } @list;
                        },

                }
        );
}

__END__

-- 
Paul Fenwick <pjf at perltraining.com.au> | http://perltraining.com.au/
Director of Training                   | Ph:  +61 3 9354 6001
Perl Training Australia                | Fax: +61 3 9354 2681