Mathematica 中函数和模式匹配之间的性能差异

发布于 2024-10-02 09:16:10 字数 717 浏览 1 评论 0原文

因此 Mathematica 与 Lisp 的其他方言不同,因为它模糊了函数和宏之间的界限。在 Mathematica 中,如果用户想要编写数学函数,他们可能会使用模式匹配,例如 f[x_]:= x*x 而不是 f=Function[{x},x*x ] 尽管用 f[x] 调用时两者都会返回相同的结果。我的理解是,第一种方法相当于 lisp 宏,根据我的经验,由于语法更简洁,因此受到青睐。

所以我有两个问题,执行函数与模式匹配/宏方法之间是否存在性能差异?如果函数实际上被转换为某种版本的宏以允许实现诸如 Listable 之类的功能,我内心的一部分不会感到惊讶。

我关心这个问题的原因是因为最近的一系列问题 (1) (2) 关于尝试捕获大型程序中的 Mathematica 错误。如果大多数计算都是根据函数定义的,那么在我看来,跟踪计算顺序和错误起源比在通过连续应用宏重写输入后尝试捕获错误更容易/模式。

So Mathematica is different from other dialects of lisp because it blurs the lines between functions and macros. In Mathematica if a user wanted to write a mathematical function they would likely use pattern matching like f[x_]:= x*x instead of f=Function[{x},x*x] though both would return the same result when called with f[x]. My understanding is that the first approach is something equivalent to a lisp macro and in my experience is favored because of the more concise syntax.

So I have two questions, is there a performance difference between executing functions versus the pattern matching/macro approach? Though part of me wouldn't be surprised if functions were actually transformed into some version of macros to allow features like Listable to be implemented.

The reason I care about this question is because of the recent set of questions (1) (2) about trying to catch Mathematica errors in large programs. If most of the computations were defined in terms of Functions, it seems to me that keeping track of the order of evaluation and where the error originated would be easier than trying to catch the error after the input has been rewritten by the successive application of macros/patterns.

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

扫码二维码加入Web技术交流群

发布评论

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

