为什么在Erlang中使用`binary：match`搜索多个二进制文件比搜索一个二进制文件更快？

我试图通过使用binary:match代替模式匹配来优化Elixir中的分析器，当我发现一些奇怪的事情时：即使二进制文件不包含任何y，binary:match(Binary, [<<"z">>, <<"y">>])比binary:match(Binary, <<"z">>)快几倍。这里有一个最小的方案，以重现此：为什么在Erlang中使用`binary：match`搜索多个二进制文件比搜索一个二进制文件更快？

-module(a). 
-compile(export_all). 

one(Binary) -> 
    binary:match(Binary, <<"z">>). 

two(Binary) -> 
    binary:match(Binary, [<<"z">>, <<"y">>]). 

three(Binary) -> 
    binary:match(Binary, [<<"z">>, <<"y">>, <<"x">>]). 

main() -> 
    As = binary:copy(<<"a">>, 10485760), 
    Zs = binary:copy(<<"z">>, 10485760), 
    Binary = <<As/binary, Zs/binary>>, 
    io:format("~p~n", [timer:tc(?MODULE, one, [Binary])]), 
    io:format("~p~n", [timer:tc(?MODULE, two, [Binary])]), 
    io:format("~p~n", [timer:tc(?MODULE, three, [Binary])]).

这里是一个相当快的OSX系统上的输出：

{62556,{10485760,1}} 
{18272,{10485760,1}} 
{18558,{10485760,1}}

，并在一个不那么快的Linux VPS：

{130249,{10485760,1}} 
{39296,{10485760,1}} 
{40805,{10485760,1}}

所以，对于包含10MB的a和10MB的z的二进制文件，搜索["z", "y"]或["z", "y", "x"]比搜索ju需要大约30％的时间st "z"，即使结果相同，因为二进制文件不包含任何y或x。即使我重新排序呼叫，我也可以重现这一点。

所以我的问题是为什么会发生这种情况，我怎样才能使单个二进制搜索更快？

（我跑Erlang/OTP 19 [erts-8.0.2]）

来源

2016-09-30 Dogbert

erl_bif_binary.c中的'do_binary_match_compile'函数似乎根据模式中是否有一个“单词”或几个选择了不同的算法;请参阅[代码]（https://github.com/erlang/otp/blob/a0abdb8631d7bd7a154023950ccdcbf09c85b92d/erts/emulator/beam/erl_bif_binary.c#L952-L999）。总之，它使用Boyer-Moore，并且有几个使用了Aho-Corasick。不知道为什么这会产生如此巨大的影响，尽管...... – legoscia

显而易见的解决办法对于单个二进制加快搜索是搜索[<<"z">>, <<"z">>]（我已经检查了它的工作原理和搜索[<<"z">>]没有）。不知道为什么会发生。

来源

2016-09-30 09:49:12

为什么在Erlang中使用`binary：match`搜索多个二进制文件比搜索一个二进制文件更快？

回答

相关问题