Erlang模式匹配性能

Question

Erlang模式匹配性能

5

我是Erlang的新手，准备开始编写一些代码。我想到的解决方案可以有两种方式。一种是进行大量的数学计算，另一种则是主要采用模式匹配进行编码。当我说“模式匹配”时，我并不是指正则表达式或类似的东西 - 我指的是在子句头中进行模式匹配。

性能通常不是问题，但在这个应用程序中却是。我不是在问你哪种方法会更快 - 我相信你会说你不知道（这取决于许多因素）。我想问的是Erlang模式匹配在子句头中的一般性能如何。换句话说，在Prolog中，引擎被优化为执行此类操作，因此在其他所有条件相等的情况下，您被“鼓励”设计一个利用子句头中的模式匹配和统一的解决方案。

Erlang是否也是如此优化了模式匹配在子句头中的操作，类似于Prolog？与其在这里提出问题，我实际上尝试在Erlang中对此进行了分析，并编写了一个玩具程序来进行数百万次的子句头模式匹配与数百万次列表求和的比较。但是，如果设置为进行“数百万次”操作，系统将崩溃。但是，如果设置为少于数百万次，结果会太快，以至于我无法了解性能方面的任何信息。

感谢您提供的任何见解。

- Ultranewb

3

发布Codz。为什么这会导致崩溃？ - EvilTeach

代码非常简单，由两个程序组成。第一个程序是序列子句的10个子句头(0) -> 0; 子句(1) -> 0; (一直到10)。为了测试，我使用了duplicate创建了一个包含200万个0的列表，并使用map将子句映射到它上面。第二个程序只是使用duplicate创建了200万个7个整数的列表，然后使用map将sum映射到它上面。再次强调，我只是想测试模式匹配作为一种编程技术的相对性能。我的问题是，Erlang程序员是否像Prolog程序员一样被鼓励在可行的情况下使用模式匹配。 - Ultranewb

2个回答

7

基本上就像@(NOT VERY) CRAP ANSWERS :-)所说的，他的例子也说明了这一点。

Prolog并不真正进行单向模式匹配，它进行的是统一，这有点像带有逻辑变量的双向模式匹配。优化模式匹配要容易得多，严肃的函数式语言如Erlang和Haskell会投入相当大的工作来优化模式匹配编译器。尤其是在深层模式下，这一点尤为明显。

因此，是的，Erlang将比Prolog更快地进行模式匹配。

- rvirding

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- I GIVE CRAP ANSWERS · Accepted Answer

一般来说，函数式语言中的模式匹配速度与Prolog相当或更快。我预计Erlang的性能与Prolog相比会快或慢一个数量级。由于函数式程序几乎仅仅是模式匹配，因此这是一个需要大量优化的领域。

内部通常有一个“模式匹配编译器”，它将高级模式匹配转换为较简单的检查序列，旨在最小化检查次数。

好的，第一个陷阱：“在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上(a, 0)匹配失败，我们就知道可以直接跳到案例(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万个工作进程的开销远远超过了实际处理的时间 :)