评论(5

似梦非梦 2024-10-09 09:16:10

我对 Mathematica 的理解是,它是一个巨大的搜索替换引擎。所有函数、变量和其他赋值本质上都存储为规则,在评估过程中,Mathematica 会遍历这个全局规则库并应用它们,直到结果表达式停止变化。

因此,您必须浏览规则列表的次数越少,评估速度就越快。看看使用 Trace 发生的情况(使用 gdelfino 的函数 g 和 h)

In[1]:= Trace@(#*#)&@x
Out[1]= {x x,x^2}
In[2]:= Trace@g@x
Out[2]= {g[x],x x,x^2}
In[3]:= Trace@h@x
Out[3]= {{h,Function[{x},x x]},Function[{x},x x][x],x x,x^2}

就清楚了为什么匿名函数最快,以及为什么使用 Function 会比简单的 SetDelayed 带来额外的开销。我建议您查看 Leonid Shifrin 的优秀著作的简介,其中包含这些概念解释了一些细节。

我有时构建了一个 Dispatch 表我需要的所有功能并手动将其应用到我的起始表达式中。与正常计算相比,这提供了显着的速度提升,因为 Mathematica 的任何内置函数都不需要与我的表达式进行匹配。

The way I understand Mathematica is that it is one giant search replace engine. All functions, variables, and other assignments are essentially stored as rules and during evaluation Mathematica goes through this global rule base and applies them until the resulting expression stops changing.

It follows that the fewer times you have to go through the list of rules the faster the evaluation. Looking at what happens using Trace (using gdelfino's function g and h)

In[1]:= Trace@(#*#)&@x
Out[1]= {x x,x^2}
In[2]:= Trace@g@x
Out[2]= {g[x],x x,x^2}
In[3]:= Trace@h@x
Out[3]= {{h,Function[{x},x x]},Function[{x},x x][x],x x,x^2}

it becomes clear why anonymous functions are fastest and why using Function introduces additional overhead over a simple SetDelayed. I recommend looking at the introduction of Leonid Shifrin's excellent book, where these concepts are explained in some detail.

I have on occasion constructed a Dispatch table of all the functions I need and manually applied it to my starting expression. This provides a significant speed increase over normal evaluation as none of Mathematica's inbuilt functions need to be matched against my expression.

月野兔 2024-10-09 09:16:10

我的理解是,第一种方法相当于 lisp 宏,根据我的经验,由于语法更简洁,因此更受青睐。

并不真地。 Mathematica 是一个术语重写器,Lisp 宏也是如此。

所以我有两个问题,执行函数与模式匹配/宏方法之间是否存在性能差异?

是的。请注意,您从来没有真正在 Mathematica 中“执行函数”。您只是应用重写规则将一个表达式更改为另一种表达式。

考虑将 Sqrt 函数映射到浮点数的压缩数组上。 Mathematica 中最快的解决方案是将 Sqrt 函数直接应用于打包数组,因为它恰好实现了我们想要的,并且针对这种特殊情况进行了优化:

In[1] := N@Range[100000];

In[2] := Sqrt[xs]; // AbsoluteTiming

Out[2] = {0.0060000, Null}

我们可以定义一个包含术语的全局重写规则将 sqrt[x] 形式重写为 Sqrt[x],以便计算平方根:

In[3] := Clear[sqrt];
         sqrt[x_] := Sqrt[x];
         Map[sqrt, xs]; // AbsoluteTiming

Out[3] = {0.4800007, Null}

请注意,这比之前的解决方案慢约 100 倍。

或者,我们可以定义一个全局重写规则,用调用 Sqrt 的 lambda 函数替换符号 sqrt

In[4] := Clear[sqrt];
         sqrt = Function[{x}, Sqrt[x]];
         Map[sqrt, xs]; // AbsoluteTiming

Out[4] = {0.0500000, Null}

请注意,这比之前的解决方案快约 10 倍。

为什么?因为慢的第二个解决方案是查找重写规则 sqrt[x_] :> Sqrt[x] 在内循环中(对于数组的每个元素),而快速的第三种解决方案查找符号 sqrt< 的值 Function[...] /code> 一次,然后重复应用该 lambda 函数。相比之下,最快的第一个解决方案是循环调用用 C 编写的 sqrt。因此搜索全局重写规则的成本非常高,并且术语重写的成本也很高。

如果是这样,为什么 Sqrt 如此快?您可能预计速度会减慢 2 倍,而不是 10 倍,因为我们已将 Sqrt 的一次查找替换为 sqrtSqrt但事实并非如此,因为 Sqrt 具有作为内置函数的特殊地位,它将在 Mathematica 术语重写器本身的核心中进行匹配,而不是通过通用全局重写表进行匹配。

其他人描述了相似函数之间的性能差异要小得多。我相信这些情况下的性能差异只是 Mathematica 内部的具体实现的微小差异。 Mathematica 最大的问题是全局重写表。特别是,这就是 Mathematica 与传统术语级解释器的不同之处。

您可以通过编写迷你 Mathematica 实现来了解有关 Mathematica 性能的更多信息。在这种情况下,上述解决方案可能会编译为(例如)F#。数组可以这样创建:

> let xs = [|1.0..100000.0|];;
...

内置的 sqrt 函数可以转换为闭包并提供给 map 函数,如下所示:

> Array.map sqrt xs;;
Real: 00:00:00.006, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
...

这需要 6ms 就像 Sqrt[xs]。但这是可以预料到的,因为该代码已由 .NET JIT 编译为机器代码,以便快速评估。

在 Mathematica 的全局重写表中查找重写规则类似于在字典中查找闭包的函数名称。这样的字典可以在 F# 中这样构造:

> open System.Collections.Generic;;
> let fns = Dictionary<string, (obj -> obj)>(dict["sqrt", unbox >> sqrt >> box]);;

这类似于 Mathematica 中的 DownValues 数据结构,只不过我们不会搜索多个结果规则来查找第一个与函数参数匹配的规则。

然后程序变成:

> Array.map (fun x -> fns.["sqrt"] (box x)) xs;;
Real: 00:00:00.044, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0
...

请注意,由于内部循环中的哈希表查找,我们得到了类似 10 倍的性能下降。

另一种方法是将与符号关联的 DownValues 存储在符号本身中,以避免哈希表查找。

我们甚至可以用几行代码编写一个完整的术语重写器。术语可以表示为以下类型的值:

> type expr =
    | Float of float
    | Symbol of string
    | Packed of float []
    | Apply of expr * expr [];;

请注意,Packed 实现了 Mathematica 的打包列表,即未装箱数组。

以下 init 函数使用函数 f 构造一个包含 n 个元素的 List,返回一个 Packed< /code> 如果每个返回值都是 Float 或更通用的 Apply(Symbol "List", ...) 否则:

> let init n f =
    let rec packed ys i =
      if i=n then Packed ys else
        match f i with
        | Float y ->
            ys.[i] <- y
            packed ys (i+1)
        | y ->
            Apply(Symbol "List", Array.init n (fun j ->
              if j<i then Float ys.[i]
              elif j=i then y
              else f j))
    packed (Array.zeroCreate n) 0;;
val init : int -> (int -> expr) -> expr

以下规则 函数使用模式匹配来识别它可以理解的表达式,并将其替换为其他表达式:

> let rec rule = function
    | Apply(Symbol "Sqrt", [|Float x|]) ->
        Float(sqrt x)
    | Apply(Symbol "Map", [|f; Packed xs|]) ->
        init xs.Length (fun i -> rule(Apply(f, [|Float xs.[i]|])))
    | f -> f;;
val rule : expr -> expr

请注意,此函数的类型 expr -> expr 是术语重写的特征:重写将表达式替换为其他表达式,而不是将它们简化为值。

我们的程序现在可以由我们的自定义术语重写器定义和执行:

> rule (Apply(Symbol "Map", [|Symbol "Sqrt"; Packed xs|]));;
Real: 00:00:00.049, CPU: 00:00:00.046, GC gen0: 24, gen1: 0, gen2: 0

我们已经恢复了 Mathematica 中 Map[Sqrt, xs] 的性能!

我们甚至可以通过添加适当的规则来恢复Sqrt[xs]的性能:

| Apply(Symbol "Sqrt", [|Packed xs|]) ->
    Packed(Array.map sqrt xs)

我写了一篇关于F# 中的术语重写

My understanding is that the first approach is something equivalent to a lisp macro and in my experience is favored because of the more concise syntax.

Not really. Mathematica is a term rewriter, as are Lisp macros.

So I have two questions, is there a performance difference between executing functions versus the pattern matching/macro approach?

Yes. Note that you are never really "executing functions" in Mathematica. You are just applying rewrite rules to change one expression into another.

Consider mapping the Sqrt function over a packed array of floating point numbers. The fastest solution in Mathematica is to apply the Sqrt function directly to the packed array because it happens to implement exactly what we want and is optimized for this special case:

In[1] := N@Range[100000];

In[2] := Sqrt[xs]; // AbsoluteTiming

Out[2] = {0.0060000, Null}

We might define a global rewrite rule that has terms of the form sqrt[x] rewritten to Sqrt[x] such that the square root will be calculated:

In[3] := Clear[sqrt];
         sqrt[x_] := Sqrt[x];
         Map[sqrt, xs]; // AbsoluteTiming

Out[3] = {0.4800007, Null}

Note that this is ~100× slower than the previous solution.

Alternatively, we might define a global rewrite rule that replaces the symbol sqrt with a lambda function that invokes Sqrt:

In[4] := Clear[sqrt];
         sqrt = Function[{x}, Sqrt[x]];
         Map[sqrt, xs]; // AbsoluteTiming

Out[4] = {0.0500000, Null}

Note that this is ~10× faster than the previous solution.

Why? Because the slow second solution is looking up the rewrite rule sqrt[x_] :> Sqrt[x] in the inner loop (for each element of the array) whereas the fast third solution looks up the value Function[...] of the symbol sqrt once and then applies that lambda function repeatedly. In contrast, the fastest first solution is a loop calling sqrt written in C. So searching the global rewrite rules is extremely expensive and term rewriting is expensive.

If so, why is Sqrt ever fast? You might expect a 2× slowdown instead of 10× because we've replaced one lookup for Sqrt with two lookups for sqrt and Sqrt in the inner loop but this is not so because Sqrt has the special status of being a built-in function that will be matched in the core of the Mathematica term rewriter itself rather than via the general-purpose global rewrite table.

Other people have described much smaller performance differences between similar functions. I believe the performance differences in those cases are just minor differences in the exact implementation of Mathematica's internals. The biggest issue with Mathematica is the global rewrite table. In particular, this is where Mathematica diverges from traditional term-level interpreters.

You can learn a lot about Mathematica's performance by writing mini Mathematica implementations. In this case, the above solutions might be compiled to (for example) F#. The array may be created like this:

> let xs = [|1.0..100000.0|];;
...

The built-in sqrt function can be converted into a closure and given to the map function like this:

> Array.map sqrt xs;;
Real: 00:00:00.006, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
...

This takes 6ms just like Sqrt[xs] in Mathematica. But that is to be expected because this code has been JIT compiled down to machine code by .NET for fast evaluation.

Looking up rewrite rules in Mathematica's global rewrite table is similar to looking up the closure in a dictionary keyed on its function name. Such a dictionary can be constructed like this in F#:

> open System.Collections.Generic;;
> let fns = Dictionary<string, (obj -> obj)>(dict["sqrt", unbox >> sqrt >> box]);;

This is similar to the DownValues data structure in Mathematica, except that we aren't searching multiple resulting rules for the first to match on the function arguments.

The program then becomes:

> Array.map (fun x -> fns.["sqrt"] (box x)) xs;;
Real: 00:00:00.044, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0
...

Note that we get a similar 10× performance degradation due to the hash table lookup in the inner loop.

An alternative would be to store the DownValues associated with a symbol in the symbol itself in order to avoid the hash table lookup.

We can even write a complete term rewriter in just a few lines of code. Terms may be expressed as values of the following type:

> type expr =
    | Float of float
    | Symbol of string
    | Packed of float []
    | Apply of expr * expr [];;

Note that Packed implements Mathematica's packed lists, i.e. unboxed arrays.

The following init function constructs a List with n elements using the function f, returning a Packed if every return value was a Float or a more general Apply(Symbol "List", ...) otherwise:

> let init n f =
    let rec packed ys i =
      if i=n then Packed ys else
        match f i with
        | Float y ->
            ys.[i] <- y
            packed ys (i+1)
        | y ->
            Apply(Symbol "List", Array.init n (fun j ->
              if j<i then Float ys.[i]
              elif j=i then y
              else f j))
    packed (Array.zeroCreate n) 0;;
val init : int -> (int -> expr) -> expr

The following rule function uses pattern matching to identify expressions that it can understand and replaces them with other expressions:

> let rec rule = function
    | Apply(Symbol "Sqrt", [|Float x|]) ->
        Float(sqrt x)
    | Apply(Symbol "Map", [|f; Packed xs|]) ->
        init xs.Length (fun i -> rule(Apply(f, [|Float xs.[i]|])))
    | f -> f;;
val rule : expr -> expr

Note that the type of this function expr -> expr is characteristic of term rewriting: rewriting replaces expressions with other expressions rather than reducing them to values.

Our program can now be defined and executed by our custom term rewriter:

> rule (Apply(Symbol "Map", [|Symbol "Sqrt"; Packed xs|]));;
Real: 00:00:00.049, CPU: 00:00:00.046, GC gen0: 24, gen1: 0, gen2: 0

We've recovered the performance of Map[Sqrt, xs] in Mathematica!

We can even recover the performance of Sqrt[xs] by adding an appropriate rule:

| Apply(Symbol "Sqrt", [|Packed xs|]) ->
    Packed(Array.map sqrt xs)

I wrote an article on term rewriting in F#.

予囚 2024-10-09 09:16:10

一些测量

基于 @gdelfino 的回答和 @rcollyer 的评论,我制作了这个小程序:

j = # # + # # &;
g[x_] := x x + x x ;
h = Function[{x}, x x + x x ];


anon = Table[Timing[Do[ # # + # # &[i], {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
jj   = Table[Timing[Do[ j[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
gg   = Table[Timing[Do[ g[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
hh   = Table[Timing[Do[ h[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];

ListLinePlot[ {anon,   jj,    gg,   hh}, 
 PlotStyle -> {Black, Red, Green, Blue},
 PlotRange -> All]

至少对我来说,结果非常令人惊讶:
alt text

有什么解释吗?请随意编辑这个答案(评论对于长文本来说是一团糟)

编辑

使用恒等函数 f[x] = x 进行测试,以将解析与实际评估分开。结果(相同颜色):

alt text

注意:结果与此常量函数图非常相似 (f[x]: =1);

Some measurements

Based on @gdelfino answer and comments by @rcollyer I made this small program:

j = # # + # # &;
g[x_] := x x + x x ;
h = Function[{x}, x x + x x ];


anon = Table[Timing[Do[ # # + # # &[i], {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
jj   = Table[Timing[Do[ j[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
gg   = Table[Timing[Do[ g[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
hh   = Table[Timing[Do[ h[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];

ListLinePlot[ {anon,   jj,    gg,   hh}, 
 PlotStyle -> {Black, Red, Green, Blue},
 PlotRange -> All]

The results are, at least for me, very surprising:
alt text

Any explanations? Please feel free to edit this answer (comments are a mess for long text)

Edit

Tested with the identity function f[x] = x to isolate the parsing from the actual evaluation. Results (same colors):

alt text

Note: results are very similar to this Plot for constant functions (f[x]:=1);

蓝眸 2024-10-09 09:16:10

模式匹配似乎更快:

In[1]:= g[x_] := x*x
In[2]:= h = Function[{x}, x*x];

In[3]:= Do[h[RandomInteger[100]], {1000000}] // Timing
Out[3]= {1.53927, Null}

In[4]:= Do[g[RandomInteger[100]], {1000000}] // Timing
Out[4]= {1.15919, Null}

模式匹配也更灵活,因为它允许您重载定义:

In[5]:= g[x_] := x * x
In[6]:= g[x_,y_] := x * y

对于简单的函数,您可以编译以获得最佳性能:

In[7]:= k[x_] = Compile[{x}, x*x]
In[8]:= Do[k[RandomInteger[100]], {100000}] // Timing
Out[8]= {0.083517, Null}

Pattern matching seems faster:

In[1]:= g[x_] := x*x
In[2]:= h = Function[{x}, x*x];

In[3]:= Do[h[RandomInteger[100]], {1000000}] // Timing
Out[3]= {1.53927, Null}

In[4]:= Do[g[RandomInteger[100]], {1000000}] // Timing
Out[4]= {1.15919, Null}

Pattern matching is also more flexible as it allows you to overload a definition:

In[5]:= g[x_] := x * x
In[6]:= g[x_,y_] := x * y

For simple functions you can compile to get the best performance:

In[7]:= k[x_] = Compile[{x}, x*x]
In[8]:= Do[k[RandomInteger[100]], {100000}] // Timing
Out[8]= {0.083517, Null}
方觉久 2024-10-09 09:16:10

您可以使用之前答案中的函数recordSteps了解 Mathematica 对函数的实际用途。它对待它就像对待任何其他头一样。 IE,假设您有以下内容

f = Function[{x}, x + 2];
f[2]

首先将 f[2] 转换

Function[{x}, x + 2][2]

为 下一步,将 x+2 转换为 2+2。本质上,“函数”评估的行为就像模式匹配规则的应用程序,因此它的速度并不快也就不足为奇了。

您可以将 Mathematica 中的所有内容视为一个表达式,其中求值是在 预定义序列,这适用于函数,就像任何其他头一样

You can use function recordSteps in previous answer to see what Mathematica actually does with Functions. It treats it just like any other Head. IE, suppose you have the following

f = Function[{x}, x + 2];
f[2]

It first transforms f[2] into

Function[{x}, x + 2][2]

At the next step, x+2 is transformed into 2+2. Essentially, "Function" evaluation behaves like an application of pattern matching rules, so it shouldn't be surprising that it's not faster.

You can think of everything in Mathematica as an expression, where evaluation is the process of rewriting parts of the expression in a predefined sequence, this applies to Function like to any other head

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文