Perl 锚定正则表达式性能

Question

问题与数据

此 post 的底部是生成此 NYTProf 数据的整个脚本。该脚本构建一个散列，然后尝试删除包含某些错误模式的键。运行通过 NYTProf 的代码生成以下内容

delete @$hash{ grep { /\Q$bad_pattern\E/ } sort keys %$hash };
# spent  7.29ms making    2 calls to main::CORE:sort, avg 3.64ms/call
# spent   808µs making 7552 calls to main::CORE:match, avg 107ns/call
# spent   806µs making 7552 calls to main::CORE:regcomp, avg 107ns/call

main::CORE:match 和 main::CORE:regcomp 有超过 7,000 个呼叫。假设这是足以降低噪音水平的调用量。

继续前进！只有出现在密钥开头的坏模式才需要删除。听起来不错！添加 ^ 来锚定正则表达式应该可以提高性能。但是，NYTProf 会生成以下内容。 NYTprof 已经运行很多次了，这非常一致

delete @$hash{ grep { /^\Q$bad_pattern\E/ } sort keys %$hash };
# spent  7.34ms making    2 calls to main::CORE:sort, avg 3.67ms/call
# spent  1.62ms making 7552 calls to main::CORE:regcomp, avg 214ns/call
# spent   723µs making 7552 calls to main::CORE:match, avg 96ns/call

问题

锚定的正则表达式几乎使这些 main::CORE:* 方法花费的时间增加一倍。但是锚定的正则表达式应该可以提高性能。这个数据集有什么独特之处导致锚定的正则表达式花费这么多额外的时间？

整个脚本

use strict;
use Devel::NYTProf;

my @states = qw(KansasCity MississippiState ColoradoMountain IdahoInTheNorthWest AnchorageIsEvenFurtherNorth);
my @cities = qw(WitchitaHouston ChicagoDenver);
my @streets = qw(DowntownMainStreetInTheCity CenterStreetOverTheHill HickoryBasketOnTheWall);
my @seasoncode = qw(8000S 8000P 8000F 8000W);
my @historycode = qw(7000S 7000P 7000F 7000W 7000A 7000D 7000G 7000H);
my @sides = qw(left right up down);

my $hash;
for my $state (@states) {
    for my $city (@cities) {
        for my $street (@streets) {
            for my $season (@seasoncode) {
                for my $history (@historycode) {
                    for my $side (@sides) {
                        $hash->{$state . '[0].' . $city . '[1].' . $street . '[2].' . $season . '.' . $history . '.' . $side} = 1;
                    }
                }
            }
        }
    }
}

sub CleanseHash {
    my @bad_patterns = (
        'KansasCity[0].WitchitaHouston[1].DowntownMainStreetInTheCity[2]',
        'ColoradoMountain[0].ChicagoDenver[1].HickoryBasketOnTheWall[2].8000F'
    );

    for my $bad_pattern (@bad_patterns) {
        delete @$hash{ grep { /^\Q$bad_pattern\E/ } sort keys %$hash };
    }
}

DB::enable_profile();
CleanseHash();
DB::finish_profile();

Answer 1

您不太可能优化正则表达式引擎。但是，如果性能是您的目标，您可以专注于代码的其他部分。例如，试试这个：

for my $bad_pattern (@bad_patterns) {
    my $re = qr/^\Q$bad_pattern\E/;
    delete @$hash{ grep /$re/, sort keys %$hash };
}

在我的机器上，它运行得更快（不管锚点是否存在），因为 grep 的表达式形式不必创建范围，并且正则表达式的复杂编译对每个错误只发生一次模式。

Answer 2

这是一个相当简单的匹配，模式是一个固定的字符串。因此，锚定模式通常必须更快。分析证实了这一点，96 ns/call 对比 107 ns/call.

但是当我对代码的锚定和非锚定版本进行基准测试时，它们运行并驾齐驱。这是关于代码的其余部分，它淹没了正则表达式的匹配：键的 sort 不需要进行比较，并且正则表达式正在 grep 的循环中编译，不需要。

当我松了一口气时，我确实让锚定调用快了 11--15%（运行倍）

use warnings;
use strict;
use feature 'say';

use Data::Dump;
use Storable qw(dclone);
use Benchmark qw(cmpthese);

my $runfor = shift // 3;

my @states = qw(KansasCity MississippiState ColoradoMountain IdahoInTheNorthWest AnchorageIsEvenFurtherNorth);
my @cities = qw(WitchitaHouston ChicagoDenver);
my @streets = qw(DowntownMainStreetInTheCity CenterStreetOverTheHill HickoryBasketOnTheWall);
my @seasoncode = qw(8000S 8000P 8000F 8000W);
my @historycode = qw(7000S 7000P 7000F 7000W 7000A 7000D 7000G 7000H);
my @sides = qw(left right up down);

my @bad_patterns = ( 
    'KansasCity[0].WitchitaHouston[1].DowntownMainStreetInTheCity[2]',
    'ColoradoMountain[0].ChicagoDenver[1].HickoryBasketOnTheWall[2].8000F'
);

my $hash_1;
for my $state (@states) {
    for my $city (@cities) {
        for my $street (@streets) {
            for my $season (@seasoncode) {
                for my $history (@historycode) {
                    for my $side (@sides) {
                        $hash_1->{$state . '[0].' . $city . '[1].' . $street . '[2].' . $season . '.' . $history . '.' . $side} = 1;
                    }
                }
            }
        }
    }   
}    
my $hash_2 = dclone $hash_1;

#say for @bad_patterns; say '---'; dd $hash_1; exit;

sub no_anchor {
    for my $bad_pattern (@bad_patterns) {
        my $re = qr/\Q$bad_pattern\E/;
        delete @$hash_2{ grep { /$re/ } keys %$hash_2 };
    }   
}   
sub w_anchor {
    for my $bad_pattern (@bad_patterns) {
        my $re = qr/^\Q$bad_pattern\E/;
        delete @$hash_1{ grep { /$re/ } keys %$hash_1 };
    }
}


cmpthese( -$runfor, {
    'no_anchor' => sub { no_anchor() },
    'w_anchor'  => sub { w_anchor() },
});

我让比较潜艇使用外部数据（不像往常一样传递给测试潜艇），以减少任何额外的工作，然后我使用通过 Storable::dclone.

获得的单独的 hashref 副本

10 秒以上运行基准测试的输出（在运行时将 10 传递给编程）：

           Rate no_anchor  w_anchor
no_anchor 296/s        --      -13%
w_anchor  341/s       15%        --

所以锚定版本确实赢了，尽管利润不大。使用此数据，匹配在大约 96% 的情况下会失败，并且对于所有这些，未锚定版本会做更多的工作，必须搜索整个字符串；我希望差异更大。

运行次的相对接近是由于代码的其余部分（grep、哈希操作、循环），特别是正则表达式编译成本，被包含在计时中，是什么稀释了匹配效率本身的差异。

这给我们上了关于计时代码的重要一课：它可以很微妙。需要确保只比较相关部分，并且公平（在同等情况下）。

Perl 锚定正则表达式性能

Perl anchored regex performance

regex

perl

performance

profiling