Erlang模式匹配性能

发布于 2024-10-13 01:51:27 字数 497 浏览 3 评论 0原文

刚接触 Erlang。我即将开始编写一些代码。我想到的解决方案可以采用两种方法之一。我可以进行一系列数学计算，或者我可以将其编码为模式匹配。当我说“模式匹配”时，我并不是指正则表达式或类似的东西 - 我指的是子句头中的模式匹配。

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

Erlang 也是如此，即 Erlang 是否针对子句头中的模式匹配进行了优化，类似于 Prolog？我没有在这里问这个问题，而是尝试在 Erlang 中对此进行分析，并编写了一个玩具程序来对子句头进行数百万次模式匹配，而不是对列表进行数百万次求和。但如果设置为“几百万次”，系统就会崩溃。但如果设置为少于几百万，结果返回得太快，我无法了解有关性能的任何信息。

感谢您的任何见解。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

疯了 2024-10-20 01:51:27

一般来说，函数式语言中的模式匹配与 Prolog 中的模式匹配一样快甚至更快。我希望 Erlang 的性能比 Prolog 快或慢 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 万个工作进程的开销远远主导了实际处理:)

In general, pattern matching in functional languages are as fast or faster than in Prolog. I would expect Erlang to perform inside a factor of 2 compared to Prolog, faster or slower. Since a functional program is almost nothing but pattern matching it is one of those areas you optimize a lot.

The internals usually have a pattern match compiler which turns an advanced pattern match into a simpler series of checks with the goal to minimize the number of checks.

Ok, the first gotcha: "Anything introduced in the shell is interpreted". So we compile modules instead:

-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].

This gives us a runner of your example.

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 runner for a more interesting example. Here, we can exploit skips in the pattern. If (a, 0) fails to match on the a we know we can skip to the case (b, 0) straight away because the negative match information can be propagated as information in the system. The pattern match compiler usually makes this optimization.

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]).

You must run this example yourself and evaluate if you think it is fast enough for your use case. Note that some time is also spent in the mapping code and quite a lot of time must be spent to pull data from the main memory through the CPU caches and onto the 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]).

Naturally this example is slower, as we need to match more data before we have a hit. But it is a more interesting case because it gives some indication of the real speed of the match compiler.

Parallel versions were tried, but they are about 10 times slower in this case since the overhead of creating 2 million worker processes far dominates the actual processing :)

回复收藏 0 原文