Erlang模式匹配性能

Question

Erlang的新手.我即将开始编写一些代码.我想到的解决方案可以采用两种方式之一.我可以做一堆数学计算,或者我可以将其编码为模式匹配.当我说"模式匹配"时,我不是指正则表达式或类似的东西 - 我的意思是在子句头中的模式匹配.

性能通常不是问题,但在这个应用程序中它是.我不是问你哪种方法会更快 - 我相信你会说你不知道(取决于很多因素).我要问的是子句头中Erlang模式匹配的一般性能.换句话说,在Prolog中,引擎被优化以执行此类操作,因此在所有其他条件相同的情况下,您"鼓励"设计利用子句头中的模式匹配和统一的解决方案.

Erlang也是如此,即Erlang针对子句中的模式匹配进行了优化,类似于Prolog？我没有在这里提出这个问题,而是试图在Erlang中对此进行分析,并编写了一个玩具程序来对子条头进行模式匹配几百万次,而将列表总和几百万次.但如果设置为"几百万次",系统就会崩溃.但设置为不到几百万,结果会回来太快,让我对性能一无所知.

感谢您的任何见解.

Answer 1

通常,函数式语言中的模式匹配与Prolog一样快或者快.我认为与Prolog相比,Erlang在2倍的内部执行,更快或更慢.由于功能程序几乎不是模式匹配,因此它是您优化很多的领域之一.

内部通常有一个模式匹配编译器,它将高级模式匹配转换为更简单的一系列检查,目的是最小化检查次数.

好的,第一个问题:" shell中引入的任何东西都被解释了 ".所以我们编译模块:

-module(z).

-compile(export_all).

%% This pattern is highly uninteresting because it only matches
%% on a single value. Any decent system can do this quickly.
cl(0) -> 0;
cl(1) -> 0;
cl(2) -> 0;
cl(3) -> 0;
cl(4) -> 0;
cl(5) -> 0;
cl(6) -> 0;
cl(7) -> 0;
cl(8) -> 0;
cl(9) -> 0.

mcl(L) ->
    [cl(E) || E <- L].

这给了我们一个你的例子.

cl2(a, 0) -> a0;
cl2(a, 1) -> a1;
cl2(a, 2) -> a2;
cl2(b, 0) -> b0;
cl2(b, 1) -> b1;
cl2(b, 2) -> b2;
cl2(c, 0) -> c0;
cl2(c, 1) -> c0;
cl2(c, 2) -> c0.

mcl2(L) ->
    [cl2(A, V) || {A, V} <- L].

一个更有趣的例子的跑步者.在这里,我们可以利用模式中的跳过.如果(a, 0)无法匹配,a我们知道我们可以立即跳过案例(b, 0),因为负匹配信息可以作为系统中的信息传播.模式匹配编译器通常进行此优化.

test1() ->
    L1 = [X rem 10 || X <- lists:seq(1, 2000000)],
    %% A Core 2 Duo 2.4Ghz P8600 eats this in 132984 microseconds without HiPE
    %% c(z).
    %% With HiPE it is 91195 or in 0.6857591890753775 of the time the non-HiPE variant use
    %% c(z, [native, {hipe, [o3]}]).
    timer:tc(z, mcl, [L1]).

您必须自己运行此示例并评估您是否认为它对您的用例来说足够快.请注意,映射代码也花费了一些时间,并且必须花费大量时间将数据从主存储器通过CPU高速缓存提取到CPU上.

test2() ->
    random:seed(erlang:now()),
    L2 = [{case random:uniform(3) of
                   1 -> a;
                   2 -> b;
                   3 -> c
                   end, V rem 3} || V <- lists:seq(1, 2000000)],
    %% With HiPE this is 220937
    %% Without HiPE this is 296980
    timer:tc(z, mcl2, [L2]).

当然这个例子比较慢,因为我们需要在命中之前匹配更多数据.但这是一个更有趣的案例,因为它给出了匹配编译器实际速度的一些指示.

尝试了并行版本,但在这种情况下它们大约慢了10倍,因为创建200万个工作进程的开销远远超过实际处理:)

Answer 2

它基本上是@(非常非常)CRAP ANSWERS :-)已经说过并且他的例子显示了.

Prolog并不真正进行单向模式匹配,它实现统一,有点像与逻辑变量匹配的双向模式.优化模式匹配要容易得多,而像Erlang和Haskell这样的严格的函数式语言在优化模式匹配编译器中投入了相当多的工作.深度模式尤其明显.

所以,是的,Erlang将比Prolog更快地进行模式匹配.