爲什麼在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`搜索多個二進制文件比搜索一個二進制文件更快？

回答

相關問題