Perl 锚定正则表达式性能

Question

问题与数据

\n

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

\n

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

\n

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

\n

继续！仅当坏模式出现在键的开头时才需要删除。听起来很棒！添加 ^ 来锚定正则表达式应该可以提高性能。然而，NYTProf 生成以下内容。NYTprof 已经运行了很多次，这是相当一致的

\n

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

\n

问题

\n

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

\n

整个脚本

\n

use strict;\nuse Devel::NYTProf;\n\nmy @states = qw(KansasCity MississippiState ColoradoMountain IdahoInTheNorthWest AnchorageIsEvenFurtherNorth);\nmy @cities = qw(WitchitaHouston ChicagoDenver);\nmy @streets = qw(DowntownMainStreetInTheCity CenterStreetOverTheHill HickoryBasketOnTheWall);\nmy @seasoncode = qw(8000S 8000P 8000F 8000W);\nmy @historycode = qw(7000S 7000P 7000F 7000W 7000A 7000D 7000G 7000H);\nmy @sides = qw(left right up down);\n\nmy $hash;\nfor my $state (@states) {\n    for my $city (@cities) {\n        for my $street (@streets) {\n            for my $season (@seasoncode) {\n                for my $history (@historycode) {\n                    for my $side (@sides) {\n                        $hash->{$state . '[0].' . $city . '[1].' . $street . '[2].' . $season . '.' . $history . '.' . $side} = 1;\n                    }\n                }\n            }\n        }\n    }\n}\n\nsub CleanseHash {\n    my @bad_patterns = (\n        'KansasCity[0].WitchitaHouston[1].DowntownMainStreetInTheCity[2]',\n        'ColoradoMountain[0].ChicagoDenver[1].HickoryBasketOnTheWall[2].8000F'\n    );\n\n    for my $bad_pattern (@bad_patterns) {\n        delete @$hash{ grep { /^\\Q$bad_pattern\\E/ } sort keys %$hash };\n    }\n}\n\nDB::enable_profile();\nCleanseHash();\nDB::finish_profile();\n

\n

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 纳秒，而每次调用 107 纳秒。

但是，当我对锚定版本和非锚定版本的代码进行基准测试时，它们的运行结果并驾齐驱。这是关于代码的其余部分，它压倒了正则表达式的匹配：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.

上面的基准测试运行 10 秒后的输出（10运行时传递给程序）：

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

因此，锚定版本确实获胜，尽管利润微薄。有了这些数据，匹配在大约 96% 的情况下会失败，尽管如此，非锚定版本会做更多的工作，必须搜索整个字符串；我预计会有更大的差异。

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

